Python Notes

解題

  • 找出所有可能變量, 注意其值域, 以及其不同值的情況下是否需要例外處理 (通常是最小最大值時)

  • 例如找最大值問題, 值域如果是-10~10, init不能是0, 而是要比-10小

  • 迴文 (Palindrome)、異位構詞 (Anagram)

    • 共通特性: 比較的兩個詞, 字母排序後會是一樣的

  • 畫出各種可能情境, 對應的處理結果

    • (e.g.,) 袋鼠跳躍問題 1. (X1>X2) Y OR N 2. (V1>V2) Y OR N, 得出四個象限, 先初步分析怎麼個別處理

  • Loop back問題, 善用取餘數(%)

    • 輪流分10顆糖果給3個人, 誰最後拿到?  🡪 10 % 3 = 1

    • 位子互換問題

List

  • 排序

    • List.sort() 而不使用 newList = sorted(list)

    • 前者為 in-place sort, 後者創新的list, 成本較高

  • Reverse

    • List.reverse(), in-place method

    • List[::-1]

    • newList = list(reversed(list))

  • Slice

    • 1D: [from:to:step], 不包含to

    • 2D reverse [[1,2,3] , [4,5,6] , [7,8,9]] 🡪 [(1,4,7) , (2,5,8) , (3,6,9)]

      • Use * and zip to invert the operation and unzip 2D array: zip(*list)

    • Numpy 2D and above: [1st D, 2nd D,…], for each [from:to:step]

enter image description here

  • List牽扯移動視窗 + 排序問題, 一律使用bisect (import bisect) 增加效率 (不用一直產生視窗、做排序)

    • Bisect用以管理排序後的List (使用前要排序)

    • bisect_left: 找到適合插入的index (同元素前面), O(log n)

      • 可用來判斷某元素在不在list

      • insertPoint = bisect_left(list, num); return list[insertPoint] == num;

    • insoft_left: 找尋並插入適合的index  (同元素前面), O(log n) + O(n)

  • 移動視窗問題

    • for x in range(len(s) - windowSize +1):

        slide = s[x:x+windowSize]

  • Enumerate index and value: for idx, val in enumerate(arr)

  • Complexity

Dict

  • 計算每個字出現次數, 可善用collections.Counter(r)

    • Just like dict[x] = dict.get(x, 0) + 1

    • 尋找沒有在Counter裡面的值, 會回傳0

    • 支援運算 e.g., Counter('abcccc') - Counter('cbd') # Counter({'a': 1, 'c': 3})

    • most_common() 可用來找出最常出現的k個key (sorted)

  • from collections import defaultdict

    • dict[x] = dict.get(x, 0) + 1 可改為 defaultdict(int)  & dict[x] += 1

  • Enumerate index and value: for key, val in dict.items():

  • Complexity (for dict and defaultdict…)

Set

  • 並集: set(a) | set(b)     OR     set(a).union(b)

  • 交集: set(a) & set(b)     OR     set(a).intersection(b)

  • 差集: set(a) - set(b)     OR     set(a).difference(b)

  • 對稱差集 (兩集合不重複的元素): set(a) ^ set(b)     OR     set(a).symmetric_difference (b)

    • = set(a) – set(b)   plus   set(b) – set(a)

    • a=[1,3,5]   b=[1,2,3]   =>   set([2, 5])

  • Complexity

itertools (import itertools)

  • List兩兩比對(不重複): itertools.combinations

    • for a, b in itertools.combinations(mylist, 2)

    • combinations([ABCD], 2) = AB AC AD BC BD CD # value pair

    • combinations(len([ABCD], 2) = 12 13 14 23 24 34 # index pair

    • 對照傳統寫法

for i in range(len(mylist)-1):

    for j in range(i + 1, len(mylist)):

Math

  • 善用取餘數

    • 2 / 3 = 0.66666 (真除法)

    • 2 // 3 = 0 (向下整除法, 無條件捨去)

    • 10 % 3 = 1 (取餘數)

    • i, j = divmod(10, 3) // 同時取商、餘數 (3, 1)

  • 階乘 math.factorial

    • math.factorial(4) = 24

    • 求取C幾取幾 Ci,j -  math.factorial(i)//(math.factorial(j)*math.factorial(i-j))

  • 次方: x ** y 

Map and Reduce

  • Map對每一個元素做操作

  • Reduce對每對元素做操作, 最後得出一個結果 (from functools import reduce)

    • E.g., 5! In one line: reduce(lambda x, y: x*y, range(1, 6))

Others

  • 賦值表達式 :=

  • Char to Int, and viceversa

    • chr(97) = ‘a’;   ord(‘a’) = 97

https://github.com/labuladong/fucking-algorithm

https://wiki.python.org/moin/TimeComplexity

https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

https://github.com/cy69855522/Shortest-LeetCode-Python-Solutions

留言

張貼留言