NeetCode刷题第20天(2025.2.1)
文章目录
- 106 Best Time to Buy and Sell Stock with Cooldown 使用 Cooldown 买卖股票的最佳时间
- 107 Coin Change II 换币 II
- 108 Target Sum 目标总和
- 109 Interleaving String 交错字符串
- 110 Edit Distance 编辑距离
- 111 Maximum Subarray 最大子数组
- 112 Jump Game 跳跃游戏
- 113 Jump Game II 跳跃游戏 II
106 Best Time to Buy and Sell Stock with Cooldown 使用 Cooldown 买卖股票的最佳时间
给定一个整数数组价格,其中的价格 [i] 是第i天 NeetCoin 的价格。
您可以多次买卖一个 NeetCoin,但有以下限制:
- 出售 NeetCoin 后,第二天不能再购买一个(即有一天的冷却期)。
- 您一次最多只能拥有一个 NeetCoin。
您可以完成任意数量的交易。
返回您可以实现的最大利润。
示例1:
Input: prices = [1,3,4,0,4]
Output: 6
说明:第 0 天买入(价格 = 1),第 1 天卖出(价格 = 3),利润 = 3-1 = 2。然后在第 3 天买入(价格 = 0),在第 4 天卖出(价格 = 4),利润 = 4-0 = 4。总利润为 2 + 4 = 6。示例2:
Input: prices = [1]
Output: 0
解题1: 递归
下面是根据题目绘制的一棵决策树
class Solution:def maxProfit(self, prices: List[int]) -> int:# 状态:buying or selling?# 如果 buying: i + 1# 如果 selling: i + 2dp = {}def dfs(i, buying):if i >= len(prices):return 0if (i, buying) in dp:return dp[(i, buying)]cooldown = dfs(i + 1, buying)if buying:buy = dfs(i + 1, not buying) - prices[i]dp[(i, buying)] = max(buy, cooldown)else:sell = dfs(i + 2, not buying) + prices[i]dp[(i, buying)] = max(sell, cooldown)return dp[(i, buying)]return dfs(0, True)
时间复杂度: O ( 2 n ) O(2^n) O(2n)
空间复杂度: O ( n ) O(n) O(n)
107 Coin Change II 换币 II
您将获得一个整数数组硬币,代表不同面额的硬币(例如 1 美元、5 美元等)和一个代表目标金额的整数金额。
返回总计达到 amount 的非重复组合的数量。如果无法补足金额,则返回 0。
您可以假设每个硬币的数量不受限制,并且硬币中的每个值都是唯一的。
示例1:
Input: amount = 4, coins = [1,2,3]
Output: 4
解释:
1+1+1+1 = 4
1+1+2 = 4
2+2 = 4
1+3 = 4示例2:
Input: amount = 7, coins = [2,4]
Output: 0
解题1: 二维动态规划(自下而上)
如果我们使用常规的决策树,通过上面可以看到,会存在重复。那么如何消除呢?
这里我们每个子树的子孙节点只可以添加该值之后的硬币就可以消除冗余。比如这里的2,之后我们只可以添加coins中2及其后面的硬币(即2和5)。
使用dfs进行循环,这里的i是coins的索引,a则是目前为止的综合。如果总和大于amount就停止,表示该路径不满足条件,返回0。
这里的1我们从下往上看。最后一个1表示,当我们使用硬币5时,有几种组合使得和为0,显然是0,当用0和硬币。倒数第二个1表示,当使用硬币2和5时,有几种可能使得结果为0,显然也是1种。
在这个位置中,当我们加入一个硬币2时,所需的值就是1-2=-1,显然超出范围不合理。我们每次向右硬币值个单位和向下看,两者的和就是该位置的值。
class Solution:def change(self, amount: int, coins: List[int]) -> int:dp = [[0] * (len(coins) + 1) for i in range(amount + 1)]dp[0] = [1] * (len(coins) + 1)for a in range(1, amount + 1):for i in range(len(coins) - 1, -1, -1):dp[a][i] = dp[a][i + 1]if a - coins[i] >= 0:dp[a][i] += dp[a - coins[i]][i]return dp[amount][0]
时间复杂度: O ( n ∗ a ) O(n*a) O(n∗a)
空间复杂度: O ( n ∗ a ) O(n*a) O(n∗a)
n是硬币的数量,a 是给定的数量。
108 Target Sum 目标总和
您将获得一个整数数组 nums 和一个整数目标。
对于数组中的每个数字,您可以选择将其相加或相减为总和。
- 例如,如果 nums = [1, 2],则一个可能的和将是 “+1-2=-1”。
如果 nums=[1,1],则有两种不同的方法可以将输入的数字相加得到 0 的总和:“+1-1” 和 “-1+1”。
返回您可以构建表达式的不同方法的数量,以便总和等于 target。
示例1:
Input: nums = [2,2,2], target = 2
Output: 3
说明:有 3 种不同的方法可以将输入的数字相加得到 2 的总和。
+2 +2 -2 = 2
+2 -2 +2 = 2
-2 +2 +2 = 2
解题1: 递归
class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:dp = {} # (index, cur_sum) -> num of waysdef backtrack(i, cur_sum):# 为了减少重复的计算,可以存储已经计算过的if (i, cur_sum) in dp:return dp[(i, cur_sum)]if i == len(nums):return 1 if cur_sum == target else 0dp[(i, cur_sum)] = (# 加上或减去backtrack(i + 1, cur_sum + nums[i]) +backtrack(i + 1, cur_sum - nums[i]))return dp[(i, cur_sum)]return backtrack(0, 0)
时间复杂度: O ( 2 n ) O(2^n) O(2n)
空间复杂度: O ( n ) O(n) O(n)
109 Interleaving String 交错字符串
有三个字符串 s1,s2 和 s3。如果 s3 是由 s1 和 s2 交错形成的,返回 true,否则返回 false。
交错两个字符串 s 和 t 是通过将 s 和 t 分别划分为 n 和 m 子字符串来完成的,其中满足以下条件:
- |n - m| <= 1,即 s 和 t 的子字符串数量之差最多为 1。
- t = t1 + t2 + … + tm
- 交错s 和 t 是 s1 + t1 + s2 + t2 + …或 t1 + s1 + t2 + s2 + …
您可以假设 s1、s2 和 s3 由小写英文字母组成。
示例1:
Input: s1 = "aaaa", s2 = "bbbb", s3 = "aabbbbaa"
Output: true示例2:
Input: s1 = "abc", s2 = "xyz", s3 = "abxzcy"
Output: false
解题1: 递归
这是决策树,这里括号里分别表示s1和s2的索引,每当匹配到一个,就+1。
class Solution:def isInterleave(self, s1: str, s2: str, s3: str) -> bool:def dfs(i, j, k):# 判断三个字符串是否都遍历完了if k == len(s3):return (i == len(s1) and (j == len(s2)))if i < len(s1) and s1[i] == s3[k]:if dfs(i + 1, j, k + 1):return Trueif j < len(s2) and s2[j] == s3[k]:if dfs(i, j + 1, k + 1):return Truereturn Falsereturn dfs(0, 0, 0)
时间复杂度: O ( n 2 ) O(n²) O(n2)
空间复杂度: O ( 1 ) O(1) O(1)
解题1: 递归
这是决策树,这里括号里分别表示s1和s2的索引,每当匹配到一个,就+1。
class Solution:def isInterleave(self, s1: str, s2: str, s3: str) -> bool:if len(s1) + len(s2) != len(s3):return Falsedp = [[False] * (len(s2) + 1) for i in range(len(s1) + 1)]dp[len(s1)][len(s2)] = Truefor i in range(len(s1), -1, -1):for j in range(len(s2), -1, -1):if i < len(s1) and s1[i] == s3[i + j] and dp[i + 1][j]:dp[i][j] = Trueif j < len(s2) and s2[j] == s3[i + j] and dp[i][j + 1]:dp[i][j] = Truereturn dp[0][0]
时间复杂度: O ( m ∗ n ) O(m * n) O(m∗n)
空间复杂度: O ( m ∗ n ) O(m * n) O(m∗n)
110 Edit Distance 编辑距离
您将获得两个字符串 word1 和 word2,每个字符串都由小写英文字母组成。
您可以对 word1 执行三个作,次数不受限制:
- 在任意位置插入字符
- 删除任意位置的字符
- 替换任意位置的字符
返回使 word1 等于 word2 的最小作数。
示例1:
Input: word1 = "monkeys", word2 = "money"
Output: 2示例2:
Input: word1 = "neatcdee", word2 = "neetcode"
Output: 3
解题1:
动态规划图。这里最下面和最右面还有空的两行。以上面图为例,顶部的3表示当w2为空,w1中有abd三字母时最少的操作次数。下面的2则表示当w2为空,w1为bd两字母时最少的操作次数。
class Solution:def minDistance(self, word1: str, word2: str) -> int:cache =[[float("inf")] * (len(word2) + 1) for i in range(len(word1) + 1)]for j in range(len(word2) + 1):cache[len(word1)][j] = len(word2) - jfor i in range(len(word1) + 1):cache[i][len(word2)] = len(word1) - i# 自下而上的动态规划for i in range(len(word1) - 1, -1, -1):for j in range(len(word2) - 1, -1, -1):if word1[i] == word2[j]:cache[i][j] = cache[i + 1][j + 1]else:cache[i][j] = 1 + min(cache[i + 1][j], cache[i][j + 1], cache[i + 1][j + 1])return cache[0][0]
时间复杂度: O ( m ∗ n ) O(m∗n) O(m∗n)
空间复杂度: O ( m ∗ n ) O(m∗n) O(m∗n)
m 是 word1 的长度,n 是 word2 的长度。
111 Maximum Subarray 最大子数组
给定一个整数数组 nums ,找到总和最大的子数组并返回总和。
子数组是数组中连续的非空元素序列。
示例1:
Input: nums = [2,-3,4,-2,2,1,-1,4]
Output: 8
说明:子数组 [4,-2,2,1,-1,4] 的最大和为 8。
解题1: Kadane 算法
如果前面的数或者前面子数组相加的和为负数,那他们就起了反向的作用,我们需要重新计数最大和。
class Solution:def maxSubArray(self, nums: List[int]) -> int:maxSub = nums[0]curSum = 0for n in nums:if curSum < 0:curSum = 0curSum += nmaxSub = max(maxSub, curSum)return maxSub
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
112 Jump Game 跳跃游戏
你得到一个整数数组 nums,其中每个元素 nums[i] 表示你在该位置的最大跳跃长度。
如果可以访问从索引 0 开始的最后一个索引,则返回 true,否则返回 false。
示例1:
Input: nums = [1,2,0,1,0]
Output: true
解释:首先从索引 0 跳转到 1,然后从索引 1 跳转到 3,最后从索引 3 跳转到 4。示例2:
Input: nums = [-2,-1]
Output: 2
解题1: 贪婪算法
这是一棵决策树,但是我们可以看到2其实已经访问过了。同时,我们可以知道,如果到了2,那么就不可能成功,所以这里设置dp[2] = False。
class Solution:def canJump(self, nums: List[int]) -> bool:goal = len(nums) - 1for i in range(len(nums) - 1, -1, -1):if i + nums[i] >= goal:goal = ireturn True if goal == 0 else False
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
113 Jump Game II 跳跃游戏 II
给你一个整数数组,其中 nums [i] 表示从索引 i 向右跳跃的最大长度。例如,如果你在 nums [i] 处,你可以跳到任何索引 i + j,其中:
- j <= nums[i]
- i + j < nums.length
您最初位于 nums[0] 处。
返回到达数组中最后一个位置的最小跳转次数 (index nums.length - 1)。您可能会假设总是有一个有效的答案。
示例1:
Input: nums = [2,4,1,1,1,1]
Output: 2
说明:从索引 0 跳转到索引 1,然后从索引 1 跳转到最后一个索引。示例2:
Input: nums = [2,1,2,1,0]
Output: 2
解题1: 广度优先搜索 (Greedy)
class Solution:def jump(self, nums: List[int]) -> int:res = 0l = r = 0while r < len(nums) - 1:farthest = 0for i in range(l, r + 1):farthest = max(farthest, i + nums[i])l = r + 1r = farthestres += 1return res
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
相关文章:

