目录
  1. 1. 日常警醒
  2. 2. 剑指offer03-数组中重复的数字
    1. 2.1. 题目
    2. 2.2. 题解
  3. 3. 剑指offer07-重建二叉树
    1. 3.1. 题目
    2. 3.2. 题解
每日一刷1

日常警醒

菜就要刷题,不要偷懒!

剑指offer03-数组中重复的数字

题目

  • 难度:简单

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字

示例1:

输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3

限制:2 <= n <= 100000

题解

1.使用额外空间,不修改数组。

  • 用字典记录遍历过的数字
  • 如果当前数字在字典中,说明重复,返回这个数字
  • 如果当前数字不在字典中,记录字典中
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
def findRepeatNumber(nums):

dict = {}
for num in nums:
if num in dict:
return num
dict[num] = 1

return None

if __name__ == '__main__':
arr = [2, 3, 1, 0, 2, 5, 3]
print(findRepeatNumber(arr))

2.对数组排序,修改数组。

  • 先对数组排序,然后遍历一遍数组,比较相邻两个数字是否相等,相等就返回,不相等就继续遍历。
  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(n)
def findRepeatNumber(nums):

nums.sort()
for i in range(len(nums) - 1):
if nums[i] == nums[i + 1]:
return nums[i]
i += 1
return None

if __name__ == '__main__':
arr = [2, 3, 1, 0, 2, 5, 3]
print(findRepeatNumber(arr))
  • 自己写快排(递归)
def partition(arr, low, high):

i = low - 1
pivot = arr[high]

for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]

arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1

def quicksort(arr, low, high):

if low < high:
pi = partition(arr, low, high)
quicksort(arr, low, pi - 1)
quicksort(arr, pi + 1, high)

return arr

def findRepeatNumber(nums):

quicksort(nums, 0, len(nums) - 1)

for i in range(len(nums) - 1):
if nums[i] == nums[i + 1]:
return nums[i]
i += 1

return None

if __name__ == '__main__':
arr = [2, 3, 1, 0, 2, 5, 3]
print(quicksort(arr, 0, len(arr) - 1))
print(findRepeatNumber(arr))

3.原地修改数组

  • 数组的数字范围和数组下标一一对应,可以把数组当做哈希表
  • 因此,看到数字就知道放在数组的哪个位置,就像编写哈希函数,找重复数字就是发生了哈希表冲突
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
def findRepeatNumber(nums):

i = 0

while i < len(nums):
#数字等于下标
if nums[i] == i:
i += 1
continue
#数字等于数字
if nums[nums[i]] == nums[i]:
return nums[i]
nums[nums[i]], nums[i] = nums[i], nums[nums[i]]

return None

if __name__ == '__main__':
arr = [2, 3, 1, 0, 2, 5, 3]
print(findRepeatNumber(arr))
  • 找出所有重复的数字
def findRepeatNumber(nums):

dict = {}

for num in nums:
if num in dict:
dict[num] += 1
else:
dict[num] = 1
return [k for k, v in dict.items() if v >= 2]

if __name__ == '__main__':
arr = [2, 3, 1, 0, 2, 5, 3]
print(findRepeatNumber(arr))

剑指offer07-重建二叉树

题目

  • 难度:中等

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如,列出:

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

3
/ \
9 20
/ \
15 7

限制:0 <= 节点个数 <= 5000

题解

  • 前序遍历->根、左节点、右节点
  • 中序遍历->左节点、根、右节点
  • 根据前序遍历和中序遍历,划分左子树、根节点、右子树的区间,然后递归构造二叉树
  • 特例:前序遍历为空或中序遍历为空或节点个数<=0,返回None(前序和中序不匹配)
  • 构造根节点:前序遍历第一个元素
  • 确定左子树在前序遍历和中序遍历的区间
  • 确定右子树在前序遍历和中序遍历的区间
  • 递归构建左右子树
  • 返回root
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None

def buildTree(preorder, inorder):

if not preorder or not inorder:
return None

root_val = preorder[0]
root = TreeNode(root_val)
root_index = inorder.index(root_val)

left_pre = preorder[1: root_index + 1]
left_in = inorder[ : root_index]

right_pre = preorder[root_index + 1: ]
right_in = inorder[root_index + 1: ]

root.left = buildTree(left_pre, left_in)
root.right = buildTree(right_pre, right_in)

return root

if __name__ == '__main__':

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
x = buildTree(preorder, inorder)
print(x.val)
print(x.left.val)
print(x.right.val)
文章作者: Lesy
文章链接: https://lesylin.com/2020/08/01/%E6%AF%8F%E6%97%A5%E4%B8%80%E5%88%B71/
文章声明: 转载请注明文章链接
打赏
  • 微信
  • 支付宝

Comment