冷意

分类

/ 注册

全部文章（共170篇）

题解 | 买卖股票的最好时机(二)

1、解题思路贪心算法：每次在价格上升时买入和卖出，累计所有上升区间的利润总和。这样可以将多次买卖的总利润最大化。一次遍历即可完成，时间复杂度 O(n)，空间复杂度 O(1)。动态规划：定义 dp[i][0] 表示第 i 天不持有股票时的最大利润。定义 dp[i][1] 表示第 i 天持有股票时的最大...

2025-06-29

0 31

题解 | 买卖股票的最好时机(一)

1、解题思路一次遍历法：遍历数组，记录当前遇到的最小价格（买入价格）。计算当前价格与最小价格的差值（当前利润），并更新最大利润。如果当前价格比最小价格还小，更新最小价格（因为后续卖出必须在买入之后）。最终的最大利润即为答案。关键点：买入必须在卖出之前。只需要一次遍历，时间复杂度 O(n)。使用常数空...

2025-06-28

0 32

题解 | 打家劫舍(二)

1、解题思路问题分解：由于第一个和最后一个房间相邻，可以将问题分解为两种情况：不偷最后一个房间（即只考虑前 n-1 个房间）。不偷第一个房间（即只考虑后 n-1 个房间）。两种情况的最大值即为最终答案。动态规划：对于非环形问题，使用动态规划： dp[i] = max(dp[i-1], dp[i-2...

2025-06-28

0 26

题解 | 打家劫舍(一)

1、解题思路动态规划：定义 dp[i] 表示偷到第 i 个房间时的最大金额。状态转移方程： dp[i] = max(dp[i-1], dp[i-2] + nums[i])即当前房间的最大金额为：不偷当前房间（继承前一个房间的最大金额）或偷当前房间（前两个房间的最大金额加上当前房间金额）中的较大值。...

2025-06-28

0 27

题解 | 最长的括号子串

1、解题思路栈方法：使用栈来跟踪括号的匹配情况。栈中存储的是下标，初始时压入 -1 作为边界。遍历字符串：遇到 '(' 时，将其下标压入栈。遇到 ')' 时，弹出栈顶元素：如果栈为空，将当前下标压入栈作为新的边界。否则，计算当前有效子串长度（当前下标 - 栈顶元素）并更新最大值。时间复杂度：O(...

2025-06-28

0 25

题解 | 正则表达式匹配

1、解题思路动态规划：定义 dp[i][j] 表示 str 的前 i 个字符和 pattern 的前 j 个字符是否匹配。状态转移：如果 pattern[j-1] == '*' ：匹配0次：dp[i][j] = dp[i][j-2]匹配1次或多次：(str[i-1] == pattern[j-2...

2025-06-28

0 38

题解 | 编辑距离(一)

1、解题思路动态规划：定义 dp[i][j] 表示将 str1 的前 i 个字符转换为 str2 的前 j 个字符所需的最少操作次数。状态转移方程：如果 str1[i-1] == str2[j-1]，则 dp[i][j] = dp[i-1][j-1]（无需操作）。否则，dp[i][j] = min(...

2025-06-28

0 19

题解 | 数字字符串转化成IP地址

1、解题思路回溯法：递归地尝试在每个位置插入分隔符（.），确保每个段满足IP地址的条件。终止条件：已经插入三个分隔符，且剩余字符串也满足条件。剪枝条件：字符串太长或太短（总长度应在4到12之间）。当前段的数字不在[0,255]范围内。当前段有前导零且长度大于1。条件检查：段长度不超过3。段数字...

2025-06-28

0 30

题解 | 最长回文子串

1、解题思路中心扩展法：遍历字符串中的每一个字符，将其作为回文中心。向左右两边扩展，检查是否构成回文。考虑奇数长度（中心为一个字符）和偶数长度（中心为两个字符）的回文子串。动态规划：定义 dp[i][j] 表示字符串从 i 到 j 的子串是否是回文。状态转移方程：如果 A[i] == A[j] 且...

2025-06-28

0 35

题解 | 连续子数组的最大和

1、解题思路动态规划：定义 dp[i] 为以 array[i] 结尾的子数组的最大和。状态转移方程：对于每个 i，如果 dp[i-1] 为正，则 dp[i] = dp[i-1] + array[i]。否则，dp[i] = array[i]（即重新开始一个新的子数组）。初始条件： dp[0] = a...

2025-06-28

0 86