一. 写在开头

读研找工作都离不开，如今已到春招，决定最近开个解析leetcode高频经典题的坑
近年来leetcode题库暴增，算法题已经达到961题，全部刷完对于一般人来说既不现实，效率也不高
看到网上又大神贴出的经典高频题，现将题目序号附上，再慢慢填坑解析，也算做个总结

二. 高频题

取自Lnho大神总结的高频题，原文：https://blog.csdn.net/lnho2015/article/details/50962989

刷题顺序：
出现频度为5：

1. Leet Code OJ 1. Two Sum [Difficulty: Easy]
2. Leet Code OJ 8. String to Integer (atoi) [Difficulty: Easy]
3. Leet Code OJ 15. 3Sum [Difficulty: Medium]
4. Leet Code OJ 20. Valid Parentheses [Difficulty: Easy]
5. Leet Code OJ 21. Merge Two Sorted Lists [Difficulty: Easy]
6. Leet Code OJ 28. Implement strStr() [Difficulty: Easy]
7. Leet Code OJ 56. Merge Intervals [Difficulty: Hard]
8. Leet Code OJ 57. Insert Interval [Difficulty: Hard]
9. Leet Code OJ 65. Valid Number [Difficulty: Hard]
10. Leet Code OJ 70. Climbing Stairs [Difficulty: Easy]
11. Leet Code OJ 73. Set Matrix Zeroes [Difficulty: Medium]
12. Leet Code OJ 88. Merge Sorted Array [Difficulty: Easy]
13. Leet Code OJ 98. Validate Binary Search Tree [Difficulty: Medium]
14. Leet Code OJ 125. Valid Palindrome [Difficulty: Easy]
15. Leet Code OJ 127. Word Ladder [Difficulty: Medium]

出现频度为4：

1. Leet Code OJ 2. Add Two Numbers [Difficulty: Medium]
2. Leet Code OJ 12. Integer to Roman
3. Leet Code OJ 13. Roman to Integer
4. Leet Code OJ 22. Generate Parentheses
5. Leet Code OJ 23. Merge k Sorted Lists
6. Leet Code OJ 24. Swap Nodes in Pairs
7. Leet Code OJ 27. Remove Element [Difficulty: Easy]
8. Leet Code OJ 46. Permutations
9. Leet Code OJ 49. Anagrams
10. Leet Code OJ 67. Add Binary
11. Leet Code OJ 69. Sqrt(x)
12. Leet Code OJ 77. Combinations
13. Leet Code OJ 78. Subsets
14. Leet Code OJ 79. Word Search
15. Leet Code OJ 91. Decode Ways [Difficulty: Medium]
16. Leet Code OJ 102. Binary Tree Level Order Traversal [Difficulty: Easy]
17. Leet Code OJ 129. Sum Root to Leaf Numbers
18. Leet Code OJ 131. Palindrome Partitioning

三. 题解

