Soft_Job 板


LINE

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



※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.161.76.160 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1627032495.A.65E.html
1F:推 yupog2003: 还没看内容,先大推,感谢 07/23 17:37
2F:推 EngineerChen: 推神人 07/23 17:38
3F:推 Csir: 神QQ 07/23 17:44
4F:推 kiki86151: 推 python很多技巧真的很好用 07/23 17:51
5F:推 mathbookh2o2: 感觉实用 07/23 17:54
6F:推 Lyumin: 推爆 07/23 17:58
7F:推 hanamini: 推 07/23 18:07
8F:推 jamfly: 大推 07/23 18:11
9F:推 KingSteven: 推 07/23 18:14
10F:推 longint: 推 07/23 18:18
11F:推 kyrie77: 推 07/23 18:23
12F:推 MoonCode: 07/23 18:26
13F:推 cossetannie: 推 07/23 18:29
14F:推 sph113: 推 07/23 18:51
15F:推 parsons12342: 推好心 07/23 18:53
16F:推 k798976869: 推 07/23 18:57
17F:推 chatnoir: 大推 07/23 18:57
18F:推 UnReal5566: 有神 07/23 19:07
19F:推 eggy1018: 真的是有刷的很深的才知道的python3小技巧! 推一本effe 07/23 19:10
20F:→ eggy1018: ctive python 90 method 07/23 19:10
21F:推 CKNTUErnie: 推 07/23 19:13
22F:推 Findagreen: 太佛了 在这边祝福原po上厕所都有卫生纸 07/23 19:25
23F:推 luweber88: 推 07/23 19:27
24F:推 oopssugar: 推推 07/23 19:33
25F:推 duck10704: 推 神人 07/23 19:35
26F:推 TAMSHUI: 推! 07/23 19:36
27F:推 ZuiYang: 推 07/23 19:41
28F:推 HMW: push 07/23 19:56
29F:→ gaowei16: 推 07/23 19:57
30F:推 Kagami3421: 推 07/23 19:58
31F:推 alpe: 大推 07/23 19:59
32F:推 phys: 推 07/23 20:00
33F:推 WaterLengend: 只能推了 07/23 20:01
34F:推 rumrumrum: 推推 07/23 20:03
35F:推 kangan987: 太强了!推 07/23 20:14
36F:推 unmolk: 推…. 07/23 20:14
37F:推 ttsung2: 推 07/23 20:20
38F:推 underwater: 虽然不是用python,还是大推 07/23 20:30
39F:推 littleshin: 推 07/23 20:34
40F:推 onthesea: 太神了 07/23 20:45
41F:推 knme: 推 07/23 20:48
42F:推 bowin: 推分享 07/23 20:49
43F:推 itis0423: 推 07/23 20:53
44F:推 lingege32: 推大神 07/23 20:57
45F:推 jinmin88: 太猛啦 07/23 20:58
46F:推 llltt123: 推 感谢大神 07/23 20:59
47F:推 OSDBNetwork: 推 大神 07/23 21:02
48F:推 leewei05: 推 07/23 21:02
49F:推 ericx790101: 推!感谢无私分享! 07/23 21:12
50F:推 tnfshjcc: 推推 实用Python技巧 07/23 21:14
51F:推 EntHeEnd: 赞喔 07/23 21:41
52F:推 caeserhaha: 推爆 07/23 21:49
53F:推 nicehorse06: 大神推 07/23 21:56
54F:推 tw11509: 推,太神啦 07/23 22:02
55F:推 aassdd926: 看完觉得我不会写Python… 07/23 22:10
56F:推 DCTmaybe: 也太神了吧 07/23 22:17
57F:推 devilkool: 厉害 07/23 22:53
58F:推 bjocke831010: 感谢大神~ 07/23 23:34
59F:推 Luke3723: 太神了 推!! 07/23 23:39
60F:→ yesgowow: 推 谢谢分享 07/23 23:47
61F:→ tommytyc: 推 07/24 00:16
62F:推 birdman: 推分享 07/24 01:03
63F:推 ss8651twtw: 学到了好多技巧 推推 07/24 01:29
64F:推 juju123: 推推 07/24 01:32
65F:推 yoshonabee: 推 07/24 01:35
66F:推 cacadeon: 感谢详细分享 07/24 01:37
67F:推 f8210440: 感谢 分享 07/24 01:57
68F:推 charle0911: 娘子出来看善心的耶稣 07/24 02:01
69F:推 vincent0965: 推 07/24 02:02
70F:推 s1020824: 推 07/24 02:26
71F:推 cococing: 推推 07/24 02:59
72F:推 la197352: 谢谢分享 07/24 03:02
73F:→ mirror0227: 有些技巧让可读性降低了 宁愿不用 07/24 03:17
74F:→ mirror0227: Code写得快没错 但好读重要很多吧 07/24 03:17
同意,所以我文中有说有些人喜欢有些人不喜欢,选自己喜欢的用就好, 像是我个人比较偏好用 dict.setdefault 建 trie 而不是用 defauldict, 但这些技巧的背後都代表着一些语言特性,了解一下并不吃亏。 而且说句实在话,限制短时间的面试 跟 长期维护的产品,出发点并不能一概而论。
75F:推 dog661121: 推爆 07/24 03:31
76F:推 jack529: 赞 07/24 03:51
77F:推 arunaway: 谢谢分享 07/24 04:36
78F:推 hydradevil: 推佛心 07/24 06:24
79F:推 davidpanda: 下面的小技巧要慎用, 主要是你需要解释给面试官听 07/24 07:12
80F:→ davidpanda: 不是写得快就好 07/24 07:12
81F:→ davidpanda: leetcode的题目其实讨论区都有很好的答案 07/24 07:13
82F:→ davidpanda: 想不出来的时候其实不妨看看讨论区 07/24 07:13
83F:→ davidpanda: 最後就是要融会贯通, 如果自己当过面试官就知道 07/24 07:14
84F:→ davidpanda: 其实很容易可以看出来面试者是真的懂还是背答案 07/24 07:15
没错,绝对不要背答案,一个变化就倒了,该学习的是每题背後用到的观念。 然後这份的解法就是揉合了讨论区跟解答写出来的 XD 因为发现有时候 leetcode 解答反而不是最佳解, 像是 Morris traversal 就只有少数几篇解答有提到,但超多题目其实都可以用。
85F:推 papaya0807: 推好神 07/24 08:55
86F:推 kiillen: 太佛拉 07/24 09:27
87F:推 j6004j6: 推起来~ 太佛了 07/24 09:34
88F:推 mike8469: 推 07/24 09:35
89F:推 jimjim951357: 推 07/24 09:36
90F:推 HelloPTT: 推 07/24 10:03
91F:推 julian9925: 好佛,谢谢大大分享 07/24 11:05
92F:→ Rayishere: 大推~~~ 感谢大大的无私分享 07/24 11:05
93F:推 swinds24: 推分享! 07/24 11:50
94F:推 elseif: 感谢分享! 来拜读! 07/24 12:12
95F:推 FireKingStar: 谢谢大大的分享,我会仔细的研读它。 07/24 12:18
96F:推 loveu8: 推分享~ 07/24 12:25
97F:推 angellee0102: 感谢分享! 07/24 12:41
98F:推 sarsman: 推 07/24 12:55
99F:推 windmax1: 天啊 大神太伟大了 07/24 13:52
100F:推 tinwen: 推~ 07/24 15:10
101F:推 ID3238: 谢谢分享 这对求职面试帮助很大 07/24 15:14
102F:推 stu51211: 谢谢! 07/24 15:19
103F:推 Raymond0710: 感谢无私分享 07/24 15:26
104F:推 hortune: 推! 07/24 15:33
105F:推 nba887215: 推 07/24 15:40
106F:推 AgileSeptor: 推 07/24 15:54
107F:推 snowm: 谢谢分享! 07/24 15:55
108F:推 euleramon: 想请问一下大大是不是有做过 AI相关的领域? 07/24 16:37
没有耶,在学期间是有修过几门 AI/ML 相关的课程, 出社会後主要是在做 web/app 的开发。
109F:推 deforest111: 推强者 07/24 16:47
110F:推 Gaogaigar: 推佛心 可惜我躺平了才看到 07/24 17:02
111F:推 blackdiz: 感谢分享,好人一生平安 07/24 17:18
112F:推 cuh0309: 推 07/24 17:41
113F:推 andy9595995: 推 07/24 18:13
114F:推 vvind: 太棒了 07/24 18:57
115F:推 freedls: 这个必推 07/24 19:11
116F:推 sky80420: 推推 07/24 19:40
117F:推 jasonwung: 推推 07/24 19:45
118F:推 playboy007gy: 好人一生平安 07/24 19:56
119F:推 tigerya: 推! 07/24 21:25
120F:推 qq9966pp: 必须推 07/24 22:15
121F:推 nofeel0: 推,感恩大大 07/24 22:30
122F:推 cotbel: 是notion,整理得好乾净! 推推 07/24 22:59
123F:推 DLHZ: 推 07/24 23:13
124F:推 hongwl030: 推 有实力又好心 07/24 23:24
125F:推 kevinfilter: 大推 感谢分享 07/24 23:47
126F:推 a24626296: 感恩,赞叹 07/24 23:50
127F:推 shieldsky: 真的好厉害!感谢分享!技巧很实用! 07/25 00:14
128F:推 ob9618: 推 07/25 00:23
129F:推 f821027: 推 07/25 01:01
130F:推 KindWei: 推 python技巧 07/25 01:14
131F:推 amiwry: 感谢分享 07/25 03:20
132F:推 PonyTail0901: 太强大了 希望我也能早日上岸 07/25 04:05
※ 编辑: wheels (118.161.76.160 台湾), 07/25/2021 04:15:03
133F:推 bcjohn: 推 07/25 08:46
134F:推 apple20132: 推 感谢 07/25 09:37
135F:推 summerleaves: 推推 07/25 09:38
136F:推 somoo: 推神人 感谢无私分享 07/25 09:50
137F:推 cypress5048: 大推!! 07/25 10:56
138F:推 blueVC: 感谢分享! 07/25 11:07
139F:推 darkch: 这一定要推 07/25 11:14
140F:推 kuochuwon: 收藏一下,推 07/25 11:51
141F:推 lofu: 推 07/25 14:51
142F:推 gn02335338: 推 07/25 15:52
143F:推 followmeyo: 高手 07/25 16:48
144F:推 rotalume: 推! 07/25 17:12
145F:推 ukuk666888: 推 07/25 17:43
146F:推 JocMon: 推! 07/25 18:48
147F:推 world4jason: 9的话分享个小东西 在整理资料的时候常常用到的 07/25 19:49
148F:→ world4jason: 主要是好几种摊平的方法 其实速度上会有差异 07/25 19:49
149F:→ world4jason: 之前因为有需求有写过一些比较 07/25 19:49
150F:→ world4jason: reduce跟map印象中到了一定的scale後速度颇慢 所以直 07/25 19:49
151F:→ world4jason: 接弃用 numpy的话如果能指定型别 速度会快上更多 07/25 19:49
152F:推 world4jason: 不过如果都是python的list的话 就要看了 通常会慢都 07/25 20:00
153F:→ world4jason: 是混用的锅 07/25 20:00
154F:→ world4jason: 像是有时候知道pure python跑比较快的写法 但拿回来 07/25 20:05
155F:→ world4jason: 的是巢状numpy array 光转成list成本就很大了 07/25 20:05
156F:→ world4jason: py真坑XD 07/25 20:05
157F:推 answermangtr: 超级巧 刚刚看完您的面试心得就发现您发新文章 07/25 20:26
158F:推 Ekmund: 用心分享给推 07/25 20:36
159F:推 snow10725: 围观感谢 07/25 20:41
160F:推 xoy232: 推大神 07/25 21:44
161F:推 elvis17: 推 感谢大神分享~ 07/25 22:41
162F:推 Ouranos: 大推,谢谢分享! 07/25 22:49
163F:推 smily134: 推 07/25 23:01
164F:推 tsubasaxxx: 收藏推 谢谢 07/25 23:19
165F:推 koichip: 推,谢谢大神分享 07/26 00:06
166F:推 hongyan: 推 谢谢大什!!! 07/26 00:09
167F:→ hongyan: 神 07/26 00:13
168F:推 dannymc: 推推,感谢分享 07/26 00:28
169F:推 whatabiggun: 感谢 07/26 00:31
170F:推 airforceso: 感恩推推推 07/26 02:54
171F:推 ufap: 谢谢 07/26 04:03
172F:推 stone0811: 先推 07/26 07:47
173F:推 whitecolor: 推 07/26 09:27
174F:推 BlazarArc: 推推 07/26 12:22
175F:推 aacs0130: 推推,实用,不过某些特殊的语法要确定自己了解再用 07/26 13:52
176F:推 maoqq0405: 推推 07/26 15:06
177F:推 sandy4645: 推 太佛 谢谢分享 07/26 16:09
178F:推 TRESS: 推 07/26 22:59
179F:→ howard50009: 推 07/26 23:40
180F:→ howard50009: 推 07/26 23:40
181F:→ howard50009: 推 07/26 23:40
182F:→ howard50009: 推 07/26 23:41
183F:推 timuwtpirt: 推 07/28 00:18
184F:→ WWIII: 感动啊 软体人都是无私奉献 07/28 16:02
185F:推 holmes2136: 推分享 07/28 19:01
186F:推 sars78786: 推 07/29 23:39
187F:推 NealPope: 推爆啦! 07/30 00:40
188F:推 justboa: 谢谢分享! 07/30 12:22
189F:推 hsiaotzu0505: 推!谢谢! 08/01 11:14
190F:推 tinnnnnngg: 推实用 08/03 02:57
191F:推 gvles1210: 推 08/03 16:13
192F:推 YNNEKUW: 大推 08/03 19:10
193F:推 salamii: 推 08/03 23:06
194F:推 markbex: 推!感谢分享 08/04 22:43
195F:推 UlyssesLee: 好久没来这版 一来就看到神 推推 08/05 23:08
196F:推 hiarpu: 推 08/07 18:18
197F:推 FourZero: 有神快拜 08/15 00:07
198F:推 pupurita: 谢谢神人 08/27 14:50
199F:推 ywbBetter: Good 09/16 12:58





