competitive programming的tips

動機

現在習慣寫LC，都已經忘了怎麼用c++或是python來讀stdin，所以來整理一下

C++

stdin

一般(空白分隔)

int n;
while (n << cin) {}

一整行

string name;
while (getline (cin,name)) {}

其他(有分隔號)

string name;
while (getline (cin,name,',')) {}

file

open

基本都是fstream，但如果只是要讀或寫可以直接用ifstream或ofstream

string name;
ifstream fs;
  fs.open("test.txt");
  while (getline(fs,name)) {}

read

同stdin(cin)

map, unorder_map (set與其實是一樣的東西)

map就是自平衡二元搜尋樹，好像是rbtree，所以這個會替key排序 unorder_map自然就是hash table了

iterate(C++11): for (auto& kv : a_map) { kv.first,kv.second; }
iterate: for (map<string, int>::iterator it = a_map.begin(); it != a_map.end(); it++) { it->first,it->second; }

string operation

cast

string->int

// C++11
#include <string>
int n = stoi("123");
double nn = stod("1.23");

// C++98
#include <sstream>
int i;
double d;

// string -> integer
std::istringstream ( "123" ) >> i;

// string -> double 
std::istringstream ( "1.23" ) >> d;

int->string:

// C++11
#include <string>
string n = to_string(123);
string nn = to_string(1.23);

// C++98
#include <sstream>
std::ostringstream ss1,ss2;

ss1 << 123;
ss2 << 1.23;
cout << ss1.str() << ',' << ss2.str();

common operations

substr: str.substr(start, len)
length: str.length()
reverse: string reversed(str.rbegin(), str.rend()); or std::reverse(copy.begin(), copy.end());
split(string -> vector
)
- 用find找pos再substr，之後erase
- 如果只有char用stringstream會好打一點

// for string delimiter
vector<string> split (string s, string delimiter) {
    size_t pos_start = 0, pos_end, delim_len = delimiter.length();
    string token;
    vector<string> res;

    while ((pos_end = s.find (delimiter, pos_start)) != string::npos) {
        token = s.substr (pos_start, pos_end - pos_start);
        pos_start = pos_end + delim_len;
        res.push_back (token);
    }

    res.push_back (s.substr (pos_start));
    return res;
}

vector operation

pop, push_back
slice: std::vector<int>(v1.begin(), v1.begin()+ len); (創一個新的)
length: vec.size()
iterate: for (auto& item : vec) {}
reverse: vector<int> reversed(vec.rbegin(), vec.rend()); or std::reverse(copy.begin(), copy.end());
map(C++11): std::transform(nums.begin(), nums.end(), nums.begin(), [](int num) {return std::pow(num, 2);});
filter(C++11): std::copy_if(nums.begin(), nums.end(), std::back_inserter(odd_nums), [](int num) {return num & 1;});
reduce(C++11): #include <numeric> std::accumulate(vector.begin(), vector.end(), decltype(vector)::value_type(0));

union find

unordered_map<int,int> fd;
vector<int> rank;

int find(int i) {
  while (i != fd[i])
    fd[i] = fd[fd[i]], i = fd[i];
  return i;
}

void union(int i,int j) {
  int a = find(i), b = find(j);
  if (a != b) {
    if (rank[i] > rank[j])
      fd[j] = i, rank[i]++;
    else
      fd[i] = j, rank[j]++;
  }
}

trie

struct Trie {
   unordered_map<char, struct Trie*> nextLevel;
   bool end;
    
    ~Trie() {
        for (auto& kv : nextLevel) {
            delete kv.second;
        }
    }

   void insert(string s) {
        Trie* trie = this;
        for (auto& c : s) {
            if (trie->nextLevel.find(c) == trie->nextLevel.end()) {
                trie->nextLevel[c] = new Trie();
            }
            trie = trie->nextLevel[c];
        }
        trie->end = 1;
    }

    bool search(string s) {
        Trie* trie = this;
        for (auto& c : s) {
            if (trie->nextLevel.find(c) != trie->nextLevel.end()) {
                trie = trie->nextLevel[c];
            } else {
                return 0;
            }
        }
        return trie->end;
    }
    
