add new answers

lixiang.2533 · lixiang.2533 · commit e1d94bad031e · 2022-02-20T11:20:17.000+08:00
Change-Id: Idf4b89eb4446642cdc7345b914b690aad97c73a2
diff --git a/二分法/278. 第一个错误的版本.md b/二分法/278. 第一个错误的版本.md
@@ -57,4 +57,4 @@ class Solution:
 
 Tips
 
-依旧是二分法，强迫症执着的
+依旧是二分法，强迫症执着的使用左右闭区间，这个时候想要知道最后返回的是左还是右区间只要模拟一下推出的挺狂求可以
diff --git a/值得二刷.md b/值得二刷.md
@@ -0,0 +1,19 @@
+- 回溯
+  - 491
+  - 39
+- 二分
+  - 81
+  - 153
+- 链表
+  - 82
+  - 61
+  - 206
+- 栈
+  - 239
+  - 215/剑指offer40
+- 双指针
+- 贪心
+- 数组
+- 哈希表
+- 树
+- 动态规划
diff --git a/双指针/0.双指针总结.md b/双指针/0.双指针总结.md
@@ -34,6 +34,7 @@
   - [ ] 88 合并两个有序数组
   - [ ] 844 比较含退格的字符串
   - [ ] 977 有序数组的平方
+  - [ ] 
   
 - 技巧
   - [ ] 28 实现 strStr() ：KMP算法
diff --git a/双指针/264.丑数II.md b/双指针/264.丑数II.md
@@ -0,0 +1,59 @@
+给你一个整数 n ，请你找出并返回第 n 个 丑数 。
+
+ 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
+
+
+
+ 示例 1：
+
+
+输入：n = 10
+输出：12
+解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
+
+
+ 示例 2：
+
+
+输入：n = 1
+输出：1
+解释：1 通常被视为丑数。
+
+
+
+
+ 提示：
+
+
+ 1 <= n <= 1690
+
+```python
+class Solution:
+    def nthUglyNumber(self, n: int) -> int:
+        ans = [0] * (n+1)
+        ans[1] = 1
+        idx1, idx2,idx3 = 1,1,1
+        idx = 2
+        while idx<=n:
+            a,b,c = ans[idx1] * 2, ans[idx2]*3, ans[idx3]*5
+            m = min(a,b,c)
+            if m==a:
+                idx1+=1
+            if m==b:
+                idx2+=1
+            if m==c:
+                idx3+=1
+            ans[idx]=m
+            idx+=1
+        print(ans)
+        return ans[n]
+```
+
+
+
+
+
+Tips
+
+1. 归并排序问题，这里放在双指针了，因为需要三个指针分别指向丑数*2， 丑数*3，丑数*5下一个最小的位置，合并是每次选择最小的并移动指针
+2. 需要注意的是因为同一个丑数可能来源于不同的指针，例如6，同时是丑数2的倍数，也是丑数3的倍数，所以指针移动时是不是互斥的
diff --git a/回溯/0.回溯算法总结.md b/回溯/0.回溯算法总结.md
@@ -1,32 +1,45 @@
 回溯是一种搜索方式，主要用来寻找所有解的可能，回溯都依赖递归实现，属于递归的一个方向。一般抽象为多叉树的深度搜索问题，候选集的大小是树的宽度，target是树的深度。空间复杂度一般是深度搜索的深度。时间复杂度不定，不过回溯并不高效
 - 求所有组合：有重复数组，无重复数组（可/不可重复取）
-  - 17 电话号码的字母组合：无重复，一次使用
-  - 39 组合总和：无重复，反复使用，sort剪枝
-  - 40 组合总和 II：有重复，sort，判断去重
-  - 77 组合：无重复，一次使用
-  - 216 组合总和 III：求和为n，注意遍历右边界要包括n
-  - 22 括号生成：left+right counter判断是否生成右括号
+  - [ ] 17 电话号码的字母组合：无重复，一次使用
+  - [ ] 22 括号生成：left+right counter判断是否生成右括号
+  - [ ] 39 组合总和：无重复，反复使用，sort剪枝
+  - [ ] 40 组合总和 II：有重复，sort，判断去重
+  - [ ] 77 组合：无重复，一次使用
+  - [ ] 216 组合总和 III：求和为n，注意遍历右边界要包括n
+  - [ ] 784 字母大小写全排列：特殊递归条件
+  
   - 空间复杂度O(n)：递归的深度
-  - 时间复杂度O(2^n*n): 虽然题目各不相同，基本不存在重复遍历所以是组合数量
+  
+  - 时间复杂度O(2^n*n): 虽然题目各不相同，基本不存在重复遍历所以是组合数量 * 组合长度，是一个宽松上街
+  
 - 求所有排列：数组有/无重复
-  - 46 全排列: 无重复，递归包含自己
-  - 47 全排列 II：有重复，sort，判断去重
+  - [ ] 46 全排列: 无重复，递归包含自己
+  - [ ] 47 全排列 II：有重复，sort，判断去重
+  
   - 空间复杂度O(n)：递归的深度