1. Two Sum [Difficulty: Easy

https://leetcode.com/problems/two-sum/

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in nums:
if target - i in nums:
return [nums.index(i), nums.index(target - i)]

15. 3Sum [Difficulty: Medium]

https://leetcode.com/problems/3sum/
很好很经典的一个题目，同样有很多变种
3SumClosest https://leetcode.com/problems/3sum-closest/
4Sum https://leetcode.com/problems/4sum/

class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
"""
lenth = len(nums)
nums.sort()
Sum = []
path = {}
for i in range(lenth):
for j in range(i+1, lenth):
a = -(nums[i] + nums[j])
if a in nums:
temp = sorted([nums[i] , nums[j], a])
if temp not in Sum:
Sum.append(temp)
return Sum
"""
# 用到了动态规划，节省了时间
if len(nums) <3: # deal with special input
return []
elif len(nums) == 3:
if sum(nums) == 0:
return [sorted(nums)]
nums = sorted(nums) # sorted, O(nlgn)
ans = []
for i in range(len(nums) -2):
j = i+1
k = len(nums) -1 # hence i < j < k
while j<k: # if not cross line
temp_sum = nums[i] + nums[j] + nums[k]
if temp_sum == 0:
ans.append((nums[i], nums[j], nums[k]))
if temp_sum > 0: # which means we need smaller sum, move k backward, remember we sort the array
k -= 1
else:
j += 1
return list(set(tuple(ans))) # I bet this is not the best way to eliminate duplicate solutions

20. Valid Parentheses [Difficulty: Easy]

class Solution:
def isValid(self, s: str) -> bool:
if s == "":
return True
left = ['(', '{', '[']
right = {')':'(', '}':'{', ']':'['}
stack = []
for i in s:
if i in left:
stack.append(i)
else:
if stack == [] or right[i] != stack.pop():
return False
if stack == []:
return True
else:
return False

56. Merge Intervals [Difficulty: Medium]

[https://leetcode.com/problems/merge-intervals/]

Given a collection of intervals, merge all overlapping intervals.
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

先用sorted函数对list按照start值来进行排序，用res保存输出结果，对于list中每个元素，比较i.start与res[-1].end的大小，如果小于等于就说明有重叠，将res[-1].end更行为i.end与自身的最大值。若大于这说明没有重叠，res加入i。

# Definition for an interval.
# class Interval:
#
def __init__(self, s=0, e=0):
#
self.start = s
#
self.end = e
# 学会使用lambda，给元素先进行排序
class Solution:
def merge(self, intervals: List[Interval]) -> List[Interval]:
if len(intervals) == 0: return []
intervals = sorted(intervals, key = lambda x: x.start)
res = [intervals[0]]
for i in intervals[1:]:
# 如果i的起点小于res[-1]的终点，res[-1]的终点取i终点和自身的最大值
if i.start <= res[-1].end :
res[-1].end = max(res[-1].end, i.end)
else:
res.append(i)
return res

57. Insert Interval [Difficulty: Hard]

https://leetcode.com/problems/insert-interval/

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

上一题的升级版，只是要先判断一下新区间该插入哪，然后再判断是否overlap。只要加入这一段代码即可

if intervals == []:
return [newInterval]
#if the newInterval.end less than the first ele.start of intervals
intervals.append(newInterval)
intervals = sorted(intervals, key = lambda x: x.start)
res = [intervals[0]]

Set Matrix Zeroes [Difficulty: Medium]

https://leetcode.com/problems/set-matrix-zeroes/

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Example 1: Input:
[
[1,1,1],
[1,0,1],
[1,1,1] ]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1] ]

题目要求使用in-place，因此不能创建一个新的矩阵来替换原先矩阵。创建两个列表来保存出现0的位置的坐标，
然后对于rows和cols中的序号，对对应的行和列进行置零处理。

class Solution:
# an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. 
However a small amount of extra storage space is allowed for auxiliary variables.
# 原地算法不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入的一种算法操作
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
rows = []
cols = []
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 0:
rows += [i]
cols += [j]
for i in rows:
matrix[i] = [0] * (len(matrix[0]))
for j in cols:
for i in range(len(matrix)):
matrix[i][j] = 0

98. Validate Binary Search Tree[Medium]

https://leetcode.com/problems/validate-binary-search-tree/

判断一个树是不是二叉搜索树，特征就是中序遍历得到的数列一定是递增的。很简单

# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, x):
#
self.val = x
#
self.left = None
#
self.right = None
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
if root == None:
return True
# 中序遍历 二叉搜索树
tree = []
self.inOrder(root, tree)
if len(tree) == 1:
return True
for i in range(len(tree)-1):
if tree[i] >= tree[i+1]:
return False
return True
def inOrder(self, root, tree):
if root == None:
return
if root.left:
self.inOrder(root.left, tree)
tree.append(root.val)
if root.right:
self.inOrder(root.right, tree)

125. Valid Palindrome [Easy]

https://leetcode.com/problems/valid-palindrome/
很简单，只是要用到 ele.,isalnum() 函数，ele是数字或者字母就返回1

class Solution:
def isPalindrome(self, s: str) -> bool:
if s == "":
return True
pali = []
for i in s:
if i.isalnum():
pali.append(i.lower())
if pali == pali[::-1]:
return True
else:
return False

127. Word Ladder [Difficulty: Medium]

https://leetcode.com/problems/word-ladder/
Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord

Input:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]

Output: 5
Explanation: As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
return its length 5.

22. Generate Parentheses [Medium]

https://leetcode.com/problems/generate-parentheses/

For example, given n = 3, a solution set is:
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

这种方法是我自己想出来的，代码略多。也是一种深度优先的策略。
将 left,right,path,res参数传入formParen函数，path是当前已经形成的字符串，在每一层函数中被加工以后穿入下一层，同时把res一层层传下去，直到要添加的括号数量满足的时候(if left == 0 and right == 0 或者 left == 0)，把当前已经形成的path传入res。

