week1

2020.3.8 - 2020.3.15

26

27

41

55

dp, dp[i] = max(dp[i-1],nums[i-1])-1 表示最远能到达的地方
return dp.back()<=0 (可以随时返回false节省时间）

80

118

119

134

169

189

283

299

442

448

week2:

2020.3.15 - 2020.3.21

11

35

56

先排序，再遍历的同时合并

57

由于intervals 是有序的，遍历即可， O(N)

75

88

153

162

164

217

278

289：

涉及到位置间的相互影响，使用余数记录变化，同时保留原本信息
in-place
使用2代表0->1
使用3代表1->0

327 hard

1.区间和的问题要计算累计数组和sums[i]
2.使用multiset: lower_bound, upper_bound set允许重复的元素
multiset.insert(XXX)
3.STL distance(iterator1, iterator2)
4.关注数字的范围，求和可能超范围。

对于某个i来说，只有那些满足 lower <= sum[i] - sum[j] <= upper 的j能形成一个区间 [j, i] 满足题意，目标就是来找到有多少个这样的 j (0 =< j < i) 满足 sum[i] - upper =< sum[j] <= sum[i] - lower

image.png

376

week 3:

2020.3.22 - 2020.3.29

42

智力趣味题,更多解法参考：https://www.cnblogs.com/logosg/p/7979690.html
双指针法： 比较 左 右指针的高度大小，若左边大，则右边只需要关注右侧能否蓄水（因为左侧一定可以支撑住）；反之亦然

设l_max 是 height[0..left] 中最高柱子的高度，r_max 是 height[right..end] 的最高柱子的高度。

单调栈法：https://www.cnblogs.com/grandyang/p/8887985.html

• 单调递增栈可以找到左起第一个比当前数字小的元素
• 单调递减栈可以找到左起第一个比当前数字大的元素

使用递减单调栈，因为当有更小的数来，直接入栈；有更大的数来，说明可以处理存水的体积了。
计算水的体积会把空隙进行横向分层。

stack存的是index而不是高度。

每一次的处理：
每次取top，pop，然后如果左面没有top，说明只有一边，无法蓄水，break。
如果昨天top高度和当前高度相同，则continue
计算高度，width（两边柱子距离-1）和height（木桶短板-底部），加到结果里去。

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.empty()) return 0;
        height.push_back(0);
        int res =0;
        stack<int> st;//decreasing stack
        for(int i = 0; i<height.size();++i){
            while(!st.empty() && height[i] > height[st.top()]){
                int top  =st.top();
                st.pop();
                if(st.empty()) break;
                if(height[top] ==height[st.top()]) continue;
                int width = i-st.top()-1;
                int h = min(height[st.top()],height[i]);
                res += width*(h-height[top]);
            }
            st.push(i);
        }
        return res;
    }
};

81

反复调试的解法: 可退化，4ms
若left,right值相等，则遍历（退化为O（n））
若【left】<【right】，则正序，正常二分查找 mid=(left+right+1/2
若【left】》【right】，则为逆序，若【target】>=【left】则在左半边，否则右半边
踩过的坑：

• 谨防陷入死循环，设定一个若mid和上次相同，直接判断
• 原本写了在正序时if(target<nums[left]) return false; 后来发现不必要，不过稍多花一些内存

待学习：不退化，1ms

public class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (target == nums[mid]) return true;
            if (nums[mid] == nums[left]) left++;
            else if (nums[mid] > nums[left]) {
                if (nums[left] <= target && nums[mid] > target) right = mid - 1;
                else left = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
        }
        return false;
    }
}

128

• 要求O(n)时，可以想使用哈希表

152

容易想到动态规划，但是负数和0的存在比较麻烦，如[5,-2,-3];
可以设计两个数组，dp_max = max{nums[i], nums[i]dp_max[i-1], nums[i]dp_min[i-1]}, dp_min = min{nums[i], nums[i]dp_max[i-1], nums[i]dp_min[i-1]}。
返回dp_max中的最大值。

209

失败尝试：看到O(nlogn)想到二分查找，可以通过一部分用例但会卡在一部分上。使用sum数组，假设，j遍历，i使用二分查找到sum[j]-sum[i]>=s 的最小的j-i
注意：特殊输入的测试用例
博客学习：双指针，right遍历，left向右滑，但未理解如何计算为O(n)的复杂度
未解决：学会O(nlogn)的算法

228

遍历一次即可，注意处理末尾的情况。

238

使用两个数组。每一位等于前面数的乘积乘后面数的乘积
优化: 不构造额外的左乘积数组和右乘积数组，直接存到res中

239

学习:使用双向队列，当列中的back比当前值小，全部pop；若列中的back比当前值大，push 当前值。 同时，超出滑窗范围的也需要从front中去掉。
待解决：其他方法

deque:
最好采用deque的情形：
1、需要在两端插入和删除元素。
2、无需引用容器内的元素。
3、要求容器释放不再使用的元素。

image.png

image.png

image.png

287

博客学习:双指针方法，由于数字的范围都在1-n之间，因此可以递归自身。 链长为c, 环长l, 则快慢指针第一次相遇时分别走了l',2l'步，l'为第一个大于c的l的倍数。
快慢指针相遇后，慢指针向前走c步，新指针从0同步c步，必将在环的入口处相遇。
未解决：使用位操作

300

1. O(n2)：容易想到dp方法，dp[i]为结尾为nums[i]的最长递增串， dp[i] = max(dp[i],dp[j]+1) j<i
2. O(nlogn): 借助lower_bound(v.begin(),v.end(),a) 简化程序。得到的数组不一定是LIS的数组。 构建数组v，遍历nums，若当前为v中最大，直接加入v；否则，替换v中第一个大于该数的数。
   得到的数组只是满足最终数目条件的替代品，同时能满足算法的要求。
   3.基于二分查找的纸牌方法：
   https://labuladong.online/algo/dynamic-programming/longest-increasing-subsequence-2/

334

• lower_bound(a, a+n, x)：返回数组a[0]~a[n-1]中，【大于等于】x的数中，最小的数的指针
• upper_bound(a, a+n, x)：返回数组a[0]~a[n-1]中，【大于】x的数中，最小的数的指针

博客学习：
O(nlogn):一开始想出的思路错误
O(n)时间，O(1)空间：因为大数要在后面，因此要在前面构造两个足够小的数m1, m2, 遍历，首先让m1足够小,否则让 m2足够小(m1<m2),若还能有个更大的数，return true.
博客学习：构造forward[i]: 0---i-1最小的数；backward[i]: i+1---n最大的数，若 forward[i]<nums[i]<backward[i], return true.

350

• 容易想到：先分别排序，再遍历
• 哈希表：nums1中出现的 哈希表中+1， nums2中也出现的，哈希表-1

