※ [本文转录自 Soft_Job 看板 #1W-eklPU ] 嗨，大家周末愉快！ 不知道还记不记得之前小弟有分享面试 Google TW SWE 的心得， 最後有提到小弟当初有发愿，如果顺利进去要把过去写过题目留存的解答整理分享出来， 最近终於施工完了，提供给有需要的人可以自由取用。 这份解答内涵盖了 781 题的 Python 3 解法（太早期刷的题目就没留解法了 QQ）， 写这些解答的目的是为了还愿并且回馈给还在努力的板友， 唯一的使用限制就是请不要拿来作商业用途，让知识无偿分享出去，感谢大家。 https://www.notion.so/lenchen/LeetCode-47d625b874894484af7c055b024b9817 内容主要分成四大类， 1. 资料结构 主题涵盖常用於 Leetcode 内解题的资料结构， 较常见的：Array/String, Matrix, Linked List, HashSet/Map, Stack, Queue, Heap 较高阶的：DSU, Trie, BIT 还有偶尔会用到 Deque 跟 sortedcontainers，但数量比较少就没特别分类。 2. 演算法 这边其实是我自己的归类，不一定只有这些 XD 内容涵盖有： greedy, multiple pointers, sliding window, sort, DFS/BFS, backtracking, sweep line, rolling sum, binary search, dynamic programming, minimax 有趣的是这边没列 divide and conquer 这个经典分类， 因为好像几乎没遇到过哪题是只能使用 divide and conquer 解的， 所以就没有让它自成一个分类了。 但若有题目也可以用 divide and conquer 解的话， 我也有写下来，所以还是可以再自行了解下。 3. 图 图相关的问题因为太经典所以自成一个主题， 整理了我所遇到的常见图论演算法，还有 topological sort 的两种方式， 最重要的是 tree 相关的分类也包含在这一部分内。 4. 其他 数学、随机、位元操作相关的题目都会在这里。 大致上就分这四个部分，每个解答底下都有一行字总结这题的解题概念， 因为跨越了两年半所以 coding style 可能也有些不一样， 但保证其中 99% 的内容都是我亲手一个个字元打出来的， 希望能帮助到有需要的人 :) 另外顺便再分享一些我觉得使用 Python 3 刷题时可以用的一些小技巧， 可以让你的 code 变得更精简，大家可以看看然後挑自己喜欢的来使用： 1. 用 next 搭配 generator comprehension 来获取第一个满足条件的元素， 像是 next(ele for ele in arr if ele > 0)，就可以拿到 arr 中的第一个正数。 2. 解对称性题目时，可以把引数调换 call 一次，减少重复的 code，像是： def foo(a, b): if a > b: return foo(b, a) ... 就可以让你接下来维持在 a <= b 的前提下继续写 code，或者直接 swap 引数也可以： def foo(a, b): if a > b: a, b = b, a ... 3. python dict 可以使用 tuple 作 multikey，像是 d[k1, k2, k3]， 如此一来就不用巢状 dict 了（d[k1][k2][k3]） 4. 可以使用 unpacking 来抽取出需要的参数，像是： A = [1, 2, 3, 4, 5] foo, *B, bar = A 可以得到 foo == 1, B == [2, 3, 4], bar == 5 另外还可以用巢状 unpacking， 像是 for i, (a, b) in enumerate(pairs): 就超级常用。 5. Python 3.8 跟 3.9 有多了一些不错的东西， 像是 3.8 的 assignment expression(:=) 跟 3.9 的 dict shallow merge(|) 都有机会可以让 code 更精简。 6. 有些 matrix 或是 grid 的题目，两个 dimension 长度有可能为 0， 可以用 if not any(matrix): return xxx 来处理（感谢 Stefan Pochmann） 7. in 也会消费 iterator， 所以如果想知道某个 str s2 是不是另一个 str s1 的 subsequence 可以这麽做， I = iter(s1) return all(c in I for c in s2) （再次感谢 Stefan Pochmann） 8. 想要测两个数是不是同正负可以用 (a > 0) is (b > 0)，记得事先检查 0 板友提供 (credit to @pig2014)： a ^ b > 0 更好 9. 想要摊平巢状 list 可以用 sum(L, []) <- 不建议！途中 list 会一直重新 alloc (credit to @coquelicot) 参考 stack overflow：https://bit.ly/3rz8UqH 建议的替代： 9.1. list comprehension: A = [ele for sub in arr for ele in sub] 9.2. itertools: A = list(itertools.chain.from_iterable(arr)) 9.3. reduce: A = functools.reduce(operator.iconcat, arr, []) 10. 某些要提供 factory function 的地方，可以递回给自己，像是： trie = lambda: collections.defaultdict(trie) 11. itemgetter 在某些需要 key 的 builtin function 很好用，像是： sorted(A, key=itemgetter(1))，等同於写 key=lambda x: x[1] 12. 因为 Python list 提供 negative indexing， 在某些情况可以用 ~i 来获得对应於 i 的反向 indexing，像是： for i in range(len(A)): A[i] += xxx # A[0], A[1], A[2] , ... A[~i] += ooo # A[-1], A[-2], A[-3], ... 大概就是这些东西了吧，这些技巧有些人喜欢有些人不喜欢， 我觉得没有对错啦，就挑自己觉得不错的用吧 XD happy coding！ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.161.76.160 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1627032495.A.65E.html ※ 转录者: wheels (118.161.76.160 台湾), 07/23/2021 17:28:45 ※ 编辑: wheels (118.161.76.160 台湾), 07/23/2021 17:29:11 感谢！完全没发现打错 XD 赞赞，又学到一招，讨论区竟然没看到有人用过 XD 我猜也有可能跟我只看 py 的文章有关 出书真的过誉了，在行家眼中这份解答可能有些地方还是坑坑洞洞的吧。 也请板友不吝告知内容有误的地方，我会尽快更正！ OMG 非常感谢您的提醒！差点就误导大家了，真的非常抱歉。 刚才确认 sum(L, []) 的 intermediate list 是会一直重新 allocated 的， 确实不该使用，附上 stack overflow 的传送门：https://bit.ly/3rz8UqH 建议的替代： 1. list comprehension: A = [ele for sub in arr for ele in sub] 2. itertools: A = list(itertools.chain.from_iterable(arr)) 3. reduce: A = functools.reduce(operator.iconcat, arr, []) 再次感谢 coquelicot 大大的指正！ ※ 编辑: wheels (118.161.76.160 台湾), 07/25/2021 04:14:23