    bool startsWith(string s) {
        Trie* trie = this;
        for (auto& c : s) {
            if (trie->nextLevel.find(c) != trie->nextLevel.end()) {
                trie = trie->nextLevel[c];
            } else {
                return 0;
            }
        }
        return 1;
    }
};

Python

stdin

要記得rstrip，不然會有newline

import sys

for line in sys.stdin:
    line.rstrip('\n')
    print(line)

這裡有分隔號的讀嗎? 其實有但很少用，而且要在open file時指定，不如用split，還比較快 python的split不用自己刻

file

with open("file.txt",'wr',encoding='utf8', newline='\r\n') as file_in:
    lines = []
    for line in file_in:
        lines.append(line)
    file_in.write('write some str')

dict operations

iterate

for (k,v) in dd.items(): # keys, values
    print(k,v)

string operation

str -> int or float: int("123") float("1.23")
numder -> str: str(123)
reverse: str[::-1] or ''.join(reservsed(str))
split: str.split(',')
slice: str[start:end:step] str[2:0:-1]
- [start, end) start包含，end不包含

list operation

append, pop
join: ','.join(arr)
slice: 同str
iterate

for item in mylist: # range(0,len(mylist))
    print(item)

list comprehension: [n+1 for n in mylist if n % 2 is 0]
map: list(map(lambda x: x+1, mylist))
filter: list(filter(lambda x: x % 2 is 0, mylist))
reduce:

from functools import reduce
reduce(lambda acc,x: acc+x, a, 10)

deque operation

q = deque()
q.append(x)
q.appendleft(x)
q.pop()
q.popleft()

union find

fd = { n:n for n in range(1,11)}
rank = [ 0 for n in range(1,11)] # how many ansestors does this item have?

def find(fd,i):
  while fd[i] != i:
    fd[i] = fd[fd[i]] # path compression, 往祖先設定
      i = fd[i]
  return i

def union(fd,rank,i,j):
  a = fd[i]
  b = fd[j]
  if a != b:
    if rank[i] > rank[j]: # 子孫越多tree越平
      fd[j] = i
      rank[i] += 1
    else:
      fd[i] = j
      rank[j] += 1

trie

trie = [{},False]

def addString(trie, s):
  for c in s:
    if c not in trie[0]:
      trie[0][c] = [{}, False]
    trie = trie[0][c]
  trie[1] = True

def find(trie, s):
  for c in s:
    if c in trie[0]:
      trie = trie[0][c]
    else:
      return False
  return trie[1]

dp tips

可以用functools.cache

@functools.cache
def fib(n):
  if n < 2:
    return 1
  else:
    return fib(n-1)+fin(n-2)

如果有重複走的問題要自己處理

def cache_computing(f,is_computing=None):
  mem = {}
  
  @functools.wraps(f)
  def wrapper(*args,**kwds):
      if args not in mem:
          mem[args] = is_computing
          mem[args] = f(*args,**kwds)
      return mem[args]
  return wrapper

Algo經典手法與題目recap

prefix sum

用法

算區間和
- 和
  - 從a~b的總和
  - 如果有負數，可以代表偏離原點多遠
- 一般來說，通常第一個會是0代表沒有加任何東西的狀態
- 所以index從1開始，代表從arr[0]~arr[i-1]

static (index -> sum)

list(accumulate(nums, initial=0))
LC209
- 因為arr只有正數
  - 可以用sliding window，去收縮大小
  - 可以用prefix sum，在prefix sum做binary search
    - 我們會先列舉起點到終點
    - 所以prefix sum也是從起點去往後找終點
    - TODO: LC209與LC525為什麼一個是從後面一個從前面

in fly (sum -> count or [index])

LC560
- 基本款
LC525
- 與LC209不同這裡是每加一個都會產生變化
- 所以可以用in fly一邊建prefix sum，再找有沒有符合的
- 注意同一個sum我們只要最前面的

Monotonic stack

用法

根據關注點不同有不同的看法
- 排序，留下最後的字典序 (stk是重點)
  - 1 3 7 2
  - 1 2
    - 可以看成2把3,7吃了，只留下該範圍最小的，這也是字典序的由來
  - 內容物:
    - 節點
    - 區塊
