• 448. 找到消失的数字
  • 解法一
  • 解法二 官方题解
• 461 汉明距离
• 543 二叉树直径
• 617 合并二叉树
• 剑指 Offer 03 数组中重复的数字
• 剑指 Offer 05. 替换空格
• 剑指 Offer 06. 从尾到头打印链表
• 剑指 Offer 09. 用两个栈实现队列
• 剑指 Offer 10 经典递归
• 剑指 Offer 11. 旋转数组的最小数字

11.25日，最近还是好好刷题 leetcode python3 & sql\n",

1. 热门100道题中的简单题——最后四道

   • 【448】找到消失的数字
   • 【461】汉明距离
   • 【543】二叉树直径
   • 【617】合并二叉树

2. 剑指 Offer 第二版

448. 找到消失的数字

找到所有在 [1, n] 范围之间没有出现在数组中的数字

解法一

nums = [4,3,2,7,8,2,3,1]
list(set(range(1, len(nums) + 1)) - set(nums))

[5, 6]

解法二 官方题解

1. 一个萝卜一个坑，鸽巢思想

   • 将每个数字放到正确的位置上（对应的下标）,
   • 遍历排序后的数组，若位置上不是正确的元素，则输出

2. 数组长度其实和数组的索引相关，最大索引+1即为数组长度,

   • 能不能通过数组的值转换为索引，,
   • 将原始数组的值加个标签，比如变为-1或者乘以*-1 作为标记 tag ，最后根据标签来判断数组索引是否存在

nums = [4, 3, 2, 7, 8, 2, 3, 1]
for num in nums:
    nums[abs(num) - 1] = - abs(nums[abs(num) - 1])      # 如果索引值1：n存在与nums中，则标记为负数
print(nums)  # 正数——对应索引值不存在nums中，负数——对应索引值存在于nums中
print([idx + 1 for idx, num in enumerate(nums) if num > 0])  # 输出正数对应的索引值 +1

[-4, -3, -2, -7, 8, 2, -3, -1]
[5, 6]

461 汉明距离

定义：两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目

543 二叉树直径

一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。两结点之间的路径长度是以它们之间边的数目表示

• 错误解答： 最大直径是左子树和右子树的最大深度之和，但是万一最大直径没有经过根节点呢？
• 所以说对于树中的每一个结点，都要把它视为根节点，然后比较所有结点的左子树和右子树的最大深度之和，取其中的最大值。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self x):
#         self.val = x
#         self.left = None
#         self.right = None
   
# 1.初步考虑（经过根节点的情况）——对左右递归
'''
def depth(root):
    if root == None:
        return 0
    l = depth(root.left)
    r = depth(root.right)
    return max(l r) + 1
'''

# 2.用一个max记录所有结点看做根节点对左右递归时候的max值
class solution:
    def __init__(self):
        self.max = 0
           
    def diameterOfBinaryTree(self, root):
        self.depth(root)
        return self.max
       
    def depth(self, root):
        if root == None:
            return 0
        l = self.depth(root.left)
        r = self.depth(root.right)
        self.max = max(self.max, l + r)
        return max(l, r) + 1

617 合并二叉树

• 如果两个节点重叠，那么将他们的值相加作为节点合并后的新值
• 否则不为 NULL 的节点将直接作为新二叉树的节点。

# Definition for a binary tree node.
   # class TreeNode:
   #     def __init__(self x):
   #         self.val = x
   #         self.left = None
   #         self.right = None

class Solution:
       def mergeTrees(self, t1, t2):
           
        # 结束条件
        if not t1 or not t2:
            return t1 or t2
           
        # 否则就合并，即+
        else:
            t1.val += t2.val
            t1.left = self.mergeTrees(t1.left, t2.left)
            t1.right = self.mergeTrees(t1.right, t2.right)
            return t1

剑指 Offer 03 数组中重复的数字

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

class Solution:
    # 解法一（找出任意一个）
    def findRepeatNumber(self, nums):
        n = len(nums)
        nums.sort()
        for i in range(n):
            if nums[i] - nums[i+1] == 0:
                return nums[i]
   
    # 解法二（可以找出所有）        
    def findRepeatNumber(self, nums):
        d = dict()
        res = []
           
        for i in range(len(nums)):
            if nums[i] in d.keys():
                d[nums[i]] += 1
            else:
                d[nums[i]] = 1
   
        for j in d.keys():
            if d[j] >= 2: res.append(j)
        return res

剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成 %20

s = "We are happy!"
def replaceblank(s):
    ss = list(s)
    res = []
    for _ in ss:
        if _ == ' ':
            res.append('%20')
        else:
            res.append(_)
    return ''.join(res)
replaceblank(s)

'We%20are%20happy!'

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

class Solution:
    def reversePrint(self head):
        val = []
        node = head
        while node:
            val.append(node.val)
            node = node.next
        res = []
        while val:
            res.append(val.pop())
        return res

剑指 Offer 09. 用两个栈实现队列

只使用一个栈 stack1 当作队列，另一个栈 stack2 用来辅助操作。

要想将新加入的元素出现栈底，需要先将 stack1 的元素转移到 stack2，将元素入栈 stack1，最后将 stack2 的元素全部回到 stack1。

class CQueue:
    def __init__(self):
        self.q1 = []
        self.q2 = []
   
    def appendTail(self, value):
        self.q1.append(value)
           
    def deleteHead(self):
        if self.q2:  # 先前进行过一次倒序
            return self.q2.pop()
        elif self.q1: # 第一次删除/把以前加入的全部删掉了，但是还有新的
            while self.q1:
                self.q2.append(self.q1.pop())  # 倒序
            return self.q2.pop()
        else:   # 都空，则按照题目要求返回-1
            return -1 
        
# 测试
test = CQueue()
for i in ['top','middle','end']:
    test.appendTail(i);
test.deleteHead(),test.deleteHead(),test.deleteHead(),test.deleteHead()

('top', 'middle', 'end', -1)

剑指 Offer 10 经典递归

fib数列、青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a %  1000000007

def numWays1(n):
    if n < 2:
        return 1
    else:
        return (numWays(n - 1) + numWays(n - 2)) %  1000000007

def numWays2(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a % 1000000007

剑指 Offer 11. 旋转数组的最小数字

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

nums = [0,1,2,4,5,6,7]
nums = [4,5,6,7,8,1,2,3]

res = None
i = 0
while (i < (len(nums)-1 )) and (res == None) :
    if nums[i] > nums[i+1]:
        res = nums[i+1]
    i += 1
if res == None:
    res = nums[0]

print(res)

1