leetcode C++高性能版

leetcode的C++高性能题解，追求运行时长打败 95%+

---

数据统计

Top100受欢迎题目: 78 / 100 已解决

Top面试题目: 86 / 145 已解决

总计: 159 / 3656 已解决

运行时长打败 95% 以上的题解占比: 144 / 159

---

题目分类

分类	题目编号
Array / String	1, 3, 6, 11, 14, 15, 16, 18, 20, 22, 26, 27, 28, 30, 31, 38, 41, 42, 44, 45, 48, 49, 54, 55, 56, 73, 75, 76, 80, 88, 125, 239, 283, 349, 350, 438, 567, 670, 832, 1838
Linked list	2, 19, 21, 23, 24, 25, 61, 86, 92, 141, 142, 160, 206, 234, 876
Recursion	4, 33, 34, 35, 69, 74, 153, 215, 240, 278, 287, 301, 540, 704
Dynamic Programming	5, 10, 32, 36, 37, 53, 62, 63, 64, 70, 79, 84, 91, 96, 118, 120, 121, 122, 123, 128, 130, 134, 188, 198, 213, 221, 279, 300, 309, 322, 509, 714, 864, 871
Numerical	7, 8, 9, 12, 13, 29, 43, 50, 66, 136, 150, 564
Backtracking	17, 39, 40, 46, 47, 51, 60, 78, 131
Binary Tree	94, 98, 101, 102, 103, 104, 105, 106, 108, 111, 114, 116, 124, 144, 145, 226, 230, 235, 236, 337, 450, 538, 543, 652, 654, 700, 701, 889, 958, 1038
Graph / DFS	127, 752
System Design	146, 460

---

开发环境

已经在以下环境测试通过：

• macOS Sequoia 15.6
  • Clang 17.0.0
  • CMake 4.1.0
  • Catch2 v3.9.1
• Windows 11 24H2
  • VC 14.44.35207 (Visual Studio 2022)
  • CMake 4.1.0
  • Catch2 v3.9.1
• Ubuntu 24.04
  • Clang 21.1.0
  • CMake 4.1.1
  • Catch2 v3.9.1

---

题解

1. Two Sum

• Hash table: 0ms (Beats 100.00%)

2. Add Two Numbers

• Linked list: 0ms (Beats 100.00%)

3. Longest Substring Without Repeating Characters

• Hash table: 0ms (Beats 100.00%)

4. Median of Two Sorted Arrays

• Non-recursive: 0ms (Beats 100.00%)
• Recursion: 0ms (Beats 100.00%)

5. Longest Palindromic Substring

• Brute force: 0ms (Beats 100.00%)
• Manacher's algorithm: 0ms (Beats 100.00%)

6. ZigZag Conversion

• Brute force: 31ms (Beats 11.68%)
• Better loop: 0ms (Beats 100.00%)

7. Reverse Integer

• 0ms (Beats 100.00%)

8. String to Integer (atoi)

• 0ms (Beats 100.00%)

9. Palindrome Number

• Lookup table: 0ms (Beats 100.00%)

10. Regular Expression Matching

• DP: 0ms (Beats 100.00%)

11. Container With Most Water

• Two pointers: 0ms (Beats 100.00%)

12. Integer to Roman

• Two arrays: 0ms (Beats 100.00%)
• Lookup table: 0ms (Beats 100.00%)

13. Roman to Integer

• 0ms (Beats 100.00%)
• Map: 3ms (Beats 75.78%)

14. Longest Common Prefix

• 0ms (Beats 100.00%)

15. 3Sum

• Two pointers: 31ms (Beats 99.17%)

16. 3Sum Closest

• Two pointers: 5ms (Beats 93.93%)

17. Letter Combinations of a Phone Number

• Deque: 0ms (Beats 100.00%)
• DFS: 0ms (Beats 100.00%)

18. 4Sum

• Set: 35ms (Beats 16.53%)
• Better loop: 0ms (Beats 100.00%)

19. Remove Nth Node From End of List

• 0ms (Beats 100.00%)

20. Valid Parentheses

• Stack: 0ms (Beats 100.00%)
• Lookup table: 0ms (Beats 100.00%)

21. Merge Two Sorted Lists

• Two swaps: 0ms (Beats 100.00%)

22. Generate Parentheses

• 0ms (Beats 100.00%)
• Deque: 0ms (Beats 100.00%)

23. Merge k Sorted Lists