- 夾出區間，中間是最大或是最小 (被pop的資料是重點)
  - while stk and stk[-1] <= n
    - 7 3 2 ..left.. 1 ..right.. 2
      - right的所有數字都會小於1
      - left的所有數字都會等於1
      - 1是這個區間(去頭尾)最大的，含頭尾的區間中的最小的
  - while stk and stk[-1] >= n
    - 1 2 3 ..left.. 7 ..right.. 2
      - right的所有數字都會大於7
      - left的所有數字都會等於7
      - 7是這個區間最小的，含頭尾的區間中的最大的
  - 這樣就可以用stk[-2]與n，做出一個閉區間
  - 記得處理沒有stk的case
在需要保持原本的順序、字典序、前面的資料會被後面的蓋掉時就可以老慮用用看

夾出區間

LC84
- 經典
- 小的柱子會被大的蓋掉，只取小的
  - 用成圖: 1,1,1,...1, 2,3,4, 10
- 很明顯就是monotonic stack
  - 取pop出的柱子去乘左右兩邊構成的區間長度
LC1130
- 如果要最小一定是找最小的數字，之後是左右兩邊最小的
  - 化成圖: a .left. min .right. b
  - 有什麼辦法可以保證min一定是a~b之間最小的?
    - monotonic stack
      - while stk and stk[-1] <= n
  - 最後乘的時候要確認哪邊是小的!!
LC1793
- 就是LC84
- 不過要在對的區間時才能更新答案
  - 這裡可以與LC402比
    - 402是控制pop
      - TODO: 這樣stack的性質會是對的嗎?
    - 1793是控制更新答案
LC1856
- 區間中最小、又要連續
  - 化成圖: 7 3 2 ..left.. 1 ..right.. 2
- 之後用prefix sum加速加總
LC907
- 區間中最小，monotonic stack
  - 化成圖: 1 2 3 ..left.. 7 ..right.. 2
LC42
- 只要被兩個柱子夾起來的部份而已!!

排序

LC402
- 如果只是移除多的字以完成最小字典序不難就mono stack
- 但是有限制次數，所以不能一直pop
LC316
- 同樣是移除字完成最小字典序
- 但與LC402不同的是，這次是不能放入同樣的字
  - 注意到，這次條件是打在最外面
  - 只要重複就連stack都不pop
    - 但402是還可以放數字到stack
LC768
- 這題把stack的sort具體化，這話怎麼說
- 前面提過小的會把大的吃掉，所以現在紀錄的是範圍最小
- 但這題最後要留下範圍最大的item
LC901
- 就是LC768
- 要記下區間最大值
- 不過這題還要區間長度
LC581
- 可以用LC768去生chunk，之後把頭尾去掉，把所有長度加起來
- TODO: 但可以不用那麼麻煩

下一個最大

LC503
- 這是monotonic stack的經典展現
- 求下一個最大
  - 觸發pop的數字就是下一個最大
- circular?
  - nums兩倍長就好
LC739
- 求下一個最大之間的距離
  - 所以stack放index
- 這裡會遇到一個有趣的case
  - [1, 2, 2]要怎麼處理?
    - 加等號: 會讓後面的2被吃掉
    - 不加: 2留著
  - 怎麼叫更溫暖?
    - 大於，所以不加等號

難

LC456
- 這要認真推
- 先暴力
  - 原本1<2<3
  - 會從3開始找，之後2再來1
  - 會從最大的開始找!!
- 但現在
  - 1<3<2
  - 這要從哪裡開始找?
  - 先從大的開始，所以是2
    - 但怎麼確認3
    - (難的地方!!)
      - 從後面開始看
      - 這樣會有
        1 1 1 2 3 3 3
    - 之後是大小，2要大於3，最好會自動清
      - monotonic stack
      - 清出來的就是可能的2，而我們挑最大的
      - 要等號嗎?
        不用!!
        保留可能性
- 所以要做的是
  - 從後往前，塞stack (3的候補)
  - 出現大的數字，清stack (2的候補)
  - 剩下只要比對是不是符合132

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stk = []
        mid = float('-inf')
        for n in reversed(nums):
            if n < mid and stk:
                return True
            
            while stk and stk[-1] < n:
                mid = max(mid,stk.pop())
            stk += n,
        return False