class Solution:
def generateParenthesis(self, n: int) -> List[str]:
"""
:type n: int
:rtype: List[str]
"""
res = []
left = n
right = n
path = ''
self.formParen(left,right,path,res)
return res
def formParen(self,left,right,path,res): #left right表示剩余要加入的左右括号
if left == 0 and right == 0:
res.append(path)
elif left == 0:
res.append(path+')'*right)
elif right == left: #表示已添加的左右括号数量相同，只能加左括号了
self.formParen(left-1,right,path+'(',res)
else:
self.formParen(left-1,right,path+'(',res)
self.formParen(left,right-1,path+')',res)

贴个短的

class Solution:
def generateParenthesis(self, n: int) -> List[str]:
return self.dfs(n, n, "", [])
def dfs(self, l, r, s, res):
if l:
self.dfs(l-1, r, s + "(", res)
if r and l < r:
# l < r is important. 
self.dfs(l, r-1, s + ")", res)
if not r:
res.append(s)
return res

23. Merge k Sorted Lists [Hard]

https://leetcode.com/problems/merge-k-sorted-lists/
没什么好说的，就是给几个排好序的列表Lists，用分治解决：将所有序列先两两合并，再把这些序列再两两合并……直到只剩一个序列。其他的和合并列表操作一样。

# Definition for singly-linked list.
# class ListNode:
#
def __init__(self, x):
#
self.val = x
#
self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
# 用分治的思想，在第一层循环内，嵌套一个循环，这个循环把链表按照两个链表合并的思想 来合并
if not lists:
return None
sentinel = ListNode(0) #as the head node
while len(lists) > 1:
mergeList = []
while len(lists) > 1:
mergeList.append(self.mergeTwo(lists.pop(), lists.pop(),sentinel))
lists += mergeList
return lists[0]
def mergeTwo(self, list1, list2, head):
cur = head
while list1 and list2:
if list1.val < list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
cur.next = list1 if list1 else list2
return head.next

24. Swap Nodes in Pairs [Medium]

https://leetcode.com/problems/swap-nodes-in-pairs/
主要是指针的问题要搞清楚，就没问题了。
[0 -> 1 -> 2 - > 3 -> 4]，if we want to swap 1 and 2，cur to 1, cur.next to 2, cur.next.next to 3, firstly, set “temp” to 3, namely ‘temp = cur.next.next’, then the’ cur.next.next = cur’, if the cur have a father node, we should make it point to the cur.next, finally, the cur.next to the temp, namely 1 -> 3, 1.next point to which the temp point to.
用英文打不用不停切换输入 : ) haa

temp = cur.next.next
if father:
father.next = cur.next
cur.next.next = cur
cur.next = temp
father = cur
cur = cur.next

# Definition for singly-linked list.
# class ListNode:
#
def __init__(self, x):
#
self.val = x
#
self.next = None
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if not head:
return None
if head.next == None:
return head
father = None
cur = head
newHead = head.next
#从第三个开始，要代入父节点否则会有指针内容丢失
while cur and cur.next: # 0->(0 is the father)1->2->3
temp->3
2->1
1->(temp->)3
temp = cur.next.next
if father:
father.next = cur.next
cur.next.next = cur
cur.next = temp
father = cur
cur = cur.next
return newHead

46. Permutations [Medium]

https://leetcode.com/problems/permutations/

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

mege(befor, after):
new = before + after
output = []
for i in range(len(new)):
for j in self.merge(new[:i], new[i+1:]):
output.append([new[i]] + j)

拿1举例子， 第一次生成了[ [1] ]，然后生成两位[ [1, 2] , [1, 3] ]，然后生成三位，分治思想，用递归来解决。
从上一轮中得到的除去了一个字符的新序列组成 new 序列。第一个循环，分别取出new里面的一个字符，然后第二个循环中，挨个把剩余的元素加入这个new[i]。
公式是 f(n) = f(1) + f(n-1)，f表示取出x个元素进行排列的可能结果，边界条件是当传下来的new只有一个元素的时候，返回[new]，表示只有一种情况。

# 2019/3/19 实现了分治思想 divide and conquer!
# 
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = self.merge([], nums)
return res
def merge(self, before, after):
new = before + after
if len(new) == None:
return []
if len(new) == 1:
return [new]
output = []
for i in range(len(new)):
for j in self.merge(new[:i], new[i+1:]):
output.append([new[i]] + j)
return output

49.Group Anagrams [Medium]

Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Output:
[
[“ate”,“eat”,“tea”],
[“nat”,“tan”],
[“bat”]
]

整个拥有相同字母的单词，这里面涉及一个知识点，dic的键值不可以是list，但是可以是tuple，此外，string可以使用sorted方法进行排序，得到一个list。

