LeetCode 652 Find Duplicate Subtrees
鏈接：https://leetcode.com/problems/find-duplicate-subtrees/
方法：遞歸、哈希、樹的編號
時間復雜度：O(n)洒缀，n為樹節(jié)點個數(shù)
想法：參考自花花醬https://www.youtube.com/watch?v=JLK92dbTt8k伦泥。想法是對樹結構進行哈希，使得相同結構的樹，哪怕不是同一棵、地址不一樣，也能對應到相同的值怜珍。這道題的其中一個做法是用二叉樹序列化，但顯然太麻煩凤粗。這里使用的是給二叉樹一個編號id的方法酥泛。每一個樹今豆，都用一個字符串代表（在下面代碼優(yōu)化為long類型數(shù)字），他可以是當前節(jié)點的值 + 左邊的id + ","+ 右邊的id柔袁。這樣遞歸到葉子節(jié)點呆躲，就會導致相同值的葉子節(jié)點，哈希出來的字符串是相同的捶索，那么遞歸一路返回就最后導致相同結構的樹對應的字符串完全相同插掂。還有一個counts的哈希表，是從id映射到個數(shù)腥例，表示能對應到這個id的樹有多少個辅甥。所以說每次發(fā)現(xiàn)ids這個map里面沒有哈希出來的字符串時，就新開一個id燎竖，為ids.size() + 1璃弄。而每次counts里面得到一個值為2的key-value pair的時候，說明有某個id被重復用到了构回，說明以當前的節(jié)點為根的子樹遇上了重復夏块，加入結果中。
另外一個學習點：映射樹結構的時候纤掸，直接搞字符串拼接比較慢脐供，觀察到里面只跟root.val, left id, right id有關，并且題目的數(shù)字數(shù)據(jù)范圍允許茁肠，因此直接把三個值拼接成一個long類型的值患民，這樣查詢比拼接字符串然后查找字符串快多了缩举。
代碼：
class Solution {
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
List<TreeNode> res = new ArrayList<>();
Map<Long, Integer> ids = new HashMap<>();
Map<Integer, Integer> counts = new HashMap<>();
getId(root, res, ids, counts);
return res;
}
private int getId(TreeNode root, List<TreeNode> res, Map<Long, Integer> ids, Map<Integer, Integer> counts){
if (root == null) {
return 0;
}
long key = ((long)root.val << 32) | (getId(root.left, res, ids, counts) << 16) | (getId(root.right, res, ids, counts));
int id = 0;
if (ids.containsKey(key)) {
id = ids.get(key);
}
else {
id = ids.size() + 1;
ids.put(key, id);
}
int tmp = counts.getOrDefault(id, 0) + 1;
counts.put(id, tmp);
if (tmp == 2) {
res.add(root);
}
return id;
}
}
LeetCode 644 Maximum Average Subarray II
鏈接：https://leetcode.com/problems/maximum-average-subarray-ii/
方法：二分
時間復雜度：O(nlogL)垦梆，其中n是數(shù)組長度，L是數(shù)組當中值的值域范圍
想法：這個題寫的是hard仅孩，但其實倒也沒有那么難做托猩，它考察了幾個很好的知識點，相當于說是幾個medium的綜合題辽慕，那如果你對這幾個題中的任何一個做的不是很熟練的話可能這題就會GG京腥。首先是想到用二分答案來做。這題的兩個變量是最大平均值v和要求的子數(shù)組最小長度k溅蛉，其中被要求滿足的子數(shù)組最小長度k是自變量公浪，在此要求下的最大平均值v是變量，我們的二分答案是來二分變量船侧。非常直觀的想法是對于子數(shù)組最小長度k的要求越低欠气，能夠達到的子數(shù)組當中的最大平均值就越大。這樣先想清楚了問題的第一部分镜撩。
問題的第二部分：在一個數(shù)組中预柒，給定子數(shù)組的最小長度，怎樣高效地計算有沒有這樣的子數(shù)組，使得平均值大于等于某個值target宜鸯？這里有一個很巧妙的做法憔古，就是我不帶著原數(shù)組和平均值來找麻煩，我先在原數(shù)組里把所有數(shù)減掉target淋袖，這樣就把問題轉化為有沒有長度>=k的子數(shù)組鸿市，和>=0。這個就比剛才的問題簡單多了即碗，這樣我們就扔掉了“平均值”這個麻煩事灸芳，可以專心解決前綴問題。搞兩個算前綴的拜姿，一個叫l(wèi)eftSum烙样，從最左邊開始加，一個叫rightSum蕊肥，在它右邊k個單位處谒获。然后每次都更新一下這倆值，維護leftSum的最小值壁却。所以只要rightSum在任何時候>=了leftSum的最小值批狱，我們就找到了這樣的子數(shù)組，問題就解決了展东。這個方法需要學習掌握赔硫，我記得好像還有哪里用過，但我忘了盐肃，有時間找出那道題來再更新這個地方爪膊。
代碼：
class Solution {
public double findMaxAverage(int[] nums, int k) {
double left = -10000.0, right = 10000.0;
while (left + 1e-5 < right) {
double mid = (left + right) / 2;
if (canFind(nums, k, mid)) {
left = mid;
}
else {
right = mid;
}
}
return left;
}
private boolean canFind(int[] nums, int k, double target) {
double leftSum = 0, rightSum = 0, minLeftSum = 0;
for (int i = 0; i < k; i++) {
rightSum += (nums[i] - target);
}
for (int i = k; i <= nums.length; i++) {
if (rightSum >= minLeftSum) {
return true;
}
if (i < nums.length) {
rightSum += (nums[i] - target);
leftSum += (nums[i - k] - target);
minLeftSum = Math.min(minLeftSum, leftSum);
}
}
return false;
}
}
LeetCode 406 Queue Reconstruction by Height
鏈接：https://leetcode.com/problems/queue-reconstruction-by-height/
方法：貪心
時間復雜度：O(n2)
想法：主要是看能不能觀察到吧。每個pair第一個元素是高度砸王，第二個元素是前面有多少人高度>=他推盛。一個非常籠統(tǒng)的想法是谦铃，肯定是個子高的人比較好處理耘成，因為個子高的人前面比他個子高的人比較少，所以相對來說狀態(tài)沒那么復雜驹闰，所以做這道題應該從個子高的開始放瘪菌。然后對于個子一樣的人，第二個元素小的說明他站的更靠前一點嘹朗，所以這樣的也應該先處理师妙。那么根據(jù)上述的方案對原數(shù)組排序。排序之后發(fā)現(xiàn)其實直接把每個元素插入到結果list的對應的index上就完了骡显，這里的index就是每個人的pair的第二個元素疆栏。為什么這樣是對的呢曾掂？因為我們按照之前說的排序，當一個元素放的時候壁顶，后面還沒放的元素沒有比他個子還高的珠洗，當前已經(jīng)在list當中的元素要么是跟他一樣高，要么比他高若专，那這時候许蓖，比方說現(xiàn)在處理的人，pair第二個元素是3调衰，說明前面有三個人>=他的高度膊爪，那就直接插入到list第三個位置就滿足要求了熊镣。
代碼：
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (a, b) -> {
if (a[0] != b[0]) {
return b[0] - a[0];
}
return a[1] - b[1];
});
List<int[]> lst = new ArrayList<>();
for (int[] p : people) {
int index = p[1];
lst.add(index, p);
}
int[][] res = new int[lst.size()][2];
int tt = 0;
for (int[] p : lst) {
res[tt++] = p;
}
return res;
}
}
LeetCode 341 Flatten Nested List Iterator
鏈接：https://leetcode.com/problems/flatten-nested-list-iterator/
方法1：全展平
想法：我一開始的做法...不知道它要考什么兴使，就直接在constructor里面把NestedInteger全拍扁成Integer放進list了。
代碼：
public class NestedIterator implements Iterator<Integer> {
private List<Integer> lst;
private int i;
private int size;
public NestedIterator(List<NestedInteger> nestedList) {
this.lst = new ArrayList<>();
dfs(lst, nestedList);
this.i = 0;
this.size = lst.size();
}
private void dfs(List<Integer> lst, List<NestedInteger> nestedList) {
for (NestedInteger ni : nestedList) {
if (ni.isInteger()) {
lst.add(ni.getInteger());
}
else {
dfs(lst, ni.getList());
}
}
}
@Override
public Integer next() {
return this.lst.get(i++);
}
@Override
public boolean hasNext() {
return this.i < this.size;
}
}
方法2：棧
想法：這種想法是倒著把原本的list中的元素入棧夭咬，然后根據(jù)題目當中所說的調用方法趋箩，它每次會先調hasNext()赃额，再調next()，那每次在hasNext()里面把棧頂拍平叫确，保證棧頂元素一定要是Integer跳芳，這樣的話在next里面直接pop出來棧頂?shù)闹导纯伞?br> 代碼：
public class NestedIterator implements Iterator<Integer> {
private Stack<NestedInteger> stack = new Stack<>();
public NestedIterator(List<NestedInteger> nestedList) {
for (int i = nestedList.size() - 1; i >= 0; i--) {
stack.push(nestedList.get(i));
}
}
@Override
public Integer next() {
return stack.pop().getInteger();
}
@Override
public boolean hasNext() {
while (!stack.isEmpty()) {
NestedInteger head = stack.peek();
if (head.isInteger()) {
return true;
}
stack.pop();
List<NestedInteger> lst = head.getList();
for (int i = lst.size() - 1; i >= 0; i--) {
stack.push(lst.get(i));
}
}
return false;
}
}