NeetCode刷题第20天(2025.2.1)
文章目录 106 Best Time to Buy and Sell Stock with Cooldown 使用 Cooldown 买卖股票的最佳时间107 Coin Change II 换币 II108 Target Sum 目标总和109 Interleaving String 交错字符串110 Edit Distance 编辑距离111 Maximum Subarray 最大子数组112 Jump Game 跳跃游戏113…...
DeepSeek:人工智能领域的革新者与未来展望
在当今这个数据驱动的时代,人工智能(AI)正以前所未有的速度发展,而DeepSeek作为这一领域的先锋,正引领着AI技术的创新与突破。作为一家致力于推动人工智能技术创新与应用的前沿企业,DeepSeek不仅在多语言编…...

Spring Bean 容器
技术成长,是对场景设计细节不断的雕刻! 你觉得自己的技术什么时候得到了快速的提高,是CRUD写的多了以后吗?想都不要想,绝对不可能!CRUD写的再多也只是能满足你作为一个搬砖工具人,敲击少逻辑流…...

Flask代码审计实战
文章目录 Flask代码审计SQL注入命令/代码执行反序列化文件操作XXESSRFXSS其他 审计实战后记reference Flask代码审计 SQL注入 1、正确的使用直白一点就是:使用”逗号”,而不是”百分号” stmt "SELECT * FROM table WHERE id?" connectio…...
springboot启动配置文件-bootstrap.yml常用基本配置
在Spring Boot应用程序中,bootstrap.yml文件通常用于配置应用程序的启动阶段。在这个文件中,你可以配置一些在应用程序启动之前需要加载的属性,例如外部配置源、加密属性等。以下是一些常用的基本配置项: 1. 外部配置源 1.1 配置…...

