当前位置: 首页 > news >正文

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(na)
空间复杂度: O ( n ∗ a ) O(n*a) O(na)
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(mn)
空间复杂度: O ( m ∗ n ) O(m * n) O(mn)

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(mn)
空间复杂度: O ( m ∗ n ) O(m∗n) O(mn)
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:人工智能领域的革新者与未来展望

在当今这个数据驱动的时代&#xff0c;人工智能&#xff08;AI&#xff09;正以前所未有的速度发展&#xff0c;而DeepSeek作为这一领域的先锋&#xff0c;正引领着AI技术的创新与突破。作为一家致力于推动人工智能技术创新与应用的前沿企业&#xff0c;DeepSeek不仅在多语言编…...

Spring Bean 容器

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

Flask代码审计实战

文章目录 Flask代码审计SQL注入命令/代码执行反序列化文件操作XXESSRFXSS其他 审计实战后记reference Flask代码审计 SQL注入 1、正确的使用直白一点就是&#xff1a;使用”逗号”&#xff0c;而不是”百分号” stmt "SELECT * FROM table WHERE id?" connectio…...

springboot启动配置文件-bootstrap.yml常用基本配置

在Spring Boot应用程序中&#xff0c;bootstrap.yml文件通常用于配置应用程序的启动阶段。在这个文件中&#xff0c;你可以配置一些在应用程序启动之前需要加载的属性&#xff0c;例如外部配置源、加密属性等。以下是一些常用的基本配置项&#xff1a; 1. 外部配置源 1.1 配置…...

2月3日星期一今日早报简报微语报早读

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

如何确认Linux嵌入式系统的触摸屏对应的是哪个设备文件(/dev/input/event1)?如何查看系统中所有的输入设备?输入设备的设备文件有什么特点?

Linux嵌入式系统的输入设备的设备文件有什么特点&#xff1f; 在 Linux 中&#xff0c;所有的输入设备&#xff08;如键盘、鼠标、触摸屏等&#xff09;都会被内核识别为 输入事件设备&#xff0c;并在 /dev/input/ 目录下创建相应的 设备文件&#xff0c;通常是&#xff1a; …...

FFmpeg:多媒体处理的瑞士军刀

FFmpeg&#xff1a;多媒体处理的瑞士军刀 前言 FFmpeg 是一个功能强大且跨平台的开源多媒体框架&#xff0c;广泛应用于音视频处理领域。 它由多个库和工具组成&#xff0c;能够处理各种音视频格式&#xff0c;涵盖编码、解码、转码、流处理等多种操作。 无论是专业视频编辑…...

电控三周速成计划参考

第1周&#xff1a;基础搭建与GPIO控制 学习目标&#xff1a;建立开发环境&#xff0c;掌握最基础的硬件控制能力 每日学习&#xff08;2-3小时&#xff09;&#xff1a; 环境搭建&#xff08;2天&#xff09; 安装Keil MDK-ARM STM32CubeMX使用CubeMX创建第一个工程&#xf…...

Ubuntu修改配置文件--编辑操作

例如。 1.打开 /etc/samba/smb.conf 该配置文件&#xff1a; sudo vi /etc/samba/smb.conf 2.当你运行sudo vi /etc/samba/smb.conf命令后&#xff0c;你需要按i键进入插入模式&#xff08;Insert Mode&#xff09;。这时&#xff0c;在屏幕底部你应该能看到“-- INSERT --”…...

2021版小程序开发5——小程序项目开发实践(1)

2021版小程序开发5——小程序项目开发实践(1) 学习笔记 2025 使用uni-app开发一个电商项目&#xff1b; Hbuidler 首选uni-app官方推荐工具&#xff1a;https://www.dcloud.io/hbuilderx.htmlhttps://dev.dcloud.net.cn/pages/app/list 微信小程序 管理后台&#xff1a;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 针对不同的网络拓扑&#xff0c;实现的是不同的优化算法的&#xff08;不同CCL库最大的区别就是这&#xff09; 不同CCL库还会根据自己的硬件、系统&#xff0c;在底层上面对一些相对应的改动&#xff1b; 但是对上的API接口…...

【Deep Seek本地化部署】模型实测:规划求解python代码

目录 前言 一、实测 1、整数规划问题 2、非线性规划问题 二、代码正确性验证 1、整数规划问题代码验证 2、非线性规划问题代码验证 三、结果正确性验证 1、整数规划问题结果正确性验证 2、非线性规划问题正确性验证 四、整数规划问题示例 后记 前言 模型&#xff…...

MySQL锁类型(详解)

锁的分类图&#xff0c;如下&#xff1a; 锁操作类型划分 读锁 : 也称为共享锁 、英文用S表示。针对同一份数据&#xff0c;多个事务的读操作可以同时进行而不会互相影响&#xff0c;相互不阻塞的。 写锁 : 也称为排他锁 、英文用X表示。当前写操作没有完成前&#xff0c;它会…...

搜索插入位置(35)

35. 搜索插入位置 - 力扣&#xff08;LeetCode&#xff09; 相关算法&#xff1a;二分查找最左侧和最右侧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. 最后&#xff1a; 在 springboot 中 , 整合 redis 可以通过 RedisTemplate 完成对 redis 的操作, 包括设置数据/获取数据 比如添加和读取数据 具体整…...

VDSuit-Full惯性动捕设备:高效率、高品质动画制作的利器

惯性动捕设备作为动画制作领域的新兴技术&#xff0c;与传统的关键帧动画制作相比&#xff0c;可以大大的缩短制作周期为创作者们提供极大便利。传统方式下&#xff0c;动画师需要逐帧调整角色动作&#xff0c;耗时费力。而惯性动捕设备能实时捕捉演员的动作&#xff0c;几乎瞬…...

【环境搭建】1.1源码下载与同步

目录 写在前面 一&#xff0c;系统要求 二&#xff0c;安装depot_tools 三&#xff0c;获取代码 四&#xff0c;代码同步 五&#xff0c;代码结构 写在前面 当前的开发背景是基于Google的开源Chromium&#xff0c;来开发Android设备的浏览器方案。 一&#xff0c;系统要…...

开源智慧园区管理系统对比其他十种管理软件的优势与应用前景分析

内容概要 在当今数字化快速发展的时代&#xff0c;园区管理软件的选择显得尤为重要。而开源智慧园区管理系统凭借其独特的优势&#xff0c;逐渐成为用户的新宠。与传统管理软件相比&#xff0c;它不仅灵活性高&#xff0c;而且具有更强的可定制性&#xff0c;让各类园区&#…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...