2023-02-23 leetcode-数据结构_匈 利算法bfs

⽬录

第⼀章 序章

数据结构知识

算法知识

第⼆章 算法专题

Array

String

Two Pointers

Linked List

Stack

Tree

Dynamic Programming

Backtracking

Depth First Search

Breadth First Search

Binary Search

Math

Hash Table

Sort

Bit Manipulation

Union Find

Sliding Window

Segment Tree

Binary Indexed Tree

第三章 ⼀些模板

线段树 Segment Tree

并查集 UnionFind

最近最少使⽤ LRUCache

最不经常最少使⽤ LFUCache

第四章 LeetCode 题解

1. Two Sum

2. Add Two Numbers

----------------------- Page 3-----------------------

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

31. Next Permutation

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

----------------------- Page 4-----------------------

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

----------------------- Page 5-----------------------

114. Flatten Binary Tree to Linked List

118. Pascal's Triangle

119. Pascal's Triangle II

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

138. Copy List with Random Pointer

141. Linked List Cycle

142. Linked List Cycle II

143. Reorder List

144. Binary Tree Preorder Traversal

145. Binary Tree Postorder Traversal

146. LRU Cache

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

189. Rotate Array

190. Reverse Bits

191. Number of 1 Bits

----------------------- Page 6-----------------------

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. Design Add and Search Words Data Structure

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

228. Summary Ranges

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

----------------------- Page 7-----------------------

283. Move Zeroes

284. Peeking Iterator

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

----------------------- Page 8-----------------------

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

460. LFU Cache

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

----------------------- Page 9-----------------------

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

538. Convert BST to Greater Tree

541. Reverse String II

542. 01 Matrix

547. Number of Provinces

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

605. Can Place Flowers

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

643. Maximum Average Subarray I

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

665. Non-decreasing Array

668. Kth Smallest Number in Multiplication Table

669. Trim a Binary Search Tree

674. Longest Continuous Increasing Subsequence

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

----------------------- Page 10-----------------------

699. Falling Squares

703. Kth Largest Element in a Stream

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

724. Find Pivot Index

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

785. Is Graph Bipartite?

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

----------------------- Page 11-----------------------

817. Linked List Components

819. Most Common Word

821. Shortest Distance to a Character

826. Most Profit Assigning Work

828. Count Unique Characters of All Substrings of a Given String

830. Positions of Large Groups

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

910. Smallest Range II

911. Online Election

914. X of a Kind in a Deck of Cards

----------------------- Page 12-----------------------

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

987. Vertical Order Traversal of a Binary Tree

989. Add to Array-Form of Integer

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

----------------------- Page 13-----------------------

1018. Binary Prefix Divisible By 5

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

1038. Binary Search Tree to Greater Sum Tree

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

1091. Shortest Path in Binary Matrix

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

1203. Sort Items by Groups Respecting Dependencies

1207. Unique Number of Occurrences

----------------------- Page 14-----------------------

1208. Get Equal Substrings Within Budget

1217. Minimum Cost to Move Chips to The Same Position

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

1319. Number of Operations to Make Network Connected

1329. Sort the Matrix Diagonally

1380. Lucky Numbers in a Matrix

1385. Find the Distance Value Between Two Arrays

1389. Create Target Array in the Given Order

1423. Maximum Points You Can Obtain from Cards

1437. Check If All 1's Are at Least Length K Places Away

1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence

1463. Cherry Pickup II

1464. Maximum Product of Two Elements in an Array

1470. Shuffle the Array

1480. Running Sum of 1d Array

1512. Number of Good Pairs

1539. Kth Missing Positive Number

1573. Number of Ways to Split a String

1579. Remove Max Number of Edges to Keep Graph Fully Traversable

1603. Design Parking System

1608. Special Array With X Elements Greater Than or Equal X

1614. Maximum Nesting Depth of the Parentheses

1619. Mean of Array After Removing Some Elements

1624. Largest Substring Between Two Equal Characters

----------------------- Page 15-----------------------

1629. Slowest Key

1631. Path With Minimum Effort

1636. Sort Array by Increasing Frequency

1640. Check Array Formation Through Concatenation

1641. Count Sorted Vowel Strings

1646. Get Maximum in Generated Array

1647. Minimum Deletions to Make Character Frequencies Unique

1648. Sell Diminishing-Valued Colored Balls

1649. Create Sorted Array through Instructions

1652. Defuse the Bomb

1653. Minimum Deletions to Make String Balanced

1654. Minimum Jumps to Reach Home

1655. Distribute Repeating Integers

1656. Design an Ordered Stream

1657. Determine if Two Strings Are Close

1658. Minimum Operations to Reduce X to Zero

1659. Maximize Grid Happiness

1662. Check If Two String Arrays are Equivalent

1663. Smallest String With A Given Numeric Value

1664. Ways to Make a Fair Array

1665. Minimum Initial Energy to Finish Tasks

1668. Maximum Repeating Substring

1669. Merge In Between Linked Lists

1670. Design Front Middle Back Queue

1672. Richest Customer Wealth

1673. Find the Most Competitive Subsequence

1674. Minimum Moves to Make Array Complementary

1675. Minimize Deviation in Array

1678. Goal Parser Interpretation

1679. Max Number of K-Sum Pairs

1680. Concatenation of Consecutive Binary Numbers

1681. Minimum Incompatibility

1684. Count the Number of Consistent Strings

1685. Sum of Absolute Differences in a Sorted Array

1688. Count of Matches in Tournament

1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

1690. Stone Game VII

1691. Maximum Height by Stacking Cuboids

1694. Reformat Phone Number

1695. Maximum Erasure Value

1696. Jump Game VI

1700. Number of Students Unable to Eat Lunch

1704. Determine if String Halves Are Alike

1716. Calculate Money in Leetcode Bank

1720. Decode XORed Array

1725. Number Of Rectangles That Can Form The Largest Square

----------------------- Page 16-----------------------

1732. Find the Highest Altitude

1736. Latest Time by Replacing Hidden Digits

1742. Maximum Number of Balls in a Box

1748. Sum of Unique Elements

1752. Check if Array Is Sorted and Rotated

1758. Minimum Changes To Make Alternating Binary String]

第⼀章 序章

关于 LeetCode

说到 LeetCode ，作为⼀个程序员来说，应该不陌⽣，近⼏年参加⾯试都会提到它。国内外的程序员⽤它

刷题主要是为了⾯试。据历史记载，这个⽹站 2011 年就成⽴了，⻢上就要到⾃⼰ 10 周年的⽣⽇了。每

周举⾏周赛，双周赛，⽉赛，在有限时间内编码，确实⾮常能考验⼈的算法能⼒。⼀些⼤公司赞助冠名

的⽐赛获得前⼏名除了有奖品，还能直接拿到内推的机会。

什么是 Cookbook

直译的话就是烹饪书，教你做各种⻝谱美⻝的书。经常看 O'Reilly 技术书的同学对这个名词会很熟悉。

⼀般动⼿操作，实践类的书都会有这个名字。

为什么会写这个开源书

笔者刷题刷了⼀年了，想和⼤家分享分享⼀些做题⼼得，解题⽅法。想和有相同爱好的⼈交个朋友，⼀

起交流学习。对于⾃⼰来说，写题解也是⼀种提⾼。把⼀道深奥的题⽬讲给⼀点都没有头绪的⼈，并能

让他完全听懂，很能锻炼⼈的表达能⼒。在讲解中很可能还会遇到听者的⼀些提问，这些问题可能是⾃

⼰的知识漏洞，强迫⾃⼰去弥补。笔者在公司做过相关的分享，感受很深，双⽅受益都还不错。

另外，在⼤学期间，笔者做题的时候最讨厌写题解，感觉是浪费时间，⽤更多的时间去做更多的

题。现在不知道算不算是“ 出来混的，总是要还的” 。

关于书的封⾯

常看 O'Reilly 动物书的同学⼀看这个封⾯就知道是向他们致敬。确实是这个⽬的。O'Reilly 的封⾯动物都

是稀缺动物，并且画⻛都是⿊⽩素描⻛。这些动物都有版权了，所以只能在⽹上找没有版权的⿊⽩素描

⻛的图⽚。常⻅的能找到 40 张这种⻛格的图⽚。不过⽤的⼈太多了，笔者费劲的找了其他⼏张这种图

⽚，这张孔雀开屏是其中⼀张。孔雀开屏的意义是希望⼤家刷完 LeetCode 以后，提⾼了⾃身的算法能

⼒，在⼈⽣的舞台上开出⾃⼰的“屏” 。全书配⾊也都是绿⾊，因为这是 AC 的颜⾊。

关于作者

----------------------- Page 17-----------------------

笔者是⼀个刚刚⼊⾏⼀年半的 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 语⾔实现。

----------------------- Page 18-----------------------

使⽤说明

本电⼦书的左上⻆有搜索栏，可以迅速帮你找到你想看的章节和题号。

本电⼦书每⻚都接⼊了 Gitalk ，每⼀⻚的最下⽅都有评论框可以评论，如果没有显示出来，请检查

⾃⼰的⽹络。

关于题解，笔者建议这样使⽤：先⾃⼰读题，思考如何解题。如果 15 分钟还没有思路，那么先看

笔者的解题思路，但是不要看代码。有思路以后⾃⼰⽤代码实现⼀遍。如果完全不会写，那就看笔

者提供的代码，找出⾃⼰到底哪⾥不会写，找出问题记下来，这就是⾃⼰要弥补的知识漏洞。如果

⾃⼰实现出来了，提交以后有错误，⾃⼰先 debug 。AC 以后没有到 100% 也先⾃⼰思考如何优

化。如果每道题⾃⼰都能优化到 100% 了，那么⼀段时间以后进步会很⼤。所以总的来说，实在没

思路，看解题思路；实在优化不到 100% ，看看代码。

互动与勘误

如果书中⽂章有所遗漏，欢迎点击所在⻚⾯下边的 edit 按钮进⾏评论和互动，感谢您的⽀持与帮助。

最后

⼀起开始刷题吧~

本作品采⽤ 知识署名-⾮商业性使⽤-禁⽌演绎 （BY-NC-ND） 4.0 国际许可协议 进⾏许可。

题解⾥⾯的所有题⽬版权均归 LeetCode 和 ⼒扣中国 所有

数据结构知识

----------------------- Page 19-----------------------

数据结构知识

以下是笔者整理的数据结构相关的知识。希望能把常⻅的数据结构都枚举穷尽。如有遗漏，欢迎⼤家赐

教，提 PR 。相关题⽬还在慢慢整理中，讲解的⽂章还在创作中。

刷题只是提升算法能⼒的⼿段，最终⽬的应该是提升⾃我的思维能⼒，知识需要凝结成块，那么就

把这些总结在第⼀章这两节中，让它得到升华吧~希望读者在刷完题之后再回过头来看这个表格，

能很清晰的梳理⾃⼰的知识体系，查缺补漏，尽早完善。

数据结构 变种 相关题⽬ 讲解⽂章

顺序线性表：向量

Vector

1. 双向链表 Double Linked Lists

单链表 2. 静态链表 Static List

Singly Linked List 3. 对称矩阵 Symmetric Matrix

4. 稀疏矩阵 Sparse Matrix

哈希表 1. 散列函数 Hash Function

Hash Table 2. 解决碰撞/填充因⼦

栈和队列 1. ⼴义栈

Stack & Queue 2. 双端队列 Deque

1. 链表实现

队列

2. 循环数组实现

Queue

3. 双端队列 Deque

1. KMP 算法

2. 有限状态⾃动机

字符串 3. 模式匹配有限状态⾃动机

String 4. BM 模式匹配算法

5. BM-KMP 算法

6. BF 算法

1. ⼆叉树 Binary Tree

树

2. 并查集 Union-Find

Tree

3. Huffman 树

1. 极⼤堆和极⼩堆

数组实现的堆 2. 极⼤极⼩堆

Heap 3. 双端堆 Deap

4. d 叉堆

1. 左堆

2. 扁堆

树实现的堆

3. ⼆项式堆

Heap

4. 斐波那契堆 Fibonacco Heap

5. 配对堆 Pairing Heap

----------------------- Page 20-----------------------

1. 哈希表 Hash

2. 跳跃表 Skip List

3. 排序⼆叉树 Binary Sort Tree

4. AVL 树

5. B 树 / B+ 树 / B* 树

查找 6. AA 树

Find 7. 红⿊树 Red Black Tree

8. 排序⼆叉堆 Binary Heap

9. Splay 树

10. 双链树 Double Chained Tree

11. Trie 树

12. R 树

------------------------- ------------------------------------------------------- -------------- -------------------

------------------- ------------------------------------- ------------- ----------------

算法知识

以下是笔者整理的算法相关的知识。希望能把常⻅的算法都枚举穷尽。如有遗漏，欢迎⼤家赐教，提

PR。相关题⽬还在慢慢整理中，讲解的⽂章还在创作中。

刷题只是提升算法能⼒的⼿段，最终⽬的应该是提升⾃我的思维能⼒，知识需要凝结成块，那么就

把这些总结在第⼀章这两节中，让它得到升华吧~希望读者在刷完题之后再回过头来看这个表格，

能很清晰的梳理⾃⼰的知识体系，查缺补漏，尽早完善。

讲

算 解

具体类型 相关题⽬

法 ⽂

章

1. 冒泡排序

2. 插⼊排序

3. 选择排序

4. 希尔 Shell 排序

5. 快速排序

6. 归并排序

排

7. 堆排序

序

8. 线性排序算法

算

9. ⾃省排序

法

10. 间接排序

11. 计数排序

12. 基数排序

13. 桶排序

14. 外部排序 - k 路归并败者树

15. 外部排序 - 最佳归并树

1. ⼆分搜索/查找

----------------------- Page 21-----------------------

2. ⼤整数的乘法

递 3. Strassen 矩阵乘法

归 4. 棋盘覆盖

与 5. 合并排序

分 6. 快速排序

治 7. 线性时间选择

8. 最接近点对问题

9. 循环赛⽇程表

1. 矩阵连乘问题

2. 最⻓公共⼦序列

3. 最⼤⼦段和

4. 凸多边形最优三⻆剖分

动 5. 多边形游戏

态 6. 图像压缩

规 7. 电路布线

划 8. 流⽔作业调度

9. 0-1 背包问题/背包九讲

10. 最优⼆叉搜索树

11. 动态规划加速原理

12. 树型 DP

1. 活动安排问题

2. 最优装载

贪 3. 哈夫曼编码

⼼ 4. 单源最短路径

5. 最⼩⽣成树

6. 多机调度问题

1. 装载问题

2. 批处理作业调度

3. 符号三⻆形问题

4. n 后问题

回 5. 0-1 背包问题

溯 6. 最⼤团问题

法 7. 图的 m 着⾊问题

8. 旅⾏售货员问题

9. 圆排列问题

10. 电路板排列问题

11. 连续邮资问题

1. 枚举

搜 2. DFS

索 3. BFS

4. 启发式搜索

1. 计算 π 值

2. 计算定积分

----------------------- Page 22-----------------------

1. 随机数 3. 解⾮线性⽅程组

随 2. 数值随机化算法 4. 线性时间选择算法

机 3. Sherwood 舍伍德算法 5. 跳跃表

化 4. Las Vegas 拉斯维加斯算法 6. n 后问题

5. Monte Carlo 蒙特卡罗算法 7. 整数因⼦分解

8. 主元素问题

9. 素数测试

1. 遍历 DFS / BFS

2. AOV / AOE ⽹络

3. Kruskal 算法(最⼩⽣成树)

1. 图遍历

4. Prim 算法(最⼩⽣成树)

2. 有向图和⽆向图的强弱连通性

5. Boruvka 算法(最⼩⽣成树)

3. 割点/割边

6. Dijkstra 算法(单源最短路径)

3. AOV ⽹络和拓扑排序

7. Bellman-Ford 算法(单源最短路径)

4. AOE ⽹络和关键路径

8. SPFA 算法(单源最短路径)

5. 最⼩代价⽣成树/次⼩⽣成树

9. Floyd 算法(多源最短路径)

6. 最短路径问题/第 K 短路问题

10. Johnson 算法(多源最短路径)

7. 最⼤⽹络流问题

11. Fleury 算法(欧拉回路)

8. 最⼩费⽤流问题

12. Ford-Fulkerson 算法(最⼤⽹络流增

9. 图着⾊问题

⼴路)

10. 差分约束系统

图 13. Edmonds-Karp 算法(最⼤⽹络流)

11. 欧拉回路

论 14. Dinic 算法(最⼤⽹络流)

12. 中国邮递员问题

15. ⼀般预流推进算法

13. 汉密尔顿回路

16. 最⾼标号预流推进 HLPP 算法

14. 最佳边割集/最佳点割集/最⼩边割

17. Primal-Dual 原始对偶算法(最⼩费

集/最⼩点割集/最⼩路径覆盖/最⼩点集

⽤流)18. Kosaraju 算法(有向图强连通

覆盖

分量)

15. 边覆盖集

19. Tarjan 算法(有向图强连通分量)

16. ⼆分图完美匹配和最⼤匹配问题

20. Gabow 算法(有向图强连通分量)

17. 仙⼈掌图

21. 匈⽛利算法(⼆分图匹配)

18. 弦图

22. Hopcroft －Karp 算法(⼆分图匹配)

19. 稳定婚姻问题

