1. 二叉树的最大深度

给定一个二叉树,找到最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数

说明:叶子节点是指没有子节点的节点

1
2
3
4
5
6
7
8
9
给定二叉树 [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7

返回最大深度为 3

实现思路
二叉树的最大深度就是二叉树的高度,一般有两种解法,一种是递归,一种是循环遍历,记录每层的节点数,遍历完一层,层数计数器加一。

代码实现

  1. 递归实现
1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root == None:
return 0
else:
left_depth = self.maxDepth(root.left)
left_depth = self.maxDepth(root.right)
return max(left_depth, left_depth)+1
  1. 循环实现
    通过记录本层元素的总和,本层已经访问过的元素,层数技术器来获取二叉树的高度,此种方法也可以获取二叉树的最大宽度。
1
2
3
4
5

class Solution(object):
def maxDepth(self, root):
if root is None:
return 0

2. 验证二叉搜索树

给定一个二叉树,判断其是否是一个有效的二叉树

假设一个二叉搜做索树具有以下特征:

  • 节点的左子树只包含小于当前节点的数
  • 节点的右子树只包含大于当前节点的数
  • 所有左子树和右子树自身必须也是二叉搜索树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入:
2
/ \
1 3
输出: true

输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ,但是其右子节点值为 4 。

实现思路
利用中根序遍历,遍历之后的数组是有序的返回True否则为False

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root ==None:
return True
### 利用中序遍历是递增的这一特点,用stack来中序遍历
result=[]
stack=[]
visited=set()
stack.append(root)
while stack!=[]:
node=stack.pop(-1)##
if not node in visited:
if node.right:
stack.append(node.right)
stack.append(node)
if node.left:
stack.append(node.left)
visited.add(node)
else:
if result==[]:
result.append(node.val)
else:
if result[-1]<node.val:
result.append(node.val)
else:
return False
return True

class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root == None:
return True
else:
res = []
self.middle_digui(root, res)
for i in range(len(res)-1):
if res[i]>=res[i+1]:
return False
return True

def middle_digui(self,root,res):
if root == None:
return
self.middle_digui(root.left,res)
res.append(root.val)
self.middle_digui(root.right,res)

3. 对称二叉树

给定一棵二叉树,检查它是否是镜像对称的。
比如:二叉树[1,2,2,3,4,4,3]是对称的。

1
2
3
4
5
    1
/ \
2 2
/ \ / \
3 4 4 3

但是[1,2,2,null,3,null,3]则不是对称的。

1
2
3
4
5
  1
/ \
2 2
\ \
3 3

实现思路
将根树进行拆分遍历,左子树的右节点要与右子树的左节点相等

  1. 递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def isSymmetric(self, root):
def check(p, q):
if p is None and q is None:
return True
if p is None or q is None:
return False
if p.val != q.val:
return False
if p.val == q.val:
return check(p.left, q.right) and check(p.right, q.left)

if root is None:
return True
return check(root.left, root.right)
  1. 非递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def isSymmetric(self, root):
if root is None:
return True

stack = []
stack.append(root.left)
stack.append(root.right)
while len(stack) != 0:
left_n, right_n = stack.pop(), stack.pop()
if left_n is None and right_n is None:
continue
if left_n is None or right_n is None or left_n.val != right_n.val:
return False
stack.append(left_n.left)
stack.append(right_n.right)
stack.append(left_n.right)
stack.append(right_n.left)
return True

4. 二叉树的层次遍历

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

例如:
给定二叉树: [3,9,20,null,null,15,7]

1
2
3
4
5
6
7
8
9
10
11
12
 3
/ \
9 20
/ \
15 7
返回其层次遍历结果:

[
[3],
[9,20],
[15,7]
]

实现思路
利用队列进行实现,由于输出的关系,因此还需要统计一下层数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
que = [root]
if root is None:
return res
while que:
temp = []
for i in range(len(que)):
node = que.pop(0)
temp.append(node.val)
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
res.append(temp)
return res

5. 将有序数组转换成二叉树

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

1
2
3
4
5
6
7
8
9
给定有序数组: [-10,-3,0,5,9],

一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

0
/ \
-3 9
/ /
-10 5

实现思路
因为给定的数组是按照升序排列的,所以可以先取出数组中间位置的值作为二叉查找树的根结点,然后以该数组中间位置的值为中心,将左边的数组划分到根结点的左子树中,右边的数组划分到根结点的右子树中,这样就能保证根结点的左子树上任意结点的值都小于根结点的值,右子树上任意结点的值大于根节点的值。接下来,可以使用递归地方法继续取出左边数组的中间值作为根结点的左子结点,右边数组的中间值作为根结点的右子结点,然后以左边数组中间值为中心,再次划分左右子树,右边数组同理,如此递归下去,对于每个结点,总是能保证其左子树上任意结点的值都要小于该节点的值,其右子树上任意结点的值都要大于该节点的值

代码实现

1
2
3
4
5
6
7
8
9
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root

6. 合并两个有序数组

给定两个有序整数数组nums1和nums2,将nums2合并到nums1中,使得nums1成为一个有序数组。

说明:

  • 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
  • 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
1
2
3
4
5
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]
  1. Pythonic 求解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    """
    Do not return anything, modify nums1 in-place instead.
    """
    if not nums1:
    return nums2
    if not nums2:
    return nums1
    nums1[m:m+n] = nums2
    nums1.sort()
  2. 混合插入求解
    混合插入数组,由于两个数组都是有序的,所以只要按照顺序比较大小即可,题中给出两个数组的大小m和n,这样可以知道混合之后数组的大小,这样只需要从nums1和nums2数组的末尾开始一个一个比较。

  • 比较nums1和nums2中最后的两个元素,把最大的插入到第m+n位
  • 改变数组的索引,再次进行上面的比较,把最大的元素插入到nums1的第m+n-1位
  • 循环一直到结束,循环结束条件:当index1或者index2有一个小于0时,此时就可以结束循环了。如果index2小于0,说明目的达到了,如果index1小于0,就吧nums2中剩余的元素都复制到nums1中去即可。