待解决：

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1's size is small compared to nums2's size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Week 4:

2020.3.29-4.5

hard:

10

讨论的情况比较多。

25

medium:

12

贪婪算法，对于1000，900，500，400，100，90，50，40，10，9，5，4，1分别对应。
待解决：时间空间待提高。使用map比使用两个vector慢一些。
map<int,string,greater<int>> map是可以排序的。

36

unordered_set
博客学习：比较巧妙，省内存，但时间不够好
使用set，行标注为 i(num),列标注为(num)j, 九宫格为 i/3(num)j/3
使用同样为m.count(num),m.insert()

48

较为经典的图像翻转
博客学习：

• 四个点依次换位
• 首先以从对角线为轴翻转，然后再以x轴中线上下翻转
• 先转置(swap(ij,ji))，后每行反转（用reverse（begin,end））

50

递归完成

89

递归的方法
如：00，01，11，10；
000，001，011，00，110，111，101，100
规律是在前面加0或1，加0可以不变照搬，加1要逆序

213

和之前的house robber的区别是第一个和最后一个不能同时偷，则使用max{rob(0,nums.size()-1),rob(0,nums.size()-1)}
博客学习：dp的空间优化版本
rob 为偷本次，notrob为本次不偷；
rob =prenotrob+cur;
notrob = max(prerob,prenotrob);

402

string resize(k) 截取string的前k个
string erase(iter)
很有启发的一道题目，能够想到移除的规律是移除第一个后一位开始下降的数字，即单调栈,仔细学习！
单调栈是抽象的数据结构，string实现即可。遍历一遍，维持结果为单调栈。
容易遗漏的点：

• 遍历后要resize到指定尺寸，因为可能只是遍历完而非已经删了k位。
• 要去除res开头的0， 如10200删1位结果0200
• res为空时要返回“0”

477

统计出每位上1的个数即可，每位上的总汉明距离是1的个数*0的个数。
待优化：时间较为复杂
easy:

461

使用位操作，x xor y, num&=num-1可使最后一位1变为0

541

C++reverse: reverse(iterator1, iterator2)

week 5

2020.4.5-2020.4.12

hard：

84：

在最后push高度为0，便于处理最后一个。
递增栈：可能出现最大面积的位置都在当高度开始下降的时候，若在上升阶段，向后可以更高。
维持一个递增栈，一旦遇到了下降，就开始全部出栈，逐一算出可能的最大面积。之后继续入一个新的栈。

85

此题和84有关，相当于在每一行构造一个立柱，立柱的高度为累加值。
同样需要扩充一个位置以应对最后一个出现极值的情况。
还有另外的解法见：https://www.cnblogs.com/grandyang/p/4322667.html

132

基于131的题目，使用两个dp，第一个用来保存是否是回文数组，第二个是dp[i]:0---i的最小切割的数量，dp[i]= min(dp[i],dp[j] +1) 如果0--j为回问，且j---i为回文，和第一个dp数组的判断条件相同，因此结构是一样的。
更多的解法见：https://www.cnblogs.com/grandyang/p/4271456.html

medium

62

一开始想到的是从右下角斜向扫描，dp[i,j] = dp[i,j+1] + dp[i+1,j] (i<m-1,j<n-1),空间为O(mn)

博客学习：有一个更巧妙优化的空间O(N)解法,逐行扫描，只保留行信息，从上一行到下一行可以直接替代。
res[i][j]=res[i-1][j]+res[i][j-1]

public int uniquePaths(int m, int n) {
    if(m<=0 || n<=0)
        return 0;
    int[] res = new int[n];
    res[0] = 1;
    for(int i=0;i<m;i++)
    {
        for(int j=1;j<n;j++)
        {
           res[j] += res[j-1];
        }
    }
    return res[n-1];
}

博客学习：一个有意思的数学解法，看成向下m-1,向右n-1,组合数m+n-2-----m-1，用公式计算即可。注意分子分母要用double，否则可能越界。

63

和上题一样，若有障碍则将dp值设为0.

64

较容易的dp问题。容易想到用一个O(n)的数组存dp，空间100%，但较费时间。
博客学习：直接在grid上累加。当i=0,j=0, continue; 当i=0，直接从左边加；当j=0,直接从上面加；否则找个最小的加。

91

细节较为复杂，技巧性强
思路容易想到使用动态规划，但需要一些技巧。
构造dp[n+1]要为size+1，如”2020“ 如果2看作单独字符，则0无法配对。因此”0“较为特殊，一定要与前一个配成“1”--“26”间的字符。若i-1位为0，这样如果到了i位时发现前两位不能组成字符，则dp[i]=0,且之后的均会为0，因为到了i+1位，前两位仍不能组成字符，则dp[i+1]=0，此后由递归便均为0.
多构造1位长度的原因是要看前两位，到了n+1位也可以看到最后两位能否组成字符。如果看前一位和本位置，如"1110"，则“11”是可以的，但最后一个0必须要和前面的1配合出现。

120

相对复杂一些的dp问题。相对容易想到在triangle上直接操作。
博客学习：空间优化：只使用最后一排的空间，从下向上更新。
结构为：
(i-1,j-1),(i-1,j)
(i,j)

131

palindrome是回文。
重要题目：因为要找到所有的情况，一定要遍历。DFS的思路进行遍历。可用dp优化判断是否是回文。
更多解法可看到：https://www.cnblogs.com/grandyang/p/4270008.html

139

学习：数组或者子字符串且求极值的题，常用DP， DP和memo的想法可互换

memo的递归：memo[i] 定义为范围为 [i, n] 的子字符串是否可以拆分，初始化为 -1，表示没有计算过，如果可以拆分，则赋值为1，反之为0
memo是向后找，DFS是向前找。
DFS:使用一个O(n^2)的遍历, dp[i] 表示0--i是否能分割，用j分割0---i的字串，若dp[j] 且j----i的字符串在字典中，dp[i]为true。
注意：dp的长度为s.size()+1,可以处理空字符串的情况；i的遍历范围是0----dp.size()；dp[0]初始化为1；因此子字符串的长度为i-j而不是i-j+1，因为i其实比实际位置多1。
BFS：和递归的方法类似。
解法见：https://www.cnblogs.com/grandyang/p/4257740.html

1186

DP的题目，思路有启发性。和最大和的区别是去除一个元素，即前面和+后面和，用两个dp数组即可。时间O(n)，空间O(n)

待学习:使用dp，从不删除和删除一个中选择较大的，时间O(n)，空间O(1)。不容易理解。

