8月刷题/Mock interview接龙活动（缺米刷题的来）

8/15 十题 dp 树

8.15 继续磕双指针
简单地说，这类问题一种是左指针先移，一种是右指针先移，一起移动的比较简单（可能会从尾部开始）。

Day 15

1550. Three Consecutive Odds, loop
1551. Minimum Operations to Make Array Equal, 数学题
1552. Magnetic Force Between Two Balls, 整个结果空间上 binary search
484. Find Permutation, 用了一个比较奇葩rule的贪心
435. Non-overlapping Intervals, sort + greedy

day 15打卡：quick select要区分不同的题是否要单独考虑等于pivot的情况。

求加米，必回加。一起加油！

DP 太难了。。。
今天基本都是hard题
472. Concatenated Words  
97. Interleaving String
32. Longest Valid Parentheses
72. Edit Distance
1048. Longest String Chain  
528. Random Pick with Weight
315. Count of Smaller Numbers After Self

8/15 打卡第15天， 刷了3道题

84. Largest Rectangle in Histogram
dynamic programming
对每个i，找出left，right，for any j, left<j<right, heights[j]>=heights[i]

221. Maximal Square
dynamic programming
height(i,j) = height(i-1,j) + 1, if matrix[i][j]=='1';
height(i,j) = 0, if matrix[i][j]=='0'
left(i,j) = max(left(i-1,j), cur_left)， cur_left是当前行满足j>=k>=cur_left, matrix(i,k)=1
right(i,j) = min(right(i-1,j), cur_right), 对于j<=k<=cur_right, matrix(i,k)=1
area = max(area, min(height(i,j),right(i,j)-left(i,j)+1)**2)

435. Non-overlapping Intervals
先排序，然后贪心算法

D8 打卡：今天刷了7题
比较好玩的一题是Add Two Numbers II，stack, reverse linked list, 或者直接数学解都可以

8/15 Day 15 打卡：

Find Right Interval
Find Lucky Integer in an Array
Non-overlapping Intervals

速度还是上不去啊，每次看dis 理解都要好久。  如果直接看答案，自己写一遍 对于第一遍是不是会更加有效率呢？  加油

打卡 刷了三题 周末事情太多了
435和经典的300是一样的 用dp就好了 关键是除掉目标区间后 得到的是最长的非严格增长子序列
笨办法 但可以学套路