重拾leetcode，每天至少两题

我们的口号是：去大厂，拿大包！！！冲鸭！！！04/29/2021: 今天是sliding window 训练，做了 3, 567, 480 ,76

跳槽成功了！封贴哈哈！

2021-05-13

763. Partition Labels
O(nlogn)
我们提取出每个字母第一次和最后一次出现的位置，作为interval
可知 这些internal 是排序好的 且 所有interval的开始位置和结束位置是唯一的
因为每个位置都是唯一的编号 0，1，2，3，... s.length()-1
the interval is already sorted  p[0] < p[1] && p[1] < q[0]
此时我们只需要转化为merge intervals 就可以得到最后的parts
注意merge的时候左右区间相同时不merge eg【1，4】【4，6】 为两个区间
这样我们把此题转化为56 merge intervals

解法2: 时间复杂度O（n）
  记录s中所有字符出现的last index，开始遍历s中的所有字符，扩张区间从而找到符合题目条件的区间 【start，end】
  用 end 记录当前已经遍历过的字符的中位置最靠后的last index value
  如果当前 index == end，说明当前的区间中所有字符都只出现在这个区间中，符合题目条件，将区间长度 end-start+1 加入 result list 中

56. Merge Intervals

18. 4Sum
嵌套版 3sum。 遍历所有数字，并跳过重复数字， targetFor3Sum  = target - currentNumber,  3sum 从 current index +1 开始遍历

2021-05-16

102. Binary Tree Level Order Traversal  

104. Binary Tree Level Order Traversal   II

145. Binary Tree Postorder Traversal
非常巧妙的一个思路 转化为 preorder
    如何 把preorder 变形为 postorder？
        root->left->right   ==>  left->right->root?
        1. reverse order of preorder(by adding every val to 0 index in ArrayList)
         root->left->right => right-left-root
        2. by switch left and right  
          right-left-root => left->right->root
            

今日题目 323, 1072, 1004, 395, 340

2021-05-04   395 & 125

2021-05-05     11. Container With Most Water,  88. Merge Sorted Array,  3. Longest Substring Without Repeating Characters

2021-05-06  
524. Longest Word in Dictionary through Deleting( 类似 392 ). 206 .reverse linked list.  234. Palindrome Linked List(使用 206 reverse 一半的linkedlist)

2021-05-07   
287. Find the Duplicate Number：
一种非常美妙的思路能做到 O(1) space complexity & O(n) space complexity ：
创建一个映射 f(x) = nuns[x] ， 然后从 0 开始 跳转 到 nums[0] , nums[nums[0]], nuns[nums[nums[0]]] ......., 如果有 duplicate number 此时会产生一个环， 然后使用 floyd warshall 算法使用快慢指针就可以找到环的开始位置，也就是重复的number
利用此思路能把题目直接转化为 142 Linked List Cycle II


142 Linked List Cycle II
283. Move Zeroes

乱个楼，请问一下楼主在 icc 找到全职了吗

salinghang17 发表于 2021-05-08 15:56:23
乱个楼，请问一下楼主在 icc 找到全职了吗

培训没完我就跑路了，目前在一小start up做front end。

今日题目 16 & 293

最近手头工作有点多加上楼主有点累了，少了两天的本周会补上

2021-05-12
986. Interval List Intersections
利用两个指针指向两个list的初始位置，然后查看当前的两个interval 是否有重叠
        Yes -> add to result list
然后判断指针前进位置，右侧边界较小的一个指针前进（右侧边界较大可能还会有重叠产生）
eg [1,2] [5,7]
   [2,6]
   => [2,2] [5,6]

532. K-diff Pairs in an Array
首先对数组排序，然后依次遍历（跳过重复数字）每个数字（curNum），我们要找的数字就是 curNum + k,
        从 curNum 的 下一个数字开始遍历数组，
                如果找到 cnt++, loop break
                如果 当前数字 > curNum + k , loop break