Lunski's Clutter

This is a place to put my clutters, no matter you like it or not, welcome here.

0%

程式語言

Posted on Edited on In
Symbols count in article: 5.1k Reading time ≈ 5 mins.

為了因應近期的新目標，以往的工作與興趣文章將整合，這種不向前兼容的改動在git上應該稱為硬分岔吧，但熊生就是需要破壞式創新啊（掩。

接下來將進行為期一個月的程式文章，但不像以前做過的30天挑戰，我會不斷更新這張表。

Big O

完成某事需要多久時間，一般來說nˆ2程式效能就很糟了

O(1): Constant, hashmap, queue的pop
O(logn): Logarithmic 遞迴，每次步驟砍半, Binary Search
O(n): Linear [List, queue, stack的pop(idx)], BFS, DFS
O(nlogn): Sub-quadratic(Linearithmic), Quick/Merge/Heap Sort
O(nˆ2): N square(Quadratic) 二次方 two layer for loop
O(nˆ3): Cubic
O(2ˆn): Exponential 遞迴，每次步驟倍增，遞迴Fibonacci
O(3ˆn)
O((n/2)ˆn/2)
O(n!): Factorial

每次步驟少一半log n (Binary Search
每次步驟多2倍2^n (遞迴Fibonacci

Search Time Complexity

BFS:
TC: O(V+E) # 最糟時要走過所有點跟邊
SC: O(Vˆ2) # queue中每個點又接多個點

DFS:
TC: O(V+E) # 最糟時要走過所有點跟邊
SC: O(h) # recursive: 樹的層數
SC: O(Vˆ2) # stack中每個點又接多個點

Strategy

  • 暴力(枚舉)法(Brute Force)：常是quadratic
  • 貪婪法 (Greedy Algorithm)：每步擇優
  • 分治法 (Divide and Conquer)：快速跟合併，還有二元搜尋
  • 回溯（Backtracking)： 列出每階段可能，排除不可能，下階段沒分支就退回： dfs，01背包問題，每步看要不要
  • 分支限界（Branch and Bound method)：bfs
  • 動態規劃(Dynamic Programming)：分治小問題，但跟分治法不同是多了儲存子問題結果

Detail

  • 要最大最小：Heap
  • 給有序陣列： Binary search, Two pointers
  • 給串列：Two pointers
  • 需要所有排列或子集： Backtracking/ BFS
  • 給樹狀結構/圖： DFS, BFS
  • 限制不能遞迴： Stack
  • O(1) time & O(n) space: HashMap/Set
  • O(nlogn) time, O(1) space: Sorting
  • Strings Bunch：Trie
  • LinkedList no extra space: Fast Slow pointer
  • in-place： Swap, Pointer
  • 要maximum/minumum subarray/subset/options：Dynamic programming

Bit Manipulation

將數字轉bit處理，先不考慮String轉Int

7.Reverse Integer
136.Single Number
338.Counting Bits
187. Repeated DNA Sequences

Strings

子字串
加解壓
32.Longest Valid Parentheses

Arrays

針對陣列操作，常須in-place 或跟其他資料結構搭配

  • Two Pointer
    常見方式可以從左右兩端指定索引往中間移動，或快慢指針同方向，常用來檢測串列是否有迴圈。

  • Sliding Window
    找出某一個區間或一個連續範圍是某滿足條件。

  • In-place
    在不用多餘空間前提下操作原陣列取得結果。

1007. Minimum Domino Rotations For Equal Row
1.Two Sum
287.Find the Duplicate Number
605.Can Place Flowers
122.Best Time to Buy and Sell Stock II
55.Jump Game
66.Plus One
基本計算機
448.Find All Numbers Disappeared in an Array
287.Find the Duplicate Number
46.Permutations
47.PermutationsII
77.Combinations
78.Subsets
239. Sliding Window Maximum
394. Decode String

735.Asteroid Collision while a < 0 and s and s[-1] > 0
424.longest repeating character replacement: defaultdict; sliding window
647.Palindromic Substring s[l] == s[r]
202.Happy Number
844.Backspace String Compare pop()
977.Squares of a Sorted Array *=, sort()
228.Summary Ranges "".join([str(start),"->",str(n)])
946.Validate Stack Sequences popped = deque(popped)
1423.Maximum Points You Can Obtain from Cards current_pick += (cardPoints[right] - cardPoints[left])

Two Points

392.Is Subsequence
42.Trapping Rain Water

Sliding Window

1046.Last Stone Weight sort(), pop()

Intervals

207.Course Schedule
210.Course Schedule II
252.Meeting Rooms
253.Meeting Rooms II

In-place