LC862
- 區間總和，但是
  - 有負數
  - 大於等於目標
- 算區間和，prefix sum
  - 所以就一直記prefix sum，從最小的開始算和(queue)
  - 如果sum太大怎麼辦
    - 所以要清 (stack，這不單調，只是要清總和太大的項目)

binary search

bsearch不一定要排序才能用 bsearch最好用左閉右開注意mid會不會重複用法

找目標
猜數字
逼近 (LC4)

題目

LC162
- 右邊的點要在答案中
  - 也就是重合時會等於的值
- 往大的方向走
  - 就算沒有sort也可以用!!
LC4
- 有sort也不一定看的出來可以用bsearch
- 這裡重點是長度
  - 每次把小的區段丟掉
LC1011
- 猜每天要在多少重量
- 但範圍是重點
  - 太大會很慢
  - 每一個貨物當成最重的重量，去算平均
LC33
- 確認兩件事
  - 哪一塊是遞增的
  - 目標在這一塊嗎
- 另外
  - 如果長度是2，mid會輪迴!!
LC153
- 對rotate的長度做bsearch
LC327
- prefix sum + 不等式
  - 用lower bound與upper bound找index

sliding window

基本

用閉區間做列舉終點

a = 0
win = []
for b in range(len(fs)):
    update_win()
    while a <= b and when_win_is_illegal():
        shrink_win()
    update_ret()
return ret

列舉起點

b = 0
win = []
for a in range(len(fs)):
    while b < len(fs) and when_win_is_legal():
        update_ret()
        expand_win()
    shrink_win()
return ret

atMost

def atmost(bound):
    ret = i = 0
    for j,n in enumerate(nums):
        update_win()
        while i <= j and when_win_is_illegal():
            shrink_win()
        ret += j-i+1
    return ret

題目

LC220
- 這裡index的abs用sliding window處理
- 數字用不等式推論
  - 之後會看到lower bound
LC995
- 這裡的重點是處理flip
  - flip的問題
    - 現在是什麼bit
    - 範圍到哪
  - 範圍就想到index
    - 所以要有方法追蹤有flip的index
    - 並在超出範圍時刷掉
      - queue做sliding window
LC713
- 用sliding window找最靠近k的window
- 但接著就是怎麼算現在的window有多少組合?
  - 魔法: right-left + 1

class Solution:
    def totalFruit(self, fs: List[int]) -> int:
        win = Counter()
        a = 0
        ret = 0
        for b in range(len(fs)):
            win[fs[b]] += 1
            while a <= b and len(win) > 2:
                win[fs[a]] -= 1
                win += Counter()
                a += 1
            ret = max(ret, b-a+1)
        return ret

LC395
- 長度是至少k
  - 所以不好當sliding window的條件
  - 需要別的條件
- 字母只有26個
  - 限制最多多少字母可以出現在window中!!
LC424
- 怎麼找出有多少非法字
  - 總長度 = 最多的字 + 其他字
LC992
- 新招式: atMost
  - 小於等於limit有多少組合
LC1234
- window中的東西可以亂生
  - 外面不超標的話就可以用window把string給平衡掉
LC1248
- 可以用atMost
- 也可以之前的魔法
  - right-left+1是以此點為終點的組合數
  - 之後就是在奇數到期時加到答案中

monotonic queue

LC239
- 明顯是sliding window
- 但要最大值
  - monotonic stack
- 還要顧index
  - deque
- 兩個結合就是monotonic queue

two pointer

linked list vs array

LC148
- 只能用merge sort
- 因為不能隨機跳位置
LC19
- 這是list，一旦過了就回不去
- 但可以像找中點，讓兩個ptr之間保持距離
- 這裡是固定距離，中點是找兩倍
LC61 & LC189
- 先談rotate array
  - 一個是Cyclic replace (不好做)
  - 另一個是
    - reverse整條
    - reverse 0~k 與 reverse k~end
- 再談rotate list
  - 延續reverse的解法
  - 第一次reverse是把後面的拉到前面
  - 第二次reverse是把順序用成對的
  - 但這裡是list，所以可以直接把list分成兩個
  - 接上去就好