class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int sum = arr[0], sumWithDeletion = 0, ans = arr[0];
        for(int i = 1; i < arr.size(); ++i){
            ans = max(ans, sumWithDeletion + arr[i]);
            sumWithDeletion = max(sumWithDeletion + arr[i], sum);
            sum = sum < 0 ? 0 : sum;
            sum += arr[i];
            ans = max(ans, sum);
        }
        return ans;
    }
};

easy

53

经典的dp题目。

122

比较直观，记录premin,premax并O（n）遍历即可。
最后注意加上premax-premin

week 6

easy

303

做过

392

最直观的方法遍历即可。
follow up: 进行优化的方法是使用哈希表和二分查找(upper_bound)。

medium

5

回文的题目+1，可以沿用之前的思路用dp，同时记录长度和left即可。
待学习：O(n)的方法马拉车算法https://www.cnblogs.com/grandyang/p/4475985.html
https://www.cnblogs.com/grandyang/p/4464476.html

54

剑指offer原题，用一个辅助函数打印一圈，之后遍历行号即可。要核对好xy坐标

59

304

303的延申，dp[i][j] 表示(0,0)---(i,j) 的矩形和，使用dp
trick：辅助数组，dp的大小多一行多一列，这样可以不用特殊处理第一行第一列的情况（因为dp初始化为0）
相应的行列号要+1

380

因为获取随机数有O(1)的要求，所以要用一个数组来辅助hashmap

413

使用dp数组，从i=2开始。dp[i]表示i为末位有多少个这样的seq. dp[i] = dp[i-1]+1 如果能和前两个组成序列，因为： 止于i-1的可以延申一个到达i位置，此外多出一个(i-2,i-1,i)。如果不能和之前的组成序列，则dp[i] = 0.
可以继续用变量优化dp空间，不构造数组。

516

回文字符串+1， 使用dp, dp[i][j] 表示i--j的字串最大长度，

if (s[i]==s[j]) dp[i][j] = dp[i+1][j-1];
else dp[i][j] = max(dp[i+1][j],dp[i,j-1]

i遍历从n-1开始-1， j从i+1开始+1，dp[i][i] =1;

718

dp[i][j]表示以A以i为结尾，B以j为结尾时，最长的重复字串的长度。空间满分，时间较低。

if(A[i]==B[j]) dp[i][j] = A[i-1][j-1]+1;
else{dp[i][j] = 0}

更多：https://www.cnblogs.com/grandyang/p/7801533.html

hard

72

非常经典的dp问题，转移方程对应增加，修改，删除三种方式

dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) +1;

更多见：https://www.cnblogs.com/grandyang/p/4344107.html

381

380的改进版本，可以重复以后，哈希表的值用一个set来代替。 其余和之前的相同。remove操作最重要，要注意删除、增加等操作的顺序，否则会报错。（m[val].erase(cur_idx); 一句的位置重要）

week6

2020.4.19-2020.4.26

easy:

67

二进制求和，先从末尾开始相加，最后reverse即可。

70

dp问题，斐波那契数列。

medium:

31

全排列的问题：46 https://www.cnblogs.com/grandyang/p/4358848.html

开始没有理解题意。 permutation是全排列中的排列。
操作方法：从后向前，找到第一个开始变大的数i，并在后面找到从后向前第一个比它大的数j，交换两数，最后reverse(i+1,end)
排列数本应该是从小到大的顺序，i即是从i+1到end的排列数是倒序的，因此之后应该把i处的数字换成一个比它大的数开始排列，然后之后的序列因为排到了最后，变成了原本的倒序，因此reverse一下就成了原始的顺序。
解答：https://www.cnblogs.com/grandyang/p/4428207.html

39

类似题目：

• 39. Combination Sum 组合之和
• 113. Path Sum II 二叉树路径之和之二
• 90. Subsets II 子集合之二
• 46. Permutations 全排列
• 47. Permutations II 全排列之二
• Combinations 组合项

需要另写一个递归函数，这里我们新加入三个变量，start 记录当前的递归到的下标，out 为一个解，res 保存所有已经得到的解，每次调用新的递归函数时，此时的 target 要减去当前数组的的数

可以想到使用递归和DFS，但是顾虑到有重复的情况，因此要加一个参数start，每次遍历从start开始，这样就不会有(3,2,2)和（2，2，3）的情况。

73

参考：https://www.cnblogs.com/grandyang/p/4341590.html
O(m+n)的方法可以想到，即用两个数组存每行每列的情况。
常数空间的方法：用第一行第一列存，同时用两个变量存第一列和第一行的情况。

79

自己解出的DFS方法。

参考：https://www.cnblogs.com/grandyang/p/4332313.html
文中的思路一致，写法更加简洁，但时间和空间复杂度都要高很多。

94

中序遍历：144
前序：
开始想到的数据结构课的计数器，第一次不出栈，入左节点；第二次出栈，入右节点。
值得记住的非递归做法：
如果有左儿子，优先访问，但并不读取，放入stack；
没有了左儿子，从stack顶取出一个（第一次取出最左的一个），然后访问其右儿子,重复上述流程

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode *p = root;
        while(p||!st.empty()){
            if(p){
                st.push(p);
                p = p->left;
            }
            else{
                p = st.top(); st.pop();
                res.push_back(p->val);
                p = p->right;
            }
        }
        return res;
    }
};

中序遍历把res.push_back放到前半部分即可。
待学习：Morris Traversal 空间复杂度为常量，见：https://www.cnblogs.com/grandyang/p/4297300.html

98

一个易错（自己的解法）是节点不仅要考虑相邻的节点，整个树的左右都要满足条件。 一个巧妙办法是设定一个重载函数，包含最大和最小的参数。 注意： 最大和最小的参数要用LONG_MIN 和 LONG_MAX.

113

相似的思路，DFS的方法，有一个out和res
容易的bug： 因为必须是root到leaf的路径，需要防止终结结点不是叶子节点。
发现：调整函数结构简化了代码，但是耗费的时间变多，可能在递归函数内的开销会更大。

1315

直观方法：遍历，发现所有偶数节点，把孙子节点的值加起来。用了两个辅助函数
学习: DFS代码非常简洁的方法, 直接写一个DFS， 把DFS的调用写在return语句里，传递patrent, grandparent 两个参数。

hard:

45

一开始想了一个dp的O(n2)方法，结果超时。dp[i] = dp[j] + 1 if nums[j] +j >=i else dp[j] + i-j;

之后用一个O(n)的贪心算法，记录一个cur是下一次跳到的最远的一格， last是本次能跳到的最远一格，若已经走到了last， 则应该再跳一次， res++， last更新为cur。注意， i的循环范围为0--nums.size()-2
因为不需要再多跳一次。

97

字符串的子序列或是匹配问题直接就上动态规划 Dynamic Programming，递归可能超时

