SP Hou

最近又接了一個案子小忙,有點拖~但還是每天都會刷一題,只是不一定有時間寫紀錄,還是會寫,只是慢了一點~

這題就是我們小時候玩的1A2B遊戲,go through一遍secret和guess的全部元素,就可以找出A的部分,同時也在secret和guess同位置但不同字元時,將secret的該字元計數。接下來歷遍guess,並將有出現在map中的元素做遞減同時計數B,當遞減到0的時候,就把這個元素移除。

Traverse element of secret and guess at the same time. The count will be pulsed one when the guess character is the same as the secret character at the same index. If the secret and guess character are different, the character will be put in map and…

--

--

行星碰撞條件是: 1. 兩個行星要不同的方向 2. 行星是依序碰撞的,不會跳著碰撞 3. 小的行星會被撞毀,一樣大小的時候會兩個都撞毀 4. 後者往前看要撞擊的行星,如果被撞掉了,就再繼續往前比較 5. 當前者為負的,後者為正的,不會被撞掉 因為要一直往前追著碰撞,所以用stack去存放前面的行星。當現在的行星的絕對值小於stack棧頂的絕對值,則表示當下的行星會被撞毀,當現在的行星的絕對值等於棧頂的絕對值,表示兩個都會被撞毀。當現在的行星的絕對值大於棧頂的絕對值,表示棧內的會被一直追朔到棧頂的行星與當下行星方向相同、棧被撞光了或是棧頂比當前行星還要大才會停下來。直到歷遍全部的行星。最後,將棧內剩下的全部倒到array中輸出。 Asteroids collision conditions are: 1. They are in different directions. 2. Asteroids collide in order in the sequence. 3. The small one will explode. The same size will explode with each other. 4. back one collides front one, if the front is explode, the back one will collide continuously. Until all ahead asteroids explode. 5. When the front one is negative, and the back one is positive, they won’t collide. with the mention above, I got those conditions: current<top of the stack: current will collide. The current asteroids will not be kept. current = top: current and top will collide. the top one will be removed from the stack. current>top: collide continuously.

[Java][LeetCode][Stack]Asteroid Collision #735
[Java][LeetCode][Stack]Asteroid Collision #735

行星碰撞條件是:
1. 兩個行星要不同的方向
2. 行星是依序碰撞的,不會跳著碰撞
3. 小的行星會被撞毀,一樣大小的時候會兩個都撞毀
4. 後者往前看要撞擊的行星,如果被撞掉了,就再繼續往前比較
5. 當前者為負的,後者為正的,不會被撞掉
因為要一直往前追著碰撞,所以用stack去存放前面的行星。當現在的行星的絕對值小於stack棧頂的絕對值,則表示當下的行星會被撞毀,當現在的行星的絕對值等於棧頂的絕對值,表示兩個都會被撞毀。當現在的行星的絕對值大於棧頂的絕對值,表示棧內的會被一直追朔到棧頂的行星與當下行星方向相同、棧被撞光了或是棧頂比當前行星還要大才會停下來。直到歷遍全部的行星。最後,將棧內剩下的全部倒到array中輸出。

Asteroids collision conditions are:
1. They are in different directions.
2. Asteroids collide in order in the sequence.
3. The small one will explode. The same size will explode with each other.
4. back one collides front one, if the front is explode, the back one will collide continuously. Until all ahead asteroids explode.
5. When the front one is negative, and the back one is positive, they won’t collide.
with the mention above, I got those conditions:
current<top of the stack: current will collide. The current asteroids will not be kept.
current = top: current and top will collide. the top one will be removed from the stack.
current>top: collide continuously.

--

--

DFS用遞迴的方式,BFS用Queue的方式。
歷遍所有1的位置,再藉由這個位置,將該位置的上下左右都蓋為0,一邊歷遍,一邊蓋0,要注意的點是:
1. 上下左右的位置必須在有matrix圍內:

x≥0 && x<grid.length && y≥0 && y<grid[0].length

2. 上下左右的值為1

grid[m][n]==’1'

DFS is with recursive, and BFS is with Queue.
Traversal all position of ‘1’. Dependent on the position, change the value of neighbors to ‘0’. Keeping in mind:
1. Positions of neighbors are inside the edge of the matrix.

x≥0 && x<grid.length && y≥0 && y<grid[0].length

2. the value of the neighbor is ‘1’

grid[m][n]==’1'

--

--

Time complexity is O(m*n)