index,ptr as list

LC283
- 一個ptr做為0的list的終點
- 另一個ptr是還沒看過的item的list的起點
LC26
- 同LC283
- 一個終點一個起點，一直換
LC905
- 類似LC283
- 但一個從array的頭，一個從尾塞
LC75
- 類似LC905
- 但要記得從後面換的部分還是屬於沒看過的部分，所以還要再看一次
LC86
- 把list分一半
- 兩個list指向list的終點
  - Linked list需要確保每次新增node時不會loop
    - 要記得把next設成None
LC143
- 類似LC86

classic

LC142
- 判圈
  - 一個走一倍，一個走兩倍
  - 只要相遇就是圈
- 圈的起點
  - 慢走的長度是
    - 起點到圈起點 + 某個數字*圈長度
  - 快走的長度是
    - 起點到圈起點 + 某個數字*圈長度
  - 兩個相減就會看到現在長度其實是
    - 圈長度的整數倍
    - 也就是說，不管從哪裡都可以算是圈的起點
  - 所以只要從起點走遇到另一個ptr就是圈的起點
LC15
- 3sum
  - 從頭開始走剩下的部分做2sum
LC18
- nSum
  - 延伸3sum，直到只剩下2sum之前
  - 都是當成3sum處理
LC876
- Linked List中點
  - 一個走一倍，一個走兩倍
  - 另一個到終點，現在的就是中點
    - 根據跳出來的條件可以看長度是奇數還是偶數
      - 因node.next跳出來，偶數
      - 因node.next.next跳出來，奇數
LC287
- 有很多解法
  - bsearch (猜數字)
  - 注意到資料都是在index的範圍內
    - 可以用判圈
    - 可以把資料換到對應的index上
      - 另外該資料也會是0~i之間最大的
        見chunk那一題

misc

LC986
- merge interval可以
- 把兩個interval看頭尾，挑最靠近裡面的部分
  - 在最小中挑最大
  - 在最大中挑最小
  - 如果新interval的頭大於尾，這新interval就是非法的
  - 每次都丟尾最小的
LC844
- 上stack
- 直接從尾開始比，之後統計刪的次數，有counter時跳掉
  - 為什麼是尾開始
    - delete往前刪
    - 所以前面不會確定
    - 但後面不會被影響
  - 有點像moore voting
LC763
- 所有char都要在同一區
- 一次一次紀錄每個char最後出線的index
- 什麼時候才切成一區?
  - 當下的位置就是最後的位置時
    - 可以看chunk與LC287作對比
LC42
- 對於每個柱子，就是看
  - 左右都比自己高
  - 挑矮的，算差距
- 因為每次都只看最矮的
  - 所以可以像2sum去縮

heap

python原本只有heapq，十分不好用
- 但是可以搭配已經sort好的list去用他的heappop與heappush
  - LC352
可以用SordtedList好用超多，遠比C++的set或是map好用

divide and conquer

LC327
- 右邊index一定大於左邊
- 針對每個左邊index找右邊符合需求的區間
LC493
- TODO: 要看裡面怎麼用bit，感覺與divide and conquer有一點關係

Dynamic programming

TODO

刷表法 & 填表法差別

用途

此點的狀態，像palindromic
到目前為止的總和，一般的dp都是以此為目標去求

from start or end

LC198
- dp可以從
  - 起點開始算
    - 要先把整個長度算好
      - 這是環狀
        長度兩倍
  - 終點算回去
    - 簡單很多!!
      - max(self.ns[i] + self.dp(i-2), self.dp(i-1))
任何dp都建議從終點算回去

bottom-up 與 top-down

LC718
- 如果用top-down
  - 除了要看字有沒有一樣
  - 還要追蹤長度!!
    - 因為要連續
    - f(i,j,l)
      - max(ret, f(i-1,j,0), f(i,j-1,0))
        ret = f(i-1,j-1,k+1) if s[i] == s[j] else k
    - 這是n^3
- 用bottom-up
  - dp[i][j] = dp[i-1][j-1]+1 if if s[i] == s[j] else 0
  - 這是n^2
  - 因為是長度所以比起top-down少很多東西