dp[i][j] 表示s1 0--i s2 0--j 能否匹配s3 的0--（i+j)
dp的大小是m+1, n+1， 多出的第0行第0列表示空字符串的情况。
首先初始化第一行第一列， dp[0][0]=true; 之后匹配条件是前一个为true及该位相等。

之后的矩阵，两种匹配方式是从上面或者左面过来，对用s1多匹配一位或者s2多匹配一位，两种有一种为true即可。注意i,j对应的位置其实是i-1,j-1,以及i+j-1

待学习:更多解法：https://www.cnblogs.com/grandyang/p/4298664.html
含有DFS，BFS的简化

week 8:

2020.4.26-5.2

easy

141

经典：链表有环
快慢指针，若追上了说明有环

206

经典反转链表
有递归和迭代两种解法
递归：
递归的方法是对每段分成head和剩下的，反转剩下的，将head放在尾部，返回rest。
注意要把head-》next设为null，否则会形成环。
边界条件要注意至少要有head和第二个节点second。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head==NULL ||head->next == NULL){
            return head;
        }
    ListNode *second = head->next;
    head->next = NULL;
    ListNode *rest = reverseList(second);
    second->next = head;
    return rest;
    }
};

迭代：
pre,cur, next三个节点在一次往前走，颠倒pre,cur之间的指针方向。
迭代终止时，cur指向null，pre指向的是最后一个（即第一个，返回）

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = NULL, *cur = head;
        while(cur!=NULL){
            ListNode *next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

medium

24

也有递归和迭代两种方法。 最开始想的设计4个节点过于低效。
链表操作多想想递归，迭代方法要画个图。

74

从右上角开始，要变小向左，要变大向下。

82

直观的想法。注意：在发现相同的词，向后推移的时候，要时刻检查是否达到最后一个。

92

想出的较复杂的方法：

image.png

记住开始点start，结束点post, 中间一段进行反转后，和前后拼接。

更简洁的方法：
1 -> 2 -> 3 -> 4 -> 5 -> NULL
1 -> 3 -> 2 -> 4 -> 5 -> NULL
1 -> 4 -> 3 -> 2 -> 5 -> NULL

在反转的过程中，pre一直是1,cur的指针一直在2上（2本身在向后移）
在每一步，都是把cur的面移到pre的后面（反转串的最前面）

    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode *dummy = new ListNode(-1), *pre = dummy;
        dummy->next = head;
        for (int i = 0; i < m - 1; ++i) pre = pre->next;
        ListNode *cur = pre->next;
        for (int i = m; i < n; ++i) {
            ListNode *t = cur->next;
            cur->next = t->next;//cur和后面相连结
            t->next = pre->next;//post接管pre的下家
            pre->next = t;//post和pre连接
        }
        return dummy->next;
    }

142

快慢指针
先追上以后，慢指针再从head开始，再次相遇时为环的入口。
更多解答见：https://www.cnblogs.com/hiddenfox/p/3408931.html

image.png

拓展：如何判断两个单链表是否有交点？先判断两个链表是否有环，如果一个有环一个没环，肯定不相交；如果两个都没有环，判断两个列表的尾部是否相等；如果两个都有环，判断一个链表上的Z点是否在另一个链表上。

两个单链表如何找到第一个相交的节点？求出两个链表的长度L1,L2（如果有环，则将Y点当做尾节点来算），假设L1<L2，用两个指针分别从两个链表的头部开始走，长度为L2的链表先走(L2-L1)步，然后两个一起走，直到二者相遇。

143

没有想出成功的解法。
方法：使用栈，把后半部分倒转，插入到前半段中。

240

参考：74 从右上角开始
https://www.cnblogs.com/grandyang/p/4323301.html

开始写了一个递归的写法，从右下角开始，但是递归的层数过多，超出时间限制。
和I不同，没有蛇形的关系，因此从左下角或者右上角开始。

328

用pre，cur两个指针。

hard

23

使用分治法，两两合并链表。
更多方法：包括最小堆(结果会稍差一些)
https://www.cnblogs.com/grandyang/p/4606710.html

329

参考：https://www.cnblogs.com/grandyang/p/5148030.html
dp + dfs能够完成，但是时间和空间都较差。

week 9

2020.5.3-2020.5.10

easy

69

二分法 解决sqrt（）

278

二分法query

medium

34

https://www.cnblogs.com/grandyang/p/4409379.html

• 借助find函数和equal_range函数可以找到上下界范围
• 使用二分法，写一个辅助函数，找到第一个大于等于target的位置

153

ratated array用二分法，rotate 以后，在分界出会有判断条件（在有序数组中也同样适用）

162

遍历一次即可。

300

dp方法，较慢
week3的题目出现过

436

建立一个map{start:idx}, 再次遍历，每一次对interval在map中寻找第一个大于等于end的idx，使用lower_bound

497

采样的问题。使用map，建立累加面积和idx的对应关系，之后在定位的矩形中随机一个点。
注意，由于矩形的边缘时包含进来的，宽度为边界的差值+1.

811

自己解法：使用. " "进行分割，使用map计算出现的次数.

911

待提高:使用map记录每一时刻的leader, query的时候，查找第一个小于该时间的leader。
但是速度和空间较满

1011

迷惑问题：一句cout的影响

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int D) {
        int n = weights.size();
        vector<int> dp(n+1,0);
        int sum =0;
        for(int i =1;i<n+1;++i){
            sum+=weights[i-1];
            dp[i] = sum;
        }
        // for(auto v:dp) cout<<v<<"\t";
        // cout<<endl;
        int res = INT_MAX;
        vector<int> split;    
        split.push_back(0);
        for (int i=0;i<=weights.size()-D+1;++i){
            // cout<<endl<<"starting"<<i<<endl;
            dfs(weights,dp,split, i,D-1, res);
        }
        return res;
    }
    
    void dfs(vector<int>& weights, vector<int>& dp, vector<int>& split, int start, int k, int& res){
        if(k==0) {
            split.push_back(weights.size());
            int cur_res = min_cap(dp,split);
            // cout<<cur_res;
            // printf("%d\n",cur_res);
            res = min(res, cur_res );
            split.pop_back();
            return; }
        
        for(int j = start+1; j<=weights.size()-k+1;++j){
            split.push_back(j);
            dfs(weights,dp,split,j,k-1,res);
            split.pop_back();
        }

    }
    
    int min_cap(vector<int>& dp, vector<int>& split){
        int split_start, split_end;
        int res;
        for(int i=0;i<split.size()-1;++i){
            split_start = split[i];
            split_end = split[i+1];
            res = max(res,dp[split_end] - dp[split_start]);
        }
        return res;
    }
};

hard

315