題目要求找出每個元素離最近的0的距離,
1. 找每個1,然後去找最近的0,特殊案例就是大多都是1,只有一個0
2. 找每個0,然後去找0附近的1,特殊案例就是大多都是0,只有一個1
因為是一個一個往外擴散,所以適用BFS。

“return the distance of the nearest 0 for each cell”
consider 1. find each 1, then find the nearest 0 and count the distance. The worst case is [[1,1,1],[1,1,1],[1,0,1]].
consider 2. find each 0, depend on the coordinate of 0 to search 1 and calculate the level. The worst case is [[0,0,0],[0,0,0],[0,0,1]].
level by level to search is qualify BFS.

--

--

試著去用DFS跟BFS來做,兩個都是O(N),沒什麼太大的差別。
DFS:
開一個全域的sum好讓之後左右tree都掃完的時候把值回出去。因為每次都要將上層累計完的值*10再加上自己node的值,所以要把上層計算完的值丟給子節點。直到node的左右兩邊都為空的時候,表示已經掃完全部,就可以跳開這個遞迴。
BFS:
開兩個Queue,一個要放node,一個要放上一層計算完的值,因為一樣要把計算完的值丟給下一層計算,當前的這個node的左右都沒有子節點時,視為該邊已經掃完了,將累計的值丟到List記起來,之後要算總和的時候要用到。當左(右)子節點不為空的時候,把該邊的子節點以及計算好的值丟到相對應的Queue,以便進到下一層。

Implement with DFS and BFS, the time complexity both are O(N).
DFS:
Create a global variable to return the sum when the tree is traversal done. The number of each level is the number of the last level multiple 10 and adds the current node value. The number needs to be delivered to the next level. Until, all nodes were traversed, quite the while loop.
BFS:
Create two Queue, one is to keep the node, and one is to keep the number of the last level calculated. While this side of the tree is traversed, put the number into a list, I will calculate the sum when the two sides of the tree are finished.

--

--

標準錯的方法,就是一直做modulo直到n=0,接著兩兩比對相鄰的,如果發現有相鄰的1,就表示non-sparse,但這樣做的時間複雜度是O(N logN),在遇到n(大約200000000)為大數時,不意外的就gg了...所以改成將n右移1,再將兩個做AND,如果是sparse,就會為0,否則為1。

The wrong approach is to do modulo and keep modulo in the list until n=0. Pair compare each other. Even I can get the binary array of n and through the pair compare to check n is sparse or not. But when n is a larger number( n=60000), it will get a run time error. The correct approach is: to right-shifted n and process AND with n to figure out whether n is sparse or not. If n is sparse, it will get 0, else get 1. the Time Complexity is O(1).

--

--

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

第一次的時候沒有注意到那句話:

imagine yourself standing on the right side of it

就只有看到,right side阿~標準的眼殘導致腦殘...第一次的時候就直接輸出right side,當然就GG了,回頭再看那句話才發現自己的蠢,我想到的解法是: 每層保留最後一個val就好,一層中的其他數值也就不用管它了,結束。

The first time, I did not take care that sentence:

imagine yourself standing on the right side of it

I just only saw right side. I output all right side elements. Absolutely, It is failed… I return to reading this problem again and saw the sentence. My approach is: to keep the last value at every layer, I don’t matter other values at this layer.

The code includes a test suit.

--

--

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

輸出是依層輸出,所以BFS起手式先來,題目要求要之字形,也就是說順排->逆排->順排->逆排...第一次我誤會成是要InOrder->PostOrder->InOrder->PostOrder…於是我就放了flag,true與false輪流來改變進Queue的順序,後來發現完全會錯意了...就改了順排逆排的方式,逆排的時候把list做反轉。最後再試試在LeetCode上面做test suit,剛好是個TreeNode跟雙層List都要自己做出來的例子...

output is dependent on Layer, so this problem is BFS. I need to output order and reverse order alternate. When this term is reverse order, I need to reverser list. The first time, I had wrong direction. I think is InOrder and PostOrder alternate.
This code include Test Suit at LeetCode.

--

--

Given the root of a binary tree, return its maximum depth. A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

好吧...開始面對Binary Tree的BFS...
題目就說要拿depth了,那就是"依層"的概念,以此判定為BFS依。
題Input可判斷為in order的tree,開一個Queue來放Node,開一個來計數幾層,每看一層就把計數+1,直到把tree歷遍。

Face to BFS of Binary Tree…
This theme of the problem is “Depth”, so it depends on the Level concept. This is the BFS concept. According to Input of example, this is In Order node. Initialize a Queue to keep node, initialize a counter to count node level, when it gets in a level, count will plus one.

--

--