LeetCode习题集
作为一名本科计算机科学与技术的学生，《数据结构与算法》《算法分析与设计》这两门课没有学到特别好
上了研究生之后感觉，这些东西需要重新拾起
于是，我找了一个平台，LeetCode，很好的一个刷题的平台，很多大厂的面试题，就出现在上面。
于是我下定决心，我要好好实践好算法，这样才能做一个有人要的打工人，呜呜呜。
（2020/12/19更新：有一些题目没有直接放链接，但是有价值的题目我一定会放在这里，供以后怀念，呜呜呜）
chapter1：递归
（lookdown）563. 二叉树的坡度（特别需要注意在Python中global与nonlocal之间的区别，复习一下留下一个问题：是否是后序遍历？），
（lookdown）242. 有效的字母异位词（一道简单题可以学到很多Algorithm Wisdom），
（lookdown）222. 完全二叉树的节点个数（用递归和非递归的差别），
（lookdown）面试题 08.05. 递归乘法（极其有趣的一道题），
（lookdown）剑指 Offer 16. 数值的整数次方（一开始就觉得暴力吧，想起来刚学过的高等算法分析与实现老师说过霍纳法则，其实中国更早，叫做秦九韶算法，计算多项式
，但是如果只计算第一项an*x^n，该公式退化成暴力法，因此提出了二进制幂乘法问题，矩阵n次幂也是如此。还好自己想起来了n次幂这种求法），
面试题 08.06. 汉诺塔问题（如何用stack模拟实现），
698. 划分为k个相等的子集（分而治之法是非常典型的递归，同时回溯也用递归的方法解决），
（lookdown）204. 计数质数（非常简单的“简单题”，太sao了这道题，真的需要点数学基础才能行），
（lookdown）17. 电话号码的字母组合（真开心自己做出来了，经典的回溯代码），
（lookdown）1306. 跳跃游戏 III（接着上面的回溯接着写代码），
（lookdown）779. 第K个语法符号（这是一道值得反思的“回溯题”，非常值得和1306和前面的1306和17对比），
90. 子集 II 幂集的产生，比如求[13,2,2,1,2]的幂集
77. 组合 （组合问题。（不是我总结的）递归的模板放在下面）
chapter2：数据结构基本结构-栈stack
（lookdown）剑指 Offer 30. 包含min函数的栈（犯了一个小错误），
20. 有效的括号（stack，简单题，但是要注意一些简单的坑）
860. 柠檬水找零（暂且用暴力的方法进行模拟，其实可以考虑用回溯的方法！！！其实也可以记录$5，$10，￥20的个数（只有三种纸币，简单），这样take change 特别方便）
1021. 删除最外层的括号(用了笨方法，肯定还可以优化，晚上22:44了，先回宿舍了！！！)
1047. 删除字符串中的所有相邻重复项(用stack极其简单，特别是python语言)
面试题 03.02. 栈的最小值(对上面的题目稍稍改造了一点点，解释之前的题目剑指 Offer 30. 包含min函数的栈)
155. 最小栈(与面试题 03.02. 栈的最小值一模一样，the same way to solve it)
682. 棒球比赛(这道题引出一个问题，Python如何确定你输入的string是数字，本题的代码我采用了避开这个问题，但是若要是避免不了，how can I do?)
389. 找不同(很多种方法可以解题，但是值得学的是一种很奇妙的 Python 位运算 （用来找不同）方法，太奇妙了，因为位运算针对于找“单个值”真的太方便了)
面试题 03.04. 化栈为队 (学会比较化栈为队，和化队为栈，思路简直一模一样)
1598. 文件夹操作日志搜集器（没有使用栈的解法）
225. 用队列实现栈 (学会比较化栈为队，和化队为栈，思路简直一模一样)
173. 二叉搜索树迭代器(非常值得学的一道题，not very ,it's very more,巧妙的 栈+受控递归（有大佬说这是一种《算法导论》中的摊还分析Amortized Analysis）)
35. 搜索插入位置(非常“简单”的简单题，自己要总结一些二分法的坑，该题属于“二分法”)
103. 二叉树的锯齿形层序遍历(层次遍历，该次属于“队列”，将每一层分层次存储，用两个指针即可)
剑指 Offer 59 - II. 队列的最大值(好好理解双端队列的基本操作，以及该题是怎么维护单调队列，这一种数据结构的)
1381. 设计一个支持增量操作的栈(1.模拟 2.模拟+改进)
205. 同构字符串（绝对够学的一道同构题，与之前290. 单词规律很像，主要是要想好怎么给“同构”下定义）
144. 二叉树的前序遍历(递归与迭代，迭代法好像需要O（n）的空间复杂度，因为需要用到栈stack，但是官方给出了一种O（1）的解法，居然可以将空间复杂度降到最低，看一下总还是可以的，菜鸟的我也只能也只能看一下这么高级的算法)
496. 下一个更大元素 I (思考用hashmap的原因和好处？栈少有的应用：单调栈，怎么维护一个单调栈，这才是关键？)
739. 每日温度(这一题与上一题496. 下一个更大元素 I 相比有差别，差别是已知数据中温度中可能出现重复值（hashmap不允许出现重复值）因此我们怎么办呢？办法：因为题目要求的是后几个元素，因为stack就存数组的下标就行，不再是是像496. 下一个更大元素 I 一样，存入数组中的数值，应该好好体会一下这两题之间的区别)
605. 种花问题（别小看这道真的很简单的简单题，第二个简单题没有打双引号，但是真的很奇怪，解法1：前后补充种花（怎么补充？）解法2：贪心，怎么贪，能种就种，管他的，贪心就是目前情况能怎么样就怎么样，不管以后怎么样）
（持续更新）
chapter3：动态规划dp
首先动态规划的步骤（动态规划五部曲）是：
（0.举例推导dp数组，发现第一步dp数组规律的过程就是举例推到dp数组的过程）
1.确定dp数组（dp table）以及下标的含义 ，dp数组是一维还是二维还是三维？（持续更新）
2.确定递推公式
3.dp数组怎么初始化
4.确定遍历顺序
5.举例推导dp数组
动态规划怎么debug？？？（灵魂三问）
1.这道题目我举例推导过转移公式吗？
2.我打印dp数组日志了吗？
3.打印出来的dp数组日志是和我想的一样吗？
振聋发聩，专治DP疑难杂症，题目刷起来！！！wuuuu
斐波那契数列是最简单的动态规划问题
746. 使用最小花费爬楼梯(爬楼梯的稍微改变版)
303. 区域和检索 - 数组不可变 简单题中体会 “前缀和”的使用
392. 判断子序列 （really?一切即可…dp???huhhhhh，其实双指针效率挺好的，终于AC了）
343. 整数拆分（第一次接触到这种类型的动态规划，有点矩阵连乘的感觉，特意回去看了看本科Sunny老师【此处感谢Sunny老师，没有他的耐心细心教导，我觉得我找不到计算机的兴趣】的“矩阵连乘”的算法（我居然想的起来2-3年前的知识，感觉好神奇呀！！！），学会比较，在比较中学习，理解的知识面将会以“指数爆炸式”增长，yets显然我tai vegetable了）
132. 分割回文串 II（困难题，但是非常值得学习其中的方法与细节）
背包系列之0-1背包
基础知识：0-1背包初讲，用二维dp数组dp[][]；然后对0-1背包进行空间优化，用dp数组dp[]，这个非常重要，为什么用一位数组的时候需要倒序，因为正序会出现覆盖问题；接下来便是学会将0-1背包问题转换问题。
所以，0-1背包的实质就是从一堆“物品”中挑选一些“物品”放进背包，使得背包内的“价值”（“价值”是目标）最大？
416. 分割等和子集 （0-1背包问题转化问题：是否可以从数组中选择出一些数字，重点理解dp[i] = i？这个判定条件）
1049. 最后一块石头的重量 II (0-1背包问题转化问题：是否可以从一堆数字当中，dp[i] 的含义和0-1背包的含义很相近)
494. 目标和 （另外一种0-1背包转化问题，不要将第一个物品放入初始化）
474. 一和零 (之前0-1背包的维度（也就是目标的维度）都是一维，比如dp[j]表示剩余空间为j时最大能够达到的价值（目标：价值），或者dp[j]表示空间为j时能够满足的方案数为dp[j]（目标：方案数）等，但是该题变成了二维，值得学习)
70. 爬楼梯 动态规划：以前我没得选，现在我选择再爬一次！（摘自Carl哥）用动态规划的思维去想爬楼梯问题
322. 零钱兑换 动态规划： 给我个机会，我再兑换一次零钱 （摘自Carl哥）用动态规划再次兑换零钱
279. 完全平方数 和上题322. 零钱兑换 一模一样，学会了思想，接下来就是遍历循序的问题了
139. 单词拆分 完全背包的转化，遍历顺序最好是先背包，再物品，为什么？需要好好体会！注意Python中s[1:3]的取值范围是下标为1,2，不包括3
0-1背包问题暂且完毕，接下来便是年后的动态规划了，2021年后dp
198. 打家劫舍 再次理解dp[i]表示包括i的前i个房间能够达到的最大金额，取决与这个第i个房间的偷与不偷，不偷的话，就是dp[i-1](包括i-1的前i-1个房间能够达到的最大金额)，偷的话就是dp[i-2] + nums[i](包括i-2的前i-2个房间能够达到的最大金额加上第i个房间的金额)，dp[i] = max(dp[i-1], dp[i-2]+nums[i])，初始化应该是dp[2] = max(dp[1], dp[0]+nums[0]) （i取2，粗体为初始化对象），遍历顺序显然是从前往后
213. 打家劫舍 II 在上题198. 打家劫舍的基础上怎么处理成环问题？【分解环】
337. 打家劫舍 III 解法一：在树上执行198. 打家劫舍，入门树状dp ; 解法二：DFS后序遍历+memoryMap，简称记忆化深搜 这道题值得复习了
动态规划问题之股票问题
121. 买卖股票的最佳时机 不容易想到的动态规划问题，需要好好看几遍，看看代码中的详细注解，另外还有一种想法：贪心
心想(贪的角度)：要是我能够在最小值（尽管最小值可能出现在数组最后一位）的时候买入，之后只要比最小值大就可以了
309. 最佳买卖股票时机含冷冻期 写了很多注释，值得一看，重视思路的培养
674. 最长连续递增序列 VS 300. 最长递增子序列 比较连续与否对递推关系式的影响
（持续更新）
chapter4：回溯（跟着Carl哥刷的回溯）
216. 组合总和 III 组合问题
77. 组合 （组合问题。（不是我总结的）递归的模板放在下面，见chapter1：递归）
131. 分割回文串 看代码处有写明错误之处，一定得看一下教训
chapter5：贪心（跟着Carl哥刷的贪心）
贪心没有捷径（贪心是朴素的思路，所以经常让我们忘记这一重要的算法）、思考点是可不可以找到一个贪的点，能够让局部最优到达全局最优。
455. 分发饼干 与排序贪心，贪的角度：为了不浪费饼干，让饼干最大的给胃口最大的。
376. 摆动序列 没有排序，贪的角度：寻找下一个满足条件的点（保持区间波动，只需要把单调区间上的元素移除就可以了。）
20200904
45. 跳跃游戏 II 不要一直想当前应该走几步，而是当前我能够走到哪里的范围！
chapterX：哈希表
剑指 Offer 50. 第一个只出现一次的字符 （用数组做哈希，比set，map这样的数据结构快一点，学会用数组用哈希）
（持续更新）
chapterX：拓扑排序（该类型的题目在leetcode上目前发现题量较少）
207. 课程表（第一次写拓扑排序，感觉用Brute Force的办法可能效率较低；一般情况下是已知有向无环图，然后给出拓扑排序的顺序，该题是给出一个图，要你去判断存不存在拓扑排序。关键是怎么判断存不存在拓扑排序的条件）
210. 课程表 II (与207. 课程表一模一样，这是对最简单的拓扑排序的加强版，若是存在多种拓扑排序，只需要输出任意一种合理的方式即可)
（持续更新）
chapterX：双指针（别小看这没人注意的双指针，多用来解决字符串问题，且效率极高）
392. 判断子序列 （really?一切即可…dp???huhhhhh，其实双指针效率挺好的）
27. 移除元素 复习双指针做的题，双指针常用于数组处理和链表处理，且是一种十分高效的方法 【快慢双指针法】
（持续更新）
chapterX：待分组
1232. 缀点成线 这题目虽然简单，但是可以从中学到其他东西，（期末考试）等待更新
1. 两数之和 这题注意看代码，为什么不能两句代码的顺序？
chapter1 Resolution：递归
563.二叉树的坡度 的题解，感觉非常奇妙，特别是最后一句“而左子树之和加右子树之和加节点值为总树的和，巧妙复用了”。“复用”一词用的非常准确，在这里感谢这位大佬分享了代码。不知道怎么应用大佬的代码，直接截图过来了，反正除了我应该也没人看。
283.移动零 的题解，话说是简单题（但是要求不允许开数组，同时尽量减少比较次数），但其实还是有很多够我这个菜鸟学的。这里总结一下双指针的解法。
双指针：1.i指针当然是遍历整个数组的指针，它的关注点发现非零元素。2.j指针指示所有非零元素的位置。
解法：i指针从头扫到尾，发现一个非零的数，就把这个数与j指针指向的数覆盖，然后j指针就开始后移，表明在j前面的元素都是非零元素。这样i指针一遍扫下来，就把所有的非零元素全部按顺序移到了前面。i扫完后，此时的j指针就指向了所有非零元素的后一个空位，如图所示。接下来便是把j指针指向的后面所有元素改成0即可完成操作。
1 class Solution:
2 def moveZeroes(self, nums: List[int]) -> None:
3 """
4 Do not return anything, modify nums in-place instead.
5 """
6 res_end = 0
7 nums_count = len(nums)
8 for i in range(nums_count):
9 if nums[i] != 0:
10 nums[res_end] = nums[i]
11 res_end += 1
12
13 for i in range(res_end,nums_count):
14 nums[i] = 0
15 # nums.sort(key=lambda x:x==0)
移动零
242.有效的字母异位词
这道题三道解法，1.暴力 violence 2.Python骚操作 3.哈希
由图可知，哈希时间空间复杂度都是很好的，随便学习了一种新的方法，哈希
1 class Solution:
2 def isAnagram(self, s: str, t: str) -> bool:
3 # 解法一：暴力法 n方
4 # A = []
5 # B = []
6 # for i in range(len(s)):
7 # A.append(s[i])
8 # for i in range(len(t)):
9 # B.append(t[i])
10 # if len(s) == len(t):
11 # for i in A:
12 # if i in B:
13 # B.remove(i)
14 # else:
15 # return False
16 # return True
17 # return False
18
19 # 解法二：排序法
20 # A = sorted(s)
21 # B = sorted(t)
22 # return A == B # [1,2]=[2,1]这是成立的
23
24 # 解法三：哈希
25 arr = [0] * 26
26 for i in range(len(s)):
27 arr[ord(s[i])-97] += 1 # ord("a")=97 ord函数表示将字符转成ASCII chr()将ASCII转成字母
28
29 for i in range(len(t)):
30 arr[ord(t[i])-97] -= 1
31
32 for i in arr:
33 if i == 0:
34 pass
35 else:
36 return False
37 return True
有效的字母异位词
222. 完全二叉树的节点个数 递归和非递归的时间和空间差别，最开始用队列模拟的方法时间和空间都比较大，但是用递归时稍微少一点，但是空间差不多，我隐隐约约感觉还有更好的方法，毕竟是完全二叉树，可以利用完全二叉树的特性。
1 # Definition for a binary tree node.
2 # class TreeNode:
3 # def __init__(self, x):
4 # self.val = x
5 # self.left = None
6 # self.right = None
7
8 class Solution:
9 def countNodes(self, root: TreeNode) -> int:
10 # # 采用层次遍历，进行计数
11 # if not root:
12 # return 0
13 # Queue = []
14 # Queue.append(root)
15
16 # s = 0
17 # while(Queue):
18 # x = Queue.pop(0)
19 # s += 1
20 # if x.left:
21 # Queue.append(x.left)
22 # if x.right:
23 # Queue.append(x.right)
24
25 # return s
26
27 # 递归
28 if not root:
29 return 0
30 s= 1 # 初始化根节点计数为1
31 def reverse(root):
32 nonlocal s
33 if not root:
34 return 0;
35 if root.left:
36 reverse(root.left)
37 s += 1
38 if root.right:
39 reverse(root.right)
40 s += 1
41
42 reverse(root)
43
44 return s
完全二叉树的节点个数
面试题 08.05. 递归乘法（极其有趣的一道题）递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。最开始的想法就是将乘法转移成加法，看了别人的思路之后，马上想起来刚学过的“俄式乘法”（对不起刚学过得算法老师，刚学不久就忘了，o(╥﹏╥)o）
用了两种方法解题，一直以为快速幂应该会快一点，但是运行完之后发现时间居然还慢一点（最简单的思路花时间36ms，但是没想到快速幂居然花了40ms,eeeeeee…..）
1 class Solution:
2 def multiply(self, A: int, B: int) -> int:
3 if A == 0 and B == 0:
4 return 0
5
6 # A, B = min(A, B), max(A, B)
7 if A == 1:
8 return B
9 if A & 1 == 1:
10 t = int(self.multiply((A-1)>>1, B)<<1) + B
11 else:
12 t = int(self.multiply((A)>>1, B)<<1)
13
14 return t
15
16 # 简单的将乘法转换成加法来做
17 # if A > B:
18 # # 交换AB
19 # t = A
20 # A = B
21 # B = t
22 # s = 0
23
24 # def nomulti(A, B):
25 # nonlocal s
26 # if A == 0:
27 # return ;
28 # s = s + B
29 # nomulti(A-1, B)
30
31 # nomulti(A,B)
32 # return s
递归乘法
剑指 Offer 16. 数值的整数次方 代码如下：
1 class Solution:
2 def myPow(self, x: float, n: int) -> float:
3 if n == 0:
4 return 1;
5 elif n > 0:
6 y = 1
7 while n:
8 if n & 1:
9 y = y * x
10 x = x * x
11 n = n >> 1
12 return y
13 elif n < 0:
14 y = 1
15 n = -n
16 while n:
17 if n & 1:
18 y = y * x
19 x = x * x
20 n = n >> 1
21 return 1/y
数值的整数次方
204. 计数质数 这道暴力解绝对不行，就算我用python埃筛了一遍也不行，还要继续优化，愁了一天，哎！！！（注释的是第一种方法，超时，后面对其进行改进才可以过）
1 class Solution:
2 def countPrimes(self, n: int) -> int:
3
4 # def isPrime(i):
5 # for ind in range(2, int(sqrt(i))+1):
6 # if i % ind == 0:
7 # return False
8 # return True
9
10 # if n == 0 or n == 1:
11 # return 0
12 # A = [i for i in range(2,n)]
13
14 # candidate_prime = []
15 # # 候选质数
16 # for i in range(2, int(sqrt(n))+1):
17 # if isPrime(i):
18 # candidate_prime.append(i)
19 # # print(candidate_prime)
20
21 # #循环消除
22 # for i in range(len(candidate_prime)):
23 # j = candidate_prime[i] * candidate_prime[i]
24 # while j < n:
25 # if j in A:
26 # A.remove(j)
27 # j += candidate_prime[i]
28 # return len(A)
29
30 def isPrime(i):
31 for ind in range(2, int(sqrt(i))+1):
32 if i % ind == 0:
33 return False
34 return True
35
36 if n == 0 or n == 1:
37 return 0
38 A = [i for i in range(2, n)]
39
40 for i in range(2, int(sqrt(n))+1):
41 if A[i-2] and isPrime(i):
42 x = i * i
43 while x < n:
44 A[x-2] = 0
45 x = x + i
46 ans = 0
47 for i in A:
48 if i != 0:
49 ans += 1
50 return ans
计数质数
17. 电话号码的字母组合 回溯&递归，顺便补充一个，将“abc”字符串直接转成['a', 'b', 'c']的方法。
1 class Solution:
2 def letterCombinations(self, digits: str) -> List[str]:
3 if digits == "":
4 return []
5 num_letter = [
6 ['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i'], ['j', 'k', 'l'], ['m', 'n', 'o'],
7 ['p', 'q', 'r', 's'], ['t', 'u', 'v'], ['w', 'x', 'y', 'z']
8 ]
9 # digits = sorted(digits)
10 digits = list(digits)
11 length = len(digits)
12
13 dig = []
14 for i in range(len(digits)):
15 dig.append(int(digits[i]) - 2)
16 # print("dig", dig)
17
18 res = []
19
20 # nums = [0, 1]
21 def backtrace(nums, k, s):
22 if k == length:
23 res.append(str(s))
24 return ;
25 x = nums[k]
26 for i in range(len(num_letter[x])):
27 s += str(num_letter[x][i])
28 backtrace(nums,k+1,s)
29 s = s[:-1]
30
31 backtrace(dig, 0, '')
32
33 return res
电话号码的字母组合
1306. 跳跃游戏 III 回溯& 递归 加vis数组稍微优化一下
1 class Solution:
2 def canReach(self, arr: List[int], start: int) -> bool:
3 if not arr:
4 return False;
5
6 length = len(arr)
7 # vis(ited) 数组稍微优化一下
8 vis = [0] * length
9 if start > length:
10 return False
11
12 def backtrace(index, arr):
13 if arr[index] == 0:
14 return True
15 else:
16 if 0 <= index + arr[index] <= length - 1 and vis[index + arr[index]] == 0:
17 vis[index + arr[index]] = 1
18 if backtrace(index + arr[index], arr):
19 return True
20 if 0 <= index - arr[index] <= length - 1 and vis[index - arr[index]] == 0:
21 vis[index - arr[index]] = 1
22 if backtrace(index - arr[index], arr):
23 return True
24 return False
25
26 TF = backtrace(start, arr)
27 vis[start] = 1
28
29 return TF
30
跳跃游戏 III
779. 第K个语法符号 一开始我就直接写了没有剪枝的回溯法，结果在N=30会超时。所以重新画了图，观察规律，其实这是二叉树。（红色部分为该层的编号，标有*号的编号3和4分别是其父节点编号2的两倍和两倍-1）
为什么要用这个规律呢？因为其实我们知道题目已知的K（第N层中的）之后我们就可以推算K-1层中的编号，以此类推，比如我们假设我们知道1（2），我们可以按照那个两倍规律，推算出1（2）-->0（1）-->0（1）-->0（1）。
1 class Solution:
2 def kthGrammar(self, N: int, K: int) -> int:
3
4 if K > pow(2, N-1):
5 return ;
6
7 # def backtrace(t, arr):
8 # if t == N:
9 # return arr[K-1]
10 # tmp = []
11 # for i in range(len(arr)):
12 # if arr[i] == 0:
13 # tmp.append(0)
14 # tmp.append(1)
15 # elif arr[i] == 1:
16 # tmp.append(1)
17 # tmp.append(0)
18 # arr = tmp
19 # return backtrace(t+1, arr)
20
21 # T = backtrace(1, [0])
22
23 # return T
24
25 feature_list = []
26 feature_list.append(K)
27 while N-1:
28 K = ceil(K / 2)
29 feature_list.append(K)
30 N -= 1
31
32 feature_list = sorted(feature_list)
33 print(feature_list)
34
35 t = 0
36 for i in range(1,len(feature_list)):
37 if feature_list[i] == feature_list[i-1] * 2 and t == 0:
38 t = 1
39 elif feature_list[i] + 1 == feature_list[i-1] * 2 and t == 0:
40 t = 0
41 elif feature_list[i] == feature_list[i-1] * 2 and t == 1:
42 t = 0
43 elif feature_list[i] + 1 == feature_list[i-1] * 2 and t == 1:
44 t = 1
45 # print(t)
46
47 return t
第K个语法符号
77. 组合 终于，递归的模板出来了，回溯是典型要使用递归的（模板取自《代码随想录》，方便以后复习的时候用）。
1 class Solution:
2 def combine(self, n: int, k: int) -> List[List[int]]:
3
4
5 A = []
6
7 def backtrace(k,start,end,arr):
8 nonlocal A
9 if k == 0:
10 # 简单赋值与浅拷贝、深拷贝之间的关系
11 # 将arr内元素拷贝到T中
12 T = []
13 for ind in range(len(arr)):
14 T.append(arr[ind])
15 A.append(T)
16 return;
17
18 for i in range(start, end+1):
19 arr.append(i)
20 k -= 1
21 backtrace(k,i+1,end,arr)
22 k += 1
23 arr.pop()
24
25 backtrace(k,1,n,[])
26
27 # print(A)
28 return A
组合
chapter2 Resolution：数据结构基本结构-栈stack
62. 不同路径 dfs runing out of time ，仔细一想这不是个数学问题嘛！！！
1 class Solution:
2 def uniquePaths(self, m: int, n: int) -> int:
3 # dfs 会 running out of time
4 # path = 0
5
6 # def backtrace(row, col):
7 # nonlocal path
8 # if row > m or col > n:
9 # return ;
10 # if row == m and col == n:
11 # path += 1
12 # return ;
13 # backtrace(row+1, col)
14 # backtrace(row, col+1)
15
16 # backtrace(1,1)
17 # return path
18
19
20 down = 1 # 分母
21 up = 1 # 分子
22 A = m+n-2
23
24 for i in range(m-1):
25 down *= A
26 A -= 1
27
28 for i in range(1,(m-1)+1):
29 up *= i
30
31 return int(down/up)
不同路径
1 class Solution:
2 def uniquePaths(self, m: int, n: int) -> int:
3 # 动态规划方法
4 # dp[i][j] 到达第i行和第j列的方案数量，有多少种走法
5 dp = [[1] * m] * n
6
7 # 初始化，dp[:][0] = 0 and dp[0][:] = 1
8
9 for i in range(1,n):
10 for j in range(1,m):
11 dp[i][j] = dp[i][j-1] + dp[i-1][j]
12
13 # print(dp)
14 return dp[n-1][m-1]
不同路径 更新（2021/1/11）
剑指 Offer 30. 包含min函数的栈 借助于helpStack进行求最小值的优化（其基本思想就是保存当下stack中的最小值，就这么简单的思想），helpStack的特点是自栈底到栈顶维持非递增结构，如[2,3,4,4,5,9]
1 class MinStack:
2
3 # def __init__(self):
4 # """
5 # initialize your data structure here.
6 # """
7 # self.Stack = []
8
9 # def push(self, x: int) -> None:
10 # self.Stack.append(x)
11
12 # def pop(self) -> None:
13 # self.Stack.pop()
14
15 # def top(self) -> int:
16 # return self.Stack[-1]
17
18 # def min(self) -> int:
19 # return min(self.Stack)
20
21 def __init__(self):
22 """
23 initialize your data structure here.
24 """
25 self.Stack = []
26 self.helpStack = []
27
28 def push(self, x: int) -> None:
29 self.Stack.append(x)
30 if not self.helpStack:
31 self.helpStack.append(x)
32 elif self.helpStack and x <= self.helpStack[-1]: # 一开始的时候该句写成了if self.helpStack and x <= self.helpStack[-1]导致出错
33 self.helpStack.append(x)
34
35 def pop(self) -> None:
36 x = self.Stack.pop()
37 if x == self.helpStack[-1]:
38 self.helpStack.pop()
39
40 def top(self) -> int:
41 return self.Stack[-1]
42
43 def min(self) -> int:
44 return self.helpStack[-1]
45
46 # Your MinStack object will be instantiated and called as such:
47 # obj = MinStack()
48 # obj.push(x)
49 # obj.pop()
50 # param_3 = obj.top()
51 # param_4 = obj.min()
包含min函数的栈
860. 柠檬水找零
1 class Solution:
2 def lemonadeChange(self, bills: List[int]) -> bool:
3 s = []
4 cnt_5_dollars = 0
5 for i in range(len(bills)):
6 if bills[i] == 5:
7 s.append(5)
8 cnt_5_dollars += 1
9 elif bills[i] == 10:
10 if 5 in s:
11 s.remove(5)
12 cnt_5_dollars -= 1
13 s.append(10)
14 else:
15 return False
16 elif bills[i] == 20:
17 if 5 in s and 10 in s:
18 s.remove(5)
19 cnt_5_dollars -= 1
20 s.remove(10)
21 s.append(20)
22 continue
23
24 if cnt_5_dollars >= 3:
25 print(cnt_5_dollars)
26 s.remove(5)
27 s.remove(5)
28 s.remove(5)
29 cnt_5_dollars -= 3
30 s.append(20)
31 continue
32 return False
33
34 return True
柠檬水找零
1021. 删除最外层的括号 第一种方法是记录要删除的位置，第二种方法就是之前学到的双指针问题（见283. 移动零）。使用双指针速度大大加快！
1 class Solution:
2 def removeOuterParentheses(self, S: str) -> str:
3 if S == "":
4 return ""
5 # 记录删除符号的位置，然后集中删除
6 # stack = []
7 # arr = list(S)
8
9 # remove_loc = []
10 # for i in range(len(arr)):
11 # if arr[i] == "(":
12 # stack.append(arr[i])
13 # if len(stack) == 1:
14 # remove_loc.append(i)
15 # if arr[i] == ")":
16 # if len(stack) != 1:
17 # x = stack.pop()
18 # elif len(stack) == 1:
19 # remove_loc.append(i)
20 # stack.pop()
21
22 # ans = ""
23 # # print(remove_loc)
24 # for i in range(len(arr)):
25 # if i not in remove_loc:
26 # ans += arr[i]
27
28 # return ans
29
30 # 双指针法
31 arr = list(S)
32 L = len(arr)
33 stack = []
34
35 point = 0
36 for i in range(L):
37 if arr[i] == "(":
38 stack.append(arr[i])
39 if len(stack) >= 2:
40 arr[point] = arr[i]
41 point += 1
42 elif arr[i] == ")":
43 x = stack.pop()
44 if len(stack) != 0:
45 arr[point] = arr[i]
46 point += 1
47 # print(arr[:point])
48
49 return "".join(arr[:point])
50
删除最外层的括号
1 class Solution:
2 def calPoints(self, ops: List[str]) -> int:
3 # 栈stack模拟
4 stack = []
5 for i in range(len(ops)):
6 if ops[i] == "C":
7 stack.pop()
8 elif ops[i] == "D":
9 stack.append(stack[-1] * 2)
10 elif ops[i] == "+":
11 stack.append(stack[-1]+stack[-2])
12 else:
13 stack.append(int(ops[i]))
14
15 return sum(stack)
棒球比赛
389. 找不同 哈希计数，位运算值得考虑。
1 class Solution:
2 def findTheDifference(self, s: str, t: str) -> str:
3 # 可以考虑排序、可以考虑计数（哈希）
4 # A = sorted(s)
5 # B = sorted(t)
6
7 # for i in range(len(A)):
8 # if A[i] == B[i]:
9 # pass
10 # else:
11 # return B[i]
12 # return B[-1]
13
14 # 还可以考虑位运算 异或 ，这种方法在特定情形下太巧秒了
15 res = 0
16
17 s = s + t
18 res = 0
19 for i in range(len(s)):
20 res = res ^ ord(s[i])
21 # print(res)
22 return chr(res)
找不同
1 class MyQueue:
2
3 def __init__(self):
4 """
5 Initialize your data structure here.
6 """
7 self.stack = []
8 self.helper_stack = []
9
10
11 def push(self, x: int) -> None:
12 """
13 Push element x to the back of queue.
14 """
15 self.stack.append(x)
16
17 def pop(self) -> int:
18 """
19 Removes the element from in front of queue and returns that element.
20 """
21 if self.helper_stack:
22 return self.helper_stack.pop()
23 elif not self.helper_stack and not self.stack:
24 return -1
25 elif not self.helper_stack and self.stack:
26 for i in range(len(self.stack)):
27 self.helper_stack.append(self.stack.pop())
28 return self.helper_stack.pop()
29
30
31 def peek(self) -> int:
32 """
33 Get the front element.
34 """
35 if self.helper_stack:
36 return self.helper_stack[-1]
37 elif not self.helper_stack and not self.stack:
38 return -1
39 elif not self.helper_stack and self.stack:
40 for i in range(len(self.stack)):
41 self.helper_stack.append(self.stack.pop())
42 return self.helper_stack[-1]
43
44
45 def empty(self) -> bool:
46 """
47 Returns whether the queue is empty.
48 """
49 if not self.helper_stack and not self.stack:
50 return True
51 else:
52 return False
53
54
55
56 # Your MyQueue object will be instantiated and called as such:
57 # obj = MyQueue()
58 # obj.push(x)
59 # param_2 = obj.pop()
60 # param_3 = obj.peek()
61 # param_4 = obj.empty()
化栈为队
1 # Definition for a binary tree node.
2 # class TreeNode:
3 # def __init__(self, val=0, left=None, right=None):
4 # self.val = val
5 # self.left = left
6 # self.right = right
7 class BSTIterator:
8
9 def __init__(self, root: TreeNode):
10 # 方法二：
11 self.stack = []
12 # 初始化的时候找到第一个next的位置，就是中序遍历的第一个节点
13 self.search_left(root)
14
15 def search_left(self, root):
16 while root:
17 self.stack.append(root)
18 root = root.left
19
20 def next(self) -> int:
21 # 方法二：
22 node = self.stack.pop()
23
24 # 步骤：将stack栈顶元素出栈，然后寻找中序遍历下一个元素进栈
25 if node.right:
26 self.search_left(node.right)
27 return node.val
28
29
30
31 def hasNext(self) -> bool:
32
33 # 方法二：
34 if self.stack:
35 return True
36 else:
37 return False
38
39 # class BSTIterator:
40 # def __init__(self, root: TreeNode):
41
42 # # 方法一：是最容易想到的方法
43 # self.stack = []
44
45 # def fun(root):
46 # if not root:
47 # return ;
48 # fun(root.left)
49 # self.stack.append(root.val)
50 # fun(root.right)
51 # fun(root)
52
53 # def next(self) -> int:
54 # # 方法一：
55 # return self.stack.pop(0)
56
57 # def hasNext(self) -> bool:
58 # # 方法一：
59 # if self.stack:
60 # return True
61 # else:
62 # return False
63
64 # Your BSTIterator object will be instantiated and called as such:
65 # obj = BSTIterator(root)
66 # param_1 = obj.next()
67 # param_2 = obj.hasNext()
二叉搜搜树迭代器
1 class Solution:
2 def searchInsert(self, nums: List[int], target: int) -> int:
3
4 # O(n)
5 # for i in range(len(nums)):
6 # if nums[i] >= target:
7 # return i
8
9 # return len(nums)
10
11 # O(logn)
12 left, right = 0, len(nums) - 1
13
14 if nums[left] > target:
15 return 0
16 if nums[right] < target:
17 return right + 1
18 while left <= right:
19
20 mid = int((right + left)>>1)
21 if right - left == 1:
22 if nums[left] == target:
23 return left
24 elif nums[right] == target:
25 return right
26 else:
27 return right
28 break
29
30 if nums[mid] < target:
31 left = mid
32 elif nums[mid] > target:
33 right = mid
34 elif nums[mid] == target:
35 return mid
搜索插入排序
1 # Definition for a binary tree node.
2 # class TreeNode:
3 # def __init__(self, x):
4 # self.val = x
5 # self.left = None
6 # self.right = None
7
8 class Solution:
9 def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
10
11 # 特殊情况
12 if not root:
13 return []
14 queue = []
15 queue.append(root)
16 p = 1
17 T = 1 # Turn 等于表示正插，-1表示反插
18
19 ans = []
20 while queue:
21 arr = []
22 m = 0
23
24 while p != 0:
25 x = queue.pop(0)
26 if T == 1:
27 arr.append(x.val)
28 else:
29 arr.insert(0, x.val)
30 p -= 1
31
32 if x.left:
33 queue.append(x.left)
34 m += 1
35 if x.right:
36 queue.append(x.right)
37 m += 1
38 p = m
39 T = -T
40
41 ans.append(arr)
42
43 # print(ans)
44 return ans
45
46
47
二叉树的锯齿形层序遍历
1 class MaxQueue:
2
3 def __init__(self):
4 self.queue = []
5 self.deque = deque([])
6
7 def max_value(self) -> int:
8 if not self.deque:
9 return -1
10 return self.deque[0]
11
12 def push_back(self, value: int) -> None:
13 self.queue.append(value)
14 if not deque:
15 self.deque.append(value)
16 else:
17 while self.deque:
18 if self.deque[-1] < value:
19 self.deque.pop()
20 else:
21 break
22 self.deque.append(value)
23
24
25 def pop_front(self) -> int:
26 if self.queue:
27 t = self.queue.pop(0)
28 if self.deque[0] == t:
29 self.deque.popleft()
30 return t
31 else:
32 return -1
33
34 # Your MaxQueue object will be instantiated and called as such:
35 # obj = MaxQueue()
36 # param_1 = obj.max_value()
37 # obj.push_back(value)
38 # param_3 = obj.pop_front()
队列的最大值（分摊原则）
205. 同构字符串（哈希表在Python中的数据结构实现：字典dict={}）
1 class Solution:
2 def isIsomorphic(self, s: str, t: str) -> bool:
3
4 map = {}
5 # 同构的定义：双射,如“ab”和“aa”,首先会建立a与a的映射，然后扫描到b和a时，虽然b没有出现，但是a已经出现了，这就不是双射了。
6 for i in range(len(s)):
7 if s[i] not in map.keys():
8 if t[i] not in map.values():
9 map[s[i]] = t[i]
10 else:
11 return False
12 else:
13 if map[s[i]] == t[i]:
14 pass
15 else:
16 return False
17
18 return True
同构字符串
1 # Definition for a binary tree node.
2 # class TreeNode:
3 # def __init__(self, val=0, left=None, right=None):
4 # self.val = val
5 # self.left = left
6 # self.right = right
7 class Solution:
8 def preorderTraversal(self, root: TreeNode) -> List[int]:
9
10 # 借助stack的迭代法，空间复杂读度为O（n）
11 if not root:
12 return []
13 stack = []
14 stack.append(root)
15
16 ans = []
17 while stack:
18 x = stack.pop()
19 ans.append(x.val)
20 if x.right:
21 stack.append(x.right)
22 if x.left:
23 stack.append(x.left)
24
25 return ans
26
27
二叉树的前序遍历
1 class Solution:
2 def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
3 # hashmap用来存储键值对,思考为什么要用hashmap？
4 hashmap = {}
5
6 stack = []
7 i = 0
8 while i <= len(nums2) - 1:
9 if not stack:
10 stack.append(nums2[i])
11 i += 1
12 else:
13 if stack[-1] < nums2[i]:
14 while stack and stack[-1] < nums2[i]: # 别忘了添加and前的stack，防止溢出
15 x = stack.pop()
16 hashmap[x] = nums2[i]
17 else:
18 stack.append(nums2[i])
19 i += 1
20
21 for i in range(len(stack)):
22 hashmap[stack.pop()] = -1
23
24 # print(hashmap)
25
26 ans = [hashmap[nums1[i]] for i in range(len(nums1))]
27 # print(ans)
28
29 return ans
30
下一个更大元素 I
1 class Solution:
2 def dailyTemperatures(self, T: List[int]) -> List[int]:
3
4 hashmap = {}
5
6 stack = []
7 i = 0
8 while i <= len(T)-1:
9 if not stack:
10 stack.append(i)
11 i += 1
12 else:
13 if T[stack[-1]] >= T[i]:
14 stack.append(i)
15 i += 1
16 else:
17 while stack and T[stack[-1]] < T[i]:
18 hashmap[stack.pop()] = i - stack[-1]
19
20 # 最后 可能栈中还有元素
21 for i in range(len(stack)):
22 hashmap[stack.pop()] = 0
23 # print(hashmap)
24 ans = [hashmap[i] for i in range(len(T))]
25
26 return ans
每日温度
1 class Solution:
2 def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
3
4 # ans = 0
5 # i = 0
6 # 解法1：前后种花，1、0、【】、0、1
7 # flowerbed.insert(0,1)
8 # flowerbed.insert(1,0)
9 # flowerbed.append(0)
10 # flowerbed.append(1)
11 # while i <= len(flowerbed)-1:
12 # p = 0
13 # if flowerbed[i] == 0:
14 # i += 1
15 # p += 1
16 # while not flowerbed[i] and i <= len(flowerbed) -1:
17 # i += 1
18 # p += 1
19 # ans += math.ceil(max((p-2), 0) / 2)
20 # else:
21 # i += 1
22
23 # # print(ans)
24 # return True if ans>= n else False
25
26 # 解法2：贪心,能种就种
27 N = 0
28 L = len(flowerbed)
29 if not flowerbed:
30 return True
31 # 特殊情况处理
32 if L<2:
33 if flowerbed\[0\] == 0 or flowerbed\[L-1\] == 0:
34 N += 1
35 else:
36 # 头部
37 if not flowerbed\[0\] and not flowerbed\[1\]: # 第一个位置与第二个位置均为0
38 N += 1
39 flowerbed\[0\] = 1
40 # 尾部
41 if not flowerbed\[L-1\] and not flowerbed\[L-2\]: # 倒数第一个位置和倒数第二个位置均为0
42 N += 1
43 flowerbed\[L-1\] = 1
44
45 for i in range(1,L-1):
46 if flowerbed\[i\] == 0:
47 if flowerbed\[i-1\] == 0 and flowerbed\[i+1\] == 0:
48 N += 1
49 flowerbed\[i\] = 1
50
51 # print(N,flowerbed)
52 return True if N>=n else False
53
种花问题
chapter3 Resolution：动态规划
1 class Solution:
2 def minCostClimbingStairs(self, cost: List[int]) -> int:
3
4 dp = [0] * len(cost)
5
6 L = len(cost)
7 if L == 1:
8 return 0
9 elif L == 2:
10 return min(cost[0], cost[1])
11
12 dp[0] = cost[0]
13 dp[1] = cost[1]
14
15 for i in range(2,L):
16 dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
17
18 return min(dp[-1], dp[-2])
使用最小花费爬楼梯
1 class Solution:
2 def uniquePaths(self, m: int, n: int) -> int:
3 # dfs 会 running out of time
4 # path = 0
5
6 # def backtrace(row, col):
7 # nonlocal path
8 # if row > m or col > n:
9 # return ;
10 # if row == m and col == n:
11 # path += 1
12 # return ;
13 # backtrace(row+1, col)
14 # backtrace(row, col+1)
15
16 # backtrace(1,1)
17 # return path
18
19 # 数论的方法
20 # down = 1 # 分母
21 # up = 1 # 分子
22 # A = m+n-2
23
24 # for i in range(m-1):
25 # down *= A
26 # A -= 1
27
28 # for i in range(1,(m-1)+1):
29 # up *= i
30
31 # return int(down/up)
32
33 # 动态规划方法
34 # dp[i][j] 到达第i行和第j列的方案数量，有多少种走法
35 dp = [[1] * m] * n
36
37 # 初始化，dp[:][0] = 0 and dp[0][:] = 1
38
39 for i in range(1,n):
40 for j in range(1,m):
41 dp[i][j] = dp[i][j-1] + dp[i-1][j]
42
43 # print(dp)
44 return dp[n-1][m-1]
不同路径
63. 不同路径 II （这个题目看出 “动态规划”五部曲当中 初始化的重要性，Success depends on details）
1 class Solution:
2 def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
3 n = len(obstacleGrid)
4 m = len(obstacleGrid[0])
5
6 # import numpy as np
7 # dp = np.array([[0] * m] * n).tolist() # 不要将m和n的位置写反了，这种是正确的
8 # dp = [[0 for _ in range(m)] for _ in range(n)]
9 dp = []
10 for i in range(n):
11 t = []
12 for j in range(m):
13 t.append(0)
14 dp.append(t)
15
16 # dp = list([[0] * m] * n) # 这种不知道哪里错了?调试出来的结果感觉就是神奇的错误，试试测试用例[[0],[1]]
17 # dp = [[0] * m] * n # 同上
18 # print("dp", dp)
19
20 # 初始化
21 # 第一行是否有障碍
22 for i in range(m):
23 if obstacleGrid[0][i] == 0:
24 # 从i到最后都需要初始化为0
25 dp[0][i] = 1
26 else:
27 break
28
29 # 第一列是否有障碍
30 for i in range(n):
31 if obstacleGrid[i][0] == 0:
32 # 从j到最后都需要初始化为0
33 dp[i][0] = 1
34 else:
35 break
36 # print(dp)
37 for i in range(1, n):
38 for j in range(1, m):
39 if obstacleGrid[i][j] == 1:
40 dp[i][j] = 0
41 else:
42 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
43
44 # print(dp)
45
46 return dp[n - 1][m - 1]
不同路径 II
1 class Solution:
2 def integerBreak(self, n: int) -> int:
3 # dp[i] 表示拆分
4 dp = [0 for _ in range(n+1)]
5
6 # print(dp)
7 # 初始化特殊情况，考虑下文中的dp[2] = 1 和 dp[3] = 2两种情况
8 if n == 2:
9 return 1
10 elif n == 3:
11 return 2
12 # 0和1拆分不符合题目的要求，可以不对其进行初始化，dp[0] dp[1]
13 dp[2] = 1
14 dp[3] = 2
15
16 for i in range(4,n+1): # 一直到持续到求出dp[n]
17 for j in range(1,(i-2) + 1):
18 dp[i] = max(dp[i], max(j * (i-j),j * dp[i-j])) # 其实此处蕴含有求循环求最大值的意思
19
20 # print(dp)
21
22 return dp[n]
整数拆分
1 class Solution:
2 def canPartition(self, nums: List[int]) -> bool:
3
4 # # 经动态规划转化后的题目
5 # m = len(nums)
6 # n = ceil(sum(nums) / 2)
7 # N = sum(nums) / 2
8 # if N != n:
9 # return False
10 # # print(m,n)
11
12 # dp = [[0 for _ in range(n+1)] for _ in range(m+1)] # 再一次倒在了n和mn弄混了
13 # # print(dp)
14
15 # for i in range(1,m+1):
16 # for j in range(1,n+1):
17 # if j < nums[i-1]:
18 # dp[i][j] = dp[i-1][j]
19 # else:
20 # A = dp[i-1][j]
21 # B = nums[i-1] + dp[i-1][j-nums[i-1]]
22 # dp[i][j] = max(A, B)
23
24 # # print(dp)
25 # if dp[i][j] == N:
26 # return True
27 # else:
28 # return False
29
30 # # 解法二：动态规划之滚动数组
31 if len(nums) == 0 or len(nums) == 1:
32 return False
33
34 m = len(nums)
35 n = int(sum(nums) / 2)
36
37 # print(n, N)
38 if int(sum(nums)) % 2 == 1:
39 return False
40 # print(m,n)
41
42 dp = [0 for _ in range(n+1)]
43 # print(dp)
44
45 for i in range(1,m+1):
46 for j in range(n,nums[i-1]-1,-1): # 细节range(4,0,-1)是[4,3,2,1],不包括0
47 A = dp[j]
48 B = nums[i-1] + dp[j-nums[i-1]]
49 # print(A, B)
50 dp[j] = max(A, B)
51 # print(dp)
52
53 if dp[n] == n:
54 return True
55 return False
分割等和子集
1 class Solution:
2 def lastStoneWeightII(self, stones: List[int]) -> int:
3
4 m = len(stones)
5 sum_weight = int(sum(stones))
6
7 half_weight = int(sum_weight / 2)
8
9 dp = [0] * (half_weight+1)
10 # print(half_weight)
11
12 for i in range(m):
13 for j in range(half_weight, stones[i]-1, -1):
14 dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
15 # print(dp)
16
17 # print(dp)
18 return abs((sum_weight - dp[-1]) - dp[-1])
最后一块石头的重量 II
1 class Solution:
2 def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
3
4 # 动态规划问题
5 # dp[i][j] 最多包含i个0，j个1的最大子集的长度为dp[i][j]
6
7 # dp[i][j] = max(dp[i][j], dp[i-zeroNum][j-oneNum] + 1)
8
9 dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
10 # print("start",dp)
11
12 L = len(strs)
13 for i in range(L):
14
15 # 统计0的个数和1的个数
16 zero_num, one_num = 0, 0
17 for idx in range(len(strs[i])):
18 if strs[i][idx] == "0":
19 zero_num += 1
20 else:
21 one_num += 1
22 # print("len",zero_num, one_num)
23
24 for j in range(m, zero_num-1, -1):
25 for k in range(n, one_num-1, -1):
26 dp[j][k] = max(dp[j][k], dp[j-zero_num][k-one_num]+1)
27 # print("dp", dp)
28
29 return dp[m][n]
一和零
322. 零钱兑换 ，因为dp表示的是方案数，而与顺序无关，因此两种遍历顺序都是正确的：（1.先遍历nums再遍历target；2.先遍历target再遍历nums）
1 class Solution:
2 def coinChange(self, coins: List[int], amount: int) -> int:
3
4 # 目标：达到target的目标的硬币最少
5
6 # dp[j]表示凑成了j的硬币最少数
7 # nums = coins, target = amount
8 # dp[j] = min(dp[j],dp[j-nums[i]]+1)
9
10 dp = [10000000] * (amount+1)
11 dp[0] = 0
12 print(dp)
13
14 for i in range(len(coins)):
15 for j in range(coins[i],amount+1):
16 dp[j] = min(dp[j],dp[j-coins[i]]+1)
17
18 # print(dp)
19
20 # print("最终答案是：",dp)
21 if dp[amount] == 10000000:
22 return -1
23 return dp[amount]
零钱兑换
1 class Solution:
2 def numSquares(self, n: int) -> int:
3
4 # dp[j]表示和为j的最少数量
5
6 # dp[j] = min(dp[j],dp[j-i*i]+1)
7
8 dp = [1000000] * (n+1)
9 dp[0] = 0
10 # print("init", dp)
11
12 # 完全背包，每个背包可以重复使用
13 max_nums2 = int(sqrt(n))
14 # print(max_nums2)
15
16 for i in range(1,max_nums2+1):
17 for j in range(i*i,n+1):
18 dp[j] = min(dp[j],dp[j-i*i]+1)
19
20 # print(dp)
21
22 # if dp[n] == 1000000:
23 # return 0
24 return dp[n]
完全平均数
1 class Solution:
2 def wordBreak(self, s: str, wordDict: List[str]) -> bool:
3
4 # 动态规划：完全背包问题，每件物品可以重复使用
5 # dp[j] 表示前j个字符都可以拆分成功
6
7 s_len = len(s)
8 wordDict_len = len(wordDict)
9 dp = [0] * (s_len + 1)
10 dp[0] = 1
11
12 for i in range(s_len+1):
13 for j in range(wordDict_len):
14 L = len(wordDict[j]) # 先知道字符串的长度
15 # print(L)
16 if i >= L:
17 substr = s[i-L:i] # 然后在s中取出L长度的字符串，看是否相等
18 if substr == wordDict[j] and dp[i-L] == 1:
19 dp[i] = 1
20 break
21 if dp[s_len] == 1:
22 return True
23 return False
24
单词拆分
2021年后
1 class Solution:
2 def rob(self, nums: List[int]) -> int:
3
4 # # dp[i]表示包括num[i]（表示nums[i]必须偷）的能够得到的最大金额，
5 # # 因此最终的最大金额是max(dp)
6 # if not nums:
7 # return 0
8 # dp = [0] * len(nums)
9 # # M = nums[0]
10 # for i in range(len(nums)):
11 # if i - 2 >= 0:
12 # M = max(dp[:i-1])
13 # else:
14 # M = 0
15 # dp[i] = M + nums[i]
16
17 # # print(dp)
18 # return max(dp)
19
20 # 方法二：dp[i]表示考虑到前i个（包括i）能够达到的最大金额
21 # dp[i] = max(dp[i-1],dp[i-2] + nums[i])
22 if len(nums) == 0:
23 return 0
24 if len(nums) == 1:
25 return nums[0]
26
27 dp = [0] * len(nums)
28 dp[0] = nums[0]
29 dp[1] = max(nums[0], nums[1])
30
31 for i in range(2,len(nums)):
32 dp[i] = max(dp[i-1],dp[i-2]+nums[i])
33
34 # print(dp)
35 return dp[len(nums)-1]
打家劫舍
1 class Solution:
2 def maxProfit(self, prices: List[int]) -> int:
3
4 # dp[i][0] 第i天(i从0开始，第0天，第1天…第i-1天，i属于【0,n-1】)若持有股票的所得最大现金
5 # dp[i][1] 第i天若不持有股票的所得最大现金
6 # dp[i][0] 由以上两种情况得出：1.昨天就已经持有股票的所得最大金额；2.当天（第i天）买了股票，所以当天的现金是-prices[i]
7 # dp[i][0] = max(dp[i-1][0], -prices[i])
8 # dp[i][1] 由以上两种情况得出：1.昨天就不持有股票的所得最大金额；2.i-1天持有股票的最大金额加上prices[i]
9 # dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
10
11 # 因此初始化
12 # 当i = 1时,dp[1][0] = max(dp[0][0], -prices[0])
13 # 当i = 1时,dp[1][1] = max(dp[0][1], dp[0][0]+prices[0])
14 # 因此初始化dp[0][0],dp[0][1]
15
16
17 # dp[][]看起来是二维数组，但是实际上表示的是一维数组，因为第二位已经用两个dp数组表示了
18 dp_holdStamp = [0] * len(prices)
19 dp_not_holdStamp = [0] * len(prices)
20
21 dp_holdStamp[0] = -prices[0]
22 dp_not_holdStamp[0] = 0
23
24 for i in range(1,len(prices)):
25 dp_holdStamp[i] = max(dp_holdStamp[i-1], -prices[i])
26 dp_not_holdStamp[i] = max(dp_not_holdStamp[i-1], dp_holdStamp[i-1]+prices[i])
27
28 # print(dp_holdStamp)
29 # print(dp_not_holdStamp)
30 return dp_not_holdStamp[len(prices)-1]
31
32 # 还可以继续优化，优化为滚动数组，向0-1背包那样
买卖股票的最佳时机
1 class Solution:
2 def maxProfit(self, prices: List[int]) -> int:
3
4 # dp[i][0] 第i天(i从0开始，第0天，第1天…第i-1天，i属于【0,n-1】)若持有股票的所得最大现金
5 # dp[i][1] 第i天若不持有股票的所得最大现金
6 # dp[i][0] 由以上两种情况得出：1.昨天就已经持有股票的所得最大金额；2.当天（第i天）买了股票，所以当天的现金是-prices[i]
7 # dp[i][0] = max(dp[i-1][0], -prices[i])
8 # dp[i][1] 由以上两种情况得出：1.昨天就不持有股票的所得最大金额；2.i-1天持有股票的最大金额加上prices[i]
9 # dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
10
11 # 因此初始化
12 # 当i = 1时,dp[1][0] = max(dp[0][0], -prices[0])
13 # 当i = 1时,dp[1][1] = max(dp[0][1], dp[0][0]+prices[0])
14 # 因此初始化dp[0][0],dp[0][1]
15
16
17 # dp[][]看起来是二维数组，但是实际上表示的是一维数组，因为第二位已经用两个dp数组表示了
18 dp_holdStamp = [0] * len(prices)
19 dp_not_holdStamp = [0] * len(prices)
20
21 dp_holdStamp[0] = -prices[0]
22 dp_not_holdStamp[0] = 0
23
24 for i in range(1,len(prices)):
25 dp_holdStamp[i] = max(dp_holdStamp[i-1], -prices[i])
26 dp_not_holdStamp[i] = max(dp_not_holdStamp[i-1], dp_holdStamp[i-1]+prices[i])
27
28 # print(dp_holdStamp)
29 # print(dp_not_holdStamp)
30 return dp_not_holdStamp[len(prices)-1]
31
32 # 还可以继续优化，优化为滚动数组，向0-1背包那样
买卖股票的最佳时机
chapter4 Resolution：回溯
1 class Solution:
2 def partition(self, s: str) -> List[List[str]]:
3
4 s_len = len(s)
5
6 path = []
7
8 def backtrace(s, s_len, startIndex, tmp_path):
9 if startIndex == s_len:
10 # print(tmp_path[:])
11 path.append(tmp_path[:])
12 return ;
13
14 for i in range(startIndex + 1, s_len + 1):
15 substr = s[startIndex: i] # 检查所切割的子串是否是回文串
16 # print("AAA", i, substr)
17 if not check(substr): continue; # 一开始continue处写成了break，找了我四五个小时的错误！
18 tmp_path.append(substr)
19 backtrace(s, s_len, i, tmp_path)
20 tmp_path.pop()
21
22
23 def check(s):
24 # 首先求出s的长度L
25 L = len(s)
26
27 left_p, right_p = 0, L - 1
28 while left_p <= right_p:
29 if s[left_p] == s[right_p]:
30 left_p += 1
31 right_p -= 1
32 else:
33 return False
34
35 return True
36
37 backtrace(s, s_len, 0, [])
38
39 # print("ans", path)
40 return path
分割字符串
chapter5 Resolution：贪心
1 class Solution:
2 def findContentChildren(self, g: List[int], s: List[int]) -> int:
3
4 g_sort = sorted(g)
5 s_sort = sorted(s)
6 # print("sort", g_sort, s_sort)
7
8 # 两个指针
9 pg = len(g_sort) - 1
10 ps = len(s_sort) - 1
11 # print("p", pg, ps)
12
13 num_ok = 0
14 while pg >=0 and ps >= 0:
15 if g_sort[pg] <= s_sort[ps]:
16 pg -= 1
17 ps -= 1
18 num_ok += 1
19 else:
20 pg -= 1
21
22 return num_ok
23
24
分发饼干
45. 跳跃游戏 II
1 class Solution:
2 def jump(self, nums: List[int]) -> int:
3
4 MAX = 1000000
5 dp = [MAX] * len(nums)
6
7 dp[0] = 0
8
9 for i in range(len(nums)):
10 if i + nums[i] >= len(nums)-1: # 如果i + nums[i] 超过了nums的长度
11 mi = len(nums)-1
12 else:
13 mi = i + nums[i]
14
15 for j in range(i+1,mi+1): # i 给 后面的nums[i]可以进行松弛
16 dp[j] = min(dp[j], dp[i] + 1)
17
18
19 # print(dp[len(nums)-1])
20 return dp[len(nums)-1]
跳跃游戏 2
chapterX Resolution：哈希表
chapterX Resolution：拓扑排序
207. 课程表 （拓扑排序的典范（模板））
1 class Solution:
2 def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
3
4 # 首先统计n门课程的入度为多少
5 in_degree = [0] * numCourses
6 for i in range(len(prerequisites)):
7 x = prerequisites[i][0]
8 in_degree[x] += 1
9 # print(in_degree)
10
11 # 初始化：将入度为0的课程入栈
12 stack = []
13 for i in range(numCourses):
14 if in_degree[i] == 0:
15 stack.append(i)
16 # print(stack)
17
18 # 要是初始化之后发现没有入度为0的课程，则直接返回False
19 if not stack:
20 return False
21
22 # 拓扑排序的core code
23 while stack:
24 x = stack.pop()
25 for i in range(len(prerequisites)):
26 if prerequisites[i][1] == x:
27 in_degree[prerequisites[i][0]] -= 1
28
29 if in_degree[prerequisites[i][0]] == 0:
30 stack.append(prerequisites[i][0])
31 # print(stack)
32
33 # 经过core code之后，如果入度表还存在非0值（表示还存在入度不为0的课程），说明已经形成环，返回False
34 for i in range(len(in_degree)):
35 if in_degree[i] != 0:
36 return False
37
38 return True
39 # 最后，1.效率比较低，需要改进
40 # 2.拓扑排序的代码一般可以作为模板使用
41
课程表
课程表 II
chapterX Resolution：双指针
1 class Solution:
2 def largeGroupPositions(self, s: str) -> List[List[int]]:
3 i = 0
4 start = 0
5 end = 0
6 ans = []
7 # 看起来两层while循环，实际上只对数组遍历了一次
8 while i <= len(s)-1:
9 start = i
10 end = start
11 while i+1 <= len(s)-1 and s[i] == s[i+1]:
12 end += 1
13 i += 1
14 if end - start >= 2:
15 ans.append([start,end])
16 i = end+1 # 别忘了这个重要的语句
17
18 return ans
较大分组的位置
1 class Solution:
2 def isSubsequence(self, s: str, t: str) -> bool:
3
4 if len(s) == 0 and len(t) == 0:
5 return True
6 sp = 0
7 tp = 0
8
9 tp_flag = 0 # tp_flag指示是否遍历完t，若是则赋值为1，结束两层while循环
10 while sp <= len(s) - 1:
11 flag = 0 # flag表示当前字符是否匹配，加他的原因，“a”，“x”这样的测试集
12 while True:
13 if tp > len(t) - 1:
14 tp_flag = 1
15 break
16 if s[sp] == t[tp]:
17 flag = 1
18 break
19 else:
20 tp += 1
21 if flag:
22 tp += 1
23 sp += 1
24 if tp_flag:
25 break
26
27 if sp == len(s):
28 return True
29 else:
30 return False
31 # print(sp)
判断子序列
1 class Solution:
2 def twoSum(self, nums: List[int], target: int) -> List[int]:
3 hashtable = dict()
4 for index,value in enumerate(nums):
5 if target - value in hashtable:
6 return [hashtable[target-value],index]
7 hashtable[value] = index # 这句话不能放在上一个IF前，因为可能出现刚放进去一个3（target=6），就会立马与6-3=3（与自己的3匹配了）匹配
8 #print(hashtable)
9
10 return []
11
12 #判断某个数在不在字典里，复杂度是O(1)
13
14 #本算法用hash这样加快了寻找target-value的速度，这样时间复杂度就下降到n
15 #空间复杂度上升到n
两数之和
手机扫一扫
移动阅读更方便
你可能感兴趣的文章