https://www.cnblogs.com/grandyang/p/5078490.html
“思路是将给定数组从最后一个开始，用二分法插入到一个新的数组，这样新数组就是有序的，那么此时该数字在新数组中的坐标就是原数组中其右边所有较小数字的个数”

另一种方法是 merge 排序，在 merge 过程中可以知道比它大的个数。

week 10:

2020.5.11-2020.5.18

easy

136

使用位运算，非常巧妙，两个相同的数与运算为111111，剩下一个单独的数即为其本身。

389

先排序，后逐个匹配

medium

221

使用dp,dp[i][j]为到i,j的最大矩形面积，dp[i][j]为[i-1,j][i-1,j-1][i,j-1]中的最小值+1 ，但如果matrix[i][j]为0，直接为0.
为了省略考虑边界情况，可以让dp数组增加一个单位，整体向后移动一格。
此次遍历用的是从上到下的顺序。为了节省空间，可以用一维dp数组。但是要记得保存dp[i]的值，用作pre。

318

https://www.cnblogs.com/grandyang/p/5090058.html

两两进行比较一定是要O(N2)的，重点在如何判定两个string有无重合字母。
方法：借助bit， 26个字母，而一个int是32bit，因此用int的后26位作为mask，用为操作进行判定。

343

dfs递归调用，25-58无法运行

class Solution {
public:
    int integerBreak(int n) {
        int res = 0;
        vector<int> nums;

        dfs(n, nums,res);
        return res;
    }
    
    void dfs(int remain_sum, vector<int>& nums,int& res){
        if(remain_sum==0){
            if(nums.size()<2) return;
            res = max(res, get_product(nums));
        }
        
        for (int first = 1; first<=remain_sum; ++first){
            nums.push_back(first);
            dfs(remain_sum - first, nums, res);
            nums.pop_back();
        }
    }
    
    int get_product(vector<int>& nums){
        int pro = 1;
        for(auto v:nums){
            pro *= v;
        }
        return pro;
    }
};

使用dp来解，dp[i]是i的最大积，n方的复杂度。
取巧的方法：找规律是找到尽量多的3，直到剩下一个4或者5为止。
原理是：

image.png

435

二维vector的排序：若通过每个的第一列排序，直接sort即可；否则写一个com函数

先排序，若发现了重复，则去除end较大的那一个（防止更多的重复），同时res+1

步骤如下：

1、从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。
2、把所有与 x 区间相交的区间从区间集合 intvs 中删除。
3、重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。

621

找规律：找到重复最多的字母，然后用最小间隔分开，中间插入其他字母。
AAAABBBEEFFGG 3
最多是A，出现4次，则有3个单元：
A---A---A---A
AB--AB--AB--A (加入B)
ABE-ABE-AB--A (加入E)
ABEFABE-ABF-A (加入F，每次尽可能填满或者是均匀填充)
ABEFABEGABFGA (加入G)

算法是（4-1）*（3+1）+1 = 13

同时至少要达到task数量的长度。

714

动态规划

对于第i天的最大收益，应分成两种情况，一是该天结束后手里没有stock，可能是保持前一天的状态也可能是今天卖出了，此时令收益为cash；二是该天结束后手中有一个stock，可能是保持前一天的状态，也可能是今天买入了，用hold表示。由于第i天的情况只和i-1天有关，所以用两个变量cash和hold就可以，不需要用数组。

 cash=max(cash,hold+prices[i]-fee);//cash in day i is the maxvalue of cash in day i-1 or you sell your stock
 hold=max(hold,cash-prices[i]);

注意要从第1天开始算，hold初始值为-prices[0]（假设在第0天买入），cash的初始值为0

870

田忌赛马：若上等马赛不过上等马，则用下等马代替。
multiset:可以重复，自动排序

multiset<int> st(A.begin(), A.end());

多方法：使用最大堆

1261

使用dfs构建，set来查找

hard

52

51 n-queens:
使用dfs的方法。用一个函数判断在此位置放置是否合法。
优化：使用以为数组，queenCol【i】表示第i个皇后的列数。判断对角线时，横纵坐标的差值相同。
52 n-queens2
不需要记录结果，只要记录数量就可。

1028

week11:

2020.5.18-2020.5.25

Easy

20

stack完成

290

python处理，建立字典

Medium

3

result [] 记录每个位置截止，最长字串长度
char_pos保存字母所在的最新position，每次更新。遇到新字母，直接长度+1. 遇到旧字母，若和上一次出现位置间的距离大于result[i-1]则长度+1；否则要更新成该距离

18

DFS可以做，但是会超时
用三层的循环。使用set防止重复，最后把set转vector。
防止相邻的重复，再j进行跳过这些重复的

58

持续计数，每次到了空格清零。

166

实现除法。要考虑的情况比较多。
除数是否为0
考虑结果的正负
考虑有没有小数位，若有，加小数点
考虑是否有循环小数位，通过一个map存储第一次出现位置，若重复，则加入（）

187

使用set存储出现过的10位字符串
空间优化：用2位的二进制数表示AGCT，使用位操作

454

brute force: O(N**4)的方法。
简化：把A,B的所有和存成map， 对应出现次数，然后再C，D和中看有多少个能和为0.

554

参考：使用hashmap，建立每个宽度上裂缝的个数，并更新最多分割的数量，划过的砖为len-max数量。

974

一定是要求累计和的。连续字串的和就是累计和的差，能被K整除就是要寻找累计和里同余的个数，每次比如余数是b，则之前余数是b的个数都能和他同余，即结果要加之前的个数。

Hard

336

992

week12: 2020.5.25-2020.6.1

Easy

242

26位的数组，计数，第一个str +1， 第二个数组 -1， 检测为0

Medium

17

DFS常见的思路。
具体处理：
从数字到字母的映射使用了vector<string>

46

全排列，熟悉的思路用DFS
待学习： BFS的解法

47

和上题相同。先排序，在dfs的时候，加入判断，如果和前一个字母相同，且前一个未访问过，则跳过。

60

DFS改编，但是超时。
参考：https://www.cnblogs.com/grandyang/p/4358678.html
找规律，发现和除数和余数有关

Hard

115

子序列问题，条件反射用dp，最重要：确认转移方程
debug用了很久，改进了空间复杂度为O(2)
dp[i][j]表示S的0--i的字串等于T的0--j的数目
dp[0][0] = 1
dp[i][0] = 1
T的0--i 包含空字串
dp[i][0] = 0 （i!=0） 空字串不可能等于字串

dp[i][j] = dp[i-1][j]
if(s[i]==t[j]){dp[i][j] = dp[i-1][j] + dp[i-1][j-1];}

用lastrow保存dp的i-1行，注意lastrow在每次循环要率先保存。