2月3日星期一今日早报简报微语报早读
2月3日星期一,农历正月初六,早报#微语早读。 1、多个景区发布公告:售票数量已达上限,请游客合理安排行程; 2、2025春节档总票房破70亿,《哪吒之魔童闹海》破31亿; 3、美宣布对中国商品加征10…...

如何确认Linux嵌入式系统的触摸屏对应的是哪个设备文件(/dev/input/event1)?如何查看系统中所有的输入设备?输入设备的设备文件有什么特点?
Linux嵌入式系统的输入设备的设备文件有什么特点? 在 Linux 中,所有的输入设备(如键盘、鼠标、触摸屏等)都会被内核识别为 输入事件设备,并在 /dev/input/ 目录下创建相应的 设备文件,通常是: …...

FFmpeg:多媒体处理的瑞士军刀
FFmpeg:多媒体处理的瑞士军刀 前言 FFmpeg 是一个功能强大且跨平台的开源多媒体框架,广泛应用于音视频处理领域。 它由多个库和工具组成,能够处理各种音视频格式,涵盖编码、解码、转码、流处理等多种操作。 无论是专业视频编辑…...
电控三周速成计划参考
第1周:基础搭建与GPIO控制 学习目标:建立开发环境,掌握最基础的硬件控制能力 每日学习(2-3小时): 环境搭建(2天) 安装Keil MDK-ARM STM32CubeMX使用CubeMX创建第一个工程…...
Ubuntu修改配置文件--编辑操作
例如。 1.打开 /etc/samba/smb.conf 该配置文件: sudo vi /etc/samba/smb.conf 2.当你运行sudo vi /etc/samba/smb.conf命令后,你需要按i键进入插入模式(Insert Mode)。这时,在屏幕底部你应该能看到“-- INSERT --”…...
2021版小程序开发5——小程序项目开发实践(1)
2021版小程序开发5——小程序项目开发实践(1) 学习笔记 2025 使用uni-app开发一个电商项目; Hbuidler 首选uni-app官方推荐工具:https://www.dcloud.io/hbuilderx.htmlhttps://dev.dcloud.net.cn/pages/app/list 微信小程序 管理后台:htt…...
二分/双指针/单调栈队列专题
1.4924. 矩阵 - AcWing题库 一开始打表找规律以为是右上角向左下角递增,但当n很大的时候就不对了,因此我们得去观察 i * i 100000 * (i - j) j * j i * j 这个式子,我们关心的是这个式子的单调性因此我们可以分别将i和j看作常数来对式子进行求导,可以得到 f(i) 2 * i 10…...

