缺大米的请参加这个刷题/Mock interview活动

打卡 day 16

今天的六题打卡

打卡第十一天：
701， 230， 108

感觉应该先左BFS和DFS再来做BST。。。。

6.17 打卡6道Binary Search

坚持14天，刷了3题
笔记
1. UNION of two queries is faster than one OR query
2. Brute force: We need a new array, a counter as index of new array, and do two for loops for even and odd numbers
3. Need to check start and end separately to decrement or increment them; 因为还包括之前没有用for loop的情况，也就是不需要swap，可能两者都是even或者💰even后odd
4. Any number XOR'd with itself is zero. Any number XOR'd with zero is the number itself.

Day 7, 3道题

3. 无重复字符的最长子串
   滑动窗口求解, start , end双指针

41. 缺失的第一个正数
   让每一个数字回到它本来的位置, 比如4应该放在3, 然后遍历寻找缺失的

88. 合并两个有序数组
    从后往前合并, 如果第二个数组还有多余的,复制到第一个数组

day 8 6题
1. 去重-group by

06.16. 刷题第五天打卡第五天

1. compress String（二刷）
觉得之前掌握的不牢固，所以今天再次刷题，然后看看之前遗漏的点是不是都已经捡了起来，
之前感觉也做过一些题目了，但是仍然未能得法，根本原因就是总结和复习不够到位；
因此今后也会拿一些老题过来再review，总结再提高

本题需要注意的点：
a. 注意到如果是unique的character， 那么就单独处理1（使用fast slow begin来处理）
b. 如果是多个，甚至是两位数及以上多个，就再单独处理2（get length）；
c. 然后就create new char；从后向前处理（注意用到Character.isDigit)

2. Decompress String
这个题目相对来说可能没有题1那么直观，需要注意的是:
也是分情况[0,2] & (2, 9]来进行讨论
同样要建立一个new Char，然后从后往前依次填入重复的元素（character）
要注意做循环的时候，是递增2/递减2的gap向前移动；

3. All anagram
使用HashMap对Base String 拿值和对应出现的次数；
通过引入match这样一个int variable来对照hashmap当中的size，来决定是不是能够把初始index倒进去；
注意：在处理index的时候，要小心“-1”的操作可能需要发生（index is 0 based）

6/17 连续第4天打卡

做题7道

总结；
1. print debug不能忘
2. 数组问题不懂是否加1，举实例
3. 子数组子字符串要想到同向双指针

打卡第五天 6道题 = 3道2pointers 3道dp
11 Container With Most Water
- left, right → two pointers
- for each time, move the lower one to find a possibly larger area than the current one
41 Trapping Rain Water
1. use extra space: left max array and right max array → sum up the min values in each position
2. left, right → two pointers, left_max, right_max → the max height →
- when left height < right height: sum+=left max - left height
  - because left max is smaller than right max → move left pointers
- vice versa
125 Valid Palindrome
- s.isalnum() → if it's alphanumeric
- s.upper() → get the uppercased string
70 Climbing Stairs
- the total ways to reach the third step = the total ways to reach the first + the second
85 Maximal Rectangle
1. dp: array to store the left consecutive width to each position → iterate through array → in each iteration, search in the upper direction to find the max rectangle →TC=O(N^2M), SC=O(NM)
2. dp: one row array left, right, height
   - height as the vertical upwards height
   - left as the leftmost position between which and current position the height is larger than the current height
   - right as the rightmost position between which and current position the height is larger than the current height
   - pay attention to the iterations
198 House Robber
- dp -> maintain max money til current position
- pay attention to the cases of 0/1