week 13 2020.6.1-6.7

Easy

257

dfs的老写法。注意如何组织结构。
终止条件：左右节点为空（root为叶子），此时添加root->val
判断分别是否有左右节点，直接使用函数调用进行+"->"的操作，这样不需要再删除。 注意string 没有&
待提升:时间和空间较低

Medium:

103

复习了一下层次遍历。加入反转bool变量，判定是否需要反转。但是反转操作耗时间。
改进：
加入数组的时候预先留好空间，将数字填进去,填的idx是size-i-1（逆序）或者i（正序）

133

使用BFS，DFS两种方法，使用一个map来看有没有克隆过。
要注意判断是否克隆过的位置，node克隆过，但它的neighbors可能没有，此时会造成漏掉节点。

310

抽丝剥茧寻找根节点。从叶子节点开始，先砍掉和叶子节点相连的边，然后如果有新的叶子节点，加入队列。

399

DFS：除法的题目，实际上是构建一个有向图，edge的weight是商。
构建的图的数据结构是unordered_map<string, unordered_map<string, double>> g
表示g[A][B] = k for A/B = k

首先遍历equations,把所有的等式加入图，反向的也加进来
找答案的时候用DFS，用set visited记录node是否访问过.如果没有则返回-1.0， 有则继续递归。

并查集：待解决

Hard

149

判断是否在同一直线， 同线最多有几个点
方法：对每个点，看经过这个点的直线最多有几个点
只要斜率相同，就在同一条线上。斜率用一对不同余的数来表示，避免小数的精度问题。（都除以最大公约数）
注意可能有重复的点，直接算共线。

week 14 2020.6.8-6.15

Easy

1042

简单遍历的方法。先建图，用一个二维vector；然后遍历每个点，把nieghbors的颜色加入set，最后选一个没有出现过的颜色加入res。

Median

207

https://www.cnblogs.com/grandyang/p/4484571.html
查找有向图中有没有环。
BFS、DFS两种方法，DFS更快
BFS：抽丝剥茧，去掉入度为0的点，最后入度应该都为0
DFS：深度访问，直到冲突（visited：冲突-1，已访问1，未访问0）

210

本质是一个拓扑排序问题。
类似于270，使用BFS，只要把结果加入res即可；如果图中有环（res结果不等于课程数目），直接返回{}；
另一种方式是 DFS，后序遍历结果即为课程顺序

Hard

123

股票买卖允许2次，见“系列题目总结”

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp10 = 0, dp11 = -INT_MAX;  //left 2 times to buy
        int dp20 = 0, dp21 = -INT_MAX;  //left 1 time to buy
        for ( int i =0; i < prices.size(); ++i){
            dp10 = max(dp10, dp11+prices[i]);
            dp11 = max(dp11, -prices[i]);
            dp20 = max(dp20, dp21+prices[i]);
            dp21 = max(dp21, dp10-prices[i]);
        }
        return dp20;
    }
};

medium：

leetcode338 数字中二进制的个数

类似于DP的方法

def countBits(num):
    """
    :type num: int
    :rtype: List[int]
    """
    ans = [0]
    for x in range(1, num + 1):
        ans += ans[x >> 1] + (x & 1)
        print()
    return ans

print(countBits(4))

位运算的trick

def countBits(n):
    """
    :type n: int
    """
    count = 0
    while(n):
        print(n)
        count+=1
        n = (n-1)&n
    return count

print(countBits(4))

215

方法一： quick select
基于快速排序的partition函数；空间好时间慢

方法二：堆排序
时间快很多，空间差一些。
堆排序步骤：1.确认最大最小堆 2. 建立堆（调用max_heapify) 3.堆排序（不断把最大值移到最后）4. 取第k个
用 puthon 的 heapq 实现，比快排更快一些。

236 最小公共父节点

• 若p和q分别位于左右子树中，那么对左右子结点调用递归函数，会分别返回p和q结点的位置，而当前结点正好就是p和q的最小共同父结点，直接返回当前结点即可，这就是题目中的例子1的情况。

• 若p和q同时位于左子树，这里有两种情况，一种情况是 left 会返回p和q中较高的那个位置，而 right 会返回空，所以最终返回非空的 left 即可，这就是题目中的例子2的情况。还有一种情况是会返回p和q的最小父结点，就是说当前结点的左子树中的某个结点才是p和q的最小父结点，会被返回。

• 若p和q同时位于右子树，同样这里有两种情况，一种情况是 right 会返回p和q中较高的那个位置，而 left 会返回空，所以最终返回非空的 right 即可，还有一种情况是会返回p和q的最小父结点，就是说当前结点的右子树中的某个结点才是p和q的最小父结点，会被返回

4 Median of Two Sorted Arrays

https://www.cnblogs.com/grandyang/p/4465932.html

134

记录curgain和totalgain，表示目前的盈余和总盈余。如果总盈余<0, 则最终无法到达；当前盈余<0,换下一个为起点。

871

1401

319

智力题。 因数的总个数为，当结果为奇数的时候灯为亮，此时均为偶数，故x为所有平方数，即为1，4，9，16，25，36，。。。100，n中完全平方数共有sqrt(n)个

309

用一个变量保存冷冻后的钱，每天缓存并更新

572

188

4

543

任意一个节点的左右depth之和，其中的最大值。

2024.5

151

使用python很容易

274

用遍历的方法过了，但速度很慢。
用二分查找的方法，先排序，见 https://blog.csdn.net/happyaaaaaaaaaaa/article/details/51595898

275

274的排序版

322

dp问题，不能用逐次整除的方法，因为可能存在大因数不满足，但小因数满足的情况.
dp方法，低速通过。
dp[i]表示，凑到i所需要的最少的硬币数。

dp[0] = 0
dp [others] = np.inf
dp[i] = min(dp[i], dp[i-coins[j]] +1)

263, 264， 丑数，ugly number

丑数问题合集见：
https://labuladong.online/algo/frequency-interview/ugly-number-summary/

1.dp方法，速度不快
丑数，一定是之前丑数的2,3,5倍数。具体几的倍数，需要各自维持一个指针。
此方法和三链表合并等价。

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = np.ones(n+5) * np.inf
        dp[0] = 0
        dp[1] = 1
        p2, p3, p5 = 1, 1, 1
        for i in range(2,n+1):
            n2, n3, n5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5
            dp[i] = min(min(n2, n3), n5)
            if n2 == dp[i]:
                p2 += 1
            if n3 == dp[i]:
                p3 += 1
            if n5 == dp[i]:
                p5 += 1
        return int(dp[n])

313, super ugly number

上一题的多指针版本。dp方法低速过。
2024.9.7，更快的解法是维护一个最小堆，存放哪一个 prime 指向的丑数最小，作为新的丑数。注意可能重复，故要排除重复。