• Use 021: 0ms (Beats 100.00%)
• Priority queue: 0ms (Beats 100.00%)

24. Swap Nodes in Pairs

• 0ms (Beats 100.00%)

25. Reverse Nodes in k-Group

• 0ms (Beats 100.00%)

26. Remove Duplicates from Sorted Array

• 0ms (Beats 100.00%)

27. Remove Element

• 0ms (Beats 100.00%)

28. Find the Index of the First Occurrence in a String

• Brute force: 0ms (Beats 100.00%)
• KMP: 0ms (Beats 100.00%)

29. Divide Two Integers

• 0ms (Beats 100.00%)

30. Substring with Concatenation of All Words

• 16ms (Beats 90.48%)

31. Next Permutation

• 0ms (Beats 100.00%)

32. Longest Valid Parentheses

• 0ms (Beats 100.00%)

33. Search in Rotated Sorted Array

• 0ms (Beats 100.00%)

34. Find First and Last Position of Element in Sorted Array

• 0ms (Beats 100.00%)

35. Search Insert Position

• 0ms (Beats 100.00%)

36. Valid Sudoku

• 3ms (Beats 62.61%)

37. Sudoku Solver

• 4ms (Beats 98.43%)

38. Count and Say

• 0ms (Beats 100.00%)

39. Combination Sum

• 0ms (Beats 100.00%)

40. Combination Sum II

• 0ms (Beats 100.00%)

41. First Missing Positive

• Lookup table: 0ms (Beats 100.00%)
• Swap: 0ms (Beats 100.00%)

42. Trapping Rain Water

• Two pointers: 515ms (Beats 5.33%)
• Auxiliary vector: 0ms (Beats 100.00%)

43. Multiply Strings

• C++ interface: 2ms (Beats 71.45%)
• C interface: 0ms (Beats 100.00%)

44. Wildcard Matching

• 0ms (Beats 100.00%)

45. Jump Game II

• 0ms (Beats 100.00%)

46. Permutations

• Recursive: 7ms (Beats 6.15%)
• Better loop: 0ms (Beats 100.00%)
• Backtracking: 0ms (Beats 100.00%)

47. Permutations II

• 3ms (Beats 67.49%)

48. Rotate Image

• 0ms (Beats 100.00%)
• Flip + swap: 0ms (Beats 100.00%)

49. Group Anagrams

• Hash table: 23ms (Beats 32.64%)
• Sort + hash table: 7ms (Beats 98.59%)

50. Pow(x, n)

• 0ms (Beats 100.00%)

51. N-Queens

• 0ms (Beats 100.00%)

53. Maximum Subarray

• Divide and conquer: 21ms (Beats 5.11%)
• Kadane: 0ms (Beats 100.00%)
• DP: 0ms (Beats 100.00%)

54. Spiral Matrix

• 0ms (Beats 100.00%)

55. Jump Game

• Forward: 0ms (Beats 100.00%)
• Backward: 0ms (Beats 100.00%)

56. Merge Intervals

• 2ms (Beats 93.23%)

60. Permutation Sequence

• 0ms (Beats 100.00%)

61. Rotate List

• 0ms (Beats 100.00%)

62. Unique Paths

• 0ms (Beats 100.00%)

63. Unique Paths II

• 0ms (Beats 100.00%)

64. Minimum Path Sum

• 0ms (Beats 100.00%)

66. Plus One

• 0ms (Beats 100.00%)

69. Sqrt(x)

• 0ms (Beats 100.00%)

70. Climbing Stairs

• 0ms (Beats 100.00%)

73. Set Matrix Zeroes

• 0ms (Beats 100.00%)

74. Search a 2D Matrix

• 0ms (Beats 100.00%)

75. Sort Colors

• 0ms (Beats 100.00%)
• three pointer: 0ms (Beats 100.00%)

76. Minimum Window Substring

• Sliding window: 23ms (Beats 13.60%)
• Hash table: 0ms (Beats 100.00%)

77. Subsets

• 0ms (Beats 100.00%)
• Backtrack: 0ms (Beats 100.00%)
• Bitwise: 0ms (Beats 100.00%)

79. Word Search

• 92ms (Beats 97.42%)
• Inplace: 72ms (Beats 97.59%)

80. Remove Duplicates from Sorted Array II

• 3ms (Beats 96.26%)

84. Largest Rectangle in Histogram

• Two vector: 4ms (Beats 99.11%)
• One vector: 4ms (Beats 99.11%)

86. Partition List

• 0ms (Beats 100.00%)

