LeetCode Digest
3 分鐘 閱讀文 (大約 403 個字)

1046. Last Stone Weight

題目
最直覺的作法就是先排序，取出最重的兩個撞擊後，把剩下的放回去，然後重複以上步驟：

Intuitive Python 3 solution
1
2
3
4
5
6
7
8
def lastStoneWeight(self, stones: List[int]) -> int:
    while len(stones) > 1:
        stones.sort()
        s1 = stones.pop()
        s2 = stones.pop()
        if s1 != s2:
            stones.append(s1 - s2)
    return stones[0] if stones else 0

但這樣的時間複雜度為 O(n^2 * log n)，太大了，有沒有其他方法？

繼續閱讀
LeetCode Digest
7 分鐘 閱讀文 (大約 1076 個字)

733. Flood Fill

題目
紀錄一下一開始的思路，檢討錯誤，再整理最後的答案。一開始的想法：

  1. 這應該可以分解成最小可重複動作，用遞迴解看看
  2. 覺得可以用原本的 method 當遞迴函式，把 image, color 照樣傳入，sr, sc 為該點的座標
  3. 最小可重複動作：從當下這點擴散到周圍四個點
繼續閱讀
LeetCode Digest
1 分鐘 閱讀文 (大約 214 個字)

121. Best Time to Buy and Sell Stock

題目
思路

  1. 最直覺的想法是從頭開始 traverse array，針對每一個 price 都去算一次那個位置之後的所有可能利潤，不過這樣會是兩個巢狀 for-loop，時間複雜度是 O(n^2)，太大了
  2. 有沒有辦法只 traverse 一次 array 就好？
  3. 利潤是由買價和賣價得出，知道最低買價和最高賣價就可以得出答案。有辦法設定這兩個變數，然後隨著 array traversal 不斷更新嗎？
繼續閱讀
LeetCode Digest
1 分鐘 閱讀文 (大約 177 個字)

Single Number

題目

  1. 因為只能用常數的額外空間，且 array 裡的數字除了目標之外都會有兩個，所以朝 bitwise operation 的方向想
  2. 把 array 裡所有數字接連做 bitwise operation，假如有兩個一樣的數字，他們就會抵銷變為 0，即使不是連著做也一樣，所以最後的結果就是那個落單的數字
    • 可以想像所有數字都用二進位表示由上而下列在一起做計算，不管他們位置怎麼換結果都會一樣 (偶數個 1 會互相抵銷)

Python3 solution:

1
2
3
4
5
def singleNumber(self, nums: List[int]) -> int:
    r = 0
    for i in nums:
        r ^= i
    return r
LeetCode Digest
2 分鐘 閱讀文 (大約 282 個字)

3Sum

題目
思路：

  • 用三個指標，iterate 最左邊那個，找出對應於每個 left 指標的所有 result
  • 先把 nums 排序，如此移動 mid, right 指標時就有個依據

Python3 solution

繼續閱讀

分類

標籤雲

android array authentication binary search binary search tree binary tree bit manipulation breadth-first search database depth-first search distributed system django docker dokku dynamic programming graph greedy hash table heap heroku java jwt linked list matrix mysql paas package management pipenv postgresql python recursion shortest path simulation sliding window sorting stack string tree two pointers

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×