赞助商连结

918预售屋新成屋团购资讯平台

like.gif 您可能会有兴趣的文章
icon.png[问题/行为] 猫晚上进房间会不会有憋尿问题
icon.pngRe: [闲聊] 选了错误的女孩成为魔法少女 XDDDDDDDDDD
icon.png[正妹] 瑞典 一张
icon.png[心得] EMS高领长版毛衣.墨小楼MC1002
icon.png[分享] 丹龙隔热纸GE55+33+22
icon.png[问题] 清洗洗衣机
icon.png[寻物] 窗台下的空间
icon.png[闲聊] 双极の女神1 木魔爵
icon.png[售车] 新竹 1997 march 1297cc 白色 四门
icon.png[讨论] 能从照片感受到摄影者心情吗
icon.png[狂贺] 贺贺贺贺 贺!岛村卯月!总选举NO.1
icon.png[难过] 羡慕白皮肤的女生
icon.png阅读文章
icon.png[黑特]
icon.png[问题] SBK S1安装於安全帽位置
icon.png[分享] 旧woo100绝版开箱!!
icon.pngRe: [无言] 关於小包卫生纸
icon.png[开箱] E5-2683V3 RX480Strix 快睿C1 简单测试
icon.png[心得] 苍の海贼龙 地狱 执行者16PT
icon.png[售车] 1999年Virage iO 1.8EXi
icon.png[心得] 挑战33 LV10 狮子座pt solo
icon.png[闲聊] 手把手教你不被桶之新手主购教学
icon.png[分享] Civic Type R 量产版官方照无预警流出
icon.png[售车] Golf 4 2.0 银色 自排
icon.png[出售] Graco提篮汽座(有底座)2000元诚可议
icon.png[问题] 请问补牙材质掉了还能再补吗?(台中半年内
icon.png[问题] 44th 单曲 生写竟然都给重复的啊啊!
icon.png[心得] 华南红卡/icash 核卡
icon.png[问题] 拔牙矫正这样正常吗
icon.png[赠送] 老莫高业 初业 102年版
icon.png[情报] 三大行动支付 本季掀战火
icon.png[宝宝] 博客来Amos水蜡笔5/1特价五折
icon.pngRe: [心得] 新鲜人一些面试分享
icon.png[心得] 苍の海贼龙 地狱 麒麟25PT
icon.pngRe: [闲聊] (君の名は。雷慎入) 君名二创漫画翻译
icon.pngRe: [闲聊] OGN中场影片:失踪人口局 (英文字幕)
icon.png[问题] 台湾大哥大4G讯号差
icon.png[出售] [全国]全新千寻侘草LED灯, 水草

请输入看板名称,例如:Gossiping站内搜寻

TOP