7月缺米的来刷题/Mock interview活动

78. Subsets 生成所有的subsets (2^n个) 递归或者回溯，solution里面提到一个有趣的解法是按顺序遍历index组成的bitmap
1512. Number of Good Pairs n^2 遍历两次 或者像2sum一样用额外的存储遍历一次
1513. Number of Substrings With Only 1s 单维dp
1514. Path with Maximum Probability 变种Dijkstra 找最大距离，并且是相乘

Maximum Product Subarray:
方法1: 可以prefixProduct + suffixProduc 的方式来求，一个array如果想扩大，左右都可以看，如果都是正数代表都可以扩展，一正一负，就扩展正的，一直到碰到两边都是负数，就又可以继续扩展。所以会有出入的就是遇到0的情况
方法2: 同时维持min 和max 的值，当nums[i] < 0的时候，swap（min, max)---》 因为大数*负数变小

Jump Game i / ii: Greedy
Greedy 的两道题目，每次看一个数字的时候，都维持住目前最远可以走多远，当做到这个最远能走到的位置的时候，就需要走下一步了。 这样才能保证最少的步数（每一步都最大化的趋向重点位置）

1. for(int i = 0; i < A.length - 1; i++){
   
2.             // 更新能到的最远位置
   
3.             rightmost = Math.max(rightmost, A[i] + i);
   
4.             // 走到当前的边界的时候，就需要走下一步
   
5.             if (i == end){
   
6.                 end = rightmost;
   
7.                 step++;
   
8.             }
   
9.         }

复制代码

Minimum Knight Moves：
可剪枝的BFS，因为八个方向上都会各有一个点可以到达远点，并且拥有同样的步数，所以这个时候只需要考虑一个象限中的可能性就可以了。

Line Reflection：
可以建立一个class Point ---》 然后 @Override equals(Object obj) 和 hashCode（） 来解决这个问题

今天刷了不少，这几道题比较有意思，可以看看

打卡终于第五天了，


102        Binary Tree Level Order Traversal       
101        Symmetric Tree         判断对称树
100        Same Tree       


这三个题都比较简单，我还差五分就188 就可以看面经了，希望大家帮我增五分呀

菜鸡七月第十二天

最近好热，今天毫无动力
1. subsets：之前做过今天复习一下，用backtracking，先sort array，dfs的时候可以直接把当前list加到result里，loop的时候根据index加对应的element，
    dfs之后记得去掉之前加进去的，注意dfs的时候带着当前index+1
2. insertion sort list: 就是insertion sort，先移current node直到prev.val > current.val, 然后再用另一个node找到应该插入的地方
3. ransom note: 可以用一个array来存magazine里面出现的字母的frequency，再看ransom note里面的，每次减去对应的count，如果可以用的count是0就
    return false
4. combine two tables: sql，用的left join，因为一个table有可能是null
5. maximum depth of N-ary tree：和binary tree差不多，只不过每个child都call一遍recursive function，或者用BFS做，每一层+1，最后的层数就是max
    depth

这两天毫无动力，希望明天会好一点

Jun 11  打卡第10天，3道题 + contests
1510. Stone Game IV, minimax+dp; 其实不用去关心当前的player是谁，只需要知道n，来判断在n的时候player能不能win；[continue thinking…];
1010. Pairs of Songs With Total Duration Divisible by 60, map TC还是比array高，可以用长度为60的array；
1514. Path with Maximum Prob, 可以使用PQ，直接用queue+probOptimal[]，需要注意optimal需要在queue.offer的时候就更新，否则TLE；

day6，继续backtracking，简单的差不多搞懂了
dfs更加intuitive，和tree相反

0711 Day10 打卡四题

Path with Maximum Probability，dijkstra，不可以DFS+MEM，因为到每个点的路径会影响这个点到终点的距离，即不满足独立子问题这一dp前提
Number of Substrings With Only 1s，dp，记录每位之前连续1的个数，dp数组的和即为答案
Number of Good Pairs，简单的array题，O(n^2)遍历所有组合
Subsets，backtracking或是通过二进制编码来确定可能的子集

day 2 打卡5题

July 第九天打卡了
Subsets:  标准 Backtrack题，
Reformat Date:
Number of Good pairs: O(N^2) to O(N) 优化
Number of Substrings with Only 1's:
Path with Maximum Probability: BFS

今天刷了4题
分别是：
Path with Maximum Probability
Number of Substrings With Only 1s
Number of Good Pairs
Subsets

刷的这4题都不难。但是昨天新出的那道难题是数学题，我就没心思去看了