• Sports Programming 筆記

Sports Programming 筆記

Sports Programming，又稱 Competitive Programming
（演算法競賽、競技プログラミング）

 

Sports Programming 心得

確實確認問題的條件

與 Interviewee 的互動

復述問題予 Interviewee
  • 增加交流
  • 確認問題
向 Interviewee 仔細確認未於文字中詳細說明的部分

把問題數學化

冷靜並透徹地看待問題全貌

不要因為慌亂，或為了急著表現/開口填補空隙，而急就章地開始
冷靜地不慌不忙了解問題，適當地向 interviewee 確認有疑義的地方
去了解這個問題的全貌，才能最快接近好的方法

草擬幾個例子推演自己的構想

以草擬的方式，無須工整，演示並測試自己初步的構想

考慮極端特例

考慮 Corner Cases

 

範例：LeetCode #43. Multiply Strings

給定字串num1, num2，求兩者乘積(in str) ーー 考慮num1, num2有一者為零時 ⇒ 直接回傳零

 

範例：LeetCode 58. Length of Last Word

Given a string s consisting of words and spaces,
return the length of the last word in the string.

可能的特例：

  • s 結束於空格
  • s 只有 1 個 word 且不始於空格
    （即 last word 前無空格）

 

class Solution:
  def lengthOfLastWord(self, s: str) -> int:
    i = len(s) - 1
    first_non_space = -1
    for i in range(len(s) - 1, -1, -1):
      if first_non_space == -1 and s[i] != " ":
        first_non_space = i
      if first_non_space != -1 and s[i] == " ":
        return first_non_space - i
    return first_non_space + 1

 

範例：LeetCode 1232. Check If It Is a Straight Line

You are given an array coordinates,
coordinates[i] = [x, y],
where [x, y] represents the coordinate of a point.
Check if these points make a straight line in the XY plane.

Constraints:

  • 2 <= coordinates.length <= 1000
  • coordinates[i].length == 2
  • -10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
  • coordinates contains no duplicate point.

如果使用斜截式 y = m * x + b
應考慮豎直線的情況導致斜率 m 無法計算（分母 xi – xj 為 0）
（此題 input 的 coordinates 不包含一樣的樣本，
可以忽略有重複樣本的可能性）

 

class Solution:
  def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
    #if ()
    x1, y1 = coordinates[0]
    x2, y2 = coordinates[1]

    if x1 == x2:
      return all(x == x1 for x, y in coordinates[2:])

    m = (y2 - y1) / (x2 - x1)
    b = coordinates[0][1] - m * coordinates[0][0]
    for x, y in coordinates[2:]:
      if y != m * x + b:
        return False
    return True
考慮 Boundary Cases (Edge Cases)
確認 constraints

 

範例：LeetCode #1178. Number of Valid Words for Each Puzzle

Constraints:

  • puzzles[i].length == 7
  • Each puzzles[i] does not contain repeated characters.

這意味著len(set(words[i]))不可超過7

Coding 過程應注意事項

Coding 過程中切勿沉默不語，敘述你的想法給 Interviewee

適當地定義新變數去縮短名稱或使得其更容易理解

範例：top, left, right, button = rectangle

推導出最佳解之前

不要一開始就想著最佳解

不要自作聰明

束手無策時，適時地請求 Interviewee 的幫助

考慮最適合的 data structure

Submission Accepted 後試著計算 Time/Space Complexity，再嘗試思考是否有更好的解

關於 return

以「易懂」的立場，將回傳值變數命名為 result

result
ans, result, return

注意題目要求 return 的是什麼，避免做多餘的運算

例：

Run 之前

先在腦中 Debug

注意過程中是否有 index out of range
注意變數被使用及改變的時間點

 

範例：Leetcode # 152. Maximum Product Subarray

要 print() 出來 debug 的內容一定要設置為變數而不是運算式

以免運算式內容被修改了，但是 print() 裡沒有同步更新

先徵求 Interviewee的許可

array / str

如果覺得複雜時，可以嘗試逆著做回來

slicing 用的指標命名：start, stop

相關網站

LeetCode

小訣竅

LeetCode 的 Python3 內建 math, collections module