241

分治法。但是要使用遍历，而不是在第一层就二分。

78 subsets

回溯法。注意backtrack调用从哪里开始。这里是设定一个start。

90 subsets 2

和上题相同，先排序，如果和上一个相同就跳过。

39， 40 combination sum 1，2

组合问题和子集问题是等价的。
40题的重点是合理剪枝，当前res的和已经超过target时候，直接结束。否则会超时。

752 （待优化）

低速过。使用bfs搜索。可以用双向BFS加速。

76

低速过。滑动窗口，先向右滑动。再收缩左边界。直到到达右端点。

567

和上题相同，变化是在长度等于s1的时候，直接返回true。

438

和上题相同，变化是最后输出left的list。

19

思路见：https://labuladong.online/algo/essential-technique/linked-list-skills-summary/#%E5%8D%95%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%AC-k-%E4%B8%AA%E8%8A%82%E7%82%B9
快慢指针，快指针先走k步，再一起走。
比较困难的是解决一个corner case：如果head刚好被抹除的情况。使用一个dummy node，最终不是返回head，而是dummy的下一个。

416

容易想到转化为sum/2的背包，但难定义dp
dp[i][w] 为i个物品，能否到达重量w，值为true/false
dp[i][w] = dp[i-1][w] or dp[i-1][w-val[i]]
注意，可以进行空间压缩，但要关注因为都基于i-1，因此遍历时候要倒序，避免使用了新的dp[i][w]的结果。

518

对凑硬币问题的更难版本，如果只定义dp[n],无法完成递归式。
假设dp[i][j]是 使用前i个硬币，凑到j元的方案的数量。
dp[i][j] = dp[i][j-coins[i-1]] + dp[i-1][j]
前一种是使用第i个，后一种是不使用第i个。

1109

使用差分数组，提升效率。

114 flatten

以下代码答案错误，但遍历顺序是对的。原因是没有in-place完成操作。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        dummy = TreeNode(-1)
        self.p  = dummy
        def traverse(theroot):
            if not theroot:
                return 
            print(theroot.val)

            self.p.right = TreeNode(theroot.val)
            self.p = self.p.right
            traverse(theroot.left)
            traverse(theroot.right)
            return
        traverse(root)
        return dummy.right

用in-place的方法，注意操作的顺序。解法见：
https://labuladong.online/algo/data-structure/binary-tree-part1

654

递归左右构建。

105

流程容易想，但要构建为算法的递归调用。关键是构造如下函数原型：

build(self, preorder, pre_start, pre_end, inorder, in_start, in_end)

977

简单方法容易想，比较难想到的是双指针方法，从头尾的正数和负数同时开始操作。

297

序列化和反序列化，可以通过前序或后续递归实现。可以把 null 写入为#，在反序列化时用 dfs 的方法构建。（注意后序方法，需要先构建 right，后构建 left）

同样也可以使用层次遍历的方法实现。

230:

O(n)的算法，中序遍历即可，时间复杂度是 O（N）
但要注意，如果每个节点维护子树的 size，即可实现 O（logN）的查询

652

遍历一次，把所有的子树都放进 hashmap。遍历过程中序列化，用序列化判断是否出现过。

700

BST的基础题目

222

完全二叉树，介于满二叉树和普通二叉树之间，因此如果局部是满二叉树，可以加速计算。

341

多叉树的遍历。记得可以用 deque 提升插入和读取的效率。

785, 886

图的遍历。
886 的区别是需要先构建双向图。

200

dfs遍历数组。没有单独维护一个 visited，而是直接修改了 原始grid数组作为 visited。
计数时候，只从最外层遍历计数，内层 dfs 只负责找到并标记相邻的岛屿。

lintcode 3651

并查集问题。

130

想到的方法是DFS，bug多，需要考虑对外围先遍历，并用一个变量维护是否只对O操作。但速度慢。
另一种方法是并查集。

1254

同样是 dfs 遍历。注意淹没最外层陆地的时候，需要用 dfs，把相邻的岛屿都淹没。

1020

同上，把岛屿面积加起来。

695

同上，面积取最大值。注意不需要淹没外围。

1905

自大欧文谈。
grid2 的岛屿中，查看是否存在 grid1 为海的情况，如果是，就把 grid2 的该处用 dfs淹没。这种情况绝不可能成为子岛屿。
剩余的岛屿，即为子岛屿，其数目为最终结果。

124

二叉树最长直径的变体。注意要看左右和，各自和 0 作比较，只保留正的。

93

回溯法。注意合法 ip 的判断。

92

用递归法翻转部分链表。
迭代法速度差不多，空间更节省。

234

判断链表是否对称，用递归思路的一个解。

1143

注意自底向上遍历时候，要对数组偏移，节省初始化。
注意：初始化 python 二维列表，你使用了 [[0] * (n2+1)] * (n1+1)，这会导致每一行实际上是对同一个列表的引用。这意味着当你修改 dp 中的某个值时，这个修改会影响到其他所有行。

    dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]

同时，可以进行空间优化。 空间优化要注意dp[j]在内层循环会变，

583

1143基础上，用2个word长度减去最长公共子序列长度即可。

25

辅助函数：反转 a 到 b 之间的
递归，找到第 k+1 个，反转 1～k 个，再递归求解后面的，然后拼起来。

1312

注意是子序列，不是子串，因此允许跳过字符
用总长度，减去最长的对称子序列的长度即可。
也可以自己迭代一套 dp 算法，和最长子序列类似。

131

回溯算法。注意下标的范围。

1288

区间问题，可以先排序，注意sort(key= lambda x: (x[0],-x[1])) 第二个字符降序，防止少算空间。

986:

关键是找到条件：a2>=b1 and b2>=a1
以及i 和 j 更新的条件。

452:

贪心算法，相当于不想交的 interval 的数目

1024

排序（key=(x[0], -x[1])），再维护cur_end, next_end. 迭代找到最远的 next_end 如果不满足，就到下一个interval。最后每个循环检查是否到达 T。

486

动态规划。注意先后手的转换：在选择完毕后，先手就变成了后手；后手在选择时，从先手挑剩下的起步，是作为先手的。
注意循环的顺序，是个上对角的形状，从对角线开始，向右上角逼近。最终状态是 d[0][n-1]

dp[i][j].fir = max(piles[i] + dp[i+1][j].sec, piles[j] + dp[i][j-1].sec)
dp[i][j].fir = max(     选择最左边的石头堆     ,     选择最右边的石头堆      )
# 解释：我作为先手，面对 piles[i...j] 时，有两种选择：

