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

打卡第十八天：
257， 129， 235

打卡第28天， 刷了3道题

39. Combination Sum
backtracking, 先排序

40. Combination Sum II
backtracking, 用dict计数，对keys排序

46. Permutations
backtracking, 把nums[0]插到permute（nums[1:]）中去

Day 9:
https://leetcode.com/problems/range-sum-of-bst
https://leetcode.com/problems/exclusive-time-of-functions
https://leetcode.com/problems/search-in-rotated-sorted-array/
https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

6.29 打卡三道Graph类型

06.28.2020
打卡第17天，刷题第17天，刷三题（温故而知新）
楼楼大大请加米啊！

1. Bucket Sort 的应用
Leetcode:220. Contains Duplicate III

//Mindset:
Use bucket sort;
use long to prevent overflow and defined every element in specific bucket by linear scan the whole array
bucket sort的核心是建立从array[i]到reconduct number的一个映射；
然后这个映射的逻辑和范围都是根据k 和t来进行界定的；
******

2.longest common subString
这个题目没有什么滑头的，用DP的知识来做就是老老实实的得用一个int[][]matrix这样的表格来记录当前的长度和start index
需要注意的是，如果i/j是0的话语，那么就需要给一个特殊条件判断；让result置为1；
public class Solution {
  public String longestCommon(String source, String target) {
    // Write your solution here
    // 基本的思路就是从头拿一个个的进行比较；这样等于是每个子循环里面就有一个n^2；total就是n^4；
    // 但是这样子效率就非常低了，因为有很多重复的计算（比如说在取substring的时候就特别缓慢）；
    // DP please
    // how? 还是新建一个int[][] matrix 把记录的最长index 摆进去；
    // corner case
    if (source.length() == 0 || target.length() == 0) {
      return "";
    }
    int longest = 0;
    int start = 0;
    int[][] result = new int[source.length()][target.length()];
    for (int i = 0; i < source.length(); i++) {
      for (int j = 0; j < target.length(); j++) {
        //这里的条件就是两个取charAt是相同的；
        if (source.charAt(i) == target.charAt(j)) {
          if (i == 0 || j == 0) {
            result[i][j] = 1;
          } else {
            //这里直接问斜角拿那个数即可；
            result[i][j] = result[i - 1][j - 1] + 1;
          }
          //check longest
          if (longest < result[i][j]) {
            //update longest;
            longest = result[i][j];
            start = i - longest + 1;
          }
        }
      }
    }
    return source.substring(start, start + longest);
  }
}

11.longest subsequence
Mindset:
DP O(n^2)
int[][] result = new int[s.length()][t.length()];
//和上面不同的是，更新的条件不仅仅是他们的char唯一相等，不相等的时候也可以更新的；
//如果不想等就照抄下来前面的数值就好；
//if (s.charAt(i - 1) == t.charAt(j - 1)) {
//然后index 从1开始的，就不能把index 为0这个条件忽略掉；得加上

6.29 day 30
494 medium 一开始只想到dfs，看了solution发现其实就是knapsack
498 medium 遍历数组，注意边界处理
528 medium 第一反应hashmap，但仔细读题发现行不通。看了solution意识到可以用cdf，从而转化为binary search

第六天，四题：
largest value in each tree row
minimum time diff
single element in sorted array
reverse string 2

Day 7, solved 6 problmes.

Tips:
1. For a simple DP problem, there could be a non-DP solution better than DP: e.g., LC 62;
2. For very simple problem as LC 414, we should make the code short, and we can learn more skills from others;
3. LC 413 looks difficult at first glance, but it turns out to be a relatively easy sliding window problem.

20200628:
3: 0332, 1155, 1360
4:
5: 0564

才知道可以刷题拿大米，昨日战果和今日战果，刷了几道medium和easy，有点滑水。