SP Hou

用二元搜尋找(猜)平方根,
用乘法:
乘法概念是比較容易理解的,但x的範圍是0~(2³²)-1,有機會在做了x的平方,會超過integer的範圍,所以要將這個部分的type用long (2⁶³-1)。
用除法:
商會落在int的範圍內,
x=n*n,n是x的平方根,所以n=x/n
product=mid*mid,mid是x的平方根,所以mid=p …

--

--

Making a note about binary logic.
[AND &]
Both elements are 1 get 1.
0&0=0
0&1=0
1&0=0
1&1=1

[OR |]
One element is 1 get 1.
0&0=0
0&1=1
1&0=1
1&1=1

[XOR ^]
Two different elements get 1, and the same element gets 0.
0&0=0
0&1=1
1&0=1
1&1=0

[NOT !]
change 1…

--

--

題目要求將同樣字母組成的字串分類成一個群組,所以將每個字串轉成char[]並且sort,sort後再重組成字串當map的key,把原字串加進去value(value的type是List<String>),最後把values全部倒去List<List<String>>並回出去。

This problem request to classify by a string of the same letter. I split the string into a character array and sorted it. Restructure the sorted char array to a string and it will be a key to the map. Added original string into the value of the map…

--

--

題目要求實作insert, remove, getRandom,開一個Map去紀錄值與位置,開一個List去紀錄掃過的值,並且之後要準備用List去做getRandom的隨機輸出。
insert: 加到Map與List中
remove: 從Map與List中移除該數值。移除前,要先將List中最後一個值放到將被移除的數值的位置,並且更新在Map的Key與Value。
getRandom: 以List的size隨機產生一個數,將此數輸出,這樣就可以達到the same probability

This problem requests to implement insert, remove, and get the random element. I am creating a Map to record value and index. Creating a List to record the value that was inserted.
insert: add value to map and list.
remove: remove…

--

--

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

這題就是我們小時候玩的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棧頂的絕對值, …

--

--

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…

--

--

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…

--

--

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

--

--