# 要么我选择最左边的那一堆石头 piles[i]，局面变成了 piles[i+1...j]，
# 然后轮到对方选了，我变成了后手，此时我作为后手的最优得分是 dp[i+1][j].sec

# 要么我选择最右边的那一堆石头 piles[j]，局面变成了 piles[i...j-1]
# 然后轮到对方选了，我变成了后手，此时我作为后手的最优得分是 dp[i][j-1].sec

if 先手选择左边:
    dp[i][j].sec = dp[i+1][j].fir
if 先手选择右边:
    dp[i][j].sec = dp[i][j-1].fir

793

因为该函数是递增的，因此可以分别求出 left_bound, right_bound, 最终结果为相减+1。
注意初始的 right的设定，要覆盖到可能的最高的k。

875

因为是个单调递减的阶跃函数，二分查找法。重点是写出运送速度和天数的关系。

1011

同上。

74

二分搜索。

410

实际等同于leetcode 1011. 注意count 函数不要写错。

337

二叉树遍历中的打家劫舍。递归方法。
更快的方法是：读者给的解法

887

dp方法。注意要使用二分法优化，否则超时。

724

前缀和方法。

525

用一个哈希表存储 presum 的 val 和 index，用空间换时间，省去 2 层的遍历。

523

方法同上，速度较慢。

658

先用 left bound 找出 p，再左右扩展边界。优先扩展左边界。注意使用 deque 降低左右 append 的复杂度。

852

同162，用二分查找

33

改进的二分搜索

81

和上图一样，但需要去除 left 和 right 的重复元素，即可用上式法

787

（1）可以使用 dp 算法。
dp[k][t] 表示可以k步内到达t的最少cost
dp[k][t] = min(dp[k+1][ind] + weights[ind, t])
（2）也可以改进 dijkstra 算法。注意，不能直接去除大于的点，而要兼顾hops。如果hops变短了，也可以保留在heap中。

188.

动态规划。注意对于 k>=n/2的题目，转化成了 k 不受限制的场合，否则因为复杂度过高无法通过。

659

思路很直接：（1））判断能否跟在已有的后面 （2）如果不能，新开一个，但需要判定新开一个队列能否形成。
重点是实现方法，即维护 freq 和 need 两个字典，动态更新。

1201

由于复杂度高，使用二分查找来改进。计算 n 内 a 并 b 并 c，用集合的公式，结合 lcm 和 gcd 来计算。

A ∩B = num/lcm(A,B),  lcm(A, B) = A*B/gcd(A,B)
A∩B∩C = num/lcm(lcm(A,B), C)

496

单调栈的简单改进。
由于nums1是nums2的子集，可以把nums2的结果变成字典，nums1直接查表得到。

739

简单改进，变为记录index。

503

用环形数组，循环2n次即可。

967

回溯算法。主要要对第一个数位进行特殊处理，可以直接在外部循环，backtrack 只处理后面数位的情况。如果放在 backtrack 内部容易出错。

347

先计算每个 num 的次数（适用 collections 的 Counter，注意 Counter 的返回是降序排序的），就转化为了求数组中第 k 个值（这里可以用最小堆，去除第 k 个之外的次数少的 num，留下的就是 k 个最多的）。

37

数独，回溯法解题。

391

2个步骤：（1)看面积的和，是否和理想矩形是否相同（2）看顶点，如果是顶点，应该出现次数为奇数次。用set来维护，不断新增和删除。最后set只剩下4个，应当对应为理想矩形的顶点。

743

用priorityqueue比heapq更快。

494

转化为子集背包问题，即找到一个子集，和为(sum+target)/2. 之后就套用背包问题的dp算法。主要j递归要从后往前。

174

定义dp为走到右下角的最少的血量。倒着遍历。

1235

dp定义很难！！因为和背包很想，最直接的想法是定义dp[i][t]，但t其实是和i的结束时间有关，不如把t直接省略。

• 首先按照endTime排序
• 定义dp[i]为0～i个任务的时间段内，最大的profit。注意，i为能够达到更大profit的最大值，i和jobs的遍历不一定相关。
• 有一个新job到来，首先找到符合约束的最早开始时间对应的任务，该任务为i，可通过bisect二分查找得到
• 再对比如果插入新job，会不会比前一个第i-1个job的总profit更高，如果更高，插入到dp的后面。

1631

dijkstra算法解。

1514

注意，dijkstra仍然可以用，因为：（1）无向图，可以看成双向图 （2）关于最小值和非负的权重，因为这里的概率乘积是边越多越小，求最大值，因此仍然可以用。注意要改成最大堆。

261(lintcode178)

并查集，检查每个边，应当不在并查集中。最终true的条件是count为1

1135（lintcode 3672)

先排序，再用并查集，如果不连通，就返回-1.

1584

并查集，排序，加入边。

514

dp问题，规定dp[i][j] 为当指向ring[i]时候，需要波动圆盘的次数，使得key[j....] 能够完成。

969

递归问题，P(n)为前n层排好序，可以转化为P(n-1)的问题。
求解P(n)的步骤：找出前n层里最大的一个，放到第n层（翻转2次），然后求解P(n-1).
注意翻转2次时候的叠加顺序，由3部分组成，最后要叠加已经排好序的部分。

10

字符串匹配，动态规划，dp[i][j表示s[i...] 匹配 s[j....]的情况。
注意，当s[i]到末尾的时候，不一定匹配成功，成功的唯一情况是p后边的全都是abc这样的。
（1） 若s[i] p[j]能匹配，可能匹配0个，1个，多个
（2）若不匹配，看j+1位置是不是通配符匹配0个的情况，如果不是就return False。

645

一个空间复杂度为O（1）的方法，即把iundex为num的数变为相反数。如果遇到某个数已经为负数，说明重复了；如果最终某个数为正数，这个数就是缺失的。

384

洗牌算法，即用i+randint（0，n-i-1）生成的数，作为第i张的交换，这样总的采样空间为n！。 只能对数组类型可用，链表就不行了。

980

dfs求解。注意细节。

235

利用二叉搜索树的性质，可以简化搜索。

295

流式数据的中位数，维护一个large小顶堆和一个small大顶堆，并且使得二者的size差距不超过1.

538

BST的核心是，中序遍历可以升序遍历。
倒着中序遍历即可，赋值不会影响遍历左子树。

1038

完全同上

98

判断BST的合法性，绝妙的递归做法：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self.isBST(root, None, None)
    def isBST(self, root, min_node, max_node):
        if not root:
            return True
        if min_node and root.val<=min_node.val:
            return False
        if max_node and root.val>=max_node.val:
            return False
        return self.isBST(root.left, min_node, root ) and self.isBST(root.right, root, max_node)

通过参数传递max_node和min_node, 并满足BST的性质