题目列表

70. 爬楼梯简单难度 leetcode链接
118. 杨辉三角简单难度 leetcode链接
198. 打家劫舍中等难度 leetcode链接
279.完全平方数中等难度 leetcode链接
322.零钱兑换中等难度 leetcode链接
139.单词拆分中等难度 leetcode链接
300.最长递增子序列中等难度 leetcode链接
152.乘积最大子数组中等难度 leetcode链接
416.分割等和子集中等难度 leetcode链接
32.最长有效括号困难难度 leetcode链接

题目

（1）爬楼梯

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶

示例 2：

输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶

提示：

1 <= n <= 45

思路

class Solution:def climbStairs(self, n: int) -> int:if n <= 1:return n        dp = [0] * 3dp[1] = 1dp[2] = 2        for i in range(3, n + 1):total = dp[1] + dp[2]dp[1] = dp[2]dp[2] = total        return dp[2]

（2）杨辉三角

题目

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1 输出: [[1]]

提示:

1 <= numRows <= 30

思路

# 时间复杂度：O(numRows^2)。
# 空间复杂度：O(1)。返回值不计入。
class Solution:def generate(self, numRows: int) -> List[List[int]]:c = [[1] * (i + 1) for i in range(numRows)]for i in range(2, numRows):for j in range(1, i):# 左上方的数 + 正上方的数c[i][j] = c[i - 1][j - 1] + c[i - 1][j]return c

（3）打家劫舍

题目

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

思路

class Solution:def rob(self, nums: List[int]) -> int:if len(nums) == 0:  # 如果没有房屋，返回0return 0if len(nums) == 1:  # 如果只有一个房屋，返回其金额return nums[0]# 创建一个动态规划数组，用于存储最大金额dp = [0] * len(nums)dp[0] = nums[0]  # 将dp的第一个元素设置为第一个房屋的金额dp[1] = max(nums[0], nums[1])  # 将dp的第二个元素设置为第一二个房屋中的金额较大者# 遍历剩余的房屋for i in range(2, len(nums)):# 对于每个房屋，选择抢劫当前房屋和抢劫前一个房屋的最大金额dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])return dp[-1]  # 返回最后一个房屋中可抢劫的最大金额

（4）完全平方数

题目

给你一个整数 n ，返回和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12输出：3 解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13输出：2 解释：13 = 4 + 9

提示：

1 <= n <= 10(4)

思路

# 完全背包问题
# 时间复杂度：O(N*sqrt(N))。其中 N=10^4。
#空间复杂度：O(N)。
N = 10000
f = [0] + [inf] * N
for i in range(1, isqrt(N) + 1):for j in range(i * i, N + 1):f[j] = min(f[j], f[j - i * i] + 1)  # 不选 vs 选class Solution:def numSquares(self, n: int) -> int:return f[n]

（5）零钱兑换

题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11输出：3 解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3输出：-1

示例 3：

输入：coins = [1], amount = 0 输出：0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 2(31) - 1
0 <= amount <= 10(4)

思路

类似于（4）的“完全平方数”求解

# 完全背包问题
# 时间复杂度：O(n⋅amount)，其中 n 为 coins 的长度。
# 空间复杂度：O(amount)。
class Solution:def coinChange(self, coins: List[int], amount: int) -> int:f = [0] + [inf] * amountfor x in coins:for c in range(x, amount + 1):f[c] = min(f[c], f[c - x] + 1)ans = f[amount]return ans if ans < inf else -1
# 链接：https://leetcode.cn/problems/coin-change/solutions/2119065/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-21m5/

（6）单词拆分

题目

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false

提示：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同

思路

# 时间复杂度：O(n^2)
# 空间复杂度：O(n)
class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:       n=len(s)dp=[False]*(n+1)dp[0]=Truefor i in range(n):for j in range(i+1,n+1):if(dp[i] and (s[i:j] in wordDict)):dp[j]=Truereturn dp[-1]

（7）最长递增子序列

题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3] 输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7] 输出：1

提示：

1 <= nums.length <= 2500
-10(4) <= nums[i] <= 10(4)

思路

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if len(nums) <= 1:return len(nums)dp = [1] * len(nums)result = 1for i in range(1, len(nums)):for j in range(0, i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j] + 1)result = max(result, dp[i]) #取长的子序列return result