*输入特殊情况:

  • 当nums1为空,nums2不为空时,将nums2的所有元素添加到nums1中即可
  • 当nums1不为空,nums2时,直接结束循环,直接返回nums1
  • 当nums1和nums2均为空的时候,返回空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class SolutionL:
def merge(self, nums1, m, nums2, n):
index1, index2 = m - 1, n - 1
# nums1的长度为 m+n
while index2 >= 0:
if index1 < 0:
nums1[0:index2+1] = nums2[0:index2+1]
break

if nums1[index1] >= nums2[index2]:
nums1[index1 + index2 + 1] = nums1[index1]
index1 -= 1
else:
nums1[index1 + index2 + 1] = nums2[index2]
index2 -= 1

7. 第一个错误的版本

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用bool isBadVersion(version)接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

1
2
3
4
5
6
7
给定 n = 5,并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以,4 是第一个错误的版本。

实现思路
二分查找

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
left = 1
right = n
while left <= right:
mid = (left + right) // 2
guess_cur = isBadVersion(mid)
guess_pre = isBadVersion(mid - 1)
if guess_cur is True and guess_pre is False:
return mid
if guess_cur is True and guess_pre is True:
right = mid - 1
if guess_cur is False and guess_pre is False:
left = mid + 1
return None

class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
left, right = 1, n
while left <= right:
mid = (left + right) // 2
if not isBadVersion(mid):
left = mid + 1
else:
right = mid - 1
return left

动态规划题目

8. 买股票的最佳时机 I

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

1
2
3
4
5
6
7
8
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

实现思路

第一种思路:
线性扫描,如果最右侧的最大元素减去当前元素的值大于当前的profit,就报profit刷新。
缺点:时间复杂度很大,速度慢

1
2
3
4
5
6
7
8
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(len(prices) - 1):
cur_profit = max(prices[i+1:]) - prices[i]
if cur_profit > profit:
profit = cur_profit
return profit

第二种思路:
动态规划
我们可以维护一个min变量,记录遍历到元素i以前的最小数值,该数值作为买入,这样当我们遍历计算nums[i]-min的值时,可以保证在该处卖出时所付出的成本总是最低的。于是我们就只要维护min以及取nums[i]-min的最大值即可

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
profit , min_elem = 0, prices[0]
for i in range(len(prices)):
if prices[i] < min_elem:
min_elem = prices[i]
if profit < prices[i] - min_elem:
profit = prices[i] - min_elem
return profit

9. 最大子序和

给定一个完整的数组 nums,找到一个具有最大和的连续子序和(子数组最小包含一个元素),返回其最大和。

1
2
3
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

进阶:
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

实现思路

第一种思路:
扫描法(O(n)) 或动态规划法
当我们加上一个正数的时候,和会增加;当我们加上一个负数的时候,和会减少。如果当前的和是一个负数那么在接下来的累加过程中应该抛弃或者清零,不然的话这个负数将会减少接下来的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
cur = nums[0]
res = nums[0]
for i in range(1, len(nums)):
if cur < 0:
# 当前的元素小于0,会对后续的结果有影响,舍去, 继续下一个元素
cur = nums[i]
else:
# 如果不小于零,那么将会对接下来的结果有积极的影响
cur += nums[i]
if cur > res:
# 这里实现了负数返回最大也实现了扫描法
res = cur
return res

第二种思路:
分治法
最大子序和要不在左半部分,要不在右半部分,或者横跨两个部分(及包括左半部分和右半部分)。返回这三种情况的最大值即可。第三种情况,其中包含左半部分最后一个元素的情形,需要挨个往前遍历,更新最大值,包含右半部分的第一个元素的情况类似,时间复杂度为O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
def maxSubArray(self, nums):
left = 0
right = len(nums)-1
maxSum = self.divide(nums,left,right)
return maxSum

def divide(self,nums,left,right):
if left==right:
return nums[left]
center = (left+right)/2
leftMaxSum = self.divide(nums,left,center)
rightMaxSum = self.divide(nums,center+1,right)
leftBorderSum = nums[center]
leftSum = nums[center]
for i in range(center-1,left-1,-1):
leftSum += nums[i]
if leftSum>leftBorderSum:
leftBorderSum = leftSum
rightBorderSum = nums[center+1]
rightSum = nums[center+1]
for i in range(center+2,right+1):
rightSum += nums[i]
if rightSum>rightBorderSum:
rightBorderSum = rightSum
BorderSum = leftBorderSum + rightBorderSum
return max(leftMaxSum,rightMaxSum,BorderSum)

10. 打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

1
2
3
4
5
6
7
8
9
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

实现思路
如果只有两家或者以下,我们选择金额最大的,如果两家以上,那我们打劫到第i家的时候,就需要考虑要不要打劫这一家,也就是(这一家的价值加上i-2家的最大价值)和打劫到上一家i-1的最大价值,比较这两个值,选择最大值作为作为打劫到第i家的最大价值,然后输出最后一家即可。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return 0 if n == 0 else nums[0]
pre = nums[0] # 上次的最大收益
cur = max(nums[0], nums[1]) # 当前的最大收益
for i in range(2, n):
# 当前的最大收益是两种选择中最大那个
pre, cur = cur, max(pre + nums[i], cur)
return cur