LC546
- 真的什麼都想不到的話就是dp去模擬
  - 要什麼項目(參數、狀態定義)
  - 怎麼轉換
- f(i,j,k)
  - i,j是範圍
  - k是與j同顏色的盒子數量
    - 所以這裡就兩個case
      - 直接把所有盒子用掉，算分數
      - 抓中點，去增加k的數量
        [dp(i,x,k+1)+dp(x+1,j-1,0) for x in range(i,j) if boxes[x] == boxes[j]]

classic

LC72
- edit dist
  - replace: (i-1,j-1)
  - delete: (i,j-1)
  - insert" (i-1,j)
    - insert多一個字，又馬上比對，所以與delete相反
LC647
- palindromic
  - s[i] == s[j] and ispalid(i+1,j-1)
- 這題其實做從中心展開會比較好
  - 都是n^2，還比較簡單
LC516
- palindromic
  - 不用在失敗時結束，要把字刪掉
    - max(dp(i+1,j),dp(i,j-1))
  - 剩下就是原本的dp
LC322
- coin
  - 有兩種
    - 一個是從背包抄來的
      - f(total, i)
        一個是完全不用: f(total, i-1)
        一個是一直try: f(total-arr[i]*n, i)
      - 這是n^2
    - 另一個是用total做狀態
      - f(total)
        每個都try: min([f(total-n) for n in arr])
      - 這個是n
LC139
- word break
  - 這不是教科書會出現的dp經典
    - 但是處理leetcode的字串列舉常常用到
  - f(s)
    - 對bank的每個字比開頭
      - f(s[len(w):])
    - 題外話
      - bank的處理還有一個是用bfs配把字碼調
        像*bc、a*b、ab*
        處理換字能不能換成另一個字的問題
        再題外話
        像是倒水問題這種狀態變化固定的都可以用bfs找最短路徑
        但要把狀態定義好!!
LC152
- LIS
  - 這題是LIS的進化版
    - 原本是
      - lis(i)
        max(arr[i], arr[i]+lis(i))
    - 但負數也有可能會是選項!!
      - 所以要同時計min與max，不能像原版只用max
LC354
- LIS
  - 這題是二維LIS
    - 但要處理第一維同數字的問題
      - 第一維increasing排序
      - 第二維decreasing排序
LC64
- 棋盤
  - 就是看能往哪走
    - f(i,j)
      - grid[i][j]+min(f(i-1,j), f(i,j-1))
    - 建議都是用終點去推
      - TODO: 有一題就是一定要用終點推
    - 如果用起點走就是dfs
LC338
- 奇偶
  - 偶: 2n
  - 奇: 2n+1
- 可以直接用!!
LC96
- BST與range
  - BST就是左邊小、右邊大
    - 所以有range
  - BST是tree
    - 常用的dfs
- 在range上列舉中點，算組合數

hard

LC87
- 這種有明確標示動作與做reduction對象的都很簡單
- 但這題要注意swap的string可能還沒被比完!!
  - 要用cache_computing
LC396
- 把函數列出來
  - 找規律 (所以難，有緣就找的到)
    - f(n) = f(n-1) - sum + len(arr)*arr[n-1]
LC312
- 如果用平常的作法
  - f(i,j)是i~j的最大分數就會變成兩邊
    - 十分痛苦
  - 要看成
    - 這區域的氣球都爆完的分數有多少
      - 列舉要爆的氣球
        max( nums[left] * nums[i] * nums[right] + dp(left, i) + dp(i, right) for i in range(left+1, right) )
LC926
- 分成ones與zeros就可以看出要用prefix sum
- 如果要用dp，就要看怎麼建構合法的答案
  - 最後一位如果是1，可以直接接上去
  - 如果是0，不是把前面的1換成0，就是把自己這一位換成1
LC600
- f(i)i位數的合法組合數 (沒有連續1)
  - 以5為例
    - 10 111 ~ 10 000: f(3)
    - 0 1111 ~ 0 0000: f(4)
      - 11 111 ~ 11 000非法
      - 01 111 ~ 01 000會被包含
    - f(i) = f(i-1)+f(i-2)
  - 所以剩下就是從最高位往下加f(k)
  - 同時看有沒有連續1出現!!