88. Merge Sorted Array

• 0ms (Beats 100.00%)
• Three pointers: 0ms (Beats 100.00%)

91. Decode Ways

• 0ms (Beats 100.00%)

92. Reverse Linked List II

• 0ms (Beats 100.00%)

94. Binary Tree Inorder Traversal

• Recursion - vector: 0ms (Beats 100.00%)
• Recursion - list: 0ms (Beats 100.00%)
• Stack: 0ms (Beats 100.00%)
• Stack: 0ms (Beats 100.00%)

96. Unique Binary Search Trees

• 0ms (Beats 100.00%)

98. Validate Binary Search Tree

• 0ms (Beats 100.00%)
• Two pointers: 0ms (Beats 100.00%)

101. Symmetric Tree

• Recursive: 0ms (Beats 100.00%)
• Queue: 0ms (Beats 100.00%)

102. Binary Tree Level Order Traversal

• 0ms (Beats 100.00%)

103. Binary Tree Zigzag Level Order Traversal

• 0ms (Beats 100.00%)

104. Maximum Depth of Binary Tree

• 0ms (Beats 100.00%)

105. Construct Binary Tree from Preorder and Inorder Traversal

• 7ms (Beats 37.32%)
• Hash table: 0ms (Beats 100.00%)
• Stack: 0ms (Beats 100.00%)

106. Construct Binary Tree from Inorder and Postorder Traversal

• 3ms (Beats 71.46%)
• Hash table: 0ms (Beats 100.00%)

108. Convert Sorted Array to Binary Search Tree

• 0ms (Beats 100.00%)

111. Minimum Depth of Binary Tree

• Recursion: 3ms (Beats 54.48%)
• Queue: 0ms (Beats 100.00%)

114. Flatten Binary Tree to Linked List

• 0ms (Beats 100.00%)

116. Populating Next Right Pointers in Each Node

• 11ms (Beats 82.38%)
• 8ms (Beats 91.84%)

118. Pascal's Triangle

• 0ms (Beats 100.00%)
• Swap: 0ms (Beats 100.00%)
• Resize: 0ms (Beats 100.00%)

120. Triangle

• 0ms (Beats 100.00%)

121. Best Time to Buy and Sell Stock

• Priority queue: 11ms (Beats 6.67%)
• Forward: 0ms (Beats 100.00%)
• Backward: 0ms (Beats 100.00%)

122. Best Time to Buy and Sell Stock II

• 0ms (Beats 100.00%)

123. Best Time to Buy and Sell Stock III

• 0ms (Beats 100.00%)

124. Binary Tree Maximum Path Sum

• 0ms (Beats 100.00%)

125. Valid Palindrome

• 0ms (Beats 100.00%)

127. Word Ladder

• 16ms (Beats 99.21%)
• Graph + BFS: 103ms (Beats 39.97%)
• Graph + BiDir BFS: 101ms (Beats 40.23%)
• BiDir BFS: 451ms (Beats 19.11%)

128. Longest Consecutive Sequence

• DP: 91ms (Beats 30.64%)
• Hash table: 78ms (Beats 70.64%)
• Sort + erase: 15ms (Beats 87.75%)
• Sort: 11ms (Beats 94.32%)

130. Surrounded Regions

• 0ms (Beats 100.00%)

131. Palindrome Partitioning

• Backtrack: 52ms (Beats 52.78%)
• Backtrack + DP: 23ms (Beats 98.28%)

134. Gas Station

• 0ms (Beats 100.00%)

136. Single Number

• 0ms (Beats 100.00%)

141. Linked List Cycle

• 3ms (Beats 99.30%)

142. Linked List Cycle II

• 3ms (Beats 98.18%)

144. Binary Tree Preorder Traversal

• Recursion: 0ms (Beats 100.00%)
• Stack: 0ms (Beats 100.00%)

145. Binary Tree Postorder Traversal

• Recursion: 0ms (Beats 100.00%)
• Stack: 0ms (Beats 100.00%)

146. LRU Cache

• 61ms (Beats 85.67%)
• Linked list: 32ms (Beats 98.86%)

150. Evaluate Reverse Polish Notation

• 0ms (Beats 100.00%)

153. Find Minimum in Rotated Sorted Array

• 0ms (Beats 100.00%)

160. Intersection of Two Linked Lists

• 28ms (Beats 96.62%)

187. Repeated DNA Sequences

• 3-bit hash: 0ms (Beats 100.00%)
• 2-bit hash: 24ms (Beats 98.77%)

