LeetCode 算法题目解答汇总

[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于 tricky 的方法。我没有为了这个再更新，就让它们去吧。请读者知道这一点。

只要不是特别忙或者特别不方便，最近一直保持着每天做几道算法题的规律，到后来随着难度的增加，每天做的题目越来越少。我的初衷就是练习，因为一方面我本身算法基础并不好，再一方面是因为工作以后传统意义上所谓算法的东西接触还是太少。为了题目查找方便起见，我把之前几篇陆陆续续贴出来的我对 LeetCode 上面算法题的解答汇总在下面，CTRL+F 就可以比较方便地找到。由于 LeetCode 上的题在不断更新，因此我也会不定期地更新。下面表格里面的 Acceptance 和 Difficulty 的 Easy/Medium/Hard 的分类都是来自 LeetCode 上面的数据，而 Difficulty 括号里面的数值和 Frequency 则来自这个文档。另外，LeetCode 数据库的那十道题（截止到目前）我记录在这里。

总体来说，做 LeetCode 的题目收获还是很大的。而这种可以很快获得代码正确性和性能即使的反馈的方式，对算法提高也是很有帮助的。有的题目困难，主要包括两方面的原因，有的是思路比较怪异，用常规思路去解题往往时间复杂度或者空间复杂度过高，还有的则是需要考虑的情况比较复杂，case 众多，很容易遗漏。

Title Acceptance Difficulty Frequency Palindrome Number 28.8% Easy (2) 2 ZigZag Conversion 23.4% Easy (3) 1 Valid Sudoku 27.6% Easy (2) 2 Add Binary 25.5% Easy (2) 4 Valid Parentheses 28.2% Easy (2) 5 Valid Palindrome 22.2% Easy (2) 5 Balanced Binary Tree 32.5% Easy (1) 2 Valid Number 11.0% Easy (2) 5 Symmetric Tree 31.6% Easy (1) 2 String to Integer (atoi) 14.2% Easy (2) 5 Same Tree 41.8% Easy (1) 1 Binary Tree Level Order Traversal 30.6% Easy (3) 4 Binary Tree Level Order Traversal II 31.0% Easy (3) 1 Roman to Integer 33.9% Easy (2) 4 Reverse Integer 39.8% Easy (2) 3 Remove Nth Node From End of List 29.3% Easy (2) 3 Remove Element 33.0% Easy (1) 4 Remove Duplicates from Sorted List 34.7% Easy (1) 3 Climbing Stairs 34.0% Easy (2) 5 Remove Duplicates from Sorted Array 32.2% Easy (1) 3 Plus One 31.4% Easy (1) 2 Path Sum 30.4% Easy (1) 3 Pascal’s Triangle II 30.1% Easy (2) 1 Pascal’s Triangle 31.1% Easy (2) 1 Minimum Depth of Binary Tree 29.4% Easy (1) 1 Merge Two Sorted Lists 33.2% Easy (2) 5 Merge Sorted Array 31.8% Easy (2) 5 Maximum Depth of Binary Tree 43.8% Easy (1) 1 Longest Common Prefix 27.0% Easy (2) 1 Count and Say 26.7% Easy (2) 2 Length of Last Word 29.0% Easy (1) 1 Implement strStr() 21.9% Easy (4) 5 Divide Two Integers 16.6% Medium (4) 3 3Sum 16.7% Medium (3) 5 Evaluate Reverse Polish Notation 19.9% Medium

Find Minimum in Rotated Sorted Array 31.7% Medium

Word Search 19.8% Medium (3) 4 Word Ladder 18.4% Medium (3) 5 Flatten Binary Tree to Linked List 28.2% Medium (3) 3 Gas Station 25.9% Medium

Generate Parentheses 31.4% Medium (3) 4 Gray Code 32.1% Medium (4) 2 Word Break 21.3% Medium

Validate Binary Search Tree 25.9% Medium (3) 5 Insertion Sort List 25.3% Medium

Integer to Roman 33.8% Medium (3) 4 4Sum 21.4% Medium (3) 2 Jump Game 27.2% Medium (3) 2 Add Two Numbers 22.9% Medium (3) 4 Anagrams 23.9% Medium (3) 4 Decode Ways 16.2% Medium (3) 4 Letter Combinations of a Phone Number 26.4% Medium (3) 3 Linked List Cycle 35.7% Medium

Linked List Cycle II 30.8% Medium

Best Time to Buy and Sell Stock 31.2% Medium (2) 1 Unique Paths II 27.9% Medium (3) 3 Longest Palindromic Substring 20.6% Medium (4) 2 Longest Substring Without Repeating Characters 22.2% Medium (3) 2 Unique Paths 31.7% Medium (2) 3 Unique Binary Search Trees II 27.3% Medium (4) 1 Unique Binary Search Trees 36.5% Medium (3) 1 Two Sum 18.4% Medium (2) 5 Convert Sorted List to Binary Search Tree 27.3% Medium (4) 3 Maximum Product Subarray 15.9% Medium

Maximum Subarray 34.0% Medium (3) 3 Triangle 26.6% Medium (3) 1 Best Time to Buy and Sell Stock II 36.6% Medium (3) 1 Swap Nodes in Pairs 32.4% Medium (2) 4 Convert Sorted Array to Binary Search Tree 32.9% Medium (2) 3 Container With Most Water 31.3% Medium (3) 2 Minimum Path Sum 31.0% Medium (3) 3 Surrounded Regions 14.2% Medium (4) 3 Multiply Strings 20.5% Medium (4) 3 Sum Root to Leaf Numbers 29.7% Medium (2) 4 Subsets II 27.0% Medium (4) 2 Next Permutation 25.4% Medium (5) 2 3Sum Closest 27.0% Medium (3) 1 Palindrome Partitioning 25.9% Medium (3) 4 Subsets 27.9% Medium (3) 4 Partition List 27.0% Medium (3) 3 Construct Binary Tree from Inorder and Postorder Traversal 26.6% Medium

Construct Binary Tree from Preorder and Inorder Traversal 26.5% Medium

Combinations 30.0% Medium (3) 4 Combination Sum II 24.7% Medium (4) 2 Path Sum II 26.9% Medium (2) 2 Permutation Sequence 22.3% Medium (5) 1 Permutations 31.2% Medium (3) 4 Sqrt(x) 22.3% Medium (4) 4 Combination Sum 26.8% Medium (3) 3 Populating Next Right Pointers in Each Node 35.3% Medium (3) 3 Spiral Matrix II 30.8% Medium (3) 2 Pow(x, n) 25.9% Medium (3) 5 Spiral Matrix 20.6% Medium (4) 2 Sort List 20.6% Medium

Clone Graph 23.0% Medium

Remove Duplicates from Sorted Array II 30.6% Medium (2) 2 Sort Colors 32.1% Medium (4) 2 Remove Duplicates from Sorted List II 24.8% Medium (3) 3 Binary Tree Zigzag Level Order Traversal 26.5% Medium (4) 3 Binary Tree Preorder Traversal 35.5% Medium

Reorder List 20.4% Medium

Restore IP Addresses 20.5% Medium (3) 3 Single Number II 33.8% Medium

Reverse Linked List II 26.1% Medium (3) 2 Single Number 45.6% Medium

Reverse Words in a String 14.0% Medium

Simplify Path 19.9% Medium (3) 1 Rotate Image 31.2% Medium (4) 2 Rotate List 22.0% Medium (3) 2 Binary Tree Inorder Traversal 35.5% Medium (4) 3 Set Matrix Zeroes 30.8% Medium (3) 5 Search a 2D Matrix 31.2% Medium (3) 3 Search for a Range 27.4% Medium (4) 3 Search Insert Position 34.9% Medium (2) 2 Search in Rotated Sorted Array II 30.9% Medium (5) 3 Text Justification 14.0% Hard (4) 2 Search in Rotated Sorted Array 28.6% Hard (4) 3 Binary Tree Maximum Path Sum 20.2% Hard (4) 2 Reverse Nodes in k-Group 24.9% Hard (4) 2 Binary Tree Postorder Traversal 31.0% Hard

Candy 19.3% Hard

Edit Distance 25.5% Hard (4) 3 Recover Binary Search Tree 23.7% Hard (4) 2 Populating Next Right Pointers in Each Node II 30.7% Hard (4) 2 Permutations II 25.0% Hard (4) 2 Best Time to Buy and Sell Stock III 22.4% Hard (4) 1 Palindrome Partitioning II 18.3% Hard (4) 3 N-Queens II 33.9% Hard (4) 3 Substring with Concatenation of All Words 18.1% Hard (3) 1 Sudoku Solver 20.9% Hard (4) 2 N-Queens 25.9% Hard (4) 3 Minimum Window Substring 18.1% Hard (4) 2 Merge k Sorted Lists 21.2% Hard (3) 4 Merge Intervals 20.9% Hard (4) 5 Scramble String 22.8% Hard (5) 2 Trapping Rain Water 28.9% Hard (4) 2 Median of Two Sorted Arrays 17.6% Hard (5) 3 Maximal Rectangle 21.5% Hard (5) 1 Max Points on a Line 11.2% Hard

LRU Cache 14.1% Hard

Longest Valid Parentheses 19.7% Hard (4) 1 Longest Consecutive Sequence 28.2% Hard (4) 3 Copy List with Random Pointer 23.5% Hard

Largest Rectangle in Histogram 21.5% Hard (5) 2 Jump Game II 24.7% Hard (4) 2 Interleaving String 19.5% Hard (5) 2 Insert Interval 20.7% Hard (4) 5 Wildcard Matching 14.3% Hard (5) 3 Distinct Subsequences 25.0% Hard (4) 2 Word Break II 16.6% Hard

First Missing Positive 22.6% Hard (5) 2 Word Ladder II 11.5% Hard (1) 1 Find Minimum in Rotated Sorted Array II 27.9% Hard

Regular Expression Matching 20.2% Hard (5) 3

【2015-6-17】从上次贴出来我的解答以后，最新更新的题目，除了一些需要买书只能在电子书上面看解答的没法验证以外，凡是题目能够在线解答和验证答案的，我把我的全部和分析放在了下面。欢迎指正。

226 Invert Binary Tree 37.6% Easy 225 Implement Stack using Queues 30.0% Medium 224 Basic Calculator 16.1% Medium 223 Rectangle Area 26.0% Easy 222 Count Complete Tree Nodes 19.8% Medium 221 Maximal Square 20.6% Medium 220 Contains Duplicate III 15.0% Medium 219 Contains Duplicate II 26.2% Easy 218 The Skyline Problem 17.0% Hard 217 Contains Duplicate 35.9% Easy 216 Combination Sum III 27.3% Medium 215 Kth Largest Element in an Array 27.4% Medium 214 Shortest Palindrome 16.3% Hard 213 House Robber II 26.1% Medium 212 Word Search II 15.0% Hard 211 Add and Search Word – Data structure design 20.9% Medium 210 Course Schedule II 19.1% Medium 209 Minimum Size Subarray Sum 23.1% Medium 208 Implement Trie (Prefix Tree) 25.0% Medium 207 Course Schedule 21.2% Medium 206 Reverse Linked List 32.0% Easy 205 Isomorphic Strings 24.2% Easy 204 Count Primes 18.9% Easy 203 Remove Linked List Elements 26.0% Easy 202 Happy Number 31.5% Easy 201 Bitwise AND of Numbers Range 27.2% Medium 200 Number of Islands 21.9% Medium 199 Binary Tree Right Side View 26.9% Medium 198 House Robber 28.8% Easy 191 Number of 1 Bits 37.3% Easy 190 Reverse Bits 28.3% Easy 189 Rotate Array 17.8% Easy 188 Best Time to Buy and Sell Stock IV 17.0% Hard 187 Repeated DNA Sequences 19.2% Medium 186 Reverse Words in a String II 31.1% Medium 179 Largest Number 15.7% Medium 174 Dungeon Game 17.5% Hard 173 Binary Search Tree Iterator 29.2% Medium 172 Factorial Trailing Zeroes 28.3% Easy 171 Excel Sheet Column Number 36.6% Easy 170 Two Sum III – Data structure design 24.7% Easy 169 Majority Element 34.9% Easy 168 Excel Sheet Column Title 18.1% Easy 167 Two Sum II – Input array is sorted 43.3% Medium 166 Fraction to Recurring Decimal 12.6% Medium 165 Compare Version Numbers 15.1% Easy 164 Maximum Gap 24.3% Hard 163 Missing Ranges 24.0% Medium 162 Find Peak Element 31.4% Medium 161 One Edit Distance 24.3% Medium 160 Intersection of Two Linked Lists 28.5% Easy 159 Longest Substring with At Most Two Distinct Characters 30.3% Hard 158 Read N Characters Given Read4 II – Call multiple times 22.2% Hard 157 Read N Characters Given Read4 29.9% Easy 156 Binary Tree Upside Down 34.4% Medium 155 Min Stack 18.3% Easy

【Updated：12/15/2015】227 到 310 题

310 Minimum Height Trees 24.0% Medium 309 Best Time to Buy and Sell Stock with Cooldown 33.7% Medium 307 Range Sum Query – Mutable 15.5% Medium 306 Additive Number 23.2% Medium 304 Range Sum Query 2D – Immutable 20.3% Medium 303 Range Sum Query – Immutable 23.9% Easy 301 Remove Invalid Parentheses 28.6% Hard 300 Longest Increasing Subsequence 31.8% Medium 299 Bulls and Cows 25.9% Easy 297 Serialize and Deserialize Binary Tree 24.2% Medium 295 Find Median from Data Stream 19.7% Hard 292 Nim Game 50.0% Easy 290 Word Pattern 27.0% Easy 289 Game of Life 32.2% Medium 287 Find the Duplicate Number 36.0% Hard 284 Peeking Iterator 31.8% Medium 283 Move Zeroes 42.3% Easy 282 Expression Add Operators 21.5% Hard 279 Perfect Squares 29.8% Medium 278 First Bad Version 21.0% Easy 275 H-Index II 31.7% Medium 274 H-Index 27.1% Medium 273 Integer to English Words 16.9% Medium 268 Missing Number 37.5% Medium 264 Ugly Number II 24.5% Medium 263 Ugly Number 34.6% Easy 260 Single Number III 40.7% Medium 258 Add Digits 47.6% Easy 257 Binary Tree Paths 24.9% Easy 242 Valid Anagram 39.1% Easy 241 Different Ways to Add Parentheses 30.6% Medium 240 Search a 2D Matrix II 31.4% Medium 239 Sliding Window Maximum 24.8% Hard 238 Product of Array Except Self 39.5% Medium 237 Delete Node in a Linked List 44.0% Easy 236 Lowest Common Ancestor of a Binary Tree 27.7% Medium 235 Lowest Common Ancestor of a Binary Search Tree 37.9% Easy 234 Palindrome Linked List 25.3% Easy 233 Number of Digit One 22.6% Medium 232 Implement Queue using Stacks 33.8% Easy 231 Power of Two 33.3% Easy 230 Kth Smallest Element in a BST 34.0% Medium 229 Majority Element II 24.2% Medium 228 Summary Ranges 21.6% Easy 227 Basic Calculator II 22.2% Medium

【Updated：1/19/2017】311 到 371 题

371

51.9% Easy 368

31.9% Medium 367

36.9% Medium 365

24.7% Medium 363

30.6% Hard 357

44.2% Medium 355

23.5% Medium 354

30.6% Hard 352

38.2% Hard 350

42.6% Easy 349

44.5% Easy 347

44.4% Medium 345

36.6% Easy 344

58.1% Easy 343

43.8% Medium 342

36.6% Easy 341

35.3% Medium 338

58.6% Medium 337

40.2% Medium 336

22.7% Hard 335

22.8% Hard 334

36.7% Medium 332

26.8% Medium 331

33.9% Medium 330

30.8% Hard 329

34.0% Hard 328

40.7% Medium 327

27.7% Hard 326

38.6% Easy 324

24.3% Medium 322

25.8% Medium 321

22.9% Hard 319

41.5% Medium 318

41.3% Medium 316

27.5% Hard 315

32.5% Hard 313

36.5% Medium 312

40.4% Hard

[Updated 11/6/2017] LeetCode 300 题以内需要付费才能查看的所有题目解答。

[Updated on 3/25/2019] 372 到 415 题：372

35.5% Medium 373

33.3% Medium 374

38.9% Easy 375

37.3% Medium 376

37.0% Medium 377

43.7% Medium 378

48.6% Medium 380

42.1% Medium 381

31.6% Hard 382

48.8% Medium 383

49.4% Easy 384

49.6% Medium 385

31.6% Medium 386

45.0% Medium 387

49.4% Easy 388

38.9% Medium 389

52.8% Easy 390

43.3% Medium 391

28.0% Hard 392

46.3% Medium 393

35.5% Medium 394

44.1% Medium 395

38.0% Medium 396

34.9% Medium 397

31.1% Medium 398

49.1% Medium 399

46.9% Medium 400

30.2% Easy 401

45.1% Easy 402

26.2% Medium 403

35.6% Hard 404

48.7% Easy 405

41.7% Easy 406

59.1% Medium 407

38.9% Hard 409

47.6% Easy 410

41.9% Hard 412

59.0% Easy 413

55.4% Medium 414

28.7% Easy 415

43.2% Easy

文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》