189.Rotate Array
833. Find And Replace in String

Sort

Quick Sort: Average: O(nlogn), Worse: O(nˆ2), SC:O(n)
Merge Sort: Average: O(nlogn), Worse: O(nlogn), SC:O(n)

2D Array

48.Rotate Image: *, [::-1], zip
54.Spiral Matrix: pop(0), pop(-1), pop(-1) [::-1], pop(0)[::-1]
6.ZigZag Conversion res = [[] for i in range(numRows)]
256.Paint House red=min(blue, green) + r 或用dp, dp[i][j] += min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3])
931.Minimum Falling Path Sum

Famous Algorithm

53.Maximum Subarray

LinkedList

206.Reverse Linked List
141.LinkedList Cycle
138.Copy List with Random Pointer

234.Palindrome Linked List: [::-1]

Tree, Stack, Queue

前中後序走訪，常搭配遞迴函式解決樹的問題。

198.House Robber
100.Same Tree Self.SameTree()
203.Remove Linked List Elements: recursion head.next
226.Invert Binary Tree if not root: return None
543.Diameter of Binary Tree diameter = depth(root.left) + depth(root.right)
617.Merge Two Binary Trees merge to one tree

Searching

搜尋一般會先Sorting，二分搜尋先訂左右介，再不斷於子集找中間floor/ceil

Linear Search: O(n)
Binary, Interpolation, Exponential Search: TC: O(logn), SC: O(1)

33.Search in Rotated Sorted Array Binary Search[return index]
153.Find Minimum in Rotated Sorted Array Binary Search[return min]
875.Koko Eating Bananas Binary Search[return min speed]
1060.Missing number in sorted array Binary Search[return k-th missing number]

BFS/DFS

  • Depth First Search
    深度優先搜尋常用Stack實作，對樹狀結構特定形式的回溯
  • Breadth First Search
    廣度優先搜尋常用Queue實作

127.Word Ladder BFS, collections.deque([beginWord])
323.Number of Connected Components DFS, collections.defaultdict(list)
547.Number of Provinces DFS, for city, edges in enumerate(isConnected)
695.Max Area of Island DFS, dfs(r,c)
366.Find Leaves of Binary Tree DFS, dfs(root)
200.Number of Islands self.dfs(x, y, m, n, grid)

Backtracking

回溯是種通用算法，用於尋找某些計算問題的所有（或部分）解決方案，過程中使用遞迴，逐步構建解決方案的候選者，並在確定候選者不能導致有效解決方案時立即放棄候選者，所以比暴力法快。

很多人誤認 backtracking 就是圖論中的 DFS ，然而兩者沒有關係。兩者相似的地方是： Backtracking 遇到不合理的解答會馬上回溯， DFS 遇到拜訪過的節點會馬上回溯。 ref

實際上Backtracking問題都可用DFS解，反之亦然。

Dynamic Programming

類似回溯，但問題可以被分解為相似子問題，且有最優子結構(轉移方程式)

Fibonacci

後項為前2項相加

53.Maximum Subarray Kadane's algorithm
121.Best Time to Buy and Sell Stock Kadane's algorithm
70.Climbing Stairs Fibonacci: F[0], F[1], F[2] = 0,1,2
1553.Minimum number of Days to eat Oranges 1 + min(n%2 + count(n//2), n%3 + count(n//3))
1871.Jump Game VII dp[i+1-minJ]-dp[i-maxJ]*(i>=maxJ)
91.Decode Ways dp[i] = dp[i-1], dp[i] += dp[i-2]
1048.Longest String Chain max(1 + d[prev], d[word])

0/1 Knapsack

每商品有重量跟價值，每商品只能取一次，在不超過限定重量下得到最大價值

62.Unique Paths dp[i][j]=dp[i-1][j]+dp[i][j-1]
63.Unique Paths II dp[i][j]=dp[i-1][j]+dp[i][j-1]
64.Minimum Path Sum grid[r][c] += min(grid[r - 1][c], grid[r][c - 1])
494.Target Sum dp[(index, s)] = helper(index + 1, s + nums[index]) + helper(index + 1, s - nums[index])

Unbound Knapsack

其他條件跟ZeroOne一樣，但每商品可以取無限次

39.Combination Sum for comb in dp[i-c]: dp[i].append(comb + [c])
139.Word Break if dp[indx - len(word)] and s[:indx].endswith(word):
322.Coin Change dp[i] = min(dp[i], 1 + dp[i-coins[j]])
518.Coin Change II dp[i] = dp[i] + dp[i-coin]

可以沒有一次就成功的實力, 但一定要有再次挑戰的勇氣。

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Welcome to my other publishing channels