第1页 / 共100页
第2页 / 共100页
第3页 / 共100页
第4页 / 共100页
第5页 / 共100页
第6页 / 共100页
第7页 / 共100页
第8页 / 共100页
LeetCode经典例题官方解答.pdf
1. Two Sum
2. Two Sum II – Input array is sorted
3. Two Sum III – Data structure design
4. Valid Palindrome
5. Implement strstr()
6. Reverse Words in a String
7. Reverse Words in a String II
8. String to Integer (atoi)
9. Valid Number
10. Longest Substring Without Repeating Characters
11. Longest Substring with At Most Two Distinct Characters
12. Missing Ranges
13. Longest Palindromic Substring
14. One Edit Distance
15. Read N Characters Given Read4
16. Read N Characters Given Read4 – Call multiple times
17. Reverse Integer
18. Plus One
19. Palindrome Number
20. Merge Two Sorted Lists
21. Add Two Numbers
22. Swap Nodes in Pairs
23. Merge K Sorted Linked Lists
24. Copy List with Random Pointer
25. Validate Binary Search Tree
26. Maximum Depth of Binary Tree
27. Minimum Depth of Binary Tree
28. Balanced Binary Tree
29. Convert Sorted Array to Balanced Binary Search Tree
30. Convert Sorted List to Balanced Binary Search Tree
31. Binary Tree Maximum Path Sum
32. Binary Tree Upside Down
33. Single Number
34. Single Number II
35. Spiral Matrix
36. Integer to Roman
37. Roman to Integer
38. Clone graph
39. Min Stack
40. Evaluate Reverse Polish Notation
41. Valid Parentheses
42. Climbing Stairs
43. Unique Paths
44. Unique Paths II
45. Maximum Sum Subarray
46. Maximum Product Subarray
47. Coins in a Line
48. Search Insert Position
49. Find Minimum in Sorted Rotated Array
50. Find Minimum in Rotated Sorted Array II – with duplicates
Sold to Jiaduo He using Selz (#8RLEKRCN)
Edition
1
LEETCODE
50 COMMON INTERVIEW QUESTIONS
Clean Code
Handbook
S
L E E T C O D E
Clean Code Handbook
2014 LeetCode
admin@leetcode.com
1
CHAPTER 0: FOREWORD ....................................................................................................................... 4
CHAPTER 1: ARRAY/STRING ............................................................................................................... 5
1. TWO SUM .................................................................................................................................................. 5
2. TWO SUM II – INPUT ARRAY IS SORTED ................................................................................................. 6
3. TWO SUM III – DATA STRUCTURE DESIGN ............................................................................................. 8
4. VALID PALINDROME .............................................................................................................................. 10
5. IMPLEMENT STRSTR() ........................................................................................................................... 11
6. REVERSE WORDS IN A STRING ............................................................................................................. 12
7. REVERSE WORDS IN A STRING II .......................................................................................................... 13
8. STRING TO INTEGER (ATOI) ................................................................................................................. 14
9. VALID NUMBER ...................................................................................................................................... 16
10. LONGEST SUBSTRING WITHOUT REPEATING CHARACTERS ........................................................... 19
11. LONGEST SUBSTRING WITH AT MOST TWO DISTINCT CHARACTERS ............................................ 21
12. MISSING RANGES ................................................................................................................................. 23
13. LONGEST PALINDROMIC SUBSTRING ................................................................................................. 24
14. ONE EDIT DISTANCE ........................................................................................................................... 27
15. READ N CHARACTERS GIVEN READ4 ................................................................................................ 29
16. READ N CHARACTERS GIVEN READ4 – CALL MULTIPLE TIMES ...................................................... 30
CHAPTER 2: MATH ............................................................................................................................... 32
17. REVERSE INTEGER .............................................................................................................................. 32
18. PLUS ONE ............................................................................................................................................. 34
19. PALINDROME NUMBER ....................................................................................................................... 35
CHAPTER 3: LINKED LIST .................................................................................................................. 37
20. MERGE TWO SORTED LISTS ............................................................................................................... 37
21. ADD TWO NUMBERS ........................................................................................................................... 38
22. SWAP NODES IN PAIRS ....................................................................................................................... 39
23. MERGE K SORTED LINKED LISTS ....................................................................................................... 40
24. COPY LIST WITH RANDOM POINTER ................................................................................................. 43
CHAPTER 4: BINARY TREE ................................................................................................................ 46
25. VALIDATE BINARY SEARCH TREE ...................................................................................................... 46
26. MAXIMUM DEPTH OF BINARY TREE ................................................................................................. 49
27. MINIMUM DEPTH OF BINARY TREE .................................................................................................. 50
28. BALANCED BINARY TREE ................................................................................................................... 52
29. CONVERT SORTED ARRAY TO BALANCED BINARY SEARCH TREE .................................................. 54
30. CONVERT SORTED LIST TO BALANCED BINARY SEARCH TREE ....................................................... 56
31. BINARY TREE MAXIMUM PATH SUM ................................................................................................. 58
32. BINARY TREE UPSIDE DOWN ............................................................................................................. 60
CHAPTER 5: BIT MANIPULATION ................................................................................................... 62
33. SINGLE NUMBER .................................................................................................................................. 62
34. SINGLE NUMBER II .............................................................................................................................. 64
CHAPTER 6: MISC .................................................................................................................................. 66
2
35. SPIRAL MATRIX ................................................................................................................................... 66
36. INTEGER TO ROMAN ........................................................................................................................... 68
37. ROMAN TO INTEGER ........................................................................................................................... 70
38. CLONE GRAPH ...................................................................................................................................... 72
CHAPTER 7: STACK .............................................................................................................................. 74
39. MIN STACK .......................................................................................................................................... 74
40. EVALUATE REVERSE POLISH NOTATION .......................................................................................... 76
41. VALID PARENTHESES .......................................................................................................................... 80
CHAPTER 8: DYNAMIC PROGRAMMING ........................................................................................ 81
42. CLIMBING STAIRS ................................................................................................................................ 81
43. UNIQUE PATHS .................................................................................................................................... 83
44. UNIQUE PATHS II ................................................................................................................................ 86
45. MAXIMUM SUM SUBARRAY ................................................................................................................ 87
46. MAXIMUM PRODUCT SUBARRAY ....................................................................................................... 89
47. COINS IN A LINE ................................................................................................................................... 90
CHAPTER 9: BINARY SEARCH ........................................................................................................... 95
48. SEARCH INSERT POSITION ................................................................................................................. 95
49. FIND MINIMUM IN SORTED ROTATED ARRAY .................................................................................. 97
50. FIND MINIMUM IN ROTATED SORTED ARRAY II – WITH DUPLICATES ........................................... 99
3
Chapter 0: Foreword
Hi, fellow LeetCoders:
First, I would like to express thank you for buying this eBook: “Clean Code Handbook:
50 Common Interview Questions”. As the title suggested, this is the definitive guide to
write clean and concise code for interview questions. You will learn how to write clean
code. Then, you will ace the coding interviews.
This eBook is written to serve as the perfect companion for LeetCode Online Judge (OJ).
Each problem has a “Code it now” link that redirects to the OJ problem statement page.
You can write the code and submit it to the OJ system, which you will get immediate
feedback on whether your solution is correct. If the “Code it now” link says “Coming
soon”, it means the problem will be added very soon in the future, so stay tuned.
On the top right side of each problem are the Difficulty and Frequency ratings. There are
three levels of difficulty: Easy, Medium, and Hard. Easy problems are problems that are
easy to come up with ideas and the implementation should be pretty straightforward.
Most interview questions fall into this level of difficulty.
On the other end, there are hard problems. Hard problems are usually algorithmic in
nature and require more thoughts beforehand. There could be some coding questions that
fall into Hard, but that is rare.
There are three frequency rating: Low, Medium, and High. The frequency of a problem
being asked in a real interview is based on data collected from the user survey: “Have you
met this question in a real interview?” This should give you an idea of what kind of
questions is currently being asked in real interviews.
Each question may contain a section called “Example Questions Candidate Might Ask”.
These are examples of good questions to ask your interviewer. Asking clarifying
questions is important and is a good chance to demonstrate your thought process.
Each question is accompanied with as many approaches as possible. Each approach
begins with a runtime and space complexity summary so you can quickly compare
between different approaches. The analysis of the runtime and space complexity is
usually provided along with the solution. Analyzing complexity is frequently being asked
in a technical interview, so you should definitely prepare for it.
You learn best when you solve a problem by yourself. If you get stuck, there are usually
hints in the book to help you. If you are still stuck, read the analysis and try to write the
code yourself in the Online Judge
Even though you might think a problem is easy, writing code that is concise and clean is
not as easy as most people think. For example, if you are writing more than 30 lines of
code during a coding interview, your code is probably not concise enough. Most code in
this eBook fall between 20 — 30 lines of code.
1337c0d3r
4
Chapter 1: Array/String
1. Two Sum
Code it now: https://oj.leetcode.com/problems/two-sum/
Difficulty: Easy, Frequency: High
Question:
Given an array of integers, find two numbers such that they add up to a specific target
number.
The function twoSum should return indices of the two numbers such that they add up to
the target, where index1 must be less than index2. Please note that your returned answers
(both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Solution:
O(n2) runtime, O(1) space – Brute force:
The brute force approach is simple. Loop through each element x and find if there is
another value that equals to target – x. As finding another value requires looping through
the rest of array, its runtime complexity is O(n2).
O(n) runtime, O(n) space – Hash table:
We could reduce the runtime complexity of looking up a value to O(1) using a hash map
that maps a value to its index.
public int[] twoSum(int[] numbers, int target) {
Map map = new HashMap<>();
for (int i = 0; i < numbers.length; i++) {
int x = numbers[i];
if (map.containsKey(target - x)) {
return new int[] { map.get(target - x) + 1, i + 1 };
}
map.put(x, i);
}
throw new IllegalArgumentException("No two sum solution");
}
Follow up:
What if the given input is already sorted in ascending order? See Question [2. Two Sum
II – Input array is sorted].
5
2. Two Sum II – Input array is sorted
Code it now: Coming soon!
Difficulty: Medium, Frequency: N/A
Question:
Similar to Question [1. Two Sum], except that the input array is already sorted in
ascending order.
Solution:
Of course we could still apply the [Hash table] approach, but it costs us O(n) extra space,
plus it does not make use of the fact that the input is already sorted.
O(n log n) runtime, O(1) space – Binary search:
For each element x, we could look up if target – x exists in O(log n) time by applying
binary search over the sorted array. Total runtime complexity is O(n log n).
public int[] twoSum(int[] numbers, int target) {
// Assume input is already sorted.
for (int i = 0; i < numbers.length; i++) {
int j = bsearch(numbers, target - numbers[i], i + 1);
if (j != -1) {
return new int[] { i + 1, j + 1 };
}
}
throw new IllegalArgumentException("No two sum solution");
}
private int bsearch(int[] A, int key, int start) {
int L = start, R = A.length - 1;
while (L < R) {
int M = (L + R) / 2;
if (A[M] < key) {
L = M + 1;
} else {
R = M;
}
}
return (L == R && A[L] == key) ? L : -1;
}
O(n) runtime, O(1) space – Two pointers:
Let’s assume we have two indices pointing to the ith and jth elements, Ai and Aj
respectively. The sum of Ai and Aj could only fall into one of these three possibilities:
i.
ii.
Ai + Aj > target. Increasing i isn’t going to help us, as it makes the sum even
bigger. Therefore we should decrement j.
Ai + Aj < target. Decreasing j isn’t going to help us, as it makes the sum even
smaller. Therefore we should increment i.
iii.
Ai + Aj == target. We have found the answer.
6
public int[] twoSum(int[] numbers, int target) {
// Assume input is already sorted.
int i = 0, j = numbers.length - 1;
while (i < j) {
int sum = numbers[i] + numbers[j];
if (sum < target) {
i++;
} else if (sum > target) {
j--;
} else {
return new int[] { i + 1, j + 1 };
}
}
throw new IllegalArgumentException("No two sum solution");
}
7
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