23. kuhn munkras 算法(⼆分图最佳匹

20. 最⼤团问题

配)

24. Edmonds’ Blossom-Contraction

算法(⼀般图匹配)

1. 最⼤公约数

2. 最⼩公倍数

3. 分解质因数

4. 素数判定

5. 进制转换

6. ⾼精度计算

7. 整除问题

8. 同余问题

数 9. 欧拉函数

论 10. 扩展欧⼏⾥得

----------------------- Page 23-----------------------

11. 置换群

12. ⺟函数

13. 离散变换

14. 康托展开

15. 矩阵

16. 向量

17. 线性⽅程组

18. 线性规划

1. 凸包 - Gift wrapping

⼏ 2. 凸包 - Graham scan

何 3. 线段问题

4. 多边形和多⾯体相关问题

1. 随机存取机 RAM

2. 随机存取存储程序机 RASP

3. 图灵机

4. ⾮确定性图灵机

5. P 类与 NP 类语⾔

6. 多项式时间验证

7. 多项式时间变换

8. Cook定理

9. 合取范式的可满⾜性问题 CNF-SAT

10. 3 元合取范式的可满⾜性问题 3-SAT

1. 计算模型 11. 团问题 CLIQUE

NP

2. P 类与 NP 类问题 12. 顶点覆盖问题 VERTEX-COVER

完

3. NP 完全问题 13. ⼦集和问题 SUBSET-SUM

全

4. NP 完全问题的近似算法 14. 哈密顿回路问题 HAM-CYCLE

15. 旅⾏售货员问题 TSP

16. 顶点覆盖问题的近似算法

17. 旅⾏售货员问题近似算法

18. 具有三⻆不等式性质的旅⾏售货员

问题

19. ⼀般的旅⾏售货员问题

20. 集合覆盖问题的近似算法

21. ⼦集和问题的近似算法

22. ⼦集和问题的指数时间算法

23. ⼦集和问题的多项式时间近似格式

|位运算 | 位操作包括：

1. 取反（NOT）

2. 按位或（OR）

3. 按位异或（XOR）

4. 按位与（AND）

5. 移位: 是⼀个⼆元运算符，⽤来将⼀个⼆进制数中的每⼀位全部都向⼀个⽅向移动指定位，溢出的部

分将被舍弃，⽽空缺的部分填⼊⼀定的值。

----------------------- Page 24-----------------------

| 1.数字范围按位与

2.UTF-8 编码验证

3.数字转换为⼗六进制数

4.找出最⻓的超赞⼦字符串

5.数组异或操作

6.幂集

7.位1的个数

8.⼆进制表示中质数个计算置位

9.⼦数组异或查询

| ⼒扣：位运算

|------------|------------------------------------------------------------------|----------------------------------------------------------

-------|--------------------|

第⼆章 算法专题

本来天真的认为，把 LeetCode 所有题都完整刷⼀遍，就可以完整这本书了。经过事实证明，确实是天

真了。因为 LeetCode 每天都会增加新题，有时候⼯作忙了，刷题进度就完全追不上题⽬更新的速度

了。⽽且以我当前的刷题速度，⼀年才完成 500+ ，⼀年 LeetCode 也会更新 400+ 多题，要起码 5~10

年才能把所有的题⽬刷完。时间太⻓了。所以先给⾃⼰定了⼀个⼩⽬标，500 题就先把书写出来，总结

这个阶段的刷题⼼得，和⼤家⼀起交流。要想把 LeetCode 所有题⽬都刷完，看来这本书要迭代 5 ~ 10

个版本了(⼀年迭代⼀版) 。

那么这⼀章就把已经刷完了的专题都整理⼀遍。有相似套路的题⽬都放在⼀起，如果想快速⾯试的话，

其实相同的题⽬刷 2 ，3 道就可以了。相同类型的题⽬⾮常熟练的情况下，再多刷⼏道也是做⽆⽤功。

----------------------- Page 25-----------------------

做到⽬前为⽌，笔者认为动态规划是最灵活的类型，这类题⽬没有⼀个模板可以给你套⽤，它也是算法

之优雅的地⽅。笔者认为称它为算法的艺术不为过。动态规划这类型，笔者也还没有刷完，只刷了⼀部

分，还在学习中。

那么就分享⼀下笔者⽬前刷过的题，和有相似点的题⽬吧。

Array

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

0001 Two Sum Go Easy O(n) O(n) 46.4%

0004 Median of Two Sorted Arrays Go Hard 31.0%

0011 Container With Most Water Go Medium O(n) O(1) 52.4%

0015 3Sum Go Medium O(n^2) O(n) 28.0%

0016 3Sum Closest Go Medium O(n^2) O(1) 46.3%

0018 4Sum Go Medium O(n^3) O(n^2) 34.8%

Remove Duplicates from Sorted

0026 Go Easy O(n) O(1) 46.5%

Array

0027 Remove Element Go Easy O(n) O(1) 49.2%

0031 Next Permutation Go Medium 33.8%

0033 Search in Rotated Sorted Array Go Medium 35.8%

Find First and Last Position of

0034 Go Medium 37.2%

Element in Sorted Array

0035 Search Insert Position Go Easy 42.8%

0039 Combination Sum Go Medium O(n log n) O(n) 59.1%

0040 Combination Sum II Go Medium O(n log n) O(n) 50.0%

0041 First Missing Positive Go Hard O(n) O(n) 33.6%

0042 Trapping Rain Water Go Hard O(n) O(1) 51.1%

0048 Rotate Image Go Medium O(n) O(1) 59.8%

0053 Maximum Subarray Go Easy O(n) O(n) 47.7%

0054 Spiral Matrix Go Medium O(n) O(n^2) 35.9%

0055 Jump Game Go Medium 35.1%

0056 Merge Intervals Go Medium O(n log n) O(1) 40.9%

0057 Insert Interval Go Medium O(n) O(1) 35.0%

0059 Spiral Matrix II Go Medium O(n) O(n^2) 57.7%

0062 Unique Paths Go Medium O(n^2) O(n^2) 55.9%

0063 Unique Paths II Go Medium O(n^2) O(n^2) 35.2%

0064 Minimum Path Sum Go Medium O(n^2) O(n^2) 56.1%

0066 Plus One Go Easy 42.3%

0074 Search a 2D Matrix Go Medium 37.7%

0075 Sort Colors Go Medium O(n) O(1) 49.3%

0078 Subsets Go Medium O(n^2) O(n) 64.9%

0079 Word Search Go Medium O(n^2) O(n^2) 36.7%

Remove Duplicates from Sorted

