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

1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

題目
思路：

  • 要找的點是可到達的點的距離在 threshold 裡的那些點，所以要找的是最短距離，因為只要最短距離可以在 threshold 內，那它就是可到達的點
  • 用 Floyd-Warshall’s algorithm 找到所有點之間的最小距離
    • k 是 i 到 j 之間的任意點。比較 i -> j 經過所有 k 的距離，最小的即為 i -> j 的最短距離。
    • Question:
      if the path is i -> 2 -> 1 -> j and the iteration consider k == 1 first. But the dist[i][1] not yet populated and still have value of float('inf'). It will have the actual value until k == 2.
繼續閱讀
LeetCode Digest
5 分鐘 閱讀文 (大約 687 個字)

House Robber II

題目
思路

  1. 跟 House Robber 很像，只差在房子的排列變成頭尾相連，有沒有辦法把這題拆解，變成能用上第一版 House Robber 的解題方法？譬如把環形變回直排？
  2. 變成環形之後多出來的限制讓我們可以把這題分成以下三種情況：
    1. 搶第一個、不搶最後一個：加入第三種情況，等同於可以視為直排，但只考慮到倒數第二個
    2. 不搶第一個、搶最後一個：加入第三種情況，等同於可以視為直排，但從第二個開始考慮
繼續閱讀
LeetCode Digest
3 分鐘 閱讀文 (大約 384 個字)

House Robber

題目
思路

  1. 可以把得出答案的過程拆解為最小可重複步驟，用遞迴來解
  2. Recursive case: 假設 index 為 i，由 index 0 搶到 i 可得的最大收穫為 inner_rob(i)。在位置 i, 可選擇搶或不搶：
    1. 不搶：最大收穫跟前一個點一樣，為 inner_rob(i - 1)
    2. 搶：代表前一個點一定是不搶，所以最大收穫為這個點的 money nums[i] 再加上前前個點的最大收穫 inner_rob(i - 2)
    • 所以 inner_rob(i) 為以上兩種情況取較大的那個
繼續閱讀
LeetCode Digest
4 分鐘 閱讀文 (大約 564 個字)

Unique Paths

題目
思路

  1. 每走一步都會是一個 unique path，到終點的路線是由每一步所組成的，所以可以用遞迴的方式來想，最小的可重複動作就是一步，點 (i, j) 到終點的 unique path count 就是 (i + 1, j) 和 (i, j + 1) 的 unique path count 的和

  2. 最小可重複動作 return u_paths(i + 1, j) + u_paths(i, j + 1)

繼續閱讀

分類

標籤雲

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

×