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

ZigZag level order---BFS , 可以用deque 或者改变加入顺序实现
Path Sum, Path Sum II - 保持prefix sum Array, get 从root 到leaf 得每个root.val
Path Sum III- 转化成 subarray 等于target问题相当于
Continuous Subarray Sum, Subarray Sum Equals K, Maximum Size Subarray Sum Equals k
这三道题本质都是将prefix sum 存入map 中, 如果后面遇到prefixSum – target 存在map中情况，说明存在equal k 情况。 几点注意： 1， put (0, 1) into the map 2. if duplicate, update the frequency.
3.first check if(maps.cotainsKey(prefixSum - target)) , then  update new prefixSum. 避免（找0出现错误）4, 根据实际情况可能加入（prefix, index）等等
Minimum Size Subarray Sum： 不是找equal K， 因此实用two point 解决

缺米中，求大米

07/22 三题一遍通过 记录一下

最小路径和   很容易想到递归搜索实现 一般来说会超时 所以用memo存储 -> 可以转化为dp, dp尝试也通过  注意是从终点向起点
有效的回旋镖  如果直接利用斜率需要判断非零 与否  ->转化成乘法 本来会有些cornercase 没想到也一遍过了 意外
单词的规律  关键是如何建立对应关系 可以用map 优化查询是否mpa已经存在 可以用set

打卡题
Binary Tree Zigzag Level Order Traversal - 记录当前层节点个数，然后倒计。即可不用额外空间分辨层数
Minimum Path Sum  - 基本熟练，但是本题可以改原表

菜鸡七月第二十三天

1. binary tree zigzag traversal1: july challenge里面的，之前做过复习一下，可以用bfs加一个boolean 来存需不需要reverse，每一层
    如果不reverse就正常加，reverse就把node加到array前面，每层之后再flip reverse
2. lowest common ancestor of binary tree: 如果root 和p，q相等，或者root是null的话，就return root，然后再root.right和root.left
    上分别找lca，如果左边找的最后是null就return右边的结果，右边找出来是null就return左边的结果
3. uncrossed lines: 这个用dp做，如果两个array的i，j index value相等就说明可以画一条新的线, 一共是1+ dp[i-1][j-1]，不然的话就找
    max(dp[i][j-1], dp[i-1][j])
4. longest continuous increasing subsequence: 可以用sliding windows，如果不符合increasing的条件的话就把window start移到当前
    index，不然的话每次求i- start + 1看看能不能update 最大window长度
5. possible bipartition: 先set up graph的adjacency matrix，然后再用dfs看能不能把有edges相连的两个node分开，感觉graph的题还
    是不太会做

今天找到了好的总结leetcode的文章，按照上面做了两道字符串的题目，再做了一道leetcode的题

七月第二天
学习了摩尔投票

今天花了点时间复习了BehaviorQuestions
刷了俩题练手：

7.22 day17 July LeetCoding Challenge

Day 8
复习binary search，开始联系line sweep
Peak Index in a Mountain Array: binary search
Find the Duplicate Number: 两种方法
方法一：binary search O(nlogn),每次iteration筛掉一半的数
方法二：快慢指针，类似找linked list的循环，很难想到
Meeting Scheduler: line sweep

Day 12

103. Binary Tree Zigzag Level Order Traversal, 比较有趣的一道题 用stack + tree bfs
1060. Missing Element in Sorted Array, binary search 主要是array index和int interval长度计算混在 一起