0080 Go Medium O(n) O(1 46.0%

Array II

0081 Search in Rotated Sorted Array II Go Medium 33.5%

0084 Largest Rectangle in Histogram Go Hard O(n) O(n) 37.0%

----------------------- Page 26-----------------------

0088 Merge Sorted Array Go Easy O(n) O(1) 40.7%

0090 Subsets II Go Medium O(n^2) O(n) 48.7%

Construct Binary Tree from

0105 Go Medium 51.6%

Preorder and Inorder Traversal

Construct Binary Tree from

0106 Go Medium 49.5%

Inorder and Postorder Traversal

0118 Pascal's Triangle Go Easy 54.7%

0119 Pascal's Triangle II Go Easy 52.1%

0120 Triangle Go Medium O(n^2) O(n) 45.7%

0121 Best Time to Buy and Sell Stock Go Easy O(n) O(1) 51.5%

Best Time to Buy and Sell Stock

0122 Go Easy O(n) O(1) 58.4%

II

0126 Word Ladder II Go Hard O(n) O(n^2) 23.6%

0128 Longest Consecutive Sequence Go Hard 46.2%

0152 Maximum Product Subarray Go Medium O(n) O(1) 32.7%

Find Minimum in Rotated Sorted

0153 Array Go Medium 46.1%

Find Minimum in Rotated Sorted

0154 Go Hard 42.0%

Array II

0162 Find Peak Element Go Medium 43.9%

Two Sum II - Input array is

0167 Go Easy O(n) O(1) 55.6%

sorted

0169 Majority Element Go Easy 60.0%

0189 Rotate Array Go Medium 36.5%

0209 Minimum Size Subarray Sum Go Medium O(n) O(1) 39.4%

0216 Combination Sum III Go Medium O(n) O(1) 60.2%

0217 Contains Duplicate Go Easy O(n) O(n) 56.6%

0219 Contains Duplicate II Go Easy O(n) O(n) 38.6%

0228 Summary Ranges Go Easy 42.3%

0229 Majority Element II Go Medium 38.7%

0268 Missing Number Go Easy 53.8%

0283 Move Zeroes Go Easy O(n) O(1) 58.5%

0287 Find the Duplicate Number Go Medium O(n) O(1) 57.4%

0414 Third Maximum Number Go Easy 30.7%

Find All Numbers Disappeared

0448 Go Easy 56.1%

in an Array

0457 Circular Array Loop Go Medium 30.0%

0485 Max Consecutive Ones Go Easy 53.0%

0509 Fibonacci Number Go Easy 67.4%

0532 K-diff Pairs in an Array Go Medium O(n) O(n) 35.1%

0561 Array Partition I Go Easy 73.2%

0566 Reshape the Matrix Go Easy O(n^2) O(n^2) 61.0%

0605 Can Place Flowers Go Easy 31.8%

Maximum Product of Three

0628 Numbers Go Easy O(n) O(1) 46.9%

0643 Maximum Average Subarray I Go Easy 42.0%

----------------------- Page 27-----------------------

0661 Image Smoother Go Easy 52.2%

0665 Non-decreasing Array Go Medium 19.7%

Longest Continuous Increasing

0674 Go Easy 46.1%

Subsequence

0695 Max Area of Island Go Medium 64.6%

0697 Degree of an Array Go Easy 54.4%

0713 Subarray Product Less Than K Go Medium O(n) O(1) 40.5%

Best Time to Buy and Sell Stock

0714 Go Medium O(n) O(1) 56.0%

with Transaction Fee

0717 1-bit and 2-bit Characters Go Easy 47.3%

Maximum Length of Repeated

0718 Go Medium 50.3%

Subarray

0719 Find K-th Smallest Pair Distance Go Hard 32.5%

0724 Find Pivot Index Go Easy 45.3%

0729 My Calendar I Go Medium 53.3%

0746 Min Cost Climbing Stairs Go Easy O(n) O(1) 50.9%

0766 Toeplitz Matrix Go Easy O(n) O(1) 65.8%

0830 Positions of Large Groups Go Easy 50.4%

0832 Flipping an Image Go Easy 78.1%

0867 Transpose Matrix Go Easy O(n) O(1) 62.1%

0888 Fair Candy Swap Go Easy 58.9%

0891 Sum of Subsequence Widths Go Hard O(n log n) O(1) 33.0%

0896 Monotonic Array Go Easy 58.0%

0907 Sum of Subarray Minimums Go Medium O(n) O(n) 33.1%

0914 X of a Kind in a Deck of Cards Go Easy 34.2%

Maximum Sum Circular

0918 Go Medium 34.2%

Subarray

0922 Sort Array By Parity II Go Easy O(n) O(1) 70.5%

0969 Pancake Sorting Go Medium O(n) O(1) 68.6%

0977 Squares of a Sorted Array Go Easy O(n) O(1) 72.1%

0978 Longest Turbulent Subarray Go Medium 46.7%

Sum of Even Numbers After

0985 Go Easy 60.7%

Queries

0989 Add to Array-Form of Integer Go Easy 44.8%

0999 Available Captures for Rook Go Easy 67.7%

1002 Find Common Characters Go Easy 68.6%

Capacity To Ship Packages

1011 Go Medium 59.7%

Within D Days

1018 Binary Prefix Divisible By 5 Go Easy 47.8%

Moving Stones Until Consecutive

1040 Go Medium 54.1%

II

1051 Height Checker Go Easy 72.2%

1052 Grumpy Bookstore Owner Go Medium 55.8%

Number of Submatrices That

1074 Go Hard 61.7%

Sum to Target

1089 Duplicate Zeros Go Easy 51.9%

1122 Relative Sort Array Go Easy 68.1%

----------------------- Page 28-----------------------

Number of Equivalent Domino

1128 Go Easy 46.6%

Pairs

Online Majority Element In

1157 Go Hard 39.7%

Subarray

Find Words That Can Be Formed

1160 Go Easy 67.9%

by Characters

Compare Strings by Frequency

1170 Go Medium 59.6%

of the Smallest Character

1184 Distance Between Bus Stops Go Easy 54.1%

1185 Day of the Week Go Easy 61.6%

1200 Minimum Absolute Difference Go Easy 67.0%

1202 Smallest String With Swaps Go Medium 48.7%

Get Equal Substrings Within

1208 Go Medium 43.9%

Budget

Minimum Cost to Move Chips to

1217 Go Easy 71.2%

The Same Position

1232 Check If It Is a Straight Line Go Easy 43.7%

1252 Cells with Odd Values in a Matrix Go Easy 78.9%

1260 Shift 2D Grid Go Easy 61.8%

1266 Minimum Time Visiting All Points Go Easy 79.5%

Find Winner on a Tic Tac Toe

1275 Go Easy 52.9%

Game

Element Appearing More Than

1287 Go Easy 60.2%

25% In Sorted Array

Find Numbers with Even

1295 Go Easy 79.2%

Number of Digits

Replace Elements with Greatest

1299 Go Easy 74.5%

Element on Right Side

Sum of Mutated Array Closest to

1300 Go Medium 43.2%

Target

Find N Unique Integers Sum up

1304 to Zero Go Easy 76.9%

Decompress Run-Length

1313 Go Easy 85.4%

Encoded List

1329 Sort the Matrix Diagonally Go Medium 81.8%

1380 Lucky Numbers in a Matrix Go Easy 70.8%

Find the Distance Value Between

1385 Go Easy 66.4%

Two Arrays

Create Target Array in the Given

1389 Go Easy 84.8%

Order

Maximum Points You Can

1423 Go Medium 46.6%

Obtain from Cards

Check If All 1's Are at Least

1437 Go Easy 62.7%

Length K Places Away

Maximum Product of Two

1464 Go Easy 77.2%

Elements in an Array

1470 Shuffle the Array Go Easy 88.4%

1480 Running Sum of 1d Array Go Easy 89.2%

1512 Number of Good Pairs Go Easy 87.7%

1539 Kth Missing Positive Number Go Easy 55.1%

----------------------- Page 29-----------------------

1608 Special Array With X Elements Go Easy 61.6%

Greater Than or Equal X

Mean of Array After Removing

1619 Go Easy 65.2%

Some Elements

1629 Slowest Key Go Easy 59.2%

Sort Array by Increasing

1636 Go Easy 66.8%

Frequency

Check Array Formation Through

1640 Go Easy 60.1%

Concatenation

Get Maximum in Generated

1646 Go Easy 53.5%

Array

1652 Defuse the Bomb Go Easy 63.0%

1656 Design an Ordered Stream Go Easy 82.3%

1672 Richest Customer Wealth Go Easy 88.4%

Number of Students Unable to

1700 Go Easy 68.9%

Eat Lunch

1732 Find the Highest Altitude Go Easy 81.6%

Maximum Number of Balls in a

1742 Go Easy 74.8%

Box

1748 Sum of Unique Elements Go Easy 77.3%

Check if Array Is Sorted and

1752 Go Easy 68.3%

Rotated

Minimum Changes To Make

1758 Go Easy 60.8%

Alternating Binary String

-------- ----------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

---- -------- -- -

String

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

Longest Substring Without

0003 Go Medium O(n) O(1) 31.4%

Repeating Characters

0013 Roman to Integer Go Easy 56.5%

Letter Combinations of a Phone

0017 Go Medium O(log n) O(1) 49.0%

Number

0020 Valid Parentheses Go Easy O(log n) O(1) 39.8%

0022 Generate Parentheses Go Medium O(log n) O(1) 65.2%

0028 Implement strStr() Go Easy O(n) O(1) 35.2%

Substring with Concatenation of

0030 Go Hard O(n) O(n) 26.2%

All Words

0049 Group Anagrams Go Medium O(n log n) O(n) 59.2%

0067 Add Binary Go Easy 46.8%

0071 Simplify Path Go Medium O(n) O(n) 34.6%

0076 Minimum Window Substring Go Hard O(n) O(n) 35.9%

0091 Decode Ways Go Medium O(n) O(n) 26.5%

0093 Restore IP Addresses Go Medium O(n) O(n) 37.5%

0125 Valid Palindrome Go Easy O(n) O(1) 38.1%

0126 Word Ladder II Go Hard O(n) O(n^2) 23.6%

----------------------- Page 30-----------------------

0151 Reverse Words in a String Go Medium 23.6%

0344 Reverse String Go Easy O(n) O(1) 70.2%

0345 Reverse Vowels of a String Go Easy O(n) O(1) 45.0%

0385 Mini Parser Go Medium 34.5%

First Unique Character in a

0387 Go Easy 53.8%

String

0537 Complex Number Multiplication Go Medium 68.3%

0541 Reverse String II Go Easy 49.1%

0557 Reverse Words in a String III Go Easy 71.8%

Smallest Range Covering

0632 Go Hard 54.2%

Elements from K Lists

0767 Reorganize String Go Medium O(n log n) O(log n) 50.0%

0819 Most Common Word Go Easy 45.5%

Split Array into Fibonacci

0842 Go Medium O(n^2) O(1) 36.8%

Sequence

0856 Score of Parentheses Go Medium O(n) O(n) 62.4%

0925 Long Pressed Name Go Easy O(n) O(1) 38.1%

Check If Word Is Valid After

1003 Go Medium O(n) O(1) 56.3%

Substitutions

1108 Defanging an IP Address Go Easy 88.4%

1170 Compare Strings by Frequency Go Medium 59.6%

of the Smallest Character

1189 Maximum Number of Balloons Go Easy 61.7%

1221 Split a String in Balanced Strings Go Easy 84.1%

Replace the Substring for

1234 Go Medium 34.3%

Balanced String

Check If a Word Occurs As a

1455 Go Easy 64.4%

Prefix of Any Word in a Sentence

1573 Number of Ways to Split a String Go Medium 31.1%

Maximum Nesting Depth of the

1614 Go Easy 83.0%

Parentheses

Largest Substring Between Two

1624 Go Easy 58.9%

Equal Characters

Minimum Deletions to Make

1653 Go Medium 50.5%

String Balanced

Check If Two String Arrays are

1662 Go Easy 83.2%

Equivalent

1668 Maximum Repeating Substring Go Easy 38.6%

1678 Goal Parser Interpretation Go Easy 85.7%

Count the Number of Consistent

1684 Go Easy 83.2%

Strings

1694 Reformat Phone Number Go Easy 66.3%

Determine if String Halves Are

1704 Go Easy 77.6%

Alike

Latest Time by Replacing Hidden

1736 Go Easy 41.1%

Digits

-------- ----------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

---- -------- -- -

Two Pointers

----------------------- Page 31-----------------------

Two Pointers

----------------------- Page 32-----------------------

双指针滑动窗⼝的经典写法。右指针不断往右移，移动到不能往右移动为⽌(具体条件根据题⽬⽽

定) 。当右指针到最右边以后，开始挪动左指针，释放窗⼝左边界。第 3 题，第 76 题，第 209 题，

第 424 题，第 438 题，第 567 题，第 713 题，第 763 题，第 845 题，第 881 题，第 904 题，第

978 题，第 992 题，第 1004 题，第 1040 题，第 1052 题。

left, right := 0, -1

for left < len(s) {

if right+1 < len(s) && freq[s[right+1]-'a'] == 0 {

freq[s[right+1]-'a']++

right++

} else {

freq[s[left]-'a']--

left++

}

result = max(result, right-left+1)

}

快慢指针可以查找重复数字，时间复杂度 O(n) ，第 287 题。

替换字⺟以后，相同字⺟能出现连续最⻓的⻓度。第 424 题。

SUM 问题集。第 1 题，第 15 题，第 16 题，第 18 题，第 167 题，第 923 题，第 1074 题。

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

0003 Longest Substring Without Go Medium O(n) O(1) ❤ 31.4%

Repeating Characters

----------------------- Page 33-----------------------

0011 Container With Most Water Go Medium O(n) O(1) 52.4%

❤

0015 3Sum Go Medium O(n^2) O(n) 28.0%

0016 3Sum Closest Go Medium O(n^2) O(1) ❤ 46.3%

❤

0018 4Sum Go Medium O(n^3) O(n^2) 34.8%

Remove Nth Node From End of

0019 Go Medium O(n) O(1) 35.7%

List

Remove Duplicates from Sorted

0026 Go Easy O(n) O(1) 46.5%

Array

0027 Remove Element Go Easy O(n) O(1) 49.2%

0028 Implement strStr() Go Easy O(n) O(1) 35.2%

Substring with Concatenation of

❤

0030 Go Hard O(n) O(n) 26.2%

All Words

❤

0042 Trapping Rain Water Go Hard O(n) O(1) 51.1%

0061 Rotate List Go Medium O(n) O(1) 31.7%

❤

0075 Sort Colors Go Medium O(n) O(1) 49.3%

❤

0076 Minimum Window Substring Go Hard O(n) O(n) 35.9%

Remove Duplicates from Sorted

0080 Go Medium O(n) O(1 46.0%

Array II

0086 Partition List Go Medium O(n) O(1) ❤ 43.3%

❤

0088 Merge Sorted Array Go Easy O(n) O(1) 40.7%

0125 Valid Palindrome Go Easy O(n) O(1) 38.1%

❤

0141 Linked List Cycle Go Easy O(n) O(1) 42.8%

0142 Linked List Cycle II Go Medium O(n) O(1) ❤ 39.6%

Two Sum II - Input array is

0167 Go Easy O(n) O(1) 55.6%

sorted

0209 Minimum Size Subarray Sum Go Medium O(n) O(1) 39.4%

0234 Palindrome Linked List Go Easy O(n) O(1) 40.4%

0283 Move Zeroes Go Easy O(n) O(1) 58.5%

❤

0287 Find the Duplicate Number Go Medium O(n) O(1) 57.4%

0344 Reverse String Go Easy O(n) O(1) 70.2%

0345 Reverse Vowels of a String Go Easy O(n) O(1) 45.0%

0349 Intersection of Two Arrays Go Easy O(n) O(n) 64.7%

0350 Intersection of Two Arrays II Go Easy O(n) O(n) 52.0%

Longest Repeating Character

0424 Go Medium O(n) O(1) 48.2%

Replacement

0457 Circular Array Loop Go Medium 30.0%

Longest Word in Dictionary

0524 Go Medium O(n) O(1) 49.0%

through Deleting

0532 K-diff Pairs in an Array Go Medium O(n) O(n) 35.1%

❤

0567 Permutation in String Go Medium O(n) O(1) 44.6%

Smallest Range Covering

0632 Go Hard 54.2%

Elements from K Lists

0713 Subarray Product Less Than K Go Medium O(n) O(1) 40.5%

❤

0763 Partition Labels Go Medium O(n) O(1) 78.0%

0826 Most Profit Assigning Work Go Medium O(n log n) O(n) 39.1%

Count Unique Characters of All

❤

0828 Go Hard O(n) O(1) 46.8%

Substrings of a Given String

----------------------- Page 34-----------------------

0838 Push Dominoes Go Medium O(n) O(n) 49.8%

0844 Backspace String Compare Go Easy O(n) O(n) 46.9%

0845 Longest Mountain in Array Go Medium O(n) O(1) 38.5%

0881 Boats to Save People Go Medium O(n log n) O(1) 48.8%

0904 Fruit Into Baskets Go Medium O(n log n) O(1) 43.0%

0923 3Sum With Multiplicity Go Medium O(n^2) O(n) 36.2%

0925 Long Pressed Name Go Easy O(n) O(1) 38.1%

❤

0930 Binary Subarrays With Sum Go Medium O(n) O(n) 44.5%

0977 Squares of a Sorted Array Go Easy O(n) O(1) 72.1%

0986 Interval List Intersections Go Medium O(n) O(1) 68.3%

Subarrays with K Different

❤

0992 Go Hard O(n) O(n) 50.6%

Integers

1004 Max Consecutive Ones III Go Medium O(n) O(1) 60.7%

1093 Statistics from a Large Sample Go Medium O(n) O(1) 49.3%

Replace the Substring for

1234 Go Medium 34.3%

Balanced String

Minimum Operations to Reduce

1658 Go Medium 33.4%

X to Zero

1695 Maximum Erasure Value Go Medium 49.6%

-------- ----------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

---- -------- -- -

Linked List

----------------------- Page 35-----------------------

巧妙的构造虚拟头结点。可以使遍历处理逻辑更加统⼀。

----------------------- Page 36-----------------------

灵活使⽤递归。构造递归条件，使⽤递归可以巧妙的解题。不过需要注意有些题⽬不能使⽤递归，

因为递归深度太深会导致超时和栈溢出。

链表区间逆序。第 92 题。

链表寻找中间节点。第 876 题。链表寻找倒数第 n 个节点。第 19 题。只需要⼀次遍历就可以得到

答案。

合并 K 个有序链表。第 21 题，第 23 题。

链表归类。第 86 题，第 328 题。

链表排序，时间复杂度要求 O(n * log n) ，空间复杂度 O(1) 。只有⼀种做法，归并排序，⾄顶向下

归并。第 148 题。

判断链表是否存在环，如果有环，输出环的交叉点的下标；判断 2 个链表是否有交叉点，如果有交

叉点，输出交叉点。第 141 题，第 142 题，第 160 题。

----------------------- Page 37-----------------------

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

0002 Add Two Numbers Go Medium O(n) O(1) 35.4%

Remove Nth Node From End of

0019 Go Medium O(n) O(1) 35.7%

List

0021 Merge Two Sorted Lists Go Easy O(log n) O(1) 55.9%

❤

0023 Merge k Sorted Lists Go Hard O(log n) O(1) 42.6%

0024 Swap Nodes in Pairs Go Medium O(n) O(1) 53.0%

❤

0025 Reverse Nodes in k-Group Go Hard O(log n) O(1) 44.7%

0061 Rotate List Go Medium O(n) O(1) 31.7%

Remove Duplicates from Sorted

0082 Go Medium O(n) O(1) 39.2%

List II

Remove Duplicates from Sorted

0083 Go Easy O(n) O(1) 46.5%

List

0086 Partition List Go Medium O(n) O(1) ❤ 43.3%

❤

0092 Reverse Linked List II Go Medium O(n) O(1) 40.5%

Convert Sorted List to Binary

0109 Go Medium O(log n) O(n) 50.1%

Search Tree

0138 Copy List with Random Pointer Go Medium 40.7%

❤

0141 Linked List Cycle Go Easy O(n) O(1) 42.8%

❤

0142 Linked List Cycle II Go Medium O(n) O(1) 39.6%

❤

0143 Reorder List Go Medium O(n) O(1) 40.5%

0147 Insertion Sort List Go Medium O(n) O(1) ❤ 44.3%

❤

0148 Sort List Go Medium O(n log n) O(n) 46.1%

0160 Intersection of Two Linked Lists Go Easy O(n) O(1) ❤ 43.1%

0203 Remove Linked List Elements Go Easy O(n) O(1) 39.2%

0206 Reverse Linked List Go Easy O(n) O(1) 65.1%

0234 Palindrome Linked List Go Easy O(n) O(1) 40.4%

0237 Delete Node in a Linked List Go Easy O(n) O(1) 66.7%

0328 Odd Even Linked List Go Medium O(n) O(1) 57.0%

0445 Add Two Numbers II Go Medium O(n) O(n) 56.2%

0707 Design Linked List Go Medium O(n) O(1) 25.8%

0725 Split Linked List in Parts Go Medium O(n) O(1) 52.9%

0817 Linked List Components Go Medium O(n) O(1) 57.8%

❤

0876 Middle of the Linked List Go Easy O(n) O(1) 69.1%

Next Greater Node In Linked

1019 Go Medium O(n) O(1) 58.2%

List

Remove Zero Sum Consecutive

1171 Go Medium 41.4%

Nodes from Linked List

Convert Binary Number in a

1290 Go Easy 81.8%

Linked List to Integer

1669 Merge In Between Linked Lists Go Medium 77.0%

Design Front Middle Back

1670 Go Medium 54.6%

Queue

-------- ---------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

---- --------- -- -

Stack

----------------------- Page 38-----------------------

Stack

----------------------- Page 39-----------------------

括号匹配问题及类似问题。第 20 题，第 921 题，第 1021 题。

栈的基本 pop 和 push 操作。第 71 题，第 150 题，第 155 题，第 224 题，第 225 题，第 232

题，第 946 题，第 1047 题。

利⽤栈进⾏编码问题。第 394 题，第 682 题，第 856 题，第 880 题。

单调栈。利⽤栈维护⼀个单调递增或者递减的下标数组 。第 84 题，第 456 题，第 496 题，第 503

题，第 739 题，第 901 题，第 907 题，第 1019 题。

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

0020 Valid Parentheses Go Easy O(log n) O(1) 39.8%

❤

0042 Trapping Rain Water Go Hard O(n) O(1) 51.1%

❤

0071 Simplify Path Go Medium O(n) O(n) 34.6%

❤

0084 Largest Rectangle in Histogram Go Hard O(n) O(n) 37.0%

0094 Binary Tree Inorder Traversal Go Medium O(n) O(1) 65.7%

Binary Tree Zigzag Level Order

0103 Go Medium O(n) O(n) 50.0%

Traversal

0144 Binary Tree Preorder Traversal Go Medium O(n) O(1) 57.4%

0145 Binary Tree Postorder Traversal Go Medium O(n) O(1) 57.5%

Evaluate Reverse Polish

0150 Go Medium O(n) O(1) 37.8%

Notation

0155 Min Stack Go Easy O(n) O(n) 46.3%

0173 Binary Search Tree Iterator Go Medium O(n) O(1) 60.0%

0224 Basic Calculator Go Hard O(n) O(n) 38.1%

0225 Implement Stack using Queues Go Easy O(n) O(n) 47.3%

0232 Implement Queue using Stacks Go Easy O(n) O(n) 52.0%

Verify Preorder Serialization of

0331 Go Medium O(n) O(1) 41.0%

a Binary Tree

0385 Mini Parser Go Medium 34.5%

0394 Decode String Go Medium O(n) O(n) 52.6%

0402 Remove K Digits Go Medium O(n) O(1) 28.6%

0456 132 Pattern Go Medium O(n) O(n) 30.6%

----------------------- Page 40-----------------------

0496 Next Greater Element I Go Easy O(n) O(n) 65.5%

0503 Next Greater Element II Go Medium O(n) O(n) 58.4%

0636 Exclusive Time of Functions Go Medium O(n) O(n) 54.3%

0682 Baseball Game Go Easy O(n) O(n) 66.8%

❤

0726 Number of Atoms Go Hard O(n) O(n) 51.1%

0735 Asteroid Collision Go Medium O(n) O(n) 43.2%

0739 Daily Temperatures Go Medium O(n) O(n) 64.5%

0844 Backspace String Compare Go Easy O(n) O(n) 46.9%

0856 Score of Parentheses Go Medium O(n) O(n) 62.4%

0880 Decoded String at Index Go Medium O(n) O(n) 28.3%

0895 Maximum Frequency Stack Go Hard O(n) O(n) 62.3%

0901 Online Stock Span Go Medium O(n) O(n) 61.3%

❤

0907 Sum of Subarray Minimums Go Medium O(n) O(n) 33.1%

Minimum Add to Make

0921 Go Medium O(n) O(n) 74.7%

Parentheses Valid

0946 Validate Stack Sequences Go Medium O(n) O(n) 63.6%

Check If Word Is Valid After

1003 Go Medium O(n) O(1) 56.3%

Substitutions

Next Greater Node In Linked

1019 Go Medium O(n) O(1) 58.2%

List

Remove Outermost

1021 Go Easy O(n) O(1) 79.0%

Parentheses

Remove All Adjacent Duplicates

1047 Go Easy O(n) O(1) 70.7%

In String

Find the Most Competitive

1673 Go Medium 45.2%

Subsequence

--------- ---------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

--- --------- -- -

Tree

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

0094 Binary Tree Inorder Traversal Go Medium O(n) O(1) 65.7%

0095 Unique Binary Search Trees II Go Medium 42.4%

0096 Unique Binary Search Trees Go Medium O(n^2) O(n) 54.4%

0098 Validate Binary Search Tree Go Medium O(n) O(1) 28.7%

0099 Recover Binary Search Tree Go Hard O(n) O(1) 42.4%

0100 Same Tree Go Easy O(n) O(1) 54.1%

0101 Symmetric Tree Go Easy O(n) O(1) 48.0%

Binary Tree Level Order

0102 Go Medium O(n) O(1) 56.5%

Traversal

Binary Tree Zigzag Level Order

0103 Go Medium O(n) O(n) 50.0%

Traversal

0104 Maximum Depth of Binary Tree Go Easy O(n) O(1) 68.0%

Construct Binary Tree from

0105 Go Medium 51.6%

Preorder and Inorder Traversal

Construct Binary Tree from

0106 Go Medium 49.5%

Inorder and Postorder Traversal

----------------------- Page 41-----------------------

Binary Tree Level Order

0107 Go Easy O(n) O(1) 55.1%

Traversal II

Convert Sorted Array to Binary

0108 Go Easy O(n) O(1) 60.3%

Search Tree

0110 Balanced Binary Tree Go Easy O(n) O(1) 44.7%

0111 Minimum Depth of Binary Tree Go Easy O(n) O(1) 39.5%

0112 Path Sum Go Easy O(n) O(1) 42.4%

0113 Path Sum II Go Medium O(n) O(1) 49.0%

Flatten Binary Tree to Linked

0114 Go Medium O(n) O(1) 51.8%

List

Binary Tree Maximum Path

0124 Go Hard O(n) O(1) 35.4%

Sum

0129 Sum Root to Leaf Numbers Go Medium O(n) O(1) 50.8%

0144 Binary Tree Preorder Traversal Go Medium O(n) O(1) 57.4%

0145 Binary Tree Postorder Traversal Go Medium O(n) O(1) 57.5%

0173 Binary Search Tree Iterator Go Medium O(n) O(1) 60.0%

0199 Binary Tree Right Side View Go Medium O(n) O(1) 56.3%

0222 Count Complete Tree Nodes Go Medium O(n) O(1) 49.2%

0226 Invert Binary Tree Go Easy O(n) O(1) 66.9%

0230 Kth Smallest Element in a BST Go Medium O(n) O(1) 62.5%

Lowest Common Ancestor of a

0235 Go Easy O(n) O(1) 51.7%

Binary Search Tree

Lowest Common Ancestor of a

0236 Go Medium O(n) O(1) 48.6%

Binary Tree

0257 Binary Tree Paths Go Easy O(n) O(1) 53.5%

0337 House Robber III Go Medium 51.8%

0404 Sum of Left Leaves Go Easy O(n) O(1) 52.2%

0437 Path Sum III Go Medium O(n) O(1) 48.1%

0508 Most Frequent Subtree Sum Go Medium 59.0%

0513 Find Bottom Left Tree Value Go Medium 62.5%

Find Largest Value in Each Tree

0515 Go Medium O(n) O(n) 62.2%

Row

0538 Convert BST to Greater Tree Go Medium 59.2%

0563 Binary Tree Tilt Go Easy 52.9%

0572 Subtree of Another Tree Go Easy 44.5%

0637 Average of Levels in Binary Tree Go Easy O(n) O(n) 64.7%

0653 Two Sum IV - Input is a BST Go Easy 56.2%

0662 Maximum Width of Binary Tree Go Medium 39.9%

0669 Trim a Binary Search Tree Go Medium 64.5%

0684 Redundant Connection Go Medium 58.9%

0685 Redundant Connection II Go Hard 33.0%

0834 Sum of Distances in Tree Go Hard 45.9%

All Nodes Distance K in Binary

0863 Go Medium 57.8%

Tree

0872 Leaf-Similar Trees Go Easy 64.6%

0897 Increasing Order Search Tree Go Easy 74.5%

----------------------- Page 42-----------------------

0968 Binary Tree Cameras Go Hard 38.7%

0979 Distribute Coins in Binary Tree Go Medium 69.7%

Vertical Order Traversal of a

0987 Go Hard 38.8%

Binary Tree

0993 Cousins in Binary Tree Go Easy O(n) O(1) 52.3%

Maximum Difference Between

1026 Go Medium 69.4%

Node and Ancestor

Recover a Tree From Preorder

1028 Go Hard 70.9%

Traversal

Binary Search Tree to Greater

1038 Go Medium 82.3%

Sum Tree

Delete Nodes And Return

1110 Go Medium 67.7%

Forest

Lowest Common Ancestor of

1123 Go Medium 68.0%

Deepest Leaves

1145 Binary Tree Coloring Game Go Medium 51.4%

1302 Deepest Leaves Sum Go Medium 84.2%

All Elements in Two Binary

1305 Go Medium 77.8%

Search Trees

-------- ---------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

---- --------- -- -

Dynamic Programming

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

0042 Trapping Rain Water Go Hard 51.1%

0053 Maximum Subarray Go Easy O(n) O(n) 47.7%

0062 Unique Paths Go Medium O(n^2) O(n^2) 55.9%

0063 Unique Paths II Go Medium O(n^2) O(n^2) 35.2%

0064 Minimum Path Sum Go Medium O(n^2) O(n^2) 56.1%

0070 Climbing Stairs Go Easy O(n) O(n) 48.6%

0091 Decode Ways Go Medium O(n) O(n) 26.5%

0095 Unique Binary Search Trees II Go Medium 42.4%

0096 Unique Binary Search Trees Go Medium O(n) O(n) 54.4%

0120 Triangle Go Medium O(n^2) O(n) 45.7%

0121 Best Time to Buy and Sell Stock Go Easy O(n) O(1) 51.5%

0131 Palindrome Partitioning Go Medium 51.8%

Maximum Product Subarray

0152 Go Medium O(n) O(1) 32.7%

0174 Dungeon Game Go Hard 33.3%

0198 House Robber Go Medium O(n) O(n) 42.8%

0213 House Robber II Go Medium O(n) O(n) 37.5%

Longest Increasing

0300 Go Medium O(n log n) O(n) 43.9%

Subsequence

0303 Range Sum Query - Immutable Go Easy 47.5%

Best Time to Buy and Sell Stock

0309 Go Medium O(n) O(n) 48.1%

with Cooldown

0322 Coin Change Go Medium O(n) O(n) 37.1%

----------------------- Page 43-----------------------

0337 House Robber III Go Medium 51.8%

0338 Counting Bits Go Medium O(n) O(n) 70.3%

0343 Integer Break Go Medium O(n^2) O(n) 51.2%

0354 Russian Doll Envelopes Go Hard 36.2%

Count Numbers with Unique

0357 Go Medium O(1) O(1) 48.8%

Digits

0392 Is Subsequence Go Easy O(n) O(1) 49.5%

0410 Split Array Largest Sum Go Hard 46.3%

0416 Partition Equal Subset Sum Go Medium O(n^2) O(n) 44.8%

0474 Ones and Zeroes Go Medium 43.6%

0494 Target Sum Go Medium 45.7%

0638 Shopping Offers Go Medium 52.8%

Best Time to Buy and Sell Stock

0714 Go Medium O(n) O(1) 56.0%

with Transaction Fee

Maximum Length of Repeated

0718 Go Medium 50.3%

Subarray

0746 Min Cost Climbing Stairs Go Easy O(n) O(1) 50.9%

0838 Push Dominoes Go Medium O(n) O(n) 49.8%

0887 Super Egg Drop Go Hard 27.1%

0898 Bitwise ORs of Subarrays Go Medium 34.1%

0920 Number of Music Playlists Go Hard 47.8%

0968 Binary Tree Cameras Go Hard 38.7%

0978 Longest Turbulent Subarray Go Medium 46.7%

1025 Divisor Game Go Easy O(1) O(1) 66.2%

1049 Last Stone Weight II Go Medium 45.2%

Number of Submatrices That

1074 Go Hard 61.7%

Sum to Target

1105 Filling Bookcase Shelves Go Medium 57.5%

Maximum Profit in Job

1235 Go Hard 47.4%

Scheduling

Maximum Points You Can

1423 Go Medium 46.6%

Obtain from Cards

1463 Cherry Pickup II Go Hard 69.3%

1641 Count Sorted Vowel Strings Go Medium 76.8%

Minimum Jumps to Reach

1654 Go Medium 26.0%

Home

1655 Distribute Repeating Integers Go Hard 40.4%

1659 Maximize Grid Happiness Go Hard 35.3%

1664 Ways to Make a Fair Array Go Medium 61.5%

1690 Stone Game VII Go Medium 47.6%

Maximum Height by Stacking

1691 Go Hard 49.9%

Cuboids

-------- ---------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

---- --------- -- -

Backtracking

----------------------- Page 44-----------------------

----------------------- Page 45-----------------------

排列问题 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 模板。(只是⼀个例⼦，不对应任何题)

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]

}

}

}