188. Best Time to Buy and Sell Stock IV

• 0ms (Beats 100.00%)

198. House Robber

• 0ms (Beats 100.00%)

206. Reverse Linked List

• Two pointers: 0ms (Beats 100.00%)
• Faster two pointers: 0ms (Beats 100.00%)
• Recursion: 0ms (Beats 100.00%)

213. House Robber II

• 0ms (Beats 100.00%)

215. Kth Largest Element in an Array

• 4ms (Beats 97.59%)
• Quick sort: 0ms (Beats 100.00%)

221. Maximal Square

• 1ms (Beats 96.15%)

226. Invert Binary Tree

• 0ms (Beats 100.00%)

230. Kth Smallest Element in a BST

• 0ms (Beats 100.00%)

234. Palindrome Linked List

• Recursion: 4ms (Beats 53.48%)
• Two pointers: 0ms (Beats 100.00%)

235. Lowest Common Ancestor of a Binary Search Tree

• 14ms (Beats 97.81%)

236. Lowest Common Ancestor of a Binary Tree

• 6ms (Beats 96.44%)

239. Sliding Window Maximum

• 11ms (Beats 97.23%)

240. Search a 2D Matrix II

• 36ms (Beats 97.55%)

278. First Bad Version

• 0ms (Beats 100.00%)

279. Perfect Squares

• 0ms (Beats 100.00%)
• Tree search: 54ms (Beats 61.29%)

283. Move Zeroes

• Two pointers: 0ms (Beats 100.00%)
• Faster two pointers: 0ms (Beats 100.00%)

287. Find the Duplicate Number

• Binary search: 8ms (Beats 48.64%)
• Two pointers: 1ms (Beats 76.75%)

300. Longest Increasing Subsequence

• 0ms (Beats 100.00%)

301. Remove Invalid Parentheses

• 0ms (Beats 100.00%)

309. Best Time to Buy and Sell Stock with Cooldown

• 0ms (Beats 100.00%)

322. Coin Change

• 15ms (Beats 93.27%)

337. House Robber III

• Vector: 11ms (Beats 25.30%)
• Pair: 0ms (Beats 100.00%)

349. Intersection of Two Arrays

• Set: 0ms (Beats 100.00%)
• Map: 0ms (Beats 100.00%)

350. Intersection of Two Arrays II

• 0ms (Beats 100.00%)

438. Find All Anagrams in a String

• 2ms (Beats 85.24%)

450. Delete Node in a BST

• 0ms (Beats 100.00%)

460. LFU Cache

• 59ms (Beats 98.92%)

509. Fibonacci Number

• 0ms (Beats 100.00%)

538. Convert BST to Greater Tree

• 0ms (Beats 100.00%)

540. Single Element in a Sorted Array

• Recursion: 0ms (Beats 100.00%)
• Iteration: 0ms (Beats 100.00%)

543. Diameter of Binary Tree

• 0ms (Beats 100.00%)

564. Find the Closest Palindrome

• 0ms (Beats 100.00%)

567. Permutation in String

• 2ms (Beats 73.12%)

652. Find Duplicate Subtrees

• 13ms (Beats 93.57%)

654. Maximum Binary Tree

• 8ms (Beats 75.89%)

670. Maximum Swap

• 0ms (Beats 100.00%)

700. Search in a Binary Search Tree

• 0ms (Beats 100.00%)

701. Insert into a Binary Search Tree

• 0ms (Beats 100.00%)

704. Binary Search

• 0ms (Beats 100.00%)

714. Best Time to Buy and Sell Stock with Transaction Fee

• 0ms (Beats 100.00%)

752. Open the Lock

• BFS: 132ms (Beats 66.03%)

832. Flipping an Image

• 0ms (Beats 100.00%)

864. Shortest Path to Get All Keys

• 8ms (Beats 98.51%)

871. Minimum Number of Refueling Stops

• DP: 13ms (Beats 15.59%)
• Priority queue: 0ms (Beats 100.00%)

876. Middle of the Linked List

• 0ms (Beats 100.00%)

889. Construct Binary Tree from Preorder and Postorder Traversal

• 0ms (Beats 100.00%)

958. Check Completeness of a Binary Tree

• 0ms (Beats 100.00%)

1038. Binary Search Tree to Greater Sum Tree

• 0ms (Beats 100.00%)

1838. Frequency of the Most Frequent Element

• 31ms (Beats 90.46%)