重拾leetcode，每天至少两题

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-14

121. Best Time to Buy and Sell Stock
953. Verifying an Alien Dictionary

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

56. Merge Intervals

2021 05-15
94. Binary Tree Inorder Traversal
144. Binary Tree Preorder Traversal

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
            

2021 05-17
今天加班好累😭 来两道简单题
226. Invert Binary Tree
543. Diameter of Binary Tree

2021-05-18
98. Validate Binary Search Tree
recursive  或者 iterative （In-Order traversal will get a increasing sequence if it's a valid BST）

545. Boundary of Binary Tree
题目的descrption 不太清楚但是还是做出来了，快乐！

2021-05-19
最近上班真的累死。。。下班健身都没劲了😒，但是刷题还是不能停的

617. Merge Two Binary Trees
iterative  --> 类似level order traversal， 不过我们处理的是node pair，如果两个node 的 left/ right child 均不是null， 变为新的node pair 加入queue， 否则 node1.left/right 为两个节点中非null的left/right child

103.Binary Tree Zigzag Level Order Traversal  
level order traversal  判断奇偶level， 偶数level list.add(0,node.val);

99. Recover Binary Search Tree
for BST , left < root < right,
so if we traver in inorder, will get an increasing sequence
if 2 node are swapped, then there will be 2 turing point in the sequence
pre > cur == > pre is the first node
pre > cur  == > cur is the second node
转化为 find 2 number swapped in an sorted list

2021-05-21
tree 的题目套路学会了就做起来很流畅

1161. Maximum Level Sum of a Binary Tree

173. Binary Search Tree Iterator

107. Binary Tree Level Order Traversal II
巧用 List.add(0,temp)   同时新的level index 变为 list.size() - old_index