----------------------- Page 46-----------------------

BFS 模板。(只是⼀个例⼦，不对应任何题)

func updateMatrix_BFS(matrix [][]int) [][]int {

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

}

----------------------- Page 47-----------------------

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

Letter Combinations of a Phone

0017 Go Medium O(log n) O(1) 49.0%

Number

0022 Generate Parentheses Go Medium O(log n) O(1) 65.2%

❤

0037 Sudoku Solver Go Hard O(n^2) O(n^2) 46.4%

0039 Combination Sum Go Medium O(n log n) O(n) 59.1%

0040 Combination Sum II Go Medium O(n log n) O(n) 50.0%

❤

0046 Permutations Go Medium O(n) O(n) 66.4%

❤

0047 Permutations II Go Medium O(n^2) O(n) 49.3%

❤

0051 N-Queens Go Hard O(n!) O(n) 49.5%

❤

0052 N-Queens II Go Hard O(n!) O(n) 60.0%

0060 Permutation Sequence Go Hard O(n log n) O(1) 39.3%

❤

0077 Combinations Go Medium O(n) O(n) 57.3%

❤

0078 Subsets Go Medium O(n^2) O(n) 64.9%

❤

0079 Word Search Go Medium O(n^2) O(n^2) 36.7%

0089 Gray Code Go Medium O(n) O(1) 50.3%

❤

0090 Subsets II Go Medium O(n^2) O(n) 48.7%

❤

0093 Restore IP Addresses Go Medium O(n) O(n) 37.5%

❤

0126 Word Ladder II Go Hard O(n) O(n^2) 23.6%

❤

0131 Palindrome Partitioning Go Medium O(n) O(n^2) 51.8%

Design Add and Search Words

❤

0211 Go Medium O(n) O(n) 40.1%

Data Structure

❤

0212 Word Search II Go Hard O(n^2) O(n^2) 36.9%

❤

0216 Combination Sum III Go Medium O(n) O(1) 60.2%

❤

0306 Additive Number Go Medium O(n^2) O(1) 29.6%

Count Numbers with Unique

0357 Go Medium O(1) O(1) 48.8%

Digits

0401 Binary Watch Go Easy O(1) O(1) 48.4%

❤

0526 Beautiful Arrangement Go Medium O(n^2) O(1) 61.8%

0784 Letter Case Permutation Go Medium O(n) O(n) 66.5%

Split Array into Fibonacci

❤

0842 Go Medium O(n^2) O(1) 36.8%

Sequence

0980 Unique Paths III Go Hard O(n log n) O(n) 77.2%

0996 Number of Squareful Arrays Go Hard O(n log n) O(n) 48.3%

❤

1079 Letter Tile Possibilities Go Medium O(n^2) O(1) 75.9%

1641 Count Sorted Vowel Strings Go Medium 76.8%

1655 Distribute Repeating Integers Go Hard 40.4%

1659 Maximize Grid Happiness Go Hard 35.3%

1681 Minimum Incompatibility Go Hard 35.4%

Count of Matches in

1688 Go Easy 82.5%

Tournament

--------- ---------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

--- --------- -- -

Depth First Search

----------------------- Page 48-----------------------

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

Letter Combinations of a Phone

0017 Go Medium 49.0%

Number

0098 Validate Binary Search Tree Go Medium O(n) O(1) 28.7%

0099 Recover Binary Search Tree Go Hard O(n) O(1) 42.4%

0100 Same Tree Go Easy O(n) O(1) 54.1%

0101 Symmetric Tree Go Easy O(n) O(1) 48.0%

0104 Maximum Depth of Binary Tree Go Easy O(n) O(1) 68.0%

Construct Binary Tree from

0105 Go Medium 51.6%

Preorder and Inorder Traversal

Construct Binary Tree from

0106 Go Medium 49.5%

Inorder and Postorder Traversal

Convert Sorted Array to Binary

0108 Go Easy O(n) O(1) 60.3%

Search Tree

Convert Sorted List to Binary

0109 Go Medium O(log n) O(n) 50.1%

Search Tree

0110 Balanced Binary Tree Go Easy O(n) O(1) 44.7%

0111 Minimum Depth of Binary Tree Go Easy O(n) O(1) 39.5%

0112 Path Sum Go Easy O(n) O(1) 42.4%

0113 Path Sum II Go Medium O(n) O(1) 49.0%

0114 Flatten Binary Tree to Linked List Go Medium O(n) O(1) 51.8%

0124 Binary Tree Maximum Path Sum Go Hard O(n) O(1) 35.4%

0129 Sum Root to Leaf Numbers Go Medium O(n) O(1) 50.8%

0130 Surrounded Regions Go Medium 29.3%

0131 Palindrome Partitioning Go Medium 51.8%

0199 Binary Tree Right Side View Go Medium O(n) O(1) 56.3%

0200 Number of Islands Go Medium O(n^2) O(n^2) 49.0%

0207 Course Schedule Go Medium O(n^2) O(n^2) 44.3%

0210 Course Schedule II Go Medium O(n^2) O(n^2) 42.5%

Design Add and Search Words

0211 Go Medium 40.1%

Data Structure

0257 Binary Tree Paths Go Easy O(n) O(1) 53.5%

Longest Increasing Path in a

0329 Go Hard 44.7%

Matrix

0337 House Robber III Go Medium 51.8%

0394 Decode String Go Medium O(n) O(n) 52.6%

0491 Increasing Subsequences Go Medium 47.5%

0494 Target Sum Go Medium 45.7%

0513 Find Bottom Left Tree Value Go Medium 62.5%

Find Largest Value in Each Tree

0515 Go Medium O(n) O(n) 62.2%

Row

0526 Beautiful Arrangement Go Medium 61.8%

0529 Minesweeper Go Medium 61.0%

0538 Convert BST to Greater Tree Go Medium 59.2%

0542 01 Matrix Go Medium O(n) O(1) 40.9%

0547 Number of Provinces Go Medium 60.4%

0563 Binary Tree Tilt Go Easy 52.9%

----------------------- Page 49-----------------------

0638 Shopping Offers Go Medium 52.8%

0685 Redundant Connection II Go Hard 33.0%

0695 Max Area of Island Go Medium 64.6%

0721 Accounts Merge Go Medium 51.7%

0733 Flood Fill Go Easy 55.9%

0753 Cracking the Safe Go Hard 52.3%

0756 Pyramid Transition Matrix Go Medium 55.5%

0778 Swim in Rising Water Go Hard 54.8%

0785 Is Graph Bipartite? Go Medium 48.6%

0802 Find Eventual Safe States Go Medium 49.8%

0834 Sum of Distances in Tree Go Hard 45.9%

0839 Similar String Groups Go Hard 40.6%

0841 Keys and Rooms Go Medium 65.4%

0851 Loud and Rich Go Medium 52.6%

All Nodes Distance K in Binary

0863 Go Medium 57.8%

Tree

0872 Leaf-Similar Trees Go Easy 64.6%

0897 Increasing Order Search Tree Go Easy 74.5%

0924 Minimize Malware Spread Go Hard 41.9%

0928 Minimize Malware Spread II Go Hard 41.2%

Most Stones Removed with

0947 Go Medium 55.4%

Same Row or Column

0959 Regions Cut By Slashes Go Medium 67.1%

0968 Binary Tree Cameras Go Hard 38.7%

0979 Distribute Coins in Binary Tree Go Medium 69.7%

0980 Unique Paths III Go Hard O(n log n) O(n) 77.2%

Vertical Order Traversal of a

0987 Go Hard 38.8%

Binary Tree

1020 Number of Enclaves Go Medium 58.9%

Maximum Difference Between

1026 Go Medium 69.4%

Node and Ancestor

Recover a Tree From Preorder

1028 Go Hard 70.9%

Traversal

Binary Search Tree to Greater

1038 Go Medium 82.3%

Sum Tree

1110 Delete Nodes And Return Forest Go Medium 67.7%

Lowest Common Ancestor of

1123 Go Medium 68.0%

Deepest Leaves

1145 Binary Tree Coloring Game Go Medium 51.4%

Sort Items by Groups Respecting

1203 Go Hard 48.9%

Dependencies

1254 Number of Closed Islands Go Medium 61.6%

1302 Deepest Leaves Sum Go Medium 84.2%

1306 Jump Game III Go Medium 62.6%

Number of Operations to Make

1319 Go Medium 55.4%

Network Connected

1631 Path With Minimum Effort Go Medium 50.1%

----------------------- Page 50-----------------------

-------- ----------------------------------------------- ------- -------------- --------------- ------------- ------------ -------------

---- -------- -- -

Breadth First Search

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

0101 Symmetric Tree Go Easy O(n) O(1) 48.0%

Binary Tree Level Order

0102 Go Medium O(n) O(1) 56.5%

Traversal

Binary Tree Zigzag Level Order

0103 Go Medium O(n) O(n) 50.0%

Traversal

Binary Tree Level Order

0107 Go Easy O(n) O(1) 55.1%

Traversal II

0111 Minimum Depth of Binary Tree Go Easy O(n) O(1) 39.5%

❤

0126 Word Ladder II Go Hard O(n) O(n^2) 23.6%

0127 Word Ladder Go Hard O(n) O(n) 31.7%

0130 Surrounded Regions Go Medium 29.3%

0199 Binary Tree Right Side View Go Medium O(n) O(1) 56.3%

0200 Number of Islands Go Medium O(n^2) O(n^2) 49.0%

0207 Course Schedule Go Medium O(n^2) O(n^2) 44.3%

0210 Course Schedule II Go Medium O(n^2) O(n^2) 42.5%

0513 Find Bottom Left Tree Value Go Medium 62.5%

Find Largest Value in Each Tree

0515 Go Medium O(n) O(n) 62.2%

Row

0529 Minesweeper Go Medium 61.0%

0542 01 Matrix Go Medium O(n) O(1) 40.9%

0785 Is Graph Bipartite? Go Medium 48.6%

0815 Bus Routes Go Hard 43.3%

All Nodes Distance K in Binary

0863 Go Medium 57.8%

Tree

0864 Shortest Path to Get All Keys Go Hard 41.9%

Vertical Order Traversal of a

0987 Go Hard 38.8%

Binary Tree

0993 Cousins in Binary Tree Go Easy O(n) O(1) 52.3%

1091 Shortest Path in Binary Matrix Go Medium 40.0%

1306 Jump Game III Go Medium 62.6%

Number of Operations to Make

1319 Go Medium 55.4%

Network Connected

Minimum Jumps to Reach

1654 Go Medium 26.0%

Home

-------- ---------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

---- --------- -- -

Binary Search

⼆分搜索的经典写法。需要注意的三点：

----------------------- Page 51-----------------------

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

}

}

return -1

}

⼆分搜索的变种写法。有 4 个基本变种:

