题目列表
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] * 3
dp[1] = 1
dp[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 <= 1000 <= nums[i] <= 400
思路
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 0: # 如果没有房屋，返回0
return 0
if 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 <= 121 <= coins[i] <= 2(31) - 10 <= 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] * amount
for 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 <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和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]=True
for i in range(n):
for j in range(i+1,n+1):
if(dp[i] and (s[i:j] in wordDict)):
dp[j]=True
return 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 = 1
for 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] <= 10nums的任何子数组的乘积都 保证 是一个 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_max
pre_min = cur_min
return res（9）分割等和子集
题目
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
思路
class Solution:
def canPartition(self, nums: List[int]) -> bool:
_sum = 0
# dp[i]中的i表示背包内总和
# 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
# 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
dp = [0] * 10001
for num in nums:
_sum += num
# 也可以使用内置函数一步求和
# _sum = sum(nums)
if _sum % 2 == 1:
return False
target = _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)
# 集合中的元素正好可以凑成总和target
if dp[target] == target:
return True
return 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=0
n=len(s)
tmp=[0]*n #标记数组
cur=0
for 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+=1
else: #遇到0时中断，进行对比，并重置
maxL=max(cur,maxL)
cur=0
maxL=max(cur,maxL) #最后一次统计可能未终断，多做一次对比
return maxL结尾
亲爱的读者朋友：感谢您在繁忙中驻足阅读本期内容！您的到来是对我们最大的支持❤️
正如古语所言："当局者迷，旁观者清"。您独到的见解与客观评价，恰似一盏明灯💡，能帮助我们照亮内容盲区，让未来的创作更加贴近您的需求。
若此文给您带来启发或收获，不妨通过以下方式为彼此搭建一座桥梁： ✨ 点击右上角【点赞】图标，让好内容被更多人看见 ✨ 滑动屏幕【收藏】本篇，便于随时查阅回味 ✨ 在评论区留下您的真知灼见，让我们共同碰撞思维的火花
我始终秉持匠心精神，以键盘为犁铧深耕知识沃土💻，用每一次敲击传递专业价值，不断优化内容呈现形式，力求为您打造沉浸式的阅读盛宴📚。
有任何疑问或建议？评论区就是我们的连心桥！您的每一条留言我都将认真研读，并在24小时内回复解答📝。
愿我们携手同行，在知识的雨林中茁壮成长🌳，共享思想绽放的甘甜果实。下期相遇时，期待看到您智慧的评论与闪亮的点赞身影✨！
万分感谢🙏🙏您的点赞👍👍、收藏⭐🌟、评论💬🗯️、关注❤️💚
自我介绍：一线互联网大厂资深算法研发（工作6年+），4年以上招聘面试官经验（一二面面试官，面试候选人400+），深谙岗位专业知识、技能雷达图，已累计辅导15+求职者顺利入职大中型互联网公司。熟练掌握大模型、NLP、搜索、推荐、数据挖掘算法和优化，提供面试辅导、专业知识入门到进阶辅导等定制化需求等服务，助力您顺利完成学习和求职之旅（有需要者可私信联系）
友友们，自己的知乎账号为“快乐星球”，定期更新技术文章，敬请关注！