[閒聊] LeetCode Weekly Contest 343

昨天雙週賽 40 名，今天 58 名，開心 https://i.imgur.com/AMyk2Le.png 其實排名我原本以為會更爛 因為我中間有寫錯方向重寫 最後一題蠻可愛的 1. Determine the Winner of a Bowling Game 這在第一題中算是很麻煩的了 維護這個x2 buff 剩餘的回合數 如果這回合打出 10 分就重置成兩回合 否則就減一 2. First Completely Painted Row or Column 因為數字不會重複，所以可以維護 1) R, R[i] 代表這一橫排被選過的次數 2) C, C[i] 代表這一直排被選過的次數 照 arr 順序選，選到就把相應的 R 和 C 加一就好 滿了就 return 3. Minimum Cost of a Path With Special Roads 關鍵的觀察是，只有兩種走法 a) 走特殊通道 b) 正常的走到終點或某個特殊通道的入口 所以只要維護出入口加上起終點的 graph 即可 |V| <= 402, |E| <= |V|^2 之後用 dijkstra 即可 4. Lexicographically Smallest Beautiful String 我們要讓字串中不存在長度 >= 2 的回文 假如 s 存在回文 t，則 t 拔掉頭尾還是回文 所以 s 不合法若且唯若存在長度是 2 或 3 的回文 也就是我們只要讓所有長度是 2 或 3 的子字串都不是回文就好 而長度是 2 的子字串不是回文若且唯若兩個字符不一樣 長度是 3 的子字串不是回文若且唯若頭尾兩個字符不一樣 也就是我們只需要讓當下這個字符和前兩個不一樣即可 要找出最小的 beautiful string 只要找出從尾巴數回來第一個可以增加又保持合法的 index 後面就在保持合法的情況下 greedy 的取最小的那個字符就好 --
※ 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1682827248.A.5F3.html