（8）乘积最大子数组

题目

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

示例 1:

输入: nums = [2,3,-2,4] 输出: 6解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组

提示:

1 <= nums.length <= 2 * 10(4)
-10 <= nums[i] <= 10
nums 的任何子数组的乘积都保证是一个 32-位 整数

思路

# 动态规划
class Solution:def maxProduct(self, nums: List[int]) -> int:if not nums: return res = nums[0]pre_max = nums[0]pre_min = nums[0]for num in nums[1:]:cur_max = max(pre_max * num, pre_min * num, num)cur_min = min(pre_max * num, pre_min * num, num)res = max(res, cur_max)pre_max = cur_maxpre_min = cur_minreturn res

（9）分割等和子集

题目

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

思路

class Solution:def canPartition(self, nums: List[int]) -> bool:_sum = 0# dp[i]中的i表示背包内总和# 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200# 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了dp = [0] * 10001for num in nums:_sum += num# 也可以使用内置函数一步求和# _sum = sum(nums)if _sum % 2 == 1:return Falsetarget = _sum // 2# 开始 0-1背包for num in nums:for j in range(target, num - 1, -1):  # 每一个元素一定是不可重复放入，所以从大到小遍历dp[j] = max(dp[j], dp[j - num] + num)# 集合中的元素正好可以凑成总和targetif dp[target] == target:return Truereturn False

（10）最长有效括号

题目

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。

示例 1：

输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"

示例 3：

输入：s = "" 输出：0

提示：

0 <= s.length <= 3 * 10(4)
s[i] 为 '(' 或 ')'

思路

# 时间复杂度: 每个字符最多入栈，出栈各一次。再加上统计1的个数，最多为 O(3n)
# 空间复杂度: O(n)
class Solution:def longestValidParentheses(self, s: str) -> int:stack=[]maxL=0n=len(s)tmp=[0]*n         #标记数组cur=0for i in range(n):if s[i]=='(':stack.append(i)else:if stack:j=stack.pop()tmp[i],tmp[j]=1,1      #匹配成功时标记    for num in tmp:    #计算连续1出现的最大次数if num:cur+=1else:          #遇到0时中断，进行对比，并重置maxL=max(cur,maxL)  cur=0maxL=max(cur,maxL) #最后一次统计可能未终断，多做一次对比return maxL

结尾

亲爱的读者朋友：感谢您在繁忙中驻足阅读本期内容！您的到来是对我们最大的支持❤️

正如古语所言："当局者迷，旁观者清"。您独到的见解与客观评价，恰似一盏明灯💡，能帮助我们照亮内容盲区，让未来的创作更加贴近您的需求。

若此文给您带来启发或收获，不妨通过以下方式为彼此搭建一座桥梁： ✨ 点击右上角【点赞】图标，让好内容被更多人看见 ✨ 滑动屏幕【收藏】本篇，便于随时查阅回味 ✨ 在评论区留下您的真知灼见，让我们共同碰撞思维的火花

我始终秉持匠心精神，以键盘为犁铧深耕知识沃土💻，用每一次敲击传递专业价值，不断优化内容呈现形式，力求为您打造沉浸式的阅读盛宴📚。

有任何疑问或建议？评论区就是我们的连心桥！您的每一条留言我都将认真研读，并在24小时内回复解答📝。

愿我们携手同行，在知识的雨林中茁壮成长🌳，共享思想绽放的甘甜果实。下期相遇时，期待看到您智慧的评论与闪亮的点赞身影✨！

万分感谢🙏🙏您的点赞👍👍、收藏⭐🌟、评论💬🗯️、关注❤️💚

自我介绍：一线互联网大厂资深算法研发（工作6年+），4年以上招聘面试官经验（一二面面试官，面试候选人400+），深谙岗位专业知识、技能雷达图，已累计辅导15+求职者顺利入职大中型互联网公司。熟练掌握大模型、NLP、搜索、推荐、数据挖掘算法和优化，提供面试辅导、专业知识入门到进阶辅导等定制化需求等服务，助力您顺利完成学习和求职之旅（有需要者可私信联系）

友友们，自己的知乎账号为“快乐星球”，定期更新技术文章，敬请关注！