1. 查找第⼀个与 target 相等的元素，时间复杂度 O(logn)

2. 查找最后⼀个与 target 相等的元素，时间复杂度 O(logn)

3. 查找第⼀个⼤于等于 target 的元素，时间复杂度 O(logn)

4. 查找最后⼀个⼩于等于 target 的元素，时间复杂度 O(logn)

// ⼆分查找第⼀个与 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

----------------------- Page 52-----------------------

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

}

// ⼆分查找第⼀个⼤于等于 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

}

}

----------------------- Page 53-----------------------

return -1

}

在基本有序的数组中⽤⼆分搜索。经典解法可以解，变种写法也可以写，常⻅的题型，在⼭峰数组

中找⼭峰，在旋转有序数组中找分界点。第 33 题，第 81 题，第 153 题，第 154 题，第 162 题，

第 852 题

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

}

max-min 最⼤值最⼩化问题。求在最⼩满⾜条件的情况下的最⼤值。第 410 题，第 875 题，第

1011 题，第 1283 题。

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

0004 Median of Two Sorted Arrays Go Hard 31.0%

0029 Divide Two Integers Go Medium 16.6%

0033 Search in Rotated Sorted Array Go Medium 35.8%

Find First and Last Position of

0034 Go Medium 37.2%

Element in Sorted Array

0035 Search Insert Position Go Easy 42.8%

0050 Pow(x, n) Go Medium O(log n) O(1) 30.9%

0069 Sqrt(x) Go Easy O(log n) O(1) 35.0%

0074 Search a 2D Matrix Go Medium 37.7%

0081 Search in Rotated Sorted Array II Go Medium 33.5%

Find Minimum in Rotated Sorted

0153 Go Medium 46.1%

Array

Find Minimum in Rotated Sorted

0154 Go Hard 42.0%

Array II

0162 Find Peak Element Go Medium 43.9%

Two Sum II - Input array is

0167 Go Easy O(n) O(1) 55.6%

sorted

0174 Dungeon Game Go Hard 33.3%

0209 Minimum Size Subarray Sum Go Medium O(n) O(1) 39.4%

0222 Count Complete Tree Nodes Go Medium O(n) O(1) 49.2%

0230 Kth Smallest Element in a BST Go Medium O(n) O(1) 62.5%

----------------------- Page 54-----------------------

0240 Search a 2D Matrix II Go Medium 44.4%

0275 H-Index II Go Medium 36.3%

❤

0287 Find the Duplicate Number Go Medium O(n) O(1) 57.4%

Longest Increasing

0300 Go Medium O(n log n) O(n) 43.9%

Subsequence

Count of Smaller Numbers After

0315 Go Hard 42.5%

Self

0327 Count of Range Sum Go Hard 36.0%

0349 Intersection of Two Arrays Go Easy O(n) O(n) 64.7%

0350 Intersection of Two Arrays II Go Easy O(n) O(n) 52.0%

0354 Russian Doll Envelopes Go Hard 36.2%

0367 Valid Perfect Square Go Easy 42.0%

Kth Smallest Element in a Sorted

0378 Go Medium 56.1%

Matrix

0392 Is Subsequence Go Easy O(n) O(1) 49.5%

0410 Split Array Largest Sum Go Hard 46.3%

0436 Find Right Interval Go Medium 48.5%

0441 Arranging Coins Go Easy 42.4%

0454 4Sum II Go Medium O(n^2) O(n) 54.6%

0475 Heaters Go Medium 33.6%

0483 Smallest Good Base Go Hard 36.2%

0493 Reverse Pairs Go Hard 26.8%

Random Point in Non-

0497 Go Medium 39.1%

overlapping Rectangles

0528 Random Pick with Weight Go Medium 44.6%

0658 Find K Closest Elements Go Medium 41.9%

Kth Smallest Number in

0668 Go Hard 47.7%

Multiplication Table

0704 Binary Search Go Easy 54.0%

0710 Random Pick with Blacklist Go Hard O(n) O(n) 32.7%

Maximum Length of Repeated

0718 Go Medium 50.3%

Subarray

0719 Find K-th Smallest Pair Distance Go Hard 32.5%

Find Smallest Letter Greater

0744 Go Easy 45.6%

Than Target

0778 Swim in Rising Water Go Hard 54.8%

0786 K-th Smallest Prime Fraction Go Hard 42.4%

Preimage Size of Factorial

0793 Go Hard 40.7%

Zeroes Function

0852 Peak Index in a Mountain Array Go Easy 71.7%

Shortest Subarray with Sum at

0862 Go Hard 25.2%

Least K

0875 Koko Eating Bananas Go Medium 53.5%

0878 Nth Magical Number Go Hard 28.9%

0887 Super Egg Drop Go Hard 27.1%

0911 Online Election Go Medium 51.3%

----------------------- Page 55-----------------------

0927 Three Equal Parts Go Hard 34.6%

0981 Time Based Key-Value Store Go Medium 54.1%

Capacity To Ship Packages

1011 Go Medium 59.7%

Within D Days

Maximum Nesting Depth of Two

1111 Go Medium 72.7%

Valid Parentheses Strings

Online Majority Element In

1157 Go Hard 39.7%

Subarray

Compare Strings by Frequency

1170 Go Medium 59.6%

of the Smallest Character

1201 Ugly Number III Go Medium 26.4%

Maximum Profit in Job

1235 Go Hard 47.4%

Scheduling

Find the Smallest Divisor Given

1283 Go Medium 49.5%

a Threshold

Sum of Mutated Array Closest to

1300 Go Medium 43.2%

Target

1631 Path With Minimum Effort Go Medium 50.1%

Create Sorted Array through

1649 Go Hard 36.3%

Instructions

Minimum Operations to Reduce

1658 Go Medium 33.4%

X to Zero

-------- ----------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

---- -------- -- -

Math

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

0002 Add Two Numbers Go Medium O(n) O(1) 35.4%

0007 Reverse Integer Go Easy 25.9%

0009 Palindrome Number Go Easy 49.7%

0013 Roman to Integer Go Easy 56.5%

0029 Divide Two Integers Go Medium 16.6%

0050 Pow(x, n) Go Medium O(log n) O(1) 30.9%

0060 Permutation Sequence Go Hard O(n log n) O(1) 39.3%

0067 Add Binary Go Easy 46.8%

0069 Sqrt(x) Go Easy O(log n) O(1) 35.0%

0168 Excel Sheet Column Title Go Easy 31.7%

0171 Excel Sheet Column Number Go Easy 56.9%

0172 Factorial Trailing Zeroes Go Easy 38.5%

0202 Happy Number Go Easy O(log n) O(1) 51.2%

0204 Count Primes Go Easy 32.2%

0223 Rectangle Area Go Medium 38.2%

0224 Basic Calculator Go Hard O(n) O(n) 38.1%

0231 Power of Two Go Easy O(1) O(1) 43.8%

0258 Add Digits Go Easy 58.4%

0263 Ugly Number Go Easy O(log n) O(1) 41.7%

----------------------- Page 56-----------------------

0268 Missing Number Go Easy 53.8%

0326 Power of Three Go Easy O(1) O(1) 42.1%

0343 Integer Break Go Medium O(n^2) O(n) 51.2%

Count Numbers with Unique

0357 Go Medium O(1) O(1) 48.8%

Digits

0367 Valid Perfect Square Go Easy 42.0%

0372 Super Pow Go Medium 36.7%

0397 Integer Replacement Go Medium 33.5%

0441 Arranging Coins Go Easy 42.4%

0447 Number of Boomerangs Go Medium 52.4%

Minimum Moves to Equal Array

0453 Go Easy 50.8%

Elements

0483 Smallest Good Base Go Hard 36.2%

0507 Perfect Number Go Easy 36.1%

0537 Complex Number Multiplication Go Medium 68.3%

0598 Range Addition II Go Easy 50.1%

Maximum Product of Three

0628 Go Easy O(n) O(1) 46.9%

Numbers

0633 Sum of Square Numbers Go Medium 32.5%

0645 Set Mismatch Go Easy 42.5%

0753 Cracking the Safe Go Hard 52.3%

0781 Rabbits in Forest Go Medium 55.5%

0812 Largest Triangle Area Go Easy 58.9%

0836 Rectangle Overlap Go Easy 44.7%

0878 Nth Magical Number Go Hard 28.9%

0885 Spiral Matrix III Go Medium O(n^2) O(1) 70.7%

0887 Super Egg Drop Go Hard 27.1%

0891 Sum of Subsequence Widths Go Hard O(n log n) O(1) 33.0%

0892 Surface Area of 3D Shapes Go Easy 59.7%

0910 Smallest Range II Go Medium 31.3%

0914 X of a Kind in a Deck of Cards Go Easy 34.2%

0927 Three Equal Parts Go Hard 34.6%

0942 DI String Match Go Easy O(n) O(1) 73.5%

0949 Largest Time for Given Digits Go Medium 36.2%

Largest Component Size by

0952 Go Hard 36.1%

Common Factor

0970 Powerful Integers Go Medium 40.0%

0976 Largest Perimeter Triangle Go Easy O(n log n) O(log n) 58.5%

0996 Number of Squareful Arrays Go Hard O(n log n) O(n) 48.3%

1017 Convert to Base -2 Go Medium 59.6%

1025 Divisor Game Go Easy O(1) O(1) 66.2%

1037 Valid Boomerang Go Easy 37.8%

Adding Two Negabinary

1073 Go Medium 34.8%

Numbers

1093 Statistics from a Large Sample Go Medium 49.3%

1154 Day of the Year Go Easy 49.2%

----------------------- Page 57-----------------------

1175 Prime Arrangements Go Easy 52.0%

1201 Ugly Number III Go Medium 26.4%

Minimum Cost to Move Chips to

1217 Go Easy 71.2%

The Same Position

1232 Check If It Is a Straight Line Go Easy 43.7%

Subtract the Product and Sum

1281 Go Easy 85.6%

of Digits of an Integer

Convert Integer to the Sum of

1317 Go Easy 56.8%

Two No-Zero Integers

1512 Number of Good Pairs Go Easy 87.7%

1641 Count Sorted Vowel Strings Go Medium 76.8%

Sell Diminishing-Valued Colored

1648 Go Medium 30.8%

Balls

Concatenation of Consecutive

1680 Go Medium 52.4%

Binary Numbers

Sum of Absolute Differences in

1685 Go Medium 62.8%

a Sorted Array

Calculate Money in Leetcode

1716 Go Easy 67.3%

Bank

-------- ---------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

---- --------- -- -

Hash Table

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

0001 Two Sum Go Easy O(n) O(n) 46.4%

Longest Substring Without

❤

0003 Go Medium O(n) O(1) 31.4%

Repeating Characters

❤

0018 4Sum Go Medium O(n^3) O(n^2) 34.8%

Substring with Concatenation of

❤

0030 Go Hard O(n) O(n) 26.2%

All Words

0036 Valid Sudoku Go Medium O(n^2) O(n^2) 50.5%

❤

0037 Sudoku Solver Go Hard O(n^2) O(n^2) 46.4%

0049 Group Anagrams Go Medium O(n log n) O(n) 59.2%

❤

0076 Minimum Window Substring Go Hard O(n) O(n) 35.9%

0094 Binary Tree Inorder Traversal Go Medium O(n) O(1) 65.7%

0136 Single Number Go Easy 66.5%

0138 Copy List with Random Pointer Go Medium O(n) O(1) 40.7%

0187 Repeated DNA Sequences Go Medium 41.4%

0202 Happy Number Go Easy O(log n) O(1) 51.2%

0204 Count Primes Go Easy 32.2%

0205 Isomorphic Strings Go Easy O(log n) O(n) 40.4%

0217 Contains Duplicate Go Easy O(n) O(n) 56.6%

0219 Contains Duplicate II Go Easy O(n) O(n) 38.6%

0242 Valid Anagram Go Easy O(n) O(n) 58.5%

0274 H-Index Go Medium O(n) O(n) 36.3%

0290 Word Pattern Go Easy O(n) O(n) 38.3%

----------------------- Page 58-----------------------

0347 Top K Frequent Elements Go Medium O(n) O(n) 62.4%

0349 Intersection of Two Arrays Go Easy O(n) O(n) 64.7%

0350 Intersection of Two Arrays II Go Easy O(n) O(n) 52.0%

First Unique Character in a

0387 Go Easy 53.8%

String

0389 Find the Difference Go Easy 57.8%

0409 Longest Palindrome Go Easy 52.2%

0438 Find All Anagrams in a String Go Medium O(n) O(1) 44.9%

0447 Number of Boomerangs Go Medium O(n) O(1) 52.4%

0451 Sort Characters By Frequency Go Medium O(n log n) O(1) 64.3%

0454 4Sum II Go Medium O(n^2) O(n) 54.6%

0463 Island Perimeter Go Easy 66.6%

0500 Keyboard Row Go Easy 65.6%

0508 Most Frequent Subtree Sum Go Medium 59.0%

0575 Distribute Candies Go Easy 62.1%

Longest Harmonious

0594 Go Easy 51.2%

Subsequence

Minimum Index Sum of Two

0599 Go Easy 51.6%

Lists

Smallest Range Covering

0632 Go Hard 54.2%

Elements from K Lists

0645 Set Mismatch Go Easy 42.5%

0648 Replace Words Go Medium O(n) O(n) 58.5%

0676 Implement Magic Dictionary Go Medium O(n) O(n) 55.2%

0705 Design HashSet Go Easy 64.7%

0706 Design HashMap Go Easy 62.8%

0710 Random Pick with Blacklist Go Hard O(n) O(n) 32.7%

Maximum Length of Repeated

0718 Go Medium 50.3%

Subarray

0720 Longest Word in Dictionary Go Easy O(n) O(n) 49.2%

❤

0726 Number of Atoms Go Hard O(n) O(n) 51.1%

0739 Daily Temperatures Go Medium O(n) O(n) 64.5%

0748 Shortest Completing Word Go Easy 57.5%

0771 Jewels and Stones Go Easy 86.9%

0781 Rabbits in Forest Go Medium 55.5%

0811 Subdomain Visit Count Go Easy 71.4%

Uncommon Words from Two

0884 Go Easy 64.1%

Sentences

0895 Maximum Frequency Stack Go Hard O(n) O(n) 62.3%

❤

0930 Binary Subarrays With Sum Go Medium O(n) O(n) 44.5%

0953 Verifying an Alien Dictionary Go Easy 52.3%

N-Repeated Element in Size 2N

0961 Go Easy 74.4%

Array

0970 Powerful Integers Go Medium 40.0%

0981 Time Based Key-Value Store Go Medium 54.1%

Vertical Order Traversal of a

0987 Go Hard 38.8%

Binary Tree

----------------------- Page 59-----------------------

0992 Subarrays with K Different Go Hard O(n) O(n) ❤ 50.6%

Integers

1002 Find Common Characters Go Easy 68.6%

1078 Occurrences After Bigram Go Easy 64.9%

Find Words That Can Be

1160 Go Easy 67.9%

Formed by Characters

1189 Maximum Number of Balloons Go Easy 61.7%

1207 Unique Number of Occurrences Go Easy 71.7%

1512 Number of Good Pairs Go Easy 87.7%

1539 Kth Missing Positive Number Go Easy 55.1%

Check Array Formation Through

1640 Go Easy 60.1%

Concatenation

1679 Max Number of K-Sum Pairs Go Medium 54.2%

1748 Sum of Unique Elements Go Easy 77.3%

-------- ---------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

---- --------- -- -

Sort

----------------------- Page 60-----------------------

深刻的理解多路快排。第 75 题。

链表的排序，插⼊排序(第 147 题)和归并排序(第 148 题)

桶排序和基数排序。第 164 题。

----------------------- Page 61-----------------------

"摆动排序"。第 324 题。

两两不相邻的排序。第 767 题，第 1054 题。

"饼⼦排序"。第 969 题。

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

0056 Merge Intervals Go Medium O(n log n) O(log n) 40.9%

0057 Insert Interval Go Medium O(n) O(1) 35.0%

❤

0075 Sort Colors Go Medium O(n) O(1) 49.3%

❤

0147 Insertion Sort List Go Medium O(n) O(1) 44.3%

0148 Sort List Go Medium O(n log n) O(log n) ❤ 46.1%

❤

0164 Maximum Gap Go Hard O(n log n) O(log n) 36.8%

❤

0179 Largest Number Go Medium O(n log n) O(log n) 30.6%

❤

0220 Contains Duplicate III Go Medium O(n log n) O(1) 21.3%

0242 Valid Anagram Go Easy O(n) O(n) 58.5%

0274 H-Index Go Medium O(n) O(n) 36.3%

Count of Smaller Numbers After

0315 Go Hard 42.5%

Self

❤

0324 Wiggle Sort II Go Medium O(n) O(n) 30.7%

0327 Count of Range Sum Go Hard 36.0%

0349 Intersection of Two Arrays Go Easy O(n) O(n) 64.7%

0350 Intersection of Two Arrays II Go Easy O(n) O(n) 52.0%

0493 Reverse Pairs Go Hard 26.8%

Longest Word in Dictionary

0524 Go Medium O(n) O(1) 49.0%

through Deleting

0710 Random Pick with Blacklist Go Hard O(n) O(n) 32.7%

❤

0767 Reorganize String Go Medium O(n log n) O(log n) 50.0%