例題筆記

Pramp

例題筆記

相關心得

Algorithm 演算法

Complexity 複雜度

Recursion 遞迴

Brute-Force 暴力法/窮舉法｜Backtracking 回溯法

Sorting 排序

Binary Method 二分法

BFS and DFS

⭐️ Dynamic Programming

Disjoint Set Union (DSU)

Data Structure 資料結構

Stack

Monotonic Stack

Linked List

Graph

Heap 堆積

Tree

  • Ancestor Nodes:
    The parent’s parent, a node reachable by repeated proceeding from child to parent.
  • Descendant:
    A node reachable by repeated proceeding from parent to child. Also known as subchild.
  • Sibling Nodes: Child nodes with the same parent.
  • Neighbor: Parent or child.
  • Internal Node / Inner Node / Inode (for short) / Branch Node:
    Any node of a tree that has child nodes.
  • External Node / Outer Node / Leaf Node / Terminal node:
    Any node of a tree that does not have child nodes.
  • Breadth: The number of leaves.
  • Degree: 
    For a given node, its number of children. A leaf, by definition, has degree zero.
  • Degree of Tree:
    The degree of a tree is the maximum degree of a node in the tree.
  • Size of a Tree:
    Number of nodes in the tree.
  • Distance: 
    The number of edges along the shortest path between two nodes.
  • Diameter:
    The length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
  • Height: The length of the longest downward path to a leaf from that node.
    (The height of the root is the height of the tree.)
  • Depth / Level: The length of the path to its root (i.e., its root path). 
  • Width: The number of nodes in a level.
Binary Tree 二元樹
Lowest Common Ancestor

Priority Queue 優先權佇列

常見題型

Prefix Sum

Subarray Sums Divisible by K

⭐️ Parsing

Merge Intervals

列出所有排列/組合 List All Permutations/Combinations

請參考 Backtracking 回溯法

Permutations
Combinations

Two pointers | Sliding Window

String-Searching Algorithm

Rabin-Karp Algorithm｜Knuth-Morris-Pratt (KMP) Algorithm

 

Hash a String
class HashString:
  def __init__(self, init_str, method = 0):
    self.MOD = [
      10 ** 9 + 33, 
      2 ** 31
    ][method]
    self.RADIX = [52, 53][method]
    self.BIAS = [0, 1][method]
    self.MAX_WEIGHT, self.value = 1, 0
    for i, c in enumerate(init_str):
      self.value = (self.value * self.RADIX + self.ord(c)) % self.MOD
      if i > 0: self.MAX_WEIGHT = (self.MAX_WEIGHT * self.RADIX) % self.MOD
    self.cur_str = init_str
  
  def __str__(self):
    return self.cur_str

  def get_value(self):
    return self.value

  def ord(self, c):
    ascii = ord(c)
    if ascii >= 65 and ascii <= 90:
      return ascii - 65 + self.BIAS
    elif ascii >= 97 and ascii <= 122:
      return ascii - 71 + self.BIAS

  def popleft_append(self, c):
    self.value = (self.value \
                   - (self.ord(self.cur_str[0]) * self.MAX_WEIGHT) % self.MOD
                 ) % self.MOD
    self.value = ((self.value * self.RADIX) % self.MOD \
                    + self.ord(c)) % self.MOD
    self.cur_str = self.cur_str[1:] + c
    return self.value

 

Find Subtring(s) in String s
def find_substr(s, target, only_first=True):
  if len(s) < len(target): return -1 if only_first else []

  result = []

  target_v = [HashString(target, m).get_value() for m in range(2)]
  hashed_str = [HashString(s[:len(target)], m) for m in range(2)]
  for i in range(len(s) - len(target) + 1):
    if all(hashed_str[m].get_value() == target_v[m] for m in range(2)):
      if only_first: return i
      result.append(i)
    if i == len(s) - len(target): break
    for m in range(2):
      hashed_str[m].popleft_append(s[i + len(target)])

  return -1 if only_first else result

關於 2D 座標

我的常用自訂函式

Python

 

 

 

Last Updated on 2024/12/18 by A1go

目錄

→ 目錄
Bitnami