XCCL、NCCL、HCCL通信库
XCCL提供的基本能力 XCCL提供的基本能力 不同的XCCL 针对不同的网络拓扑,实现的是不同的优化算法的(不同CCL库最大的区别就是这) 不同CCL库还会根据自己的硬件、系统,在底层上面对一些相对应的改动; 但是对上的API接口…...

【Deep Seek本地化部署】模型实测:规划求解python代码
目录 前言 一、实测 1、整数规划问题 2、非线性规划问题 二、代码正确性验证 1、整数规划问题代码验证 2、非线性规划问题代码验证 三、结果正确性验证 1、整数规划问题结果正确性验证 2、非线性规划问题正确性验证 四、整数规划问题示例 后记 前言 模型ÿ…...

MySQL锁类型(详解)
锁的分类图,如下: 锁操作类型划分 读锁 : 也称为共享锁 、英文用S表示。针对同一份数据,多个事务的读操作可以同时进行而不会互相影响,相互不阻塞的。 写锁 : 也称为排他锁 、英文用X表示。当前写操作没有完成前,它会…...
搜索插入位置(35)
35. 搜索插入位置 - 力扣(LeetCode) 相关算法:二分查找最左侧和最右侧target的index-CSDN博客 class Solution { public:int searchInsert(vector<int>& nums, int target) {int left 0;int right nums.size() - 1;int ans nu…...

八. Spring Boot2 整合连接 Redis(超详细剖析)
八. Spring Boot2 整合连接 Redis(超详细剖析) 文章目录 八. Spring Boot2 整合连接 Redis(超详细剖析)2. 注意事项和细节3. 最后: 在 springboot 中 , 整合 redis 可以通过 RedisTemplate 完成对 redis 的操作, 包括设置数据/获取数据 比如添加和读取数据 具体整…...

VDSuit-Full惯性动捕设备:高效率、高品质动画制作的利器
惯性动捕设备作为动画制作领域的新兴技术,与传统的关键帧动画制作相比,可以大大的缩短制作周期为创作者们提供极大便利。传统方式下,动画师需要逐帧调整角色动作,耗时费力。而惯性动捕设备能实时捕捉演员的动作,几乎瞬…...
【环境搭建】1.1源码下载与同步
目录 写在前面 一,系统要求 二,安装depot_tools 三,获取代码 四,代码同步 五,代码结构 写在前面 当前的开发背景是基于Google的开源Chromium,来开发Android设备的浏览器方案。 一,系统要…...

开源智慧园区管理系统对比其他十种管理软件的优势与应用前景分析
内容概要 在当今数字化快速发展的时代,园区管理软件的选择显得尤为重要。而开源智慧园区管理系统凭借其独特的优势,逐渐成为用户的新宠。与传统管理软件相比,它不仅灵活性高,而且具有更强的可定制性,让各类园区&#…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...

使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...