0853 Car Fleet Go Medium O(n log n) O(log n) 43.8%

0922 Sort Array By Parity II Go Easy O(n) O(1) 70.5%

❤

0969 Pancake Sorting Go Medium O(n log n) O(log n) 68.6%

0973 K Closest Points to Origin Go Medium O(n log n) O(log n) 64.6%

0976 Largest Perimeter Triangle Go Easy O(n log n) O(log n) 58.5%

1030 Matrix Cells in Distance Order Go Easy O(n^2) O(1) 66.9%

❤

1054 Distant Barcodes Go Medium O(n log n) O(log n) 44.2%

1122 Relative Sort Array Go Easy 68.1%

Maximum Profit in Job

1235 Go Hard 47.4%

Scheduling

All Elements in Two Binary

1305 Go Medium 77.8%

Search Trees

1329 Sort the Matrix Diagonally Go Medium 81.8%

Sort Array by Increasing

1636 Go Easy 66.8%

Frequency

Check Array Formation Through

1640 Go Easy 60.1%

Concatenation

Minimum Deletions to Make

1647 Go Medium 54.5%

Character Frequencies Unique

Sell Diminishing-Valued Colored

1648 Go Medium 30.8%

Balls

----------------------- Page 62-----------------------

Maximum Height by Stacking

1691 Go Hard 49.9%

Cuboids

1710 Maximum Units on a Truck Go Easy 70.5%

-------- ----------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

---- -------- -- -

Bit Manipulation

----------------------- Page 63-----------------------

异或的特性。第 136 题，第 268 题，第 389 题，第 421 题，

----------------------- Page 64-----------------------

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 (结合律)

构造特殊 Mask ，将特殊位置放 0 或 1 。

将 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)）

有特殊意义的 & 位操作运算。第 260 题，第 201 题，第 318 题，第 371 题，第 397 题，第 461

题，第 693 题，

X & 1 == 1 判断是否是奇数 (偶数)

X & = (X - 1) 将最低位 (LSB)的 1 清零

X & -X 得到最低位 (LSB)的 1

X & ~X = 0

----------------------- Page 65-----------------------

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

❤

0078 Subsets Go Medium O(n^2) O(n) 64.9%

0136 Single Number Go Easy O(n) O(1) 66.5%

❤

0137 Single Number II Go Medium O(n) O(1) 53.7%

❤

0169 Majority Element Go Easy O(n) O(1) 60.0%

0187 Repeated DNA Sequences Go Medium O(n) O(1) 41.4%

❤

0190 Reverse Bits Go Easy O(n) O(1) 42.0%

0191 Number of 1 Bits Go Easy O(n) O(1) 53.6%

❤

0201 Bitwise AND of Numbers Range Go Medium O(n) O(1) 39.6%

0231 Power of Two Go Easy O(1) O(1) 43.8%

❤

0260 Single Number III Go Medium O(n) O(1) 65.3%

0268 Missing Number Go Easy O(n) O(1) 53.8%

Maximum Product of Word

0318 Go Medium O(n) O(1) 52.2%

Lengths

0338 Counting Bits Go Medium O(n) O(n) 70.3%

0342 Power of Four Go Easy O(n) O(1) 41.7%

0371 Sum of Two Integers Go Medium O(n) O(1) 50.6%

0389 Find the Difference Go Easy O(n) O(1) 57.8%

0393 UTF-8 Validation Go Medium O(n) O(1) 38.0%

0397 Integer Replacement Go Medium O(n) O(1) 33.5%

0401 Binary Watch Go Easy O(1) O(1) 48.4%

Convert a Number to

0405 Go Easy O(n) O(1) 44.4%

Hexadecimal

Maximum XOR of Two Numbers

❤

0421 Go Medium O(n) O(1) 54.0%

in an Array

0461 Hamming Distance Go Easy O(n) O(1) 73.2%

0476 Number Complement Go Easy O(n) O(1) 65.1%

0477 Total Hamming Distance Go Medium O(n) O(1) 50.6%

Binary Number with Alternating

❤

0693 Go Easy O(n) O(1) 59.8%

Bits

0756 Pyramid Transition Matrix Go Medium O(n log n) O(n) 55.5%

Prime Number of Set Bits in

0762 Go Easy O(n) O(1) 64.3%

Binary Representation

0784 Letter Case Permutation Go Medium O(n) O(1) 66.5%

0898 Bitwise ORs of Subarrays Go Medium O(n) O(1) 34.1%

Convert Binary Number in a

1290 Go Easy 81.8%

Linked List to Integer

1720 Decode XORed Array Go Easy 85.7%

-------- ----------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

---- -------- -- -

Union Find

----------------------- Page 66-----------------------

灵活使⽤并查集的思想，熟练掌握并查集的模板 ，模板中有两种并查集的实现⽅式，⼀种是路径压

缩 + 秩优化的版本，另外⼀种是计算每个集合中元素的个数 + 最⼤集合元素个数的版本，这两种版

本都有各⾃使⽤的地⽅。能使⽤第⼀类并查集模板的题⽬有：第 128 题，第 130 题，第 547 题，

第 684 题，第 721 题，第 765 题，第 778 题，第 839 题，第 924 题，第 928 题，第 947 题，第

952 题，第 959 题，第 990 题。能使⽤第⼆类并查集模板的题⽬有：第 803 题，第 952 题。第

803 题秩优化和统计集合个数这些地⽅会卡时间，如果不优化，会 TLE 。

并查集是⼀种思想，有些题需要灵活使⽤这种思想，⽽不是死套模板，如第 399 题，这⼀题是

stringUnionFind，利⽤并查集思想实现的。这⾥每个节点是基于字符串和 map 的，⽽不是单纯的

⽤ int 节点编号实现的。

有些题死套模板反⽽做不出来，⽐如第 685 题，这⼀题不能路径压缩和秩优化，因为题⽬中涉及到

----------------------- Page 67-----------------------

有向图，需要知道节点的前驱节点，如果路径压缩了，这⼀题就没法做了。这⼀题不需要路径压缩

和秩优化。

灵活的抽象题⽬给的信息，将给定的信息合理的编号，使⽤并查集解题，并⽤ map 降低时间复杂

度，如第 721 题，第 959 题。

关于地图，砖块，⽹格的题⽬，可以新建⼀个特殊节点，将四周边缘的砖块或者⽹格都 union() 到

这个特殊节点上。第 130 题，第 803 题。

能⽤并查集的题⽬，⼀般也可以⽤ DFS 和 BFS 解答，只不过时间复杂度会⾼⼀点。

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

0128 Longest Consecutive Sequence Go Hard O(n) O(n) ❤ 46.2%

0130 Surrounded Regions Go Medium O(m*n) O(m*n) 29.3%

0200 Number of Islands Go Medium O(m*n) O(m*n) 49.0%

0399 Evaluate Division Go Medium O(n) O(n) 54.3%

0547 Number of Provinces Go Medium O(n^2) O(n) 60.4%

0684 Redundant Connection Go Medium O(n) O(n) 58.9%

0685 Redundant Connection II Go Hard O(n) O(n) 33.0%

❤

0721 Accounts Merge Go Medium O(n) O(n) 51.7%

0765 Couples Holding Hands Go Hard O(n) O(n) ❤ 55.5%

❤

0778 Swim in Rising Water Go Hard O(n^2) O(n) 54.8%

0803 Bricks Falling When Hit Go Hard O(n^2) O(n) ❤ 31.4%

0839 Similar String Groups Go Hard O(n^2) O(n) 40.6%

0924 Minimize Malware Spread Go Hard O(m*n) O(n) 41.9%

❤

0928 Minimize Malware Spread II Go Hard O(m*n) O(n) 41.2%

Most Stones Removed with

0947 Go Medium O(n) O(n) 55.4%

Same Row or Column

Largest Component Size by

0952 Common Factor Go Hard O(n) O(n) ❤ 36.1%

0959 Regions Cut By Slashes Go Medium O(n^2) O(n^2) ❤ 67.1%

Satisfiability of Equality

0990 Go Medium O(n) O(n) 46.7%

Equations

1202 Smallest String With Swaps Go Medium 48.7%

Number of Operations to Make

1319 Go Medium 55.4%

Network Connected

Remove Max Number of Edges

1579 Go Hard 46.3%

to Keep Graph Fully Traversable

1631 Path With Minimum Effort Go Medium 50.1%

------- ---------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

----- --------- -- -

Sliding Window

----------------------- Page 68-----------------------

双指针滑动窗⼝的经典写法。右指针不断往右移，移动到不能往右移动为⽌(具体条件根据题⽬⽽

定) 。当右指针到最右边以后，开始挪动左指针，释放窗⼝左边界。第 3 题，第 76 题，第 209 题，

第 424 题，第 438 题，第 567 题，第 713 题，第 763 题，第 845 题，第 881 题，第 904 题，第

978 题，第 992 题，第 1004 题，第 1040 题，第 1052 题。

left, right := 0, -1

for left < len(s) {

if right+1 < len(s) && freq[s[right+1]-'a'] == 0 {

freq[s[right+1]-'a']++

right++

} else {

freq[s[left]-'a']--

left++

}

result = max(result, right-left+1)

}

----------------------- Page 69-----------------------

滑动窗⼝经典题。第 239 题，第 480 题。

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

Longest Substring Without

❤

0003 Go Medium O(n) O(1) 31.4%

Repeating Characters

❤

0076 Minimum Window Substring Go Hard O(n) O(n) 35.9%

❤

0239 Sliding Window Maximum Go Hard O(n * k) O(n) 44.6%

Longest Repeating Character

0424 Go Medium O(n) O(1) 48.2%

Replacement

0480 Sliding Window Median Go Hard O(n * log k) O(k) ❤ 38.6%

❤

0567 Permutation in String Go Medium O(n) O(1) 44.6%

❤

0978 Longest Turbulent Subarray Go Medium O(n) O(1) 46.7%

Subarrays with K Different

❤

0992 Go Hard O(n) O(n) 50.6%

Integers

Minimum Number of K

❤

0995 Go Hard O(n) O(1) 49.8%

Consecutive Bit Flips

1004 Max Consecutive Ones III Go Medium O(n) O(1) 60.7%

Moving Stones Until

❤

1040 Go Medium O(n log n) O(1) 54.1%

Consecutive II

1052 Grumpy Bookstore Owner Go Medium O(n log n) O(1) 55.8%

Number of Submatrices That

❤

1074 Go Hard O(n^3) O(n) 61.7%

Sum to Target

Get Equal Substrings Within

1208 Go Medium 43.9%

Budget

Maximum Points You Can

1423 Go Medium 46.6%

Obtain from Cards

Minimum Operations to

1658 Go Medium 33.4%

Reduce X to Zero

-------- ---------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

---- --------- -- -

Segment Tree

----------------------- Page 70-----------------------

线段树的经典数组实现写法。将合并两个节点 pushUp 逻辑抽象出来了，可以实现任意操作(常⻅

的操作有：加法，取 max ，min 等等) 。第 218 题，第 303 题，第 307 题，第 699 题。

计数线段树的经典写法。第 315 题，第 327 题，第 493 题。

线段树的树的实现写法。第 715 题，第 732 题。

区间懒惰更新。第 218 题，第 699 题。

离散化。离散化需要注意⼀个特殊情况：假如三个区间为 [1,10] [1,4] [6,10] ，离散化后

x[1]=1,x[2]=4,x[3]=6,x[4]=10 。第⼀个区间为 [1,4] ，第⼆个区间为 [1,2] ，第三个区间为 [3,4] ，这

样⼀来，区间⼀ = 区间⼆ + 区间三，这和离散前的模型不符，离散前，很明显，区间⼀ > 区间⼆ +

区间三。正确的做法是：在相差⼤于 1 的数间加⼀个数，例如在上⾯ 1 4 6 10 中间加 5 ，即可

x[1]=1,x[2]=4,x[3]=5,x[4]=6,x[5]=10 。这样处理之后，区间⼀是 1-5 ，区间⼆是 1-2 ，区间三是 4-

5 。

灵活构建线段树。线段树节点可以存储多条信息，合并两个节点的 pushUp 操作也可以是多样的。

第 850 题，第 1157 题。

线段树题型从简单到困难:

1. 单点更新:

HDU 1166 敌兵布阵 update:单点增减 query: 区间求和

HDU 1754 I Hate It update:单点替换 query: 区间最值

HDU 1394 Minimum Inversion Number update:单点增减 query: 区间求和

HDU 2795 Billboard query: 区间求最⼤值的位⼦(直接把update的操作在query⾥做了)

2. 区间更新:

HDU 1698 Just a Hook update:成段替换 ( 由于只query⼀次总区间,所以可以直接输出 1 结点的信

息)

POJ 3468 A Simple Problem with Integers update:成段增减 query: 区间求和

----------------------- Page 71-----------------------

POJ 2528 Mayor’s posters 离散化 + update:成段替换 query:简单hash

POJ 3225 Help with Intervals update:成段替换, 区间异或 query:简单hash

3. 区间合并(这类题⽬会询问区间中满⾜条件的连续最⻓区间,所以PushUp的时候需要对左右⼉⼦的区

间进⾏合并):

POJ 3667 Hotel update: 区间替换 query:询问满⾜条件的最左端点

4. 扫描线(这类题⽬需要将⼀些操作排序,然后从左到右⽤⼀根扫描线扫过去最典型的就是矩形⾯积并,

周⻓并等题):

HDU 1542 Atlantis update: 区间增减 query:直接取根节点的值

HDU 1828 Picture update: 区间增减 query:直接取根节点的值

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

❤

0218 The Skyline Problem Go Hard O(n log n) O(n) 36.2%

0307 Range Sum Query - Mutable Go Medium O(1) O(n) 36.7%

Count of Smaller Numbers

0315 Go Hard O(n log n) O(n) 42.5%

After Self

0327 Count of Range Sum Go Hard O(n log n) O(n) ❤ 36.0%

0493 Reverse Pairs Go Hard O(n log n) O(n) 26.8%

❤

0699 Falling Squares Go Hard O(n log n) O(n) 42.5%

❤

0715 Range Module Go Hard O(log n) O(n) 40.2%

❤

0732 My Calendar III Go Hard O(log n) O(n) 61.7%

0850 Rectangle Area II Go Hard O(n log n) O(n) ❤ 48.3%

Online Majority Element In

❤

1157 Go Hard O(log n) O(n) 39.7%

Subarray

Create Sorted Array through

1649 Go Hard 36.3%

Instructions

--------- -------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

--- ----------- -- -

Binary Indexed Tree

----------------------- Page 72-----------------------

No. Title Solution Difficulty TimeComplexity SpaceComplexity Favorite Acceptance

0218 The Skyline Problem Go Hard 36.2%

0307 Range Sum Query - Mutable Go Medium 36.7%

Count of Smaller Numbers

0315 Go Hard 42.5%

After Self

0327 Count of Range Sum Go Hard 36.0%

0493 Reverse Pairs Go Hard 26.8%

Create Sorted Array through

1649 Go Hard 36.3%

Instructions

--------- -------------------------------------------- -------------- ------------

------- --------------- ------------- -------------

--- ----------- -- -

第三章 ⼀些模板

这⼀章会罗列⼀些整理好的模板。⼀起来看看吧。

线段树 Segment Tree

package template

// SegmentTree define

type SegmentTree struct {

data, tree, lazy []int

left, right int

merge func(i, j int) int

}

----------------------- Page 73-----------------------

// Init define

func (st *SegmentTree) Init(nums []int, oper func(i, j int) int) {

st.merge = oper

data, tree, lazy := make([]int, len(nums)), make([]int, 4*len(nums)),

make([]int, 4*len(nums))

for i := 0; i < len(nums); i++ {

data[i] = nums[i]

}

st.data, st.tree, st.lazy = data, tree, lazy

if len(nums) > 0 {

st.buildSegmentTree(0, 0, len(nums)-1)

}

}

// 在 treeIndex 的位置创建 [left....right] 区间的线段树

func (st *SegmentTree) buildSegmentTree(treeIndex, left, right int) {

if left == right {

st.tree[treeIndex] = st.data[left]

return

}

midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1,

st.leftChild(treeIndex), st.rightChild(treeIndex)

st.buildSegmentTree(leftTreeIndex, left, midTreeIndex)

st.buildSegmentTree(rightTreeIndex, midTreeIndex+1, right)

st.tree[treeIndex] = st.merge(st.tree[leftTreeIndex],

st.tree[rightTreeIndex])

}

func (st *SegmentTree) leftChild(index int) int {

return 2*index + 1

}

func (st *SegmentTree) rightChild(index int) int {

return 2*index + 2

}

// 查询 [left....right] 区间内的值

// Query define

func (st *SegmentTree) Query(left, right int) int {

if len(st.data) > 0 {

return st.queryInTree(0, 0, len(st.data)-1, left, right)

}

return 0

}

// 在以 treeIndex 为根的线段树中 [left...right] 的范围⾥，搜索区间

[queryLeft...queryRight] 的值

----------------------- Page 74-----------------------

