32. Longest Valid Parentheses
dp[i] = dp[start - 1] + (i - start + 1)
: dp[i]表示到第i个位置为止的有效括号长度,dp[start - 1]表示在start之前的有效括号长度,i - start + 1表示从i到start中间的有效括号长度,start是从栈里pop出来与右括号相对应的左括号,i是当前右括号的下标
if s[i] == '(': stack.append(i)
,注意存放的是左括号下标
else: if stack: start = stack.pop()
如果遇到了右括号,且栈不为空,就从stack里pop出一个左括号的下标作为start
注意最后返回的是max(dp)
53. Maximum Subarray
假设我们已知第i步的global[i](全局最优)和local[i](局部最优),那么第i+1步的表达式是:
local[i+1]=Math.max(A[i], local[i]+A[i]),就是局部最优是一定要包含当前元素,所以不然就是上一步的局部最优local[i]+当前元素A[i](因为local[i]一定包含第i个元素,所以不违反条件),但是如果local[i]是负的,那么加上他就不如不需要的,所以不然就是直接用A[i];
global[i+1]=Math(local[i+1],global[i]),有了当前一步的局部最优,那么全局最优就是当前的局部最优或者还是原来的全局最优(所有情况都会被涵盖进来,因为最优的解如果不包含当前元素,那么前面会被维护在全局最优里面,如果包含当前元素,那么就是这个局部最优)
70. Climbing Stairs
这道题目是求跑楼梯的可行解法数量。每一步可以爬一格或者两个楼梯,可以发现,递推式是f(n)=f(n-1)+f(n-2),也就是等于前一格的可行数量加上前两格的可行数量。熟悉的朋友可能发现了,这个递归式正是[斐波那契数列]
注意当n==0时,也返回1. 初始化时,dp[0]=1, dp[1] = 2, 是从0和1开始,不是从1和2开始。
follow up是有没有更好的解法: 有,O(logn),使用斐波那契的通项公式
91. Decode Ways
dp[i]存储的是加入s中第i-1个元素后有多少种decode方式,所以dp[]初始化时的长度要比s多一位,并且使dp[0]=1
- 注意,0只能出现在1或者2后边,构成10,20,如果单独出现的0,则无法解析
- 如果字符s[i-1]不为0,则这个字符可以独立地被解析,例如:1-9,
dp[i] += dp[i-1]
- 如果字符s[i-2:i]大于'09'且小于'27',证明i-1位字符和i-2位字符可以放在一起被解析,
dp[i] += dp[i-2]
-
dp[i-2:i] < '27'
这是按ASCII码值来比较的,python中可以对字符串进行比较,都是先将其转换为ASCII码值。其中,大写字母的值都小于小写字母,同时('ab'<'abc')即空位的序数为所有字符最小 - 最后返回dp[-1]
96. Unique Binary Search Trees
这道题在树的分类里已经写过了,但还是有些细节需要添加。
- res数组要初始化n+1位,因为包括0在内了,并且res[0]和res[1]都要初始化为1,其余均为0
-
res[i]+= res[j]*res[i-j-1]
, res[j]代表i左边的left branch数量,res[i-j-1]代表right branch数量。j是i左边的node个数,i-j-1是i右边的node个数,因为n是顺序分解的,所以个数相同,生成的BST就相同。 - 注意外层for循环i的范围:
for i in range(2, n+1):
- 最后返回res[n]
95. Unique Binary Search Trees II
虽然在dp分类里,但其实更偏向于divide and conquer
- 构建一个生产子树的函数,参数为start, end,分别等于1和n
- 在这个函数内,如果start>end,就返回[None], 括号里一定要有none, 如果start==end, 就返回[TreeNode(start)]
-
for i in range(start, end+1)
, end要加1 leftsubtree = self.generate(start, i-1), rightsubtree = self.generate(i+1, end)
- 在for循环前要初始化
res = []
- 将左右子树用两个for循环排列组合起来,要先
root = TreeNode(i)
, 每组合成功一个后就res.append(root)
120. Triangle
这道题之前也写过了,需要注意的点有:
- res初始化时的长度为triangle最后一行的长度再加1,加1是因为如果triangle里只有一行,那就超出了递归式里的索引范围
- 思路是将triangle reverse,然后针对每一行(倒序)里的每一个数字,更新res[i],等于当前数字,加上一组的min(res[i], res[i+1])
- 最后返回res[0], 因为第一行只有一个数字
121. Best Time to Buy and Sell Stock
又是局部最优,全局最优方法。初始化local和res均为0, 先判断数组是不是递减的,如果是就返回0if sorted(prices) == prices[::-1]: return 0
若不是递减的,针对数组中每一个数字,计算
local = max(0, local + prices[i+1] - prices[i]), res = max(res, local)
- i的循环范围是
for i in range(len(prices)-1)
, 因为后边有i+1 - 更新local时,应该加上原来的Local, 和0比较是因为价格有可能是负数。
- 为什么要加上原来的Local, 因为1,5,3,6, 1到6的距离是5,等于(5-1)+(3-5)+(6-3)
139. Word Break
针对动态规划的思路:
- 决定存储什么历史信息以及用什么数据结构来存储
- 递推式,就是如何从存储的历史信息中得到当前结果
- 初始值的设定
这道题,dp[i]表示的是在s中的前i-1个字符s[:i]
是否存在wordDict里,初始化dp的长度要是s的长度加1,因为要存储dp[0]=True
双重for循环,注意内层循环时j的范围是for j in range(i, len(s)):
, 从i开始到字符串结束。
判断条件if dp[i] and s[i:j+1] in wordDict: dp[j+1] = True
dp[i]为真证明s的前i-1个字符存在里边,如果s[i:j+1]也存在,我们就更新dp[j+1]为真
最后返回dp[-1],d[7] is True because there is "code" in the dictionary that ends at the 7th index of "leetcode" AND d[3] is True
152. Maximum Product Subarray
和maximum sum subarray类似,只不过这道题是求最大乘积。方法也是先初始化maxlocal和res, 但这道题要再加一个minlocal,因为两个很小的负数相乘之后可能会变成很大的整数。所以对nums进行遍历时,递推式里要再加一项对minlocal的更新。
并且要注意因为已经初始化了maxlocal, minlocal, res = nums[0], nums[0], nums[0]
, 所以for循环要从1开始。
在每次循环过程中:
maxcopy = maxlocal
maxlocal = max(maxlocal*nums[i], nums[i], minlocal*nums[i])
minlocal = min(maxcopy*nums[i], nums[i], minlocal*nums[i])
res = max(maxlocal, res)
要先将maxlocal复制一下,作为计算minloca时使用
62. Unique Paths
具体思路参考第161页https://www.dropbox.com/s/d839bnp9lcroxmq/Sample_Interview_Questions_Set_16.pdf?dl=0
- 需要注意的是,我们可以用二维数组代替一维数组。只需要对一维数组更新m次就可以。因为在二维数组中,每个方格所拥有的路径数等于上边方格➕左边方格。在一维数组中,每次更新时,当前方格就属于上边方格,所以只需要加上左边方格就可。
- 还有一点需要注意,内部循环从1开始. 这是因为第一列中每个方格的路径数始终都是1
for i in range(m):
for j in range(1, n)```
- 初始化res[0] = 1,res的长度要和n一样!!
#63. Unique Paths II
在上一题的基础上增加了障碍,即有的方格为1时便不可通过。总体思想没有变化,依然可以用一维数组代替二维数组。
- 这次内部循环不能从1开始,因为第一列的方格中有可能存在障碍,即值为1,所以每次循环都要做判断:
if board[i][j] == 1:
res[j] = 0
elif j > 0:
res[j] += res[j-1]
- 依然需要初始化res[0] = 1,res的长度要和n一样!!
#64. Minimum Path Sum
依然是从左上角到右下角,求最短路径和。同样使用一维数组,因为第一行的每个元素只能从左边那个元素过来,所以grid第一行对应的一维数组:
for i in range(1, n):
res[i] = res[i-1] + grid[0][i]
然后对一维数组更新!!m-1次:
for i in range(1, m):
for j in range(n):
if j == 0:
res[j] = res[j] + grid[i][0]
else:
res[j] = min(res[j-1], res[j]) + grid[i][j]
- 当j==0时,证明我们在更新第一列,第一列的元素只能由上边的元素过来,所以是上边元素的值加上当前元素的值,res[j]就是上一行的第一列的元素。
- 当j!=0时,针对每个元素,它可以从上或左的元素得到,我们就在上和左元素中选一个最小值,再加上当前元素。上边的元素就是res[j](因为此时还没有更新res[j]), 左边的元素就是res[j-1]