class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
mydic = {}
res = []
for item in strs:
# 字典索引不能为list但是可以是tuple
item_ele = tuple(sorted(item))
if item_ele not in mydic:
mydic[item_ele] = [item]
else:
mydic[item_ele].append(item)
for key in mydic:
res.append(mydic[key])
return res

Leet Code OJ 67. Add Binary
Leet Code OJ 69. Sqrt(x)

77. Combinations [Medium]

https://leetcode.com/problems/combinations/
permutation的升级版，能通过k控制组合的数字数目

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

class Solution:
# 和Permutations有点像.
'''def combine(self, n: int, k: int) -> List[List[int]]:
res = []
path = []
self.dfs(list(range(1, n+1)), k, 0, path, res)
return res
def dfs(self, nums, k, index, path, res):
if k == 0:
res.append(path)
return #回溯。
for i in nums:
# 每次index加一，表示可用的数字减少一个，按照从头到尾的顺序减少。k控制最后生成的序列元素长度，每次path增加一个元素
self.dfs(nums[index+1:], k-1, i+1, path+[i], res)'''
def combine(self, n, k):
res = []
self.dfs(range(1,n+1), k, 0, [], res)
return res
def dfs(self, nums, k, index, path, res):
#if k < 0:
#backtracking
#return 
if k == 0:
res.append(path)
return # backtracking 
for i in range(index, len(nums)):
self.dfs(nums, k-1, i+1, path+[nums[i]], res)

78. Subsets [Medium]

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

可以动态更新result的值，如果用for循环就会报错，因为在for循环里的变量不能变更
for i in result: result += i + [num]（错误）
result += [i + [num] for i in result] （正确）

class Solution:
def subsets(self, nums):
nums.sort()
result = [[]]
for num in nums:
result += [i + [num] for i in result]
return result

79. Word Search [Medium]

91. Decode Ways [Difficulty: Medium]

第一种动态规划的方法，无奈时间复杂度太高，被毙了

#不用开dic，'123' 直接拆分成几个组合比如[1,2,3][12,3][1,23]，元素只有两位且介于1~26 
if s == '' or s[0] == '0':
return 0 #能分出单个'0'的那一种情况直接去掉
if len(s) == 1:
return 1
if len(s) == 2:
if s[1] == '0':
if s == '10' or s == '20':
return 1
else:
return 0
elif s[0] == '0' or int(s) > 26 :
return 1
else:
return 2
num = self.judge(s[0]) * self.numDecodings(s[1:]) + self.judge(s[0:2]) * self.numDecodings(s[2:])
return num
def judge(self, s):
if s[0] == '0' or int(s) > 26:
return 0
elif s == '10' or s == '20':
return 1
else:
return 1
'''

class Solution:
def numDecodings(self, s: str) -> int
# 不用递归 可以把字符串从第一位看起，当做每次加入一个新的字符，然后看增加了多少种可能性（0种或一种），比如123，先看1，然后看12，在看12加入3 以后，多了一种23 和2 3 的可能
if s[0] == '0':
return 0
if len(s) == 1:
return 1
dp = [0] * len(s)
dp[0] = 1
if s[1] == '0':
if s[0] > '2':
return 0
else:
dp[1] = 1
else:
if s[0:2] >= '11' and s[0:2] <= '26':
dp[1] = 2
else:
dp[1] = 1
for i in range(2, len(s)):
if s[i-1] > '2' and s[i] == '0':
return 0
if s[i] >= '1' and s[i] <= '9':
dp[i] = dp[i-1]
if s[i-1:i+1] >='10' and s[i-1:i+1] <= '26':
dp[i] += dp[i-2]
return dp[-1]

102. Binary Tree Level Order Traversal [Difficulty: Easy]

层序遍历而已

129. Sum Root to Leaf Numbers [easy]

又是层序遍历

131. Palindrome Partitioning

又是回溯法。

class Solution:
def partition(self, s):
res = []
self.dfs(s, [], res)
return res
def dfs(self, s, path, res):
if not s:
res.append(path)
return
for i in range(1, len(s)+1):
if self.isPal(s[:i]):
self.dfs(s[i:], path+[s[:i]], res)
def isPal(self, s):
return s == s[::-1]

最后

以上就是诚心钥匙为你收集整理的leetcode高频面试题一. 写在开头二. 高频题三. 题解的全部内容，希望文章能够帮你解决leetcode高频面试题一. 写在开头二. 高频题三. 题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。