LeetCode刷题手册-【千锋教育】面试宝典

说明 此版本是 https://books.halfrost.com/leetcode ⽹⻚的离线版，由于⽹⻚版实时会更新，所以此 PDF 版难免会有⼀些排版或者错别字。如果读者遇到了，可以到⽹⻚版相应⻚⾯，点击⻚⾯ edit 按钮，提交 pr 进⾏更改。此 PDF 版本号是 V1.5.20。PDF 永久更新地址是 https://github.com/halfrost/LeetCode -Go/releases/，以版本号区分不同版本。笔者还是强烈推荐看在线版，有任何错误都会⽴即更新。如果 觉得此书对刷题有⼀点点帮助，可以给此书点⼀个 star，⿎励⼀下笔者早点更新更多题解。 版本号说明，V1.5.20，1 是⼤版本号，5 代表当前题解中有⼏百题，⽬前是 520 题，所以第⼆个 版本号是 5，20 代表当前题解中有⼏⼗题，⽬前是 520 题，所以第三个版本号是 20 。 ⽬录 说明 ⽬录 第⼀章 序章 关于 LeetCode 什么是 Cookbook 为什么会写这个开源书 关于书的封⾯ 关于作者 关于书中的代码 ⽬标读者 编程语⾔ 使⽤说明 互动与勘误 后 第⼆章 算法专题 Array Backtracking Binary Indexed Tree Binary Search Bit Manipulation Breadth First Search Depth First Search Dynamic Programming Hash Table Linked List Math Segment Tree Sliding Window Sort Stack String Tree Two Pointers Union Find 第三章 ⼀些模板 线段树 Segment Tree 并查集 UnionFind 第四章 Leetcode 题解 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 13. Roman to Integer 15. 3Sum 16. 3Sum Closest 17. Letter Combinations of a Phone Number 18. 4Sum 19. Remove Nth Node From End of List 20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Duplicates from Sorted Array 27. Remove Element 28. Implement strStr() 29. Divide Two Integers 30. Substring with Concatenation of All Words 33. Search in Rotated Sorted Array 34. Find First and Last Position of Element in Sorted Array 35. Search Insert Position 36. Valid Sudoku 37. Sudoku Solver 39. Combination Sum 40. Combination Sum II 41. First Missing Positive 42. Trapping Rain Water 46. Permutations 47. Permutations II 48. Rotate Image 49. Group Anagrams 50. Pow(x, n) 51. N-Queens 52. N-Queens II 53. Maximum Subarray 54. Spiral Matrix 55. Jump Game 56. Merge Intervals 57. Insert Interval 59. Spiral Matrix II 60. Permutation Sequence 61. Rotate List 62. Unique Paths 63. Unique Paths II 64. Minimum Path Sum 66. Plus One 67. Add Binary 69. Sqrt(x) 70. Climbing Stairs 71. Simplify Path 74. Search a 2D Matrix 75. Sort Colors 76. Minimum Window Substring 77. Combinations 78. Subsets 79. Word Search 80. Remove Duplicates from Sorted Array II 81. Search in Rotated Sorted Array II 82. Remove Duplicates from Sorted List II 83. Remove Duplicates from Sorted List 84. Largest Rectangle in Histogram 86. Partition List 88. Merge Sorted Array 89. Gray Code 90. Subsets II 91. Decode Ways 92. Reverse Linked List II 93. Restore IP Addresses 94. Binary Tree Inorder Traversal 95. Unique Binary Search Trees II 96. Unique Binary Search Trees 98. Validate Binary Search Tree 99. Recover Binary Search Tree 100. Same Tree 101. Symmetric Tree 102. Binary Tree Level Order Traversal 103. Binary Tree Zigzag Level Order Traversal 104. Maximum Depth of Binary Tree 105. Construct Binary Tree from Preorder and Inorder Traversal 106. Construct Binary Tree from Inorder and Postorder Traversal 107. Binary Tree Level Order Traversal II 108. Convert Sorted Array to Binary Search Tree 109. Convert Sorted List to Binary Search Tree 110. Balanced Binary Tree 111. Minimum Depth of Binary Tree 112. Path Sum 113. Path Sum II 114. Flatten Binary Tree to Linked List 120. Triangle 121. Best Time to Buy and Sell Stock 122. Best Time to Buy and Sell Stock II 124. Binary Tree Maximum Path Sum 125. Valid Palindrome 126. Word Ladder II 127. Word Ladder 128. Longest Consecutive Sequence 129. Sum Root to Leaf Numbers 130. Surrounded Regions 131. Palindrome Partitioning 136. Single Number 137. Single Number II 141. Linked List Cycle 143. Reorder List 144. Binary Tree Preorder Traversal 145. Binary Tree Postorder Traversal 147. Insertion Sort List 148. Sort List 150. Evaluate Reverse Polish Notation 151. Reverse Words in a String 152. Maximum Product Subarray 153. Find Minimum in Rotated Sorted Array 154. Find Minimum in Rotated Sorted Array II 155. Min Stack 160. Intersection of Two Linked Lists 162. Find Peak Element 164. Maximum Gap 167. Two Sum II - Input array is sorted 168. Excel Sheet Column Title 169. Majority Element 171. Excel Sheet Column Number 172. Factorial Trailing Zeroes 173. Binary Search Tree Iterator 174. Dungeon Game 179. Largest Number 187. Repeated DNA Sequences 190. Reverse Bits 191. Number of 1 Bits 198. House Robber 199. Binary Tree Right Side View 200. Number of Islands 201. Bitwise AND of Numbers Range 202. Happy Number 203. Remove Linked List Elements 204. Count Primes 205. Isomorphic Strings 206. Reverse Linked List 207. Course Schedule 208. Implement Trie (Prefix Tree) 209. Minimum Size Subarray Sum 210. Course Schedule II 211. Add and Search Word - Data structure design 212. Word Search II 213. House Robber II 215. Kth Largest Element in an Array 216. Combination Sum III 217. Contains Duplicate 218. The Skyline Problem 219. Contains Duplicate II 220. Contains Duplicate III 222. Count Complete Tree Nodes 223. Rectangle Area 224. Basic Calculator 225. Implement Stack using Queues 226. Invert Binary Tree 229. Majority Element II 230. Kth Smallest Element in a BST 231. Power of Two 232. Implement Queue using Stacks 234. Palindrome Linked List 235. Lowest Common Ancestor of a Binary Search Tree 236. Lowest Common Ancestor of a Binary Tree 237. Delete Node in a Linked List 239. Sliding Window Maximum 240. Search a 2D Matrix II 242. Valid Anagram 257. Binary Tree Paths 258. Add Digits 260. Single Number III 263. Ugly Number 268. Missing Number 274. H-Index 275. H-Index II 283. Move Zeroes 287. Find the Duplicate Number 290. Word Pattern 300. Longest Increasing Subsequence 303. Range Sum Query - Immutable 306. Additive Number 307. Range Sum Query - Mutable 309. Best Time to Buy and Sell Stock with Cooldown 315. Count of Smaller Numbers After Self 318. Maximum Product of Word Lengths 322. Coin Change 324. Wiggle Sort II 326. Power of Three 327. Count of Range Sum 328. Odd Even Linked List 329. Longest Increasing Path in a Matrix 331. Verify Preorder Serialization of a Binary Tree 337. House Robber III 338. Counting Bits 342. Power of Four 343. Integer Break 344. Reverse String 345. Reverse Vowels of a String 347. Top K Frequent Elements 349. Intersection of Two Arrays 350. Intersection of Two Arrays II 354. Russian Doll Envelopes 357. Count Numbers with Unique Digits 367. Valid Perfect Square 371. Sum of Two Integers 372. Super Pow 373. Find K Pairs with Smallest Sums 378. Kth Smallest Element in a Sorted Matrix 385. Mini Parser 386. Lexicographical Numbers 387. First Unique Character in a String 389. Find the Difference 392. Is Subsequence 393. UTF-8 Validation 394. Decode String 397. Integer Replacement 399. Evaluate Division 401. Binary Watch 402. Remove K Digits 404. Sum of Left Leaves 405. Convert a Number to Hexadecimal 409. Longest Palindrome 410. Split Array Largest Sum 412. Fizz Buzz 414. Third Maximum Number 416. Partition Equal Subset Sum 421. Maximum XOR of Two Numbers in an Array 424. Longest Repeating Character Replacement 433. Minimum Genetic Mutation 435. Non-overlapping Intervals 436. Find Right Interval 437. Path Sum III 438. Find All Anagrams in a String 441. Arranging Coins 445. Add Two Numbers II 447. Number of Boomerangs 448. Find All Numbers Disappeared in an Array 451. Sort Characters By Frequency 453. Minimum Moves to Equal Array Elements 454. 4Sum II 455. Assign Cookies 456. 132 Pattern 457. Circular Array Loop 461. Hamming Distance 463. Island Perimeter 470. Implement Rand10() Using Rand7() 474. Ones and Zeroes 475. Heaters 476. Number Complement 477. Total Hamming Distance 480. Sliding Window Median 483. Smallest Good Base 485. Max Consecutive Ones 491. Increasing Subsequences 493. Reverse Pairs 494. Target Sum 496. Next Greater Element I 497. Random Point in Non-overlapping Rectangles 498. Diagonal Traverse 500. Keyboard Row 503. Next Greater Element II 507. Perfect Number 508. Most Frequent Subtree Sum 509. Fibonacci Number 513. Find Bottom Left Tree Value 515. Find Largest Value in Each Tree Row 524. Longest Word in Dictionary through Deleting 526. Beautiful Arrangement 528. Random Pick with Weight 529. Minesweeper 532. K-diff Pairs in an Array 537. Complex Number Multiplication 541. Reverse String II 542. 01 Matrix 547. Friend Circles 557. Reverse Words in a String III 561. Array Partition I 563. Binary Tree Tilt 566. Reshape the Matrix 567. Permutation in String 572. Subtree of Another Tree 575. Distribute Candies 594. Longest Harmonious Subsequence 598. Range Addition II 599. Minimum Index Sum of Two Lists 628. Maximum Product of Three Numbers 632. Smallest Range Covering Elements from K Lists 633. Sum of Square Numbers 636. Exclusive Time of Functions 637. Average of Levels in Binary Tree 638. Shopping Offers 645. Set Mismatch 648. Replace Words 653. Two Sum IV - Input is a BST 658. Find K Closest Elements 661. Image Smoother 662. Maximum Width of Binary Tree 668. Kth Smallest Number in Multiplication Table 676. Implement Magic Dictionary 682. Baseball Game 684. Redundant Connection 685. Redundant Connection II 693. Binary Number with Alternating Bits 695. Max Area of Island 697. Degree of an Array 699. Falling Squares 704. Binary Search 705. Design HashSet 706. Design HashMap 707. Design Linked List 710. Random Pick with Blacklist 713. Subarray Product Less Than K 714. Best Time to Buy and Sell Stock with Transaction Fee 715. Range Module 717. 1-bit and 2-bit Characters 718. Maximum Length of Repeated Subarray 719. Find K-th Smallest Pair Distance 720. Longest Word in Dictionary 721. Accounts Merge 725. Split Linked List in Parts 726. Number of Atoms 729. My Calendar I 732. My Calendar III 733. Flood Fill 735. Asteroid Collision 739. Daily Temperatures 744. Find Smallest Letter Greater Than Target 745. Prefix and Suffix Search 746. Min Cost Climbing Stairs 748. Shortest Completing Word 753. Cracking the Safe 756. Pyramid Transition Matrix 762. Prime Number of Set Bits in Binary Representation 763. Partition Labels 765. Couples Holding Hands 766. Toeplitz Matrix 767. Reorganize String 771. Jewels and Stones 778. Swim in Rising Water 781. Rabbits in Forest 784. Letter Case Permutation 786. K-th Smallest Prime Fraction 793. Preimage Size of Factorial Zeroes Function 802. Find Eventual Safe States 803. Bricks Falling When Hit 811. Subdomain Visit Count 812. Largest Triangle Area 815. Bus Routes 817. Linked List Components 819. Most Common Word 826. Most Profit Assigning Work 828. Unique Letter String 832. Flipping an Image 834. Sum of Distances in Tree 836. Rectangle Overlap 838. Push Dominoes 839. Similar String Groups 841. Keys and Rooms 842. Split Array into Fibonacci Sequence 844. Backspace String Compare 845. Longest Mountain in Array 850. Rectangle Area II 851. Loud and Rich 852. Peak Index in a Mountain Array 853. Car Fleet 856. Score of Parentheses 862. Shortest Subarray with Sum at Least K 863. All Nodes Distance K in Binary Tree 864. Shortest Path to Get All Keys 867. Transpose Matrix 872. Leaf-Similar Trees 875. Koko Eating Bananas 876. Middle of the Linked List 878. Nth Magical Number 880. Decoded String at Index 881. Boats to Save People 884. Uncommon Words from Two Sentences 885. Spiral Matrix III 887. Super Egg Drop 888. Fair Candy Swap 891. Sum of Subsequence Widths 892. Surface Area of 3D Shapes 895. Maximum Frequency Stack 896. Monotonic Array 897. Increasing Order Search Tree 898. Bitwise ORs of Subarrays 901. Online Stock Span 904. Fruit Into Baskets 907. Sum of Subarray Minimums 911. Online Election 914. X of a Kind in a Deck of Cards 918. Maximum Sum Circular Subarray 920. Number of Music Playlists 921. Minimum Add to Make Parentheses Valid 922. Sort Array By Parity II 923. 3Sum With Multiplicity 924. Minimize Malware Spread 925. Long Pressed Name 927. Three Equal Parts 928. Minimize Malware Spread II 930. Binary Subarrays With Sum 933. Number of Recent Calls 942. DI String Match 946. Validate Stack Sequences 947. Most Stones Removed with Same Row or Column 949. Largest Time for Given Digits 952. Largest Component Size by Common Factor 953. Verifying an Alien Dictionary 959. Regions Cut By Slashes 961. N-Repeated Element in Size 2N Array 968. Binary Tree Cameras 969. Pancake Sorting 970. Powerful Integers 973. K Closest Points to Origin 976. Largest Perimeter Triangle 977. Squares of a Sorted Array 978. Longest Turbulent Subarray 979. Distribute Coins in Binary Tree 980. Unique Paths III 981. Time Based Key-Value Store 984. String Without AAA or BBB 985. Sum of Even Numbers After Queries 986. Interval List Intersections 990. Satisfiability of Equality Equations 992. Subarrays with K Different Integers 993. Cousins in Binary Tree 995. Minimum Number of K Consecutive Bit Flips 996. Number of Squareful Arrays 999. Available Captures for Rook 1002. Find Common Characters 1003. Check If Word Is Valid After Substitutions 1004. Max Consecutive Ones III 1005. Maximize Sum Of Array After K Negations 1011. Capacity To Ship Packages Within D Days 1017. Convert to Base -2 1019. Next Greater Node In Linked List 1020. Number of Enclaves 1021. Remove Outermost Parentheses 1025. Divisor Game 1026. Maximum Difference Between Node and Ancestor 1028. Recover a Tree From Preorder Traversal 1030. Matrix Cells in Distance Order 1037. Valid Boomerang 1040. Moving Stones Until Consecutive II 1047. Remove All Adjacent Duplicates In String 1049. Last Stone Weight II 1051. Height Checker 1052. Grumpy Bookstore Owner 1054. Distant Barcodes 1073. Adding Two Negabinary Numbers 1074. Number of Submatrices That Sum to Target 1078. Occurrences After Bigram 1079. Letter Tile Possibilities 1089. Duplicate Zeros 1093. Statistics from a Large Sample 1105. Filling Bookcase Shelves 1108. Defanging an IP Address 1110. Delete Nodes And Return Forest 1111. Maximum Nesting Depth of Two Valid Parentheses Strings 1122. Relative Sort Array 1123. Lowest Common Ancestor of Deepest Leaves 1128. Number of Equivalent Domino Pairs 1137. N-th Tribonacci Number 1145. Binary Tree Coloring Game 1154. Day of the Year 1157. Online Majority Element In Subarray 1160. Find Words That Can Be Formed by Characters 1170. Compare Strings by Frequency of the Smallest Character 1171. Remove Zero Sum Consecutive Nodes from Linked List 1175. Prime Arrangements 1184. Distance Between Bus Stops 1185. Day of the Week 1189. Maximum Number of Balloons 1200. Minimum Absolute Difference 1201. Ugly Number III 1202. Smallest String With Swaps 1207. Unique Number of Occurrences 1208. Get Equal Substrings Within Budget 1217. Play with Chips 1221. Split a String in Balanced Strings 1232. Check If It Is a Straight Line 1234. Replace the Substring for Balanced String 1235. Maximum Profit in Job Scheduling 1252. Cells with Odd Values in a Matrix 1254. Number of Closed Islands 1260. Shift 2D Grid 1266. Minimum Time Visiting All Points 1275. Find Winner on a Tic Tac Toe Game 1281. Subtract the Product and Sum of Digits of an Integer 1283. Find the Smallest Divisor Given a Threshold 1287. Element Appearing More Than 25% In Sorted Array 1290. Convert Binary Number in a Linked List to Integer 1295. Find Numbers with Even Number of Digits 1299. Replace Elements with Greatest Element on Right Side 1300. Sum of Mutated Array Closest to Target 1302. Deepest Leaves Sum 1304. Find N Unique Integers Sum up to Zero 1305. All Elements in Two Binary Search Trees 1306. Jump Game III 1313. Decompress Run-Length Encoded List 1317. Convert Integer to the Sum of Two No-Zero Integers 1380. Lucky Numbers in a Matrix 1385. Find the Distance Value Between Two Arrays 1389. Create Target Array in the Given Order 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence 1464. Maximum Product of Two Elements in an Array 1470. Shuffle the Array 第⼀章 序章 关于 LeetCode 说到 LeetCode，作为⼀个程序员来说，应该不陌⽣，近⼏年参加⾯试都会提到它。国内外的程序员⽤ 它刷题主要是为了⾯试。据历史记载，这个⽹站 2011 年就成⽴了，⻢上就要到⾃⼰ 10 周年的⽣⽇ 了。每周举⾏周赛，双周赛，⽉赛，在有限时间内编码，确实⾮常能考验⼈的算法能⼒。⼀些⼤公司赞 助冠名的⽐赛获得前⼏名除了有奖品，还能直接拿到内推的机会。 什么是 Cookbook 直译的话就是烹饪书，教你做各种⻝谱美⻝的书。经常看 O'Reilly 技术书的同学对这个名词会很熟悉。 ⼀般动⼿操作，实践类的书都会有这个名字。 为什么会写这个开源书 笔者刷题刷了⼀年了，想和⼤家分享分享⼀些做题⼼得，解题⽅法。想和有相同爱好的⼈交个朋友，⼀ 起交流学习。对于⾃⼰来说，写题解也是⼀种提⾼。把⼀道深奥的题⽬讲给⼀点都没有头绪的⼈，并能 让他完全听懂，很能锻炼⼈的表达能⼒。在讲解中很可能还会遇到听者的⼀些提问，这些问题可能是⾃ ⼰的知识漏洞，强迫⾃⼰去弥补。笔者在公司做过相关的分享，感受很深，双⽅受益都还不错。 另外，在⼤学期间，笔者做题的时候 讨厌写题解，感觉是浪费时间，⽤更多的时间去做更多的 题。现在不知道算不算是“出来混的，总是要还的”。 关于书的封⾯ 常看 O'Reilly 动物书的同学⼀看这个封⾯就知道是向他们致敬。确实是这个⽬的。O'Reilly 的封⾯动物 都是稀缺动物，并且画⻛都是⿊⽩素描⻛。这些动物都有版权了，所以只能在⽹上找没有版权的⿊⽩素 描⻛的图⽚。常⻅的能找到 40 张这种⻛格的图⽚。不过⽤的⼈太多了，笔者费劲的找了其他⼏张这种 图⽚，这张孔雀开屏是其中⼀张。孔雀开屏的意义是希望⼤家刷完 LeetCode 以后，提⾼了⾃身的算法 能⼒，在⼈⽣的舞台上开出⾃⼰的“屏”。全书配⾊也都是绿⾊，因为这是 AC 的颜⾊。 关于作者 笔者是⼀个刚刚⼊⾏⼀年半的 gopher 新⼈，还请各位⼤佬多多指点⼩弟我。⼤学参加了 3 年 ACM- ICPC，但是由于资质不⾼，没有拿到⼀块⾦牌。所以在算法⽅⾯，我对⾃⼰的评价算是新⼿吧。参加 ACM-ICPC ⼤的收获是训练了思维能⼒，这种能⼒也会运⽤到⽣活中。其次是认识了很多国内很聪明 的选⼿，看到了⾃⼰和他们的差距。 后，就是那 200 多⻚，有些⾃⼰都没有完全理解的，打印的密密 麻麻的算法模板。知识学会了，终身都是⾃⼰的，没有学会，那些知识都是身外之物。 笔者从 2019 年 3 ⽉ 25 号开始刷题，到 2020 年 3 ⽉ 25 号，整整⼀年的时间。原计划是每天⼀题。实 际上每天有时候不⽌⼀题， 终完成了 600+： ⼀个温馨提示：笔者本以为每天做⼀题，会让这个 submissions 图全绿，但是我发现我错了。如 果你也想坚持，让这个图全绿，⼀定要注意以下的问题：LeetCode 服务器是在 +0 时区的，这个 图也是按照这个时区计算的。也就是说，中国每天早上 8 点之前，是算前⼀天的！也是因为时区 的问题，导致我空⽩了这 22 个格⼦。⽐如有⼀道 Hard 题很难，当天⼯作也很多，晚上下班回家 想出来了就到第⼆天凌晨了。于是再做⼀题当做第⼆天的量。结果会发现这 2 题都算前⼀天的。 有时候笔者早上 6 点起床刷题，提交以后也都是前⼀天的。 (当然这些都是过去了，不重要了，全当是奋⽃路上的⼀些⼩插曲) 2020 年笔者肯定还会继续刷题，因为还没有达到⾃⼰的⼀些⽬标。可能会朝着 1000 题奋进，也有可能 刷到 800 题的时候回头开始⼆刷，三刷。(不达⽬的不罢休吧~) 关于书中的代码 代码都放在 github repo 中，按题号可以搜索到题⽬。 本书题⽬的代码都已经 beats 100% 了。没有 beats 100% 题解就没有放到本书中了。那些题⽬笔者会 继续优化到 100% 再放进来。 有可能读者会问，为何要追求 beats 100%。笔者认为优化到 beats 100% 才算是把这题做出感觉了。 有好⼏道 Hard 题，笔者都⽤暴⼒解法 AC 了，然后只 beats 了 5%。这题就如同没做⼀样。⽽且⾯试中 如果给了这样的答案，⾯试官也不会满意，“还有没有更优解？”。如果通过⾃⼰的思考能给出更优解， ⾯试官会更满意⼀些。 LeetCode 统计代码运⾏时⻓会有波动的，相同的代码提交 10 次可能就会 beats 100% 了。笔者开始没 有发现这个问题，很多题⽤正确的代码连续交了很多次，⼀年提交 3400+ 次，导致我的正确率也变的奇 ⾼。 ! 当然，如果还有其他更优美的解法，也能 beats 100% 的，欢迎提交 PR，笔者和⼤家⼀起学习。 ⽬标读者 想通过 LeetCode 提⾼算法能⼒的编程爱好者。 编程语⾔ 本书的算法全部⽤ Go 语⾔实现。 使⽤说明 本电⼦书的左上⻆有搜索栏，可以迅速帮你找到你想看的章节和题号。 本电⼦书每⻚都接⼊了 Gitalk，每⼀⻚的 下⽅都有评论框可以评论，如果没有显示出来，请检查 ⾃⼰的⽹络。 关于题解，笔者建议这样使⽤：先⾃⼰读题，思考如何解题。如果 15 分钟还没有思路，那么先看 笔者的解题思路，但是不要看代码。有思路以后⾃⼰⽤代码实现⼀遍。如果完全不会写，那就看笔 者提供的代码，找出⾃⼰到底哪⾥不会写，找出问题记下来，这就是⾃⼰要弥补的知识漏洞。如果 ⾃⼰实现出来了，提交以后有错误，⾃⼰先 debug。AC 以后没有到 100% 也先⾃⼰思考如何优 化。如果每道题⾃⼰都能优化到 100% 了，那么⼀段时间以后进步会很⼤。所以总的来说，实在没 思路，看解题思路；实在优化不到 100%，看看代码。 互动与勘误 如果书中⽂章有所遗漏，欢迎点击所在⻚⾯下边的 edit 按钮进⾏评论和互动，感谢您的⽀持与帮助。 最后 ⼀起开始刷题吧~ 本作品采⽤ 知识署名-⾮商业性使⽤-禁⽌演绎 （BY-NC-ND） 4.0 国际许可协议 进⾏许可。 题解⾥⾯的所有题⽬版权均归 LeetCode 和 ⼒扣中国 所有 第⼆章 算法专题 Title Solution Difficulty Time Space 收 藏 1. Two Sum Go Easy O(n) O(n) 11. Container With Most Water Go Medium O(n) O(1) 15. 3Sum Go Medium O(n^2) O(n) ❤ 16. 3Sum Closest Go Medium O(n^2) O(1) 本来天真的认为，把 LeetCode 所有题都完整刷⼀遍，就可以完整这本书了。经过事实证明，确实是天 真了。因为 LeetCode 每天都会增加新题，有时候⼯作忙了，刷题进度就完全追不上题⽬更新的速度 了。⽽且以我当前的刷题速度，⼀年才完成 500+，⼀年 LeetCode 也会更新 400+ 多题，要起码 5~10 年才能把所有的题⽬刷完。时间太⻓了。所以先给⾃⼰定了⼀个⼩⽬标，500 题就先把书写出来，总结 这个阶段的刷题⼼得，和⼤家⼀起交流。要想把 LeetCode 所有题⽬都刷完，看来这本书要迭代 5 ~ 10 个版本了(⼀年迭代⼀版)。 那么这⼀章就把已经刷完了的专题都整理⼀遍。有相似套路的题⽬都放在⼀起，如果想快速⾯试的话， 其实相同的题⽬刷 2，3 道就可以了。相同类型的题⽬⾮常熟练的情况下，再多刷⼏道也是做⽆⽤功。 做到⽬前为⽌，笔者认为动态规划是 灵活的类型，这类题⽬没有⼀个模板可以给你套⽤，它也是算法 之优雅的地⽅。笔者认为称它为算法的艺术不为过。动态规划这类型，笔者也还没有刷完，只刷了⼀部 分，还在学习中。 那么就分享⼀下笔者⽬前刷过的题，和有相似点的题⽬吧。 Array 18. 4Sum Go Medium O(n^3) O(n^2) ❤ 26. Remove Duplicates from Sorted Array Go Easy O(n) O(1) 27. Remove Element Go Easy O(n) O(1) 39. Combination Sum Go Medium O(n log n) O(n) 40. Combination Sum II Go Medium O(n log n) O(n) 41. First Missing Positive Go Hard O(n) O(n) 42. Trapping Rain Water Go Hard O(n) O(1) 48. Rotate Image Go Medium O(n) O(1) 53. Maximum Subarray Go Easy O(n) O(n) 54. Spiral Matrix Go Medium O(n) O(n^2) 56. Merge Intervals Go Medium O(n log n) O(1) 57. Insert Interval Go Hard O(n) O(1) 59. Spiral Matrix II Go Medium O(n) O(n^2) 62. Unique Paths Go Medium O(n^2) O(n^2) 63. Unique Paths II Go Medium O(n^2) O(n^2) 64. Minimum Path Sum Go Medium O(n^2) O(n^2) 75. Sort Colors Go Medium O(n) O(1) 78. Subsets Go Medium O(n^2) O(n) 79. Word Search Go Medium O(n^2) O(n^2) 80. Remove Duplicates from Sorted Array II Go Medium O(n) O(1 84. Largest Rectangle in Histogram Go Medium O(n) O(n) 88. Merge Sorted Array Go Easy O(n) O(1) 90. Subsets II Go Medium O(n^2) O(n) 120. Triangle Go Medium O(n^2) O(n) 121. Best Time to Buy and Sell Stock Go Easy O(n) O(1) 122. Best Time to Buy and Sell Stock II Go Easy O(n) O(1) 126. Word Ladder II Go Hard O(n) O(n^2) ❤ 152. Maximum Product Subarray Go Medium O(n) O(1) 167. Two Sum II - Input array is sorted Go Easy O(n) O(1) 209. Minimum Size Subarray Sum Go Medium O(n) O(1) 216. Combination Sum III Go Medium O(n) O(1) 217. Contains Duplicate Go Easy O(n) O(n) 219. Contains Duplicate II Go Easy O(n) O(n) 283. Move Zeroes Go Easy O(n) O(1) 287. Find the Duplicate Number Go Easy O(n) O(1) 532. K-diff Pairs in an Array Go Easy O(n) O(n) 566. Reshape the Matrix Go Easy O(n^2) O(n^2) 628. Maximum Product of Three Numbers Go Easy O(n) O(1) 713. Subarray Product Less Than K Go Medium O(n) O(1) 714. Best Time to Buy and Sell Stock with Transaction Fee Go Medium O(n) O(1) 746. Min Cost Climbing Stairs Go Easy O(n) O(1) 766. Toeplitz Matrix Go Easy O(n) O(1) 867. Transpose Matrix Go Easy O(n) O(1) 891. Sum of Subsequence Widths Go Hard O(n log n) O(1) 907. Sum of Subarray Minimums Go Medium O(n) O(n) 922. Sort Array By Parity II Go Medium O(n) O(1) 969. Pancake Sorting Go Medium O(n) O(1) 977. Squares of a Sorted Array Go Easy O(n) O(1) --------------------------------------- ------------------- -------------- --------------- ----------- ------------- ---------- --------- -- ---- ---- Backtracking 排列问题 Permutations。第 46 题，第 47 题。第 60 题，第 526 题，第 996 题。 组合问题 Combination。第 39 题，第 40 题，第 77 题，第 216 题。 排列和组合杂交问题。第 1079 题。 N 皇后终极解法(⼆进制解法)。第 51 题，第 52 题。 数独问题。第 37 题。 四个⽅向搜索。第 79 题，第 212 题，第 980 题。 ⼦集合问题。第 78 题，第 90 题。 Trie。第 208 题，第 211 题。 BFS 优化。第 126 题，第 127 题。 DFS 模板。(只是⼀个例⼦，不对应任何题) BFS 模板。(只是⼀个例⼦，不对应任何题) func combinationSum2(candidates []int, target int) [][]int { if len(candidates) == 0 { return [][]int{} } c, res := []int{}, [][]int{} sort.Ints(candidates) findcombinationSum2(candidates, target, 0, c, &res) return res } func findcombinationSum2(nums []int, target, index int, c []int, res *[][]int) { if target == 0 { b := make([]int, len(c)) copy(b, c) *res = append(*res, b) return } for i := index; i < len(nums); i++ { if i > index && nums[i] == nums[i-1] { // 这⾥是去重的关键逻辑 continue } if target >= nums[i] { c = append(c, nums[i]) findcombinationSum2(nums, target-nums[i], i+1, c, res) c = c[:len(c)-1] } } } func updateMatrix_BFS(matrix [][]int) [][]int { Title Solution Difficulty Time Space 收 藏 17. Letter Combinations of a Go Medium O(1) res := make([][]int, len(matrix)) if len(matrix) == 0 || len(matrix[0]) == 0 { return res } queue := make([][]int, 0) for i, _ := range matrix { res[i] = make([]int, len(matrix[0])) for j, _ := range res[i] { if matrix[i][j] == 0 { res[i][j] = -1 queue = append(queue, []int{i, j}) } } } level := 1 for len(queue) > 0 { size := len(queue) for size > 0 { size -= 1 node := queue[0] queue = queue[1:] i, j := node[0], node[1] for _, direction := range [][]int{{-1, 0}, {1, 0}, {0, 1}, {0, -1}} { x := i + direction[0] y := j + direction[1] if x < 0 || x >= len(matrix) || y < 0 || y >= len(matrix[0]) || res[x] [y] < 0 || res[x][y] > 0 { continue } res[x][y] = level queue = append(queue, []int{x, y}) } } level++ } for i, row := range res { for j, cell := range row { if cell == -1 { res[i][j] = 0 } } } return res } Phone Number O(log n) 22. Generate Parentheses Go Medium O(log n) O(1) 37. Sudoku Solver Go Hard O(n^2) O(n^2) ❤ 39. Combination Sum Go Medium O(n log n) O(n) 40. Combination Sum II Go Medium O(n log n) O(n) 46. Permutations Go Medium O(n) O(n) 47. Permutations II Go Medium O(n^2) O(n) 51. N-Queens Go Hard O(n^2) O(n) 52. N-Queens II Go Hard O(n^2) O(n) 60. Permutation Sequence Go Medium O(n log n) O(1) 77. Combinations Go Medium O(n) O(n) 78. Subsets Go Medium O(n^2) O(n) 79. Word Search Go Medium O(n^2) O(n^2) 89. Gray Codes Go Medium O(n) O(1) 90. Subsets II Go Medium O(n^2) O(n) 93. Restore IP Addresses Go Medium O(n) O(n) 126. Word Ladder II Go Hard O(n) O(n^2) 131. Palindrome Partitioning Go Medium O(n) O(n^2) 211. Add and Search Word - Data structure design Go Medium O(n) O(n) 212. Word Search II Go Hard O(n^2) O(n^2) 216. Combination Sum III Go Medium O(n) O(1) 306. Additive Number Go Medium O(n^2) O(1) 357. Count Numbers with Unique Digits Go Medium O(1) O(1) 401. Binary Watch Go Easy O(1) O(1) 526. Beautiful Arrangement Go Medium O(n^2) O(1) 784. Letter Case Permutation Go Easy O(n) O(n) 842. Split Array into Fibonacci Sequence Go Medium O(n^2) O(1) 980. Unique Paths III Go Hard O(n log n) O(n) 996. Number of Squareful Arrays Go Hard O(n log n) O(n) 1079. Letter Tile Possibilities Go Medium O(n^2) O(1) ❤ --------------------------------------- --------------------- ------------ ---------------- ---------- -------------- --------- --------- -- ---- ---- Binary Indexed Tree Binary Search ⼆分搜索的经典写法。需要注意的三点： 1. 循环退出条件，注意是 low <= high，⽽不是 low < high。 2. mid 的取值，mid := low + (high-low)>>1 3. low 和 high 的更新。low = mid + 1，high = mid - 1。 func binarySearchMatrix(nums []int, target int) int { low, high := 0, len(nums)-1 for low <= high { mid := low + (high-low)>>1 if nums[mid] == target { return mid } else if nums[mid] > target { high = mid - 1 } else { low = mid + 1 ⼆分搜索的变种写法。有 4 个基本变种: 1. 查找第⼀个与 target 相等的元素，时间复杂度 O(logn) 2. 查找 后⼀个与 target 相等的元素，时间复杂度 O(logn) 3. 查找第⼀个⼤于等于 target 的元素，时间复杂度 O(logn) 4. 查找 后⼀个⼩于等于 target 的元素，时间复杂度 O(logn) } } return -1 } // ⼆分查找第⼀个与 target 相等的元素，时间复杂度 O(logn) func searchFirstEqualElement(nums []int, target int) int { low, high := 0, len(nums)-1 for low <= high { mid := low + ((high - low) >> 1) if nums[mid] > target { high = mid - 1 } else if nums[mid] < target { low = mid + 1 } else { if (mid == 0) || (nums[mid-1] != target) { // 找到第⼀个与 target 相等的元素 return mid } high = mid - 1 } } return -1 } // ⼆分查找 后⼀个与 target 相等的元素，时间复杂度 O(logn) func searchLastEqualElement(nums []int, target int) int { low, high := 0, len(nums)-1 for low <= high { mid := low + ((high - low) >> 1) if nums[mid] > target { high = mid - 1 } else if nums[mid] < target { low = mid + 1 } else { if (mid == len(nums)-1) || (nums[mid+1] != target) { // 找到 后⼀个与 target 相等的元素 return mid } low = mid + 1 } } return -1 在基本有序的数组中⽤⼆分搜索。经典解法可以解，变种写法也可以写，常⻅的题型，在⼭峰数组 中找⼭峰，在旋转有序数组中找分界点。第 33 题，第 81 题，第 153 题，第 154 题，第 162 题， 第 852 题 } // ⼆分查找第⼀个⼤于等于 target 的元素，时间复杂度 O(logn) func searchFirstGreaterElement(nums []int, target int) int { low, high := 0, len(nums)-1 for low <= high { mid := low + ((high - low) >> 1) if nums[mid] >= target { if (mid == 0) || (nums[mid-1] < target) { // 找到第⼀个⼤于等于 target 的元 素 return mid } high = mid - 1 } else { low = mid + 1 } } return -1 } // ⼆分查找 后⼀个⼩于等于 target 的元素，时间复杂度 O(logn) func searchLastLessElement(nums []int, target int) int { low, high := 0, len(nums)-1 for low <= high { mid := low + ((high - low) >> 1) if nums[mid] <= target { if (mid == len(nums)-1) || (nums[mid+1] > target) { // 找到 后⼀个⼩于等于 target 的元素 return mid } low = mid + 1 } else { high = mid - 1 } } return -1 } max-min ⼤值 ⼩化问题。求在 ⼩满⾜条件的情况下的 ⼤值。第 410 题，第 875 题，第 1011 题，第 1283 题。 func peakIndexInMountainArray(A []int) int { low, high := 0, len(A)-1 for low < high { mid := low + (high-low)>>1 // 如果 mid 较⼤，则左侧存在峰值，high = m，如果 mid + 1 较⼤，则右侧存在峰值，low = mid + 1 if A[mid] > A[mid+1] { high = mid } else { low = mid + 1 } } return low } Title Solution Difficulty Time Space 收 藏 50. Pow(x, n) Go Medium O(log n) O(1) 69. Sqrt(x) Go Easy O(log n) O(1) 167. Two Sum II - Input array is sorted Go Easy O(n) O(1) 209. Minimum Size Subarray Sum Go Medium O(n) O(1) 222. Count Complete Tree Nodes Go Medium O(n) O(1) 230. Kth Smallest Element in a BST Go Medium O(n) O(1) 287. Find the Duplicate Number Go Easy O(n) O(1) ❤ 300. Longest Increasing Subsequence Go Medium O(n log n) O(n) 349. Intersection of Two Arrays Go Easy O(n) O(n) 350. Intersection of Two Arrays II Go Easy O(n) O(n) 392. Is Subsequence Go Medium O(n) O(1) 454. 4Sum II Go Medium O(n^2) O(n) 710. Random Pick with Blacklist Go Hard O(n) O(n) ----------------------------------------- ------ ------------------------ --------- ------------------ -------- ---------------- ------- -------- --- ---- ---- Bit Manipulation 异或的特性。第 136 题，第 268 题，第 389 题，第 421 题， Title Solution Difficulty Time Space 收 藏 78. Subsets Go Medium O(n^2) O(n) ❤ 136. Single Number Go Easy O(n) O(1) 137. Single Number II Go Medium O(n) O(1) 169. Majority Element Go Easy O(n) O(1) 187. Repeated DNA Sequences Go Medium O(n) O(1) 190. Reverse Bits Go Easy O(n) O(1) 191. Number of 1 Bits Go Easy O(n) O(1) 201. Bitwise AND of Numbers Range Go Medium O(n) O(1) 231. Power of Two Go Easy O(1) O(1) 260. Single Number III Go Medium O(n) O(1) 268. Missing Number Go Easy O(n) O(1) 318. Maximum Product of Word 构造特殊 Mask，将特殊位置放 0 或 1。 有特殊意义的 & 位操作运算。第 260 题，第 201 题，第 318 题，第 371 题，第 397 题，第 461 题，第 693 题， x ^ 0 = x x ^ 11111……1111 = ~x x ^ (~x) = 11111……1111 x ^ x = 0 a ^ b = c => a ^ c = b => b ^ c = a (交换律) a ^ b ^ c = a ^ (b ^ c) = (a ^ b）^ c (结合律) 将 x 右边的 n 位清零， x & ( ~0 << n ) 获取 x 的第 n 位值(0 或者 1)，(x >> n) & 1 获取 x 的第 n 位的幂值，x & (1 << (n - 1)) 仅将第 n 位置为 1，x | (1 << n) 仅将第 n 位置为 0，x & (~(1 << n)) 将 x ⾼位⾄第 n 位(含)清零，x & ((1 << n) - 1) 将第 n 位⾄第 0 位(含)清零，x & (~((1 << (n + 1)) - 1)） X & 1 == 1 判断是否是奇数(偶数) X & = (X - 1) 将 低位(LSB)的 1 清零 X & -X 得到 低位(LSB)的 1 X & ~X = 0 Lengths Go Medium O(n) O(1) 338. Counting Bits Go Medium O(n) O(n) 342. Power of Four Go Easy O(n) O(1) 371. Sum of Two Integers Go Easy O(n) O(1) 389. Find the Difference Go Easy O(n) O(1) 393. UTF-8 Validation Go Medium O(n) O(1) 397. Integer Replacement Go Medium O(n) O(1) 401. Binary Watch Go Easy O(1) O(1) 405. Convert a Number to Hexadecimal Go Easy O(n) O(1) 421. Maximum XOR of Two Numbers in an Array Go Medium O(n) O(1) ❤ 461. Hamming Distance Go Easy O(n) O(1) 476. Number Complement Go Easy O(n) O(1) 477. Total Hamming Distance Go Medium O(n) O(1) 693. Binary Number with Alternating Bits Go Easy O(n) O(1) 756. Pyramid Transition Matrix Go Medium O(n log n) O(n) 762. Prime Number of Set Bits in Binary Representation Go Easy O(n) O(1) 784. Letter Case Permutation Go Easy O(n) O(1) 898. Bitwise ORs of Subarrays Go Medium O(n) O(1) --------------------------------------- -------------------- ------------- ---------------- ---------- ------------- ---------- -------- --- ---- ---- Breadth First Search