嗨，大家周末愉快！
不知道还记不记得之前小弟有分享面试 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！

还没看内容，先大推，感谢

推神人

神QQ

推 python很多技巧真的很好用

感觉实用

推爆

推

大推

推

推

推

推

推

推好心

推

大推

有神

真的是有刷的很深的才知道的python3小技巧！ 推一本effective python 90 method

推

太佛了 在这边祝福原po上厕所都有卫生纸

推

推推

推 神人

推！

推

push

推

推

大推

推

只能推了

推推

太强了！推

推….

推

虽然不是用python,还是大推

推

太神了

推

推分享

推

推大神

太猛啦

推 感谢大神

推 大神

推

推！感谢无私分享！

推推 实用Python技巧

赞喔

推爆

大神推

推，太神啦

看完觉得我不会写Python…

也太神了吧

厉害

感谢大神～

太神了 推！！

推 谢谢分享

推

推分享

学到了好多技巧 推推

推推

推

感谢详细分享

感谢 分享

娘子出来看善心的耶稣

推

推

推推

谢谢分享

有些技巧让可读性降低了 宁愿不用Code写得快没错 但好读重要很多吧

推爆

赞

谢谢分享

推佛心

下面的小技巧要慎用, 主要是你需要解释给面试官听不是写得快就好leetcode的题目其实讨论区都有很好的答案想不出来的时候其实不妨看看讨论区最后就是要融会贯通, 如果自己当过面试官就知道其实很容易可以看出来面试者是真的懂还是背答案

推好神

太佛拉

推起来~ 太佛了

推

推

推

好佛，谢谢大大分享

大推~~~ 感谢大大的无私分享

推分享！

感谢分享! 来拜读!

谢谢大大的分享，我会仔细的研读它。

推分享~

感谢分享！

推

天啊 大神太伟大了

推~

谢谢分享 这对求职面试帮助很大

谢谢！

感谢无私分享

推！

推

推

谢谢分享！

想请问一下大大是不是有做过 AI相关的领域？

推强者

推佛心 可惜我躺平了才看到

感谢分享，好人一生平安

推

推

太棒了

这个必推

推推

推推

好人一生平安

推！

必须推

推，感恩大大

是notion，整理得好干净! 推推

推

推 有实力又好心

大推 感谢分享

感恩，赞叹

真的好厉害！感谢分享！技巧很实用！

推

推

推 python技巧

感谢分享

太强大了 希望我也能早日上岸

推

推 感谢

推推

推神人 感谢无私分享

大推！！

感谢分享！

这一定要推

收藏一下，推

推

推

高手

推！

推

推！

9的话分享个小东西 在整理资料的时候常常用到的主要是好几种摊平的方法 其实速度上会有差异之前因为有需求有写过一些比较reduce跟map印象中到了一定的scale后速度颇慢 所以直接弃用 numpy的话如果能指定型别 速度会快上更多不过如果都是python的list的话 就要看了 通常会慢都是混用的锅像是有时候知道pure python跑比较快的写法 但拿回来的是巢状numpy array 光转成list成本就很大了py真坑XD

超级巧 刚刚看完您的面试心得就发现您发新文章

用心分享给推

围观感谢

推大神

推 感谢大神分享～

大推，谢谢分享！

推

收藏推 谢谢

推，谢谢大神分享

推 谢谢大什!!!神

推推，感谢分享

感谢

感恩推推推

谢谢

先推

推

推推

推推，实用，不过某些特殊的语法要确定自己了解再用

推推

推 太佛 谢谢分享

推

推推推推

推

感动啊 软件人都是无私奉献

推分享

推

推爆啦！

谢谢分享！

推！谢谢！

推实用

推

大推

推

推！感谢分享

好久没来这版 一来就看到神 推推

推

有神快拜