func (st *SegmentTree) queryInTree(treeIndex, left, right, queryLeft,

queryRight int) int {

if left == queryLeft && right == queryRight {

return st.tree[treeIndex]

}

midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1,

st.leftChild(treeIndex), st.rightChild(treeIndex)

if queryLeft > midTreeIndex {

return st.queryInTree(rightTreeIndex, midTreeIndex+1, right, queryLeft,

queryRight)

} else if queryRight <= midTreeIndex {

return st.queryInTree(leftTreeIndex, left, midTreeIndex, queryLeft,

queryRight)

}

return st.merge(st.queryInTree(leftTreeIndex, left, midTreeIndex, queryLeft,

midTreeIndex),

st.queryInTree(rightTreeIndex, midTreeIndex+1, right, midTreeIndex+1,

queryRight))

}

// 查询 [left....right] 区间内的值

// QueryLazy define

func (st *SegmentTree) QueryLazy(left, right int) int {

if len(st.data) > 0 {

return st.queryLazyInTree(0, 0, len(st.data)-1, left, right)

}

return 0

}

func (st *SegmentTree) queryLazyInTree(treeIndex, left, right, queryLeft,

queryRight int) int {

midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1,

st.leftChild(treeIndex), st.rightChild(treeIndex)

if left > queryRight || right < queryLeft { // segment completely outside

range

return 0 // represents a null node

}

if st.lazy[treeIndex] != 0 { // this node is lazy

for i := 0; i < right-left+1; i++ {

st.tree[treeIndex] = st.merge(st.tree[treeIndex], st.lazy[treeIndex])

// st.tree[treeIndex] += (right - left + 1) * st.lazy[treeIndex] //

normalize current node by removing lazinesss

}

if left != right { // update lazy[] for children nodes

st.lazy[leftTreeIndex] = st.merge(st.lazy[leftTreeIndex],

st.lazy[treeIndex])

st.lazy[rightTreeIndex] = st.merge(st.lazy[rightTreeIndex],

st.lazy[treeIndex])

----------------------- Page 75-----------------------

// st.lazy[leftTreeIndex] += st.lazy[treeIndex]

// st.lazy[rightTreeIndex] += st.lazy[treeIndex]

}

st.lazy[treeIndex] = 0 // current node processed. No longer lazy

}

if queryLeft <= left && queryRight >= right { // segment completely inside

range

return st.tree[treeIndex]

}

if queryLeft > midTreeIndex {

return st.queryLazyInTree(rightTreeIndex, midTreeIndex+1, right, queryLeft,

queryRight)

} else if queryRight <= midTreeIndex {

return st.queryLazyInTree(leftTreeIndex, left, midTreeIndex, queryLeft,

queryRight)

}

// merge query results

return st.merge(st.queryLazyInTree(leftTreeIndex, left, midTreeIndex,

queryLeft, midTreeIndex),

st.queryLazyInTree(rightTreeIndex, midTreeIndex+1, right, midTreeIndex+1,

queryRight))

}

// 更新 index 位置的值

// Update define

func (st *SegmentTree) Update(index, val int) {

if len(st.data) > 0 {

st.updateInTree(0, 0, len(st.data)-1, index, val)

}

}

// 以 treeIndex 为根，更新 index 位置上的值为 val

func (st *SegmentTree) updateInTree(treeIndex, left, right, index, val int) {

if left == right {

st.tree[treeIndex] = val

return

}

midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1,

st.leftChild(treeIndex), st.rightChild(treeIndex)

if index > midTreeIndex {

st.updateInTree(rightTreeIndex, midTreeIndex+1, right, index, val)

} else {

st.updateInTree(leftTreeIndex, left, midTreeIndex, index, val)

}

st.tree[treeIndex] = st.merge(st.tree[leftTreeIndex],

st.tree[rightTreeIndex])

}

----------------------- Page 76-----------------------

// 更新 [updateLeft....updateRight] 位置的值

// 注意这⾥的更新值是在原来值的基础上增加或者减少，⽽不是把这个区间内的值都赋值为 x，区间更新

和单点更新不同

// 这⾥的区间更新关注的是变化，单点更新关注的是定值

// 当然区间更新也可以都更新成定值，如果只区间更新成定值，那么 lazy 更新策略需要变化，merge

策略也需要变化，这⾥暂不详细讨论

// UpdateLazy define

func (st *SegmentTree) UpdateLazy(updateLeft, updateRight, val int) {

if len(st.data) > 0 {

st.updateLazyInTree(0, 0, len(st.data)-1, updateLeft, updateRight, val)

}

}

func (st *SegmentTree) updateLazyInTree(treeIndex, left, right, updateLeft,

updateRight, val int) {

midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1,

st.leftChild(treeIndex), st.rightChild(treeIndex)

if st.lazy[treeIndex] != 0 { // this node is lazy

for i := 0; i < right-left+1; i++ {

st.tree[treeIndex] = st.merge(st.tree[treeIndex], st.lazy[treeIndex])

//st.tree[treeIndex] += (right - left + 1) * st.lazy[treeIndex] //

normalize current node by removing laziness

}

if left != right { // update lazy[] for children nodes

st.lazy[leftTreeIndex] = st.merge(st.lazy[leftTreeIndex],

st.lazy[treeIndex])

st.lazy[rightTreeIndex] = st.merge(st.lazy[rightTreeIndex],

st.lazy[treeIndex])

// st.lazy[leftTreeIndex] += st.lazy[treeIndex]

// st.lazy[rightTreeIndex] += st.lazy[treeIndex]

}

st.lazy[treeIndex] = 0 // current node processed. No longer lazy

}

if left > right || left > updateRight || right < updateLeft {

return // out of range. escape.

}

if updateLeft <= left && right <= updateRight { // segment is fully within

update range

for i := 0; i < right-left+1; i++ {

st.tree[treeIndex] = st.merge(st.tree[treeIndex], val)

//st.tree[treeIndex] += (right - left + 1) * val // update segment

}

if left != right { // update lazy[] for children

st.lazy[leftTreeIndex] = st.merge(st.lazy[leftTreeIndex], val)

st.lazy[rightTreeIndex] = st.merge(st.lazy[rightTreeIndex], val)

// st.lazy[leftTreeIndex] += val

----------------------- Page 77-----------------------

// st.lazy[rightTreeIndex] += val

}

return

}

st.updateLazyInTree(leftTreeIndex, left, midTreeIndex, updateLeft,

updateRight, val)

st.updateLazyInTree(rightTreeIndex, midTreeIndex+1, right, updateLeft,

updateRight, val)

// merge updates

st.tree[treeIndex] = st.merge(st.tree[leftTreeIndex],

st.tree[rightTreeIndex])

}

// SegmentCountTree define

type SegmentCountTree struct {

data, tree []int

left, right int

merge func(i, j int) int

}

// Init define

func (st *SegmentCountTree) Init(nums []int, oper func(i, j int) int) {

st.merge = oper

data, tree := make([]int, len(nums)), make([]int, 4*len(nums))

for i := 0; i < len(nums); i++ {

data[i] = nums[i]

}

st.data, st.tree = data, tree

}

// 在 treeIndex 的位置创建 [left....right] 区间的线段树

func (st *SegmentCountTree) buildSegmentTree(treeIndex, left, right int) {

if left == right {

st.tree[treeIndex] = st.data[left]

return

}

midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1,

st.leftChild(treeIndex), st.rightChild(treeIndex)

st.buildSegmentTree(leftTreeIndex, left, midTreeIndex)

st.buildSegmentTree(rightTreeIndex, midTreeIndex+1, right)

st.tree[treeIndex] = st.merge(st.tree[leftTreeIndex],

st.tree[rightTreeIndex])

}

func (st *SegmentCountTree) leftChild(index int) int {

return 2*index + 1

}

----------------------- Page 78-----------------------

func (st *SegmentCountTree) rightChild(index int) int {

return 2*index + 2

}

// 查询 [left....right] 区间内的值

// Query define

func (st *SegmentCountTree) Query(left, right int) int {

if len(st.data) > 0 {

return st.queryInTree(0, 0, len(st.data)-1, left, right)

}

return 0

}

// 在以 treeIndex 为根的线段树中 [left...right] 的范围⾥，搜索区间

[queryLeft...queryRight] 的值，值是计数值

func (st *SegmentCountTree) queryInTree(treeIndex, left, right, queryLeft,

queryRight int) int {

if queryRight < st.data[left] || queryLeft > st.data[right] {

return 0

}

if queryLeft <= st.data[left] && queryRight >= st.data[right] || left ==

right {

return st.tree[treeIndex]

}

midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1,

st.leftChild(treeIndex), st.rightChild(treeIndex)

return st.queryInTree(rightTreeIndex, midTreeIndex+1, right, queryLeft,

queryRight) +

st.queryInTree(leftTreeIndex, left, midTreeIndex, queryLeft, queryRight)

}

// 更新计数

// UpdateCount define

func (st *SegmentCountTree) UpdateCount(val int) {

if len(st.data) > 0 {

st.updateCountInTree(0, 0, len(st.data)-1, val)

}

}

// 以 treeIndex 为根，更新 [left...right] 区间内的计数

func (st *SegmentCountTree) updateCountInTree(treeIndex, left, right, val int)

{

if val >= st.data[left] && val <= st.data[right] {

st.tree[treeIndex]++

if left == right {

return

}

----------------------- Page 79-----------------------

midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1,

st.leftChild(treeIndex), st.rightChild(treeIndex)

st.updateCountInTree(rightTreeIndex, midTreeIndex+1, right, val)

st.updateCountInTree(leftTreeIndex, left, midTreeIndex, val)

}

}

并查集 UnionFind

package template

// UnionFind defind

// 路径压缩 + 秩优化

type UnionFind struct {

parent, rank []int

count int

}

// Init define

func (uf *UnionFind) Init(n int) {

uf.count = n

uf.parent = make([]int, n)

uf.rank = make([]int, n)

for i := range uf.parent {

uf.parent[i] = i

}

}

// Find define

func (uf *UnionFind) Find(p int) int {

root := p

for root != uf.parent[root] {

root = uf.parent[root]

}

// compress path

for p != uf.parent[p] {

tmp := uf.parent[p]

uf.parent[p] = root

p = tmp

}

return root

}

// Union define

func (uf *UnionFind) Union(p, q int) {

proot := uf.Find(p)

qroot := uf.Find(q)

----------------------- Page 80-----------------------

if proot == qroot {

return

}

if uf.rank[qroot] > uf.rank[proot] {

uf.parent[proot] = qroot

} else {

uf.parent[qroot] = proot

if uf.rank[proot] == uf.rank[qroot] {

uf.rank[proot]++

}

}

uf.count--

}

// TotalCount define

func (uf *UnionFind) TotalCount() int {

return uf.count

}

// UnionFindCount define

// 计算每个集合中元素的个数 + 最⼤集合元素个数

type UnionFindCount struct {

parent, count []int

maxUnionCount int

}

// Init define

func (uf *UnionFindCount) Init(n int) {

uf.parent = make([]int, n)

uf.count = make([]int, n)

for i := range uf.parent {

uf.parent[i] = i

uf.count[i] = 1

}

}

// Find define

func (uf *UnionFindCount) Find(p int) int {

root := p

for root != uf.parent[root] {

root = uf.parent[root]

}

return root

}

// 不进⾏秩压缩，时间复杂度爆炸，太⾼了

// func (uf *UnionFindCount) union(p, q int) {

// proot := uf.find(p)

// qroot := uf.find(q)

----------------------- Page 81-----------------------

// if proot == qroot {

// return

// }

// if proot != qroot {

// uf.parent[proot] = qroot

// uf.count[qroot] += uf.count[proot]

// }

// }

// Union define

func (uf *UnionFindCount) Union(p, q int) {

proot := uf.Find(p)

qroot := uf.Find(q)

if proot == qroot {

return

}

if proot == len(uf.parent)-1 {

//proot is root

} else if qroot == len(uf.parent)-1 {

// qroot is root, always attach to root

proot, qroot = qroot, proot

} else if uf.count[qroot] > uf.count[proot] {

proot, qroot = qroot, proot

}

//set relation[0] as parent

uf.maxUnionCount = max(uf.maxUnionCount, (uf.count[proot] + uf.count[qroot]))

uf.parent[qroot] = proot

uf.count[proot] += uf.count[qroot]

}

// Count define

func (uf *UnionFindCount) Count() []int {

return uf.count

}

// MaxUnionCount define

func (uf *UnionFindCount) MaxUnionCount() int {

return uf.maxUnionCount

}

func max(a int, b int) int {

if a > b {

return a

}

return b

}

最近最少使⽤ LRUCache

----------------------- Page 82-----------------------

最近最少使⽤ LRUCache

LRU 是 Least Recently Used 的缩写，即最近最少使⽤，是⼀种常⽤的⻚⾯置换算法，选择最近最久未

使⽤的⻚⾯予以淘汰。如上图，要插⼊ F 的时候，此时需要淘汰掉原来的⼀个⻚⾯。

根据 LRU 的策略，每次都淘汰最近最久未使⽤的⻚⾯，所以先淘汰 A ⻚⾯。再插⼊ C 的时候，发现缓存

中有 C ⻚⾯，这个时候需要把 C ⻚⾯放到⾸位，因为它被使⽤了。以此类推，插⼊ G ⻚⾯，G ⻚⾯是新

⻚⾯，不在缓存中，所以淘汰掉 B ⻚⾯。插⼊ H ⻚⾯，H ⻚⾯是新⻚⾯，不在缓存中，所以淘汰掉 D ⻚

⾯。插⼊ E 的时候，发现缓存中有 E ⻚⾯，这个时候需要把 E ⻚⾯放到⾸位。插⼊ I ⻚⾯，I ⻚⾯是新⻚

⾯，不在缓存中，所以淘汰掉 F ⻚⾯。

可以发现，LRU 更新和插⼊新⻚⾯都发⽣在链表⾸，删除⻚⾯都发⽣在链表尾。

解法⼀ Get O(1) / Put O(1)

----------------------- Page 83-----------------------

LRU 要求查询尽量⾼效，O(1) 内查询。那肯定选⽤ map 查询。修改，删除也要尽量 O(1) 完成。搜寻常

⻅的数据结构，链表，栈，队列，树，图。树和图排除，栈和队列⽆法任意查询中间的元素，也排除。

所以选⽤链表来实现。但是如果选⽤单链表，删除这个结点，需要 O(n) 遍历⼀遍找到前驱结点。所以选

⽤双向链表，在删除的时候也能 O(1) 完成。

由于 Go 的 container 包中的 list 底层实现是双向链表，所以可以直接复⽤这个数据结构。定义

LRUCache 的数据结构如下：

import "container/list"

type LRUCache struct {

Cap int

Keys map[int]*list.Element

List *list.List

}

type pair struct {

K, V int

}

func Constructor(capacity int) LRUCache {

return LRUCache{

Cap: capacity,

Keys: make(map[int]*list.Element),

List: list.New(),

}

}

这⾥需要解释 2 个问题，list 中的值存的是什么？pair 这个结构体有什么⽤？

type Element struct {

// Next and previous pointers in the doubly-linked list of elements.

// To simplify the implementation, internally a list l is implemented

// as a ring, such that &l.root is both the next element of the last

// list element (l.Back()) and the previous element of the first list

// element (l.Front()).

next, prev *Element

// The list to which this element belongs.

list *List

// The value stored with this element.

Value interface{}

}

----------------------- Page 84-----------------------

在 container/list 中，这个双向链表的每个结点的类型是 Element 。Element 中存了 4 个值，前驱和后

继结点，双向链表的头结点，value 值。这⾥的 value 是 interface 类型。笔者在这个 value ⾥⾯存了

pair 这个结构体。这就解释了 list ⾥⾯存的是什么数据。

为什么要存 pair 呢？单单指存 v 不⾏么，为什么还要存⼀份 key ？原因是在 LRUCache 执⾏删除操作

的时候，需要维护 2 个数据结构，⼀个是 map ，⼀个是双向链表。在双向链表中删除淘汰出去的

value ，在 map 中删除淘汰出去 value 对应的 key 。如果在双向链表的 value 中不存储 key ，那么再删

除 map 中的 key 的时候有点麻烦。如果硬要实现，需要先获取到双向链表这个结点 Element 的地址。

然后遍历 map ，在 map 中找到存有这个 Element 元素地址对应的 key ，再删除。这样做时间复杂度是

O(n)，做不到 O(1) 。所以双向链表中的 Value 需要存储这个 pair 。

LRUCache 的 Get 操作很简单，在 map 中直接读取双向链表的结点。如果 map 中存在，将它移动到双

向链表的表头，并返回它的 value 值，如果 map 中不存在，返回 -1 。

func (c *LRUCache) Get(key int) int {

if el, ok := c.Keys[key]; ok {

c.List.MoveToFront(el)

return el.Value .(pair).V

}

return -1

}

LRUCache 的 Put 操作也不难。先查询 map 中是否存在 key ，如果存在，更新它的 value ，并且把该结

点移到双向链表的表头。如果 map 中不存在，新建这个结点加⼊到双向链表和 map 中。最后别忘记还

需要维护双向链表的 cap ，如果超过 cap ，需要淘汰最后⼀个结点，双向链表中删除这个结点，map 中

删掉这个结点对应的 key 。

func (c *LRUCache) Put(key int, value int) {

if el, ok := c.Keys[key]; ok {

el.Value = pair{K: key, V : value}

c.List.MoveToFront(el)

} else {

el := c.List.PushFront(pair{K: key, V : value})

c.Keys[key] = el

}

if c.List.Len() > c.Cap {

el := c.List.Back()

c.List.Remove(el)

delete(c.Keys, el.Value .(pair).K)

}

}