-  - 时间复杂度O(n!)：排列的数量
+  - 时间复杂度O(n!)：排列的数量 
+  
 - 分割问题：把字符串/数组按要求分割
-  - 131 分割回文串：在组合的基础上，加一步是否回文的判断
-  - 93 复原 IP 地址：在组合的基础上，加一步是否满足IP的判断
+  - [ ] 131 分割回文串：在组合的基础上，加一步是否回文的判断
+  - [ ] 93 复原 IP 地址：在组合的基础上，加一步是否满足IP的判断
+  
   - 空间复杂度O(n)
-  - 时间复杂度
+  - 时间复杂度O(2^n*n)
+  
 - 求子集
-  - 78 子集：无重复，在组合的基础上，每一步都append result
-  - 90 子集 II：有重复，同上
+  - [ ] 78 子集：无重复，在组合的基础上，每一步都append result
+  - [ ] 90 子集 II：有重复，同上
+  
   - 空间复杂度O(n)：和组合相同
   - 时间复杂度O(2^n*n): 和组合相同
+  
 - 求子序列
-  - 491 递增子序列：注意是按原顺序递增，因为不能sort，所以只能通过set来判断解是否重复
+  - [ ] 491 递增子序列：注意是按原顺序递增，因为不能sort，所以只能通过set来判断解是否重复
+  - [ ] 784 字母大小写全排列：只需要区分字母/非字母进行递归
+  
   - 空间复杂度O(n)
-  - 时间复杂度
+  - 时间复杂度O(2^n*n)
+  
 - 回溯问题模版
   - 停止条件
   - 递归方式
diff --git a/回溯/784.字母大小写全排列.md b/回溯/784.字母大小写全排列.md
@@ -0,0 +1,42 @@
+给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
+
+
+
+ 示例：
+输入：S = "a1b2"
+输出：["a1b2", "a1B2", "A1b2", "A1B2"]
+
+输入：S = "3z4"
+输出：["3z4", "3Z4"]
+
+输入：S = "12345"
+输出：["12345"]
+
+
+
+
+ 提示：
+
+
+ S 的长度不超过12。
+ S 仅由数字和字母组成。
+
+
+
+```python
+class Solution:
+    def letterCasePermutation(self, s: str) -> List[str]:
+        result = []
+        def dfs(s, path):
+            if not s:
+                result.append(path)
+                return
+            if s[0].isalpha():
+                dfs(s[1:], path+s[0].lower())
+                dfs(s[1:], path + s[0].upper())
+            else:
+                dfs(s[1:], path+s[0])
+        dfs(s, '')
+        return result
+```
+
diff --git a/栈/0.栈总结.md b/栈/0.栈总结.md
@@ -29,10 +29,11 @@
 
   - [ ] 42 接雨水：单调栈，需要左中右三个元素来计算雨水
   - [ ] 239 滑动窗口最大值：滑动窗口+单调队列
+  - [ ] 264 丑数II：优先队列
   - [ ] 316 去除重复字母：单调栈+贪心，对越高的位置优先保留更大/更小
   - [ ] 402 移掉K位数字：单调栈+贪心，对越高的位置优先保留更大/更小
   - [ ] 496 下一个更大元素 I：单调栈，哈希存储
   - [ ] 503 下一个更大元素 II：单调栈， 数组存储（数组有重复），循环用遍历2*len的方式实现
   - [ ] 1438 绝对差不超过限制的最长连续子数组: 滑动窗口+最大最小两个单调队列
-
+  
   
diff --git a/链表/82. 删除排序链表中的重复元素 II.md b/链表/82. 删除排序链表中的重复元素 II.md
@@ -49,5 +49,4 @@ class Solution:
 Tips
 
 1. 永远机制链表不能对当前节点进行修改，只能修改next
-2. 这里因为要判断连续两个元素是否重复，所以要保留两个指针位置node.next和node.next.next 
-3. 且当发现存在重复元素师不要移动指针位置，只是继续向前判断知道发现不重复的元素，改变link，然后继续判断。只有当确认玄素不重复的时候才移动指针位置
+3. 注意只有当不重复的时候才会移动指针位置
diff --git a/链表/83. 删除排序链表中的重复元素.md b/链表/83. 删除排序链表中的重复元素.md
@@ -49,4 +49,4 @@ class Solution:
 Tips
 
 1. 链表注意事项永远记得保留head
-2. 每一步都是调整当前节点的link，所以head=head.next一定要放在后面做不然pointer就已经离开当前节点了
+2. 注意只有当不重复的时候才会移动指针位置

Original file line number	Diff line number	Diff line change
`@@ -57,4 +57,4 @@ class Solution:`
`57`	`57`
`58`	`58`	`Tips`
`59`	`59`
`60`		`-依旧是二分法，强迫症执着的`
	`60`	`+依旧是二分法，强迫症执着的使用左右闭区间，这个时候想要知道最后返回的是左还是右区间只要模拟一下推出的挺狂求可以`