LC44
- 其實就是用string比對處理(edit dist)
- 但要注意最後pat只剩下star的狀態!!
LC188
- 能用到mutual recursion!!
- 定義buy(i,k)andsell(i,k)
  - 分別定義
    - buy(i,k): 在i時還有k次購買機會的購買的最大收益
      - buy(i-1,k)
      - sell(i-k,k-1)-arr[i]
    - sell(i,k): 在i時還有k次購買機會的賣出的最大收益
      - sell(i-1,k)
      - buy(i-k,k)+arr[i]
- 另外也可以用挑區段，去接來看
- 如果當成lis去看，之後跑k次
  - 分成歷史上的最大(global)與當前的最大(local)
  - 之後就是用lis更新local
  - 之後更新global
    - local = max(global[i], local + prices[i] - prices[i-1])
    - global[i] = max(global[i-1], local)
- 另外。LC122
  - 最高到最低的總和就是各個區段的總和
  - 所以就是在increasing時把所有差額加起來
LC376
- 這題對我有因緣
- 因為是用自己的dp過的
  - 先過整條array看是increasing還是decreasing
  - 之後根據方向，跑lis
- 因為有兩個方向，所以可以定義mutual recursion
  - arr[i-1] > arr[i]
    - up[i] = down[i-1]+1
    - down[i] = down[i-1]
  - arr[i-1] < arr[i]
    - up[i] = up[i-1]
    - down[i] = up[i-1]+1
  - arr[i-1] == arr[i]
    - up[i] = up[i-1]
    - down[i] = down[i-1]

line sweap

把起終點分開，[start, -height], [end, height]
根據位置與高度排序
之後一個一個走
- 把高度塞到heap中 (line sweap)
  - 負的就塞
  - 正的就去刪
- 之後就是用heap去確認當前高度，去調整答案

elegant sol

這裡是收集一些原本用dp但是有超級優雅的解
LC828
- from lee215
- AXXXAXXA
  - 看中間的A到左右兩邊的A隔3與2個字元(4與3個洞)
  - 所以只包含中間A的組合是12
- 所以只要針對所有字元中間的洞算組合數就好!!
LC1569
- 這是BST，有左右兩邊
- 而我們有第一個點，root
- 可以分左右兩邊
- 算組合數: comb(len(right)+len(left), len(right))*f(right)*f(left)
LC678
- 把所有星號當成左括號，去計數，如果左括號太少，就直接False
- 把所有星號當成右括號，去計數，全部跑完，看有沒有被扣完

動機#

C++#

stdin#

一般(空白分隔)#

一整行#

其他(有分隔號)#

file#

open#

read#

map, unorder_map (set與其實是一樣的東西)#

string operation#

cast#

common operations#

vector operation#

union find#

trie#

Python#

stdin#

file#

dict operations#

string operation#

list operation#

deque operation#

union find#

trie#

dp tips#

Algo經典手法與題目recap#

prefix sum#

用法#

static (index -> sum)#

in fly (sum -> count or [index])#

Monotonic stack#

用法#

夾出區間#

排序#

下一個最大#

難#

binary search#

題目#

sliding window#

基本#

題目#

monotonic queue#

two pointer#

linked list vs array#

index,ptr as list#

classic#

misc#

heap#

divide and conquer#

Dynamic programming#

TODO#

用途#

from start or end#

bottom-up 與 top-down#

classic#

hard#

line sweap#

elegant sol#

動機

C++

stdin

一般(空白分隔)

一整行

其他(有分隔號)

file

open

read

map, unorder_map (set與其實是一樣的東西)

string operation

cast

common operations

vector operation

union find

trie

Python

stdin

file

dict operations

string operation

list operation

deque operation

union find

trie

dp tips

Algo經典手法與題目recap

prefix sum

用法

static (index -> sum)

in fly (sum -> count or [index])

Monotonic stack

用法

夾出區間

排序

下一個最大

難

binary search

題目

sliding window

基本

題目

monotonic queue

two pointer

linked list vs array

index,ptr as list

classic

misc

heap

divide and conquer

Dynamic programming

TODO

用途

from start or end

bottom-up 與 top-down

classic

hard

line sweap

elegant sol