总结，LRU 是由⼀个 map 和⼀个双向链表组成的数据结构。map 中 key 对应的 value 是双向链表的结

点。双向链表中存储 key-value 的 pair 。双向链表表⾸更新缓存，表尾淘汰缓存。如下图：

----------------------- Page 85-----------------------

提交代码以后，成功通过所有测试⽤例。

解法⼆ Get O(1) / Put O(1)

数据结构上想不到其他解法了，但从打败的百分⽐上，看似还有常数的优化空间。笔者反复思考，觉得

可能导致运⾏时间变⻓的地⽅是在 interface{} 类型推断，其他地⽅已⽆优化的空间。⼿写⼀个双向链表

提交试试，代码如下：

type LRUCache struct {

head, tail *Node

keys map[int]*Node

capacity int

}

----------------------- Page 86-----------------------

type Node struct {

key, val int

prev, next *Node

}

func ConstructorLRU(capacity int) LRUCache {

return LRUCache{keys: make(map[int]*Node), capacity: capacity}

}

func (this *LRUCache) Get(key int) int {

if node, ok := this.keys[key]; ok {

this.Remove(node)

this.Add(node)

return node.val

}

return -1

}

func (this *LRUCache) Put(key int, value int) {

if node, ok := this.keys[key]; ok {

node.val = value

this.Remove(node)

this.Add(node)

return

} else {

node = &Node{key: key, val: value}

this.keys[key] = node

this.Add(node)

}

if len(this.keys) > this.capacity {

delete(this.keys, this.tail.key)

this.Remove(this.tail)

}

}

func (this *LRUCache) Add(node *Node) {

node.prev = nil

node.next = this.head

if this.head != nil {

this.head.prev = node

}

this.head = node

if this.tail == nil {

this.tail = node

this.tail.next = nil

}

}

func (this *LRUCache) Remove(node *Node) {

----------------------- Page 87-----------------------

if node == this.head {

this.head = node.next

if node.next != nil {

node.next.prev = nil

}

node.next = nil

return

}

if node == this.tail {

this.tail = node.prev

node.prev.next = nil

node.prev = nil

return

}

node.prev.next = node.next

node.next.prev = node.prev

}

提交以后还真的 100% 了。

上述代码实现的 LRU 本质并没有优化，只是换了⼀个写法，没有⽤ container 包⽽已。

模板

type LRUCache struct {

head, tail *Node

Keys map[int]*Node

Cap int

}

----------------------- Page 88-----------------------

type Node struct {

Key, Val int

Prev, Next *Node

}

func Constructor(capacity int) LRUCache {

return LRUCache{Keys: make(map[int]*Node), Cap: capacity}

}

func (this *LRUCache) Get(key int) int {

if node, ok := this.Keys[key]; ok {

this.Remove(node)

this.Add(node)

return node.Val

}

return -1

}

func (this *LRUCache) Put(key int, value int) {

if node, ok := this.Keys[key]; ok {

node.Val = value

this.Remove(node)

this.Add(node)

return

} else {

node = &Node{Key: key, Val : value}

this.Keys[key] = node

this.Add(node)

}

if len(this.Keys) > this.Cap {

delete(this.Keys, this.tail.Key)

this.Remove(this.tail)

}

}

func (this *LRUCache) Add(node *Node) {

node.Prev = nil

node.Next = this.head

if this.head != nil {

this.head.Prev = node

}

this.head = node

if this.tail == nil {

this.tail = node

this.tail.Next = nil

}

}

func (this *LRUCache) Remove(node *Node) {

----------------------- Page 89-----------------------

if node == this.head {

this.head = node.Next

node.Next = nil

return

}

if node == this.tail {

this.tail = node.Prev

node.Prev.Next = nil

node.Prev = nil

return

}

node.Prev.Next = node.Next

node.Next.Prev = node.Prev

}

最不经常最少使⽤ LFUCache

LFU 是 Least Frequently Used 的缩写，即最不经常最少使⽤，也是⼀种常⽤的⻚⾯置换算法，选择访

问计数器最⼩的⻚⾯予以淘汰。如下图，缓存中每个⻚⾯带⼀个访问计数器。

----------------------- Page 90-----------------------

根据 LFU 的策略，每访问⼀次都要更新访问计数器。当插⼊ B 的时候，发现缓存中有 B ，所以增加访问

计数器的计数，并把 B 移动到访问计数器从⼤到⼩排序的地⽅。再插⼊ D ，同理先更新计数器，再移动

到它排序以后的位置。当插⼊ F 的时候，缓存中不存在 F ，所以淘汰计数器最⼩的⻚⾯的⻚⾯，所以淘

汰 A ⻚⾯。此时 F 排在最下⾯，计数为 1 。

这⾥有⼀个⽐ LRU 特别的地⽅。如果淘汰的⻚⾯访问次数有多个相同的访问次数，选择最靠尾部的。如

上图中，A 、B、C 三者的访问次数相同，都是 1 次。要插⼊ F ，F 不在缓存中，此时要淘汰 A ⻚⾯。F

是新插⼊的⻚⾯，访问次数为 1 ，排在 C 的前⾯。也就是说相同的访问次数，按照新旧顺序排列，淘汰

掉最旧的⻚⾯。这⼀点是和 LRU 最⼤的不同的地⽅。

可以发现，LFU 更新和插⼊新⻚⾯可以发⽣在链表中任意位置，删除⻚⾯都发⽣在表尾。

解法⼀ Get O(1) / Put O(1)

----------------------- Page 91-----------------------

LFU 同样要求查询尽量⾼效，O(1) 内查询。依旧选⽤ map 查询。修改和删除也需要 O(1) 完成，依旧选

⽤双向链表，继续复⽤ container 包中的 list 数据结构。LFU 需要记录访问次数，所以每个结点除了存

储 key ，value ，需要再多存储 frequency 访问次数。

还有 1 个问题需要考虑，⼀个是如何按频次排序？相同频次，按照先后顺序排序。如果你开始考虑排序

算法的话，思考⽅向就偏离最佳答案了。排序⾄少 O(nlogn) 。重新回看 LFU 的⼯作原理，会发现它只关

⼼最⼩频次。其他频次之间的顺序并不关⼼。所以不需要排序。⽤⼀个 min 变量保存最⼩频次，淘汰时

读取这个最⼩值能找到要删除的结点。相同频次按照先后顺序排列，这个需求还是⽤双向链表实现，双

向链表插⼊的顺序体现了结点的先后顺序。相同频次对应⼀个双向链表，可能有多个相同频次，所以可

能有多个双向链表。⽤⼀个 map 维护访问频次和双向链表的对应关系。删除最⼩频次时，通过 min 找

到最⼩频次，然后再这个 map 中找到这个频次对应的双向链表，在双向链表中找到最旧的那个结点删

除。这就解决了 LFU 删除操作。

LFU 的更新操作和 LRU 类似，也需要⽤⼀个 map 保存 key 和双向链表结点的映射关系。这个双向链表

结点中存储的是 key-value-frequency 三个元素的元组。这样通过结点中的 key 和 frequency 可以反过

来删除 map 中的 key 。

定义 LFUCache 的数据结构如下：

import "container/list"

type LFUCache struct {

nodes map[int]*list.Element

lists map[int]*list.List

capacity int

min int

}

type node struct {

key int

value int

frequency int

}

func Constructor(capacity int) LFUCache {

return LFUCache{nodes: make(map[int]*list.Element),

lists: make(map[int]*list.List),

capacity: capacity,

min: 0,

}

}

LFUCache 的 Get 操作涉及更新 frequency 值和 2 个 map 。在 nodes map 中通过 key 获取到结点信

息。在 lists 删除结点当前 frequency 结点。删完以后 frequency ++ 。新的 frequency 如果在 lists 中存

在，添加到双向链表表⾸，如果不存在，需要新建⼀个双向链表并把当前结点加到表⾸。再更新双向链

表结点作为 value 的 map 。最后更新 min 值，判断⽼的 frequency 对应的双向链表中是否已经为空，

如果空了，min++。

----------------------- Page 92-----------------------

func (this *LFUCache) Get(key int) int {

value, ok := this.nodes[key]

if !ok {

return -1

}

currentNode := value.Value .(*node)

this.lists[currentNode.frequency].Remove(value)

currentNode.frequency++

if _ , ok := this.lists[currentNode.frequency]; !ok {

this.lists[currentNode.frequency] = list.New()

}

newList := this.lists[currentNode.frequency]

newNode := newList.PushFront(currentNode)

this.nodes[key] = newNode

if currentNode.frequency-1 == this.min && this.lists[currentNode.frequency-

1].Len() == 0 {

this.min++

}

return currentNode.value

}

LFU 的 Put 操作逻辑稍微多⼀点。先在 nodes map 中查询 key 是否存在，如果存在，获取这个结点，

更新它的 value 值，然后⼿动调⽤⼀次 Get 操作，因为下⾯的更新逻辑和 Get 操作⼀致。如果 map 中

不存在，接下来进⾏插⼊或者删除操作。判断 capacity 是否装满，如果装满，执⾏删除操作。在 min 对

应的双向链表中删除表尾的结点，对应的也要删除 nodes map 中的键值。

由于新插⼊的⻚⾯访问次数⼀定为 1 ，所以 min 此时置为 1 。新建结点，插⼊到 2 个 map 中。

func (this *LFUCache) Put(key int, value int) {

if this.capacity == 0 {

return

}

// 如果存在，更新访问次数

if currentValue, ok := this.nodes[key]; ok {

currentNode := currentValue.Value .(*node)

currentNode.value = value

this.Get(key)

return

}

// 如果不存在且缓存满了，需要删除

if this.capacity == len(this.nodes) {

currentList := this.lists[this.min]

backNode := currentList.Back()

delete(this.nodes, backNode.Value .(*node).key)

currentList.Remove(backNode)

}

----------------------- Page 93-----------------------

// 新建结点，插⼊到 2 个 map 中

this.min = 1

currentNode := &node{

key: key,

value: value,

frequency: 1,

}

if _ , ok := this.lists[1]; !ok {

this.lists[1] = list.New()

}

newList := this.lists[1]

newNode := newList.PushFront(currentNode)

this.nodes[key] = newNode

}

总结，LFU 是由两个 map 和⼀个 min 指针组成的数据结构。⼀个 map 中 key 存的是访问次数，对应的

value 是⼀个个的双向链表，此处双向链表的作⽤是在相同频次的情况下，淘汰表尾最旧的那个⻚⾯。

另⼀个 map 中 key 对应的 value 是双向链表的结点，结点中⽐ LRU 多存储了⼀个访问次数的值，即结

点中存储 key-value-frequency 的元组。此处双向链表的作⽤和 LRU 是类似的，可以根据 map 中的

key 更新双向链表结点中的 value 和 frequency 的值，也可以根据双向链表结点中的 key 和 frequency

反向更新 map 中的对应关系。如下图：

提交代码以后，成功通过所有测试⽤例。

解法⼆ Get O(capacity) / Put O(capacity)

LFU 的另外⼀个思路是利⽤ Index Priority Queue 这个数据结构。别被名字吓到，Index Priority

Queue = map + Priority Queue，仅此⽽已。

----------------------- Page 94-----------------------

利⽤ Priority Queue 维护⼀个最⼩堆，堆顶是访问次数最⼩的元素。map 中的 value 存储的是优先队列

中结点。

import "container/heap"

type LFUCache struct {

capacity int

pq PriorityQueue

hash map[int]*Item

counter int

}

func Constructor(capacity int) LFUCache {

lfu := LFUCache{

pq: PriorityQueue{},

hash: make(map[int]*Item, capacity),

capacity: capacity,

}

return lfu

}

Get 和 Put 操作要尽量的快，有 2 个问题需要解决。当访问次数相同时，如何删除掉最久的元素？当元

素的访问次数发⽣变化时，如何快速调整堆？为了解决这 2 个问题，定义如下的数据结构：

// An Item is something we manage in a priority queue.

type Item struct {

value int // The value of the item; arbitrary.

key int

frequency int // The priority of the item in the queue.

count int // use for evicting the oldest element

// The index is needed by update and is maintained by the heap.Interface

methods.

index int // The index of the item in the heap.

}

堆中的结点存储这 5 个值。count 值⽤来决定哪个是最⽼的元素，类似⼀个操作时间戳。index 值⽤来

re-heapify 调整堆的。接下来实现 PriorityQueue 的⽅法。

// A PriorityQueue implements heap.Interface and holds Items.

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {

// We want Pop to give us the highest, not lowest, priority so we use greater

than here.

----------------------- Page 95-----------------------

if pq[i].frequency == pq[j].frequency {

return pq[i].count < pq[j].count

}

return pq[i].frequency < pq[j].frequency

}

func (pq PriorityQueue) Swap(i, j int) {

pq[i], pq[j] = pq[j], pq[i]

pq[i].index = i

pq[j].index = j

}

func (pq *PriorityQueue) Push(x interface{}) {

n := len(*pq)

item := x.(*Item)

item.index = n

*pq = append(*pq, item)

}

func (pq *PriorityQueue) Pop() interface{} {

old := *pq

n := len(old)

item := old[n-1]

old[n-1] = nil // avoid memory leak

item.index = -1 // for safety

*pq = old[0 : n-1]

return item

}

// update modifies the priority and value of an Item in the queue.

func (pq *PriorityQueue) update(item *Item, value int, frequency int, count

int) {

item.value = value

item.count = count

item.frequency = frequency

heap.Fix(pq, item.index)

}

在 Less() ⽅法中，frequency 从⼩到⼤排序，frequency 相同的，按 count 从⼩到⼤排序。按照优先队

列建堆规则，可以得到，frequency 最⼩的在堆顶，相同的 frequency ，count 最⼩的越靠近堆顶。

在 Swap() ⽅法中，记得要更新 index 值。在 Push() ⽅法中，插⼊时队列的⻓度即是该元素的 index

值，此处也要记得更新 index 值。update() ⽅法调⽤ Fix() 函数。Fix() 函数⽐先 Remove() 再 Push() ⼀

个新的值，花销要⼩。所以此处调⽤ Fix() 函数，这个操作的时间复杂度是 O(log n) 。

这样就维护了最⼩ Index Priority Queue 。Get 操作⾮常简单：

----------------------- Page 96-----------------------

func (this *LFUCache) Get(key int) int {

if this.capacity == 0 {

return -1

}

if item, ok := this.hash[key]; ok {

this.counter++

this.pq.update(item, item.value, item.frequency+1, this.counter)

return item.value

}

return -1

}

在 hashmap 中查询 key ，如果存在，counter 时间戳累加，调⽤ Priority Queue 的 update ⽅法，调

整堆。

func (this *LFUCache) Put(key int, value int) {

if this.capacity == 0 {

return

}

this.counter++

// 如果存在，增加 frequency，再调整堆

if item, ok := this.hash[key]; ok {

this.pq.update(item, value, item.frequency+1, this.counter)

return

}

// 如果不存在且缓存满了，需要删除。在 hashmap 和 pq 中删除。

if len(this.pq) == this.capacity {

item := heap.Pop(&this.pq).(*Item)

delete(this.hash, item.key)

}

// 新建结点，在 hashmap 和 pq 中添加。

item := &Item{

value: value,

key: key,

count: this.counter,

}

heap.Push(&this.pq, item)

this.hash[key] = item

}

⽤最⼩堆实现的 LFU ，Put 时间复杂度是 O(capacity) ，Get 时间复杂度是 O(capacity) ，不及 2 个 map

实现的版本。巧的是最⼩堆的版本居然打败了 100% 。

----------------------- Page 97-----------------------

模板

import "container/list"

type LFUCache struct {

nodes map[int]*list.Element

lists map[int]*list.List

capacity int

min int

}

type node struct {

key int

value int

frequency int

}

func Constructor(capacity int) LFUCache {

return LFUCache{nodes: make(map[int]*list.Element),

lists: make(map[int]*list.List),

capacity: capacity,

min: 0,

}

}

func (this *LFUCache) Get(key int) int {

value, ok := this.nodes[key]

if !ok {

return -1

}

----------------------- Page 98-----------------------

currentNode := value.Value .(*node)

this.lists[currentNode.frequency].Remove(value)

currentNode.frequency++

if _ , ok := this.lists[currentNode.frequency]; !ok {

this.lists[currentNode.frequency] = list.New()

}

newList := this.lists[currentNode.frequency]

newNode := newList.PushBack(currentNode)

this.nodes[key] = newNode

if currentNode.frequency-1 == this.min && this.lists[currentNode.frequency-

1].Len() == 0 {

this.min++

}

return currentNode.value

}

func (this *LFUCache) Put(key int, value int) {

if this.capacity == 0 {

return

}

if currentValue, ok := this.nodes[key]; ok {

currentNode := currentValue.Value .(*node)

currentNode.value = value

this.Get(key)

return

}

if this.capacity == len(this.nodes) {

currentList := this.lists[this.min]

frontNode := currentList.Front()

delete(this.nodes, frontNode.Value .(*node).key)

currentList.Remove(frontNode)

}

this.min = 1

currentNode := &node{

key: key,

value: value,

frequency: 1,

}

if _ , ok := this.lists[1]; !ok {

this.lists[1] = list.New()

}

newList := this.lists[1]

newNode := newList.PushBack(currentNode)

this.nodes[key] = newNode

}