目录
  1. 1. 前言
  2. 2. 数组中重复的数字
    1. 2.1. 题目
    2. 2.2. 题解
  3. 3. 二维数组中的查找
    1. 3.1. 题目
    2. 3.2. 题解
  4. 4. 替换空格
    1. 4.1. 题目
    2. 4.2. 题解
  5. 5. 从尾到头打印链表
    1. 5.1. 题目
    2. 5.2. 题解
  6. 6. 重建二叉树
    1. 6.1. 题目
    2. 6.2. 题解
  7. 7. 用两个栈实现队列
    1. 7.1. 题目
    2. 7.2. 题解
  8. 8. 用两个队列实现栈
    1. 8.1. 题解
  9. 9. 斐波那契数列
    1. 9.1. 题目
    2. 9.2. 题解
  10. 10. 青蛙跳台阶问题
    1. 10.1. 题目
    2. 10.2. 题解
  11. 11. 旋转数组中最小的数字
    1. 11.1. 题目
    2. 11.2. 题解
  12. 12. 矩阵中的路径
    1. 12.1. 题目
    2. 12.2. 题解
  13. 13. 机器人的运动范围
    1. 13.1. 题目
    2. 13.2. 题解
  14. 14. 剪绳子I
    1. 14.1. 题目
    2. 14.2. 题解
  15. 15. 剪绳子II
    1. 15.1. 题目
    2. 15.2. 题解
  16. 16. 二进制中1的个数
    1. 16.1. 题目
    2. 16.2. 题解
  17. 17. 数值的整数次方
    1. 17.1. 题目
    2. 17.2. 题解
  18. 18. 打印从1到最大的n位数
    1. 18.1. 题目
    2. 18.2. 题解
  19. 19. 删除链表的节点
    1. 19.1. 题目
    2. 19.2. 题解
  20. 20. 正则表达式匹配
    1. 20.1. 题目
    2. 20.2. 题解
  21. 21. 表示数值的字符串
    1. 21.1. 题目
    2. 21.2. 题解
  22. 22. 调整数组顺序使奇数位于偶数前面
    1. 22.1. 题目
    2. 22.2. 题解
  23. 23. 链表中倒数第k个结点
    1. 23.1. 题目
    2. 23.2. 题解
  24. 24. 反转链表
    1. 24.1. 题目
    2. 24.2. 题解
  25. 25. 合并两个排序链表
    1. 25.1. 题目
    2. 25.2. 题解
  26. 26. 树的子结构
    1. 26.1. 题目
    2. 26.2. 题解
  27. 27. 二叉树的镜像
    1. 27.1. 题目
    2. 27.2. 题解
  28. 28. 对称的二叉树
    1. 28.1. 题目
    2. 28.2. 题解
  29. 29. 顺时针打印矩阵
    1. 29.1. 题目
    2. 29.2. 题解
  30. 30. 包含min函数的栈
    1. 30.1. 题目
    2. 30.2. 题解
  31. 31. 栈的压入、弹出序列
    1. 31.1. 题目
    2. 31.2. 题解
  32. 32. 从上到下打印二叉树
    1. 32.1. 题目
    2. 32.2. 题解
  33. 33. 从上到下打印二叉树II
    1. 33.1. 题目
    2. 33.2. 题解
  34. 34. 从上到下打印二叉树III
    1. 34.1. 题目
    2. 34.2. 题解
  35. 35. 二叉搜索树的后序遍历序列
    1. 35.1. 题目
    2. 35.2. 题解
  36. 36. 二叉树中和为某一值的路径
    1. 36.1. 题目
    2. 36.2. 题解
  37. 37. 复杂链表的复制
    1. 37.1. 题目
    2. 37.2. 题解
  38. 38. 二叉搜索树与双向链表
    1. 38.1. 题目
    2. 38.2. 题解
  39. 39. 序列化二叉树
    1. 39.1. 题目
    2. 39.2. 题解
  40. 40. 字符串的排列
    1. 40.1. 题目
    2. 40.2. 题解
  41. 41. 数组中出现次数超过一半的数字
    1. 41.1. 题目
    2. 41.2. 题解
  42. 42. 最小的k个数
    1. 42.1. 题目
    2. 42.2. 题解(排序)
剑指offer

前言

 面试必备《剑指offer》,题解整理,方便今后自己查阅,要为接下来的秋招做准备了呀~

数组中重复的数字

题目

  • 难度:简单

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

  • 示例:

    输入:
    [2, 3, 1, 0, 2, 5, 3]
    输出:2 或 3
  • 限制:2n1000002≤n≤100000

题解

  • Tips:这道题有多种解法,如果面试中遇到这道题,让你找出数组中重复的数字,要向面试官询问,是否可以使用额外空间是否可以修改原数组?然后,根据要求给出解决方案。(本题对数组长度做了限制,如果没有限制数组长度,需要进行非空判断

    1. 使用额外空间,不修改原数组——哈希表

      • 思路:遍历数组,用哈希表记录数组中每个数字出现的情况,如果该数字没有出现在哈希表,就将其加入哈希表,如果该数字在哈希表中已经存在,就直接返回。

      • 时间复杂度:O(n)

      • 空间复杂度:O(n)

        class Solution(object):
        def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic = {}
        for num in nums:
        if num in dic:
        return num
        else:
        dic[num] = 1
        return None
    2. 不使用额外空间,修改原数组——sort排序

      • 思路:对数组排序,这样重复的两个数字的位置就是相邻的,然后,遍历一遍数组,判断相邻位置的两个数字是否相等,相等就返回,不相等就继续遍历。

      • list.sort()的原理:https://blog.csdn.net/yangzhongblog/article/details/8184707

      • 时间复杂度:O(nlogn)

      • 空间复杂度:O(1)

        class Solution(object):
        def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        for i in range(len(nums)):
        if nums[i] == nums[i + 1]:
        return nums[i]
        return None
    3. 不使用额外空间,修改原数组——原地排序

      • 思路:因为数组的数字范围和数组的长度是一样的,即与数组下标一一对应(把数组视为哈希表)。因此,我们看到数字,就可以知道把这个数字放在数组的哪个位置上。这就像是我们人为编写了哈希函数,这个哈希函数的规则还特别简单,而找到重复数字就是发生了哈希冲突。

      • 时间复杂度:O(n)

      • 空间复杂度:O(1)

      • Python 中, a, b = c, d 操作的原理是先暂存元组 (c, d) ,然后 “按顺序” 赋值给 a 和 b 。
        若写为 nums[i], nums[nums[i]] = nums[nums[i]], nums[i] ,则 nums[i] 先被赋值,之后 nums[nums[i]] 指向的元素则会出错。

      class Solution(object):
      def findRepeatNumber(self, nums):
      """
      :type nums: List[int]
      :rtype: int
      """
      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 -1

二维数组中的查找

题目

  • 难度:简单

  • 题目(leetcode-面试题04):在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

  • 示例:

    现有矩阵 matrix 如下:
    [
    [1, 4, 7, 11, 15],
    [2, 5, 8, 12, 19],
    [3, 6, 9, 16, 22],
    [10, 13, 14, 17, 24],
    [18, 21, 23, 26, 30]
    ]

    给定 target = 5,返回 true。
    给定 target = 20,返回 false。
  • 限制:0n10000m10000≤n≤1000,0≤m≤1000

题解

  • Tips:如果这个n * m的数组是无序的,要查找该数组中是否存在目标整数,需要遍历完二维数组每一行或者每一列,即暴力求解法,时间复杂度是O(n*m),空间复杂度是O(1)。仔细观察题目的二维数组,可以发现行和列的数字是按一定顺序排列的。

  • (《剑指offer》分析):在分析这个问题的时候,很多应聘者都会把二维数组画成矩形,然后从数组中选取一个数字,分3种情况来分析查找过程。当数组中选取的数字刚好要和查找的数字相等时,就结束查找过程。如果选取的数字小于要查找的数字,那么根据数组排序的规则,要查找的数字应该在当前选取位置的右边或者下边。同样,如果选取的数字大于要查找的数字,那么要查找的数字应该在当前选取的位置的上边或者右边。(若当前选取位置在正中间,则在右下角或左上角可能会出现查找重叠区域)。

  • 思路:从数组的一个角上选取数字来和要查找的数字做比较。

    • 左上角数字:是所在列和行最小的数字(如果查找的数字大于左上角数字,情况和上述分析一样,可以往右边或者下边查找)

    • 左下角数字:是所在列最大的数字,所在行最小的数字(如果查找的数字大于左下角数字,往右边查找,如果小于做左下角数字,往上边查找)

    • 右上角数字:是所在列最小的数字,所在行最大的数字(如果查找的数字大于右上角数字,往下边查找,如果小于右上角数字,往左边查找)

    • 右下角数字:是所在列和行最大的数字(如果查找的数字小于右下角数字,情况和上述分析一样,可以往左边或者上边查找)

    • 因此,本题可以选择左下角数字或右上角数字来和查找的数字做比较。

    • 算法流程:

      • 特殊用例:二维数组为空,返回空
      • 假设从矩阵matrix的左下角数字开始遍历(索引设为i,j),与要查找的数字做比较:(右上角同理分析)
        • matrix[i][j] == target,返回True
        • matrix[i][j] > target,行索引i向上查找,即i--
        • matrix[i][j] < target,列索引j向右查找,即j++
      • 若行索引或列索引越界,则代表矩阵中无目标值,返回 False。
    • 算法本质: 每轮 i 或 j 移动后,相当于生成了“消去一行(列)的新矩阵”, 索引(i,j) 指向新矩阵的左下角元素(标志数),因此可重复使用以上性质消去行(列)。

  • 时间复杂度:O(n + m)

  • 空间复杂度:O(1)

    class Solution(object):
    def findNumberIn2DArray(self, matrix, target):
    """
    :type matrix: List[List[int]]
    :type target: int
    :rtype: bool
    """
    if not matrix or not target:
    return False
    i = len(matrix) - 1
    j = 0
    while i >= 0 and j < len(matrix[0]):
    if matrix[i][j] == target:
    return True
    elif matrix[i][j] > target:
    i -= 1
    else:
    j += 1
    return False

替换空格

题目

  • 难度:简单

  • 题目(leetcode-面试题05):请实现一个函数,把字符串 s 中的每个空格替换成"%20"。

  • 示例:

    输入:s = "We are happy."
    输出:"We%20are%20happy."
  • 限制:0s100000 ≤ s的长度 ≤ 10000

题解

  • (《剑指offer》分析):看到这个题目,我们首先应该想到的是原来一个空格字符,替换之后变成’%’、‘2’、'0’这3个字符,因此字符串会变长。如果是在原来的字符串上做替换,那么就有可能覆盖修改在该字符串后面的内存。如果是创建新的字符串并在新的字符串上做替换,那么我们可以自己分配足够多的内存。
  • Tips:根据上述分析,在面试的时候,要明确面试官的需求,然后,从两种方案中选择一种完成。下面是三种最优的解法:

    1. 使用replace函数(新)

      • python内置的replace函数用来替换字符串中指定的字符。

        replace() 方法把字符串中的 old(旧字符串) 替换成 new(新字符串),如果指定第三个参数max,则替换不超过 max 次。

        replace()方法语法:str.replace(old, new[, max])

        参数

        • old – 将被替换的子字符串。
        • new – 新字符串,用于替换old子字符串。
        • max – 可选字符串, 替换不超过 max 次

        返回值:返回字符串中的 old(旧字符串) 替换成 new(新字符串)后生成的新字符串,如果指定第三个参数max,则替换不超过 max 次。

      • 时间复杂度:O(n)

      • 空间复杂度:O(n)

        class Solution(object):
        def replaceSpace(self, s):
        """
        :type s: str
        :rtype: str
        """
        return s.replace(' ','%20')
    2. 循环(新)

      • Python的六个标准数据类型中不可变数据(3 个):Number(数字)、String(字符串)、Tuple(元组)。
      • 将字符串先转换为list,然后,遍历list,当遍历到空格,就将空格替换成’%20’,最后,将list转成str。

      • 时间复杂度:O(n)

      • 空间复杂度:O(n)

        class Solution(object):
        def replaceSpace(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) == 0:
        return s
        l = list(s)
        for i in range(len(l)):
        if l[i] == ' ':
        l[i] = '%20'
        return ''.join(l)
    3. 双指针移动+计数(原始)

      • 首先遍历一次字符串s,统计空格数

      • 假设有m个空格,我们需要填充’%20’占用的三个字符串位置,所以需要额外开辟2 * m个空间

      • 将开辟出的空间链接到原字符串的后面,新的字符串命名为s_new

      • 设置两个指针p1和p2,初始时p1指向原字符串s的末尾,p2指向s_new的末尾

      • p1指针向前移动,当p1指向的字符不是空格时,将p1指向的字符复制到p2指向的位置,并都向前移动一位

      • 当p1指向的字符是空格时,p1向前移动一格,这时应该插入%20,所以p2向前移动三格,并在这三格中插入%,2,0

      • 时间复杂度:O(n)

      • 空间复杂度:O(2m)

        class Solution(object):
        def replaceSpace(self, s):
        """
        :type s: str
        :rtype: str
        """
        s_len = len(s)
        space_count = 0
        for i in s:
        if i == ' ':
        space_count += 1
        s_len += 2 * space_count
        new_array = [' '] * s_len
        p2 = 0
        for p1 in range(len(s)):
        if s[p1] == ' ':
        new_array[p2] = '%'
        new_array[p2 + 1] = '2'
        new_array[p2 + 2] = '0'
        p2 += 3
        else:
        new_array[p2] = s[p1]
        p2 += 1
        return ''.join(new_array)

从尾到头打印链表

题目

  • 难度:简单

  • 题目(leetcode-面试题06):输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

  • 示例:

    输入:head = [1,3,2]
    输出:[2,3,1]
  • 限制:0100000 ≤ 链表长度 ≤ 10000

题解

  • (《剑指offer》分析):看到这道题后,很多人的第一反应是从头到尾输出将会比较简单,于是我们很自然地想到把链表中链接结点的指针反转过来,改变链表的方向,然后就可以从头到尾输出了。但该方法会改变原来链表的结构。
  • Tips:面试时候,需要明确**是否允许在打印链表的时候修改链表的结构**?如果可以修改,那么就是面试题24-反转链表,先对链表进行反转,然后输出。如果不可以修改,那肯定需要遍历链表,遍历顺序是从头到尾,输出是从尾到头,典型的“后进先出”,我们可以使用栈实现。想到栈,我们还可以想到递归,递归在本质上就是一个栈结构,即每访问到一个结点的时候,先递归输出它后面的结点,再输出该结点自身。

    1. 修改链表结构-反转链表(具体看面试题24-反转链表)

      • 特殊用例:链表头结点指针为空,返回[]

      • 双指针反转链表:

      • 初始化两个指针,pre == Nonecur == head

      • 遍历链表,用临时变量tmp记录当前结点,并将当前结点的下一个结点指向当前结点的前一个结点,即cur.next = pre

      • pre和cur都向链表尾部移动,直到cur为空。

      • 题目要求用数组返回,因此,初始化数组s = [],遍历反转后的链表,依次将每个结点的值加入数组,然后返回数组s。

        # Definition for singly-linked list.
        # class ListNode(object):
        # def __init__(self, x):
        # self.val = x
        # self.next = None

        class Solution(object):
        def reversePrint(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        if not head:
        return []
        pre = None
        cur = head
        while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
        s = []
        while pre:
        s.append(pre.val)
        pre = pre.next
        return s
    2. 不修改链表结构-栈(迭代):

      • 创建一个栈,用于存储链表结点

      • 创建一个指针,初始时指向链表的头结点

      • 当指针指向元素非空时,重复下列操作:

        • 将指针指向的结点压入栈内
        • 将指针移到当前结点的下一个结点
      • 初始化数组s=[]

      • 当栈不为空时,重复下列操作:

        • 将栈顶结点弹出,将栈顶结点的值加入数组s
      • 返回数组s

      • 时间复杂度:O(n)

      • 空间复杂度:O(n)

        # Definition for singly-linked list.
        # class ListNode(object):
        # def __init__(self, x):
        # self.val = x
        # self.next = None

        class Solution(object):
        def reversePrint(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        if not head:
        return []
        stack = []
        i = head
        s = []
        while i:
        stack.append(i)
        i = i.next
        while stack:
        s.append(stack.pop().val)
        return s
      • python可以对上面的代码优化,不需要再创建一个数组s,可以直接利用切片,直接输出倒序列表stack

        # Definition for singly-linked list.
        # class ListNode(object):
        # def __init__(self, x):
        # self.val = x
        # self.next = None

        class Solution(object):
        def reversePrint(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        if not head:
        return []
        stack = []
        i = head
        while i:
        stack.append(i.val)
        i = i.next
        return stack[::-1]
    3. 不修改链表结构-递归

      • 利用递归: 先走至链表末端,回溯时依次将节点值加入列表 ,这样就可以实现链表值的倒序输出。

      • 递推阶段: 每次传入 head.next ,以 head == None(即走过链表尾部节点)为递归终止条件,此时返回空列表 []

      • 回溯阶段: 利用 Python 语言特性,递归回溯时每次返回 当前 list + 当前节点值 [head.val],即可实现节点的倒序输出

      • (《剑指offer》分析):当链表非常长的时候,就会导致函数调用的层级很深,从而有可能导致函数调用栈溢出。显示用栈基于循环实现的代码鲁棒性要好一些。

      • 时间复杂度:O(n)

      • 空间复杂度:O(n)

        # Definition for singly-linked list.
        # class ListNode(object):
        # def __init__(self, x):
        # self.val = x
        # self.next = None

        class Solution(object):
        def reversePrint(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        if not head:
        return []
        return self.reversePrint(head.next) + [head.val]

重建二叉树

题目

  • 难度:中等

  • 题目(leetcode-面试题07):输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

  • 示例:

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

    返回如下的二叉树:
    3
    / \
    9 20
    / \
    15 7
  • 限制:050000 ≤ 节点个数 ≤ 5000

题解

  • 思路:根据前序遍历和中序遍历的特点,可以对前序遍历和中序遍历序列进行划分,划分出左子树、根节点、右子树的区间,然后,递归构造二叉树。

    • 特殊用例:前序遍历为空或中序遍历为空或节点个数≤0,返回None(前序遍历和中序遍历不匹配)
    • 根据前序遍历特点,前序遍历序列的第一个数字是根节点的值,即root_val = preorder[0]
    • 构建根节点,root = TreeNode(root_val)
    • 确定根节点在中序遍历的序列的索引:root_in_index = inorder.index(root_val)
    • 确定左子树在前序遍历序列的区间,以及在中序遍历序列的区间
    • 确定右子树在前序遍历序列的区间,以及在中序遍历序列的区间
    • 递归构建左子树和右子树
    • 返回root
  • 时间复杂度:O(n)

  • 空间复杂度:O(n)

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

    class Solution(object):
    def buildTree(self, preorder, inorder):
    """
    :type preorder: List[int]
    :type inorder: List[int]
    :rtype: TreeNode
    """
    if not preorder or not inorder:
    return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    root_in_index = inorder.index(root_val)
    left_pre = preorder[1: root_in_index + 1]
    left_in = inorder[: root_in_index]
    right_pre = preorder[root_in_index + 1:]
    right_in = inorder[root_in_index + 1:]
    root.left = self.buildTree(left_pre, left_in)
    root.right = self.buildTree(right_pre, right_in)
    return root

用两个栈实现队列

题目

  • 难度:简单

  • 题目(leetcode-面试题09):用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

  • 示例:

    示例1:
    输入:
    ["CQueue","appendTail","deleteHead","deleteHead"]
    [[],[3],[],[]]
    输出:[null,null,3,-1]

    示例2:
    输入:
    ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
    [[],[],[5],[2],[],[]]
    输出:[null,-1,null,null,5,2]
  • 提示:

    • 1values100001 ≤ values ≤ 10000
    • 最多会对 appendTail、deleteHead 进行 10000 次调用

题解

  • (《剑指offer》分析):
    • 初始化stack1和stack2
    • 插入元素:将元素插入stack1
    • 删除元素:stack2中不为空时,在stack2中的栈顶元素是最先进入队列的元素,可以弹出。如果stack2为空时,我们把stack1中的元素逐个弹出并压入stack2。
class CQueue(object):

def __init__(self):
self.stack1 = []
self.stack2 = []


def appendTail(self, value):
"""
:type value: int
:rtype: None
"""
self.stack1.append(value)


def deleteHead(self):
"""
:rtype: int
"""
if self.stack2:
return self.stack2.pop()
if not self.stack1:
return -1
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()

用两个队列实现栈

题解

  • Tips:pop(0)是pop第一个元素,pop()是pop最后一个元素,时间效率上pop最后一个元素效率高。pop用于stack,可带参数,popleft用于collections中,不可带参数。(都是pop出来且在原数据删除)

  • 思路:

    • 初始化两个队列,q1和q2
    • 进栈:元素队列q1
    • 出栈:当队列q1只有一个元素,直接出队,否则,把q1的元素出队并入队q2,直到q1中只有一个元素,再直接出队。为了下一次继续操作,互换q1和q2
    class Stack():
    def __init__(self):
    self.q1 = []
    self.q2 = []
    def push(self, val):
    self.q1.append(val)
    def pop(self):
    if len(self.q1) == 0:
    return None
    while len(self.q1) != 1:
    self.q2.append(self.q1.pop(0))
    self.q1, self.q2 = self.q2, self.q1
    return self.q2.pop()

    if __name__ == '__main__':
    s = Stack()
    l = [0, 1, 2, 3]
    for i in range(len(l)):
    s.push(l[i])
    print(l)
    for i in range(len(l)):
    print(s.pop(), ',', end = '')

斐波那契数列

题目

  • 难度:简单

  • 题目(leetcode-面试题10-I):写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:

    F(0) = 0,   F(1) = 1
    F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

    斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

    答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

  • 示例:

    输入:n = 2
    输出:1

    输入:n = 5
    输出:5
  • 提示:0n1000 ≤ n ≤ 100

题解

  • 参考https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/solution/mian-shi-ti-10-i-fei-bo-na-qi-shu-lie-dong-tai-gui/
class Solution(object):
def fib(self, n):
"""
:type n: int
:rtype: int
"""
if n < 2:
return n
dp = [0] * (n + 1)
dp[ 1] = 1
for i in range(2, n+1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[-1] % 1000000007
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
  • 可以用3个变量,sum,a,b,优化上述代码,时间复杂度不变,空间复杂度降为O(1)
class Solution(object):
def fib(self, n):
"""
:type n: int
:rtype: int
"""
a = 0
b = 1
for _ in range(n):
a,b = b, a+b
return a % 1000000007

青蛙跳台阶问题

题目

  • 难度:简单

  • 题目(leetcode-面试题10-II):一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1

  • 示例:

    输入:n = 2
    输出:2

    输入:n = 7
    输出:21
  • 提示:0n1000 ≤ n ≤ 100

题解

  • 参考https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/solution/mian-shi-ti-10-ii-qing-wa-tiao-tai-jie-wen-ti-dong/
  • 此类求 多少种可能性 的题目一般都有 递推性质 ,即 f(n)f(n)f(n1)....f(1)f(n - 1)....f(1)之间是有联系的。
  • 设跳上 nn 级台阶有 f(n)f(n) 种跳法。在所有跳法中,青蛙的最后一步只有两种情况: 跳上 1 级或 2级台阶。
  • 当为 1 级台阶: 剩 n1n-1个台阶,此情况共有 f(n1)f(n-1)种跳法;
  • 当为 2 级台阶: 剩 n2n-2个台阶,此情况共有 f(n2)f(n-2)种跳法。
  • f(n)f(n)为以上两种情况之和,即 f(n)=f(n1)+f(n2)f(n)=f(n-1)+f(n-2) ,以上递推性质为斐波那契数列。
  • 本题可转化为 求斐波那契数列第 n项的值 ,与 面试题10- I. 斐波那契数列 等价,唯一的不同在于起始数字不同。
    • 青蛙跳台阶问题: f(0)=1,f(1)=1,f(2)=2f(0)=1 , f(1)=1 , f(2)=2
    • 斐波那契数列问题:$ f(0)=0 , f(1)=1 , f(2)=1$ ;
  • Tips:直接在面试题10-I 斐波那契数列的基础上,将起始数字做一个修改。

    class Solution(object):
    def numWays(self, n):
    """
    :type n: int
    :rtype: int
    """
    a = 1
    b = 1
    for _ in range(n):
    a, b = b, a+b
    return a % 1000000007
    class Solution(object):
    def numWays(self, n):
    """
    :type n: int
    :rtype: int
    """
    if n == 0:
    return 1
    one = 1
    two = 2
    res = 0
    for i in range(3,n+1):
    res = one + two
    one = two
    two = res
    m = max(n, res)
    return m % 1000000007

旋转数组中最小的数字

题目

  • 难度:简单

  • 题目(leetcode-面试题11):把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。

  • 示例:

    输入:[3,4,5,1,2]
    输出:1

    输入:[2,2,2,0,1]
    输出:0

题解

  • Tips如果面试题是要求在排序的数组(或者部分排序的数组)中查找一个数字或者统计某个数字出现的次数,我们都可以尝试用二分查找算法。关于查找和排序见另一篇博客《八大排序》
  • 思路:

    • 根据题目可以发现,输入的递增排序数组,可以从中点划分成两个递增数组。左排序数组的任一元素都大于右排序数组的任一元素。
    • 双指针法,初始化两个指针i,j,指向数组的头和尾,即i == 0j == len(numbers)
    • mid = (i + j) // 2,每次二分的中点
    • numbers[mid] > numbers[j],m在左边的递增数组,最小元素一定在[m+1, j]
    • numbers[mid] < numbers[j],m在右边的递增数组,最小元素一定在[i,m]
    • numbers[mid] = numbers[j],无法判断m在哪,缩小区间即可[i,j-1]
  • 时间复杂度:O(logn)

  • 空间复杂度:O(1)

    class Solution(object):
    def minArray(self, numbers):
    """
    :type numbers: List[int]
    :rtype: int
    """
    i, j = 0, len(numbers) - 1
    while i < j:
    mid = (i + j) // 2
    if numbers[mid] > numbers[j]:
    i = mid + 1
    elif numbers[mid] < numbers[j]:
    j = mid
    else:
    j -= 1
    return numbers[i]

矩阵中的路径

题目

  • 难度:中等

  • 题目(leetcode-面试题12):请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如,在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。

    [[“a”,“b”,“c”,“e”],
    [“s”,“f”,“c”,“s”],
    [“a”,“d”,“e”,“e”]]

    但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。

  • 示例:

    输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
    输出:true

    输入:board = [["a","b"],["c","d"]], word = "abcd"
    输出:false
  • 提示:

    • 1<=board.length<=2001 <= board.length <= 200
    • 1<=board[i].length<=2001 <= board[i].length <= 200

题解

  • 参考https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/solution/mian-shi-ti-12-ju-zhen-zhong-de-lu-jing-shen-du-yo/
  • 思路:DFS+剪枝

    • 递归参数:当前元素在矩阵board中行列索引ij,当前目标字符在word中的索引k
    • 终止条件:
      • 返回false:①行或列索引越界或②当前矩阵元素与目标字符不同或③当前矩阵元素已访问过(③可合并至②)。
      • 返回true:字符串word已全部匹配,即k == len(word) - 1
    • 递推工作:
      • 标记当前矩阵元素:将board[i][j]值暂存于变量tmp,并修改为字符'/',代表此元素已访问过,防止之后搜索时重复访问。
      • 搜索下一单元格:朝当前元素的上、下、左、右四个方向开启下层递归,使用或连接(代表只需一条可行路径),并记录结果至res
      • 还原当前矩阵元素:将tmp暂存值还原至board[i][j]元素。
    • 回溯返回值:返回res,代表是否搜索到目标字符串。
  • 时间复杂度:O(MN)

  • 空间复杂度:O(K)

  • M,N 分别为矩阵行列大小, KK 为字符串 word 长度。

    class Solution(object):
    def exist(self, board, word):
    """
    :type board: List[List[str]]
    :type word: str
    :rtype: bool
    """
    def dfs(i, j, k):
    if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: # 如果路径出界或者矩阵中的值不是word的首字母,返回False
    return False
    if k == len(word) - 1:
    return True
    tmp, board[i][j] = board[i][j], "/"
    res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j -1, k + 1)
    board[i][j] = tmp
    return res
    for i in range(len(board)):
    for j in range(len(board[0])):
    if dfs(i, j, 0):
    return True
    return False
  • 牛客网对应的这个题的python解法的通过榜单的榜首的代码都会有部分case过不了,正确代码如下:

    class Solution:
    def hasPath(self, matrix, rows, cols, path):
    for i in range(rows):
    for j in range(cols):
    if matrix[i*cols + j] == path[0]:
    if self.dfs(list(matrix), rows, cols, path[1:], i, j):
    return True
    return False

    def dfs(self, matrix, rows, cols, path, i, j):
    if not path:
    return True
    matrix[i*cols + j] = '-'
    for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
    if 0<=x<rows and 0<=y<cols and matrix[x*cols+y]==path[0]:
    if self.dfs(matrix, rows, cols, path[1:], x, y):
    return True
    return False

机器人的运动范围

题目

  • 难度:中等

  • 题目(leetcode-面试题13):地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?

  • 示例:

    输入:m = 2, n = 3, k = 1
    输出:3

    输入:m = 3, n = 1, k = 0
    输出:1
  • 提示:

    • 1<=n,m<=1001 <= n,m <= 100
    • 0<=k<=200 <= k <= 20

题解

  • Tips

  • 参考:https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/mian-shi-ti-13-ji-qi-ren-de-yun-dong-fan-wei-dfs-b/

  • 思路1:

    • DFS
      • 递归参数: 当前元素在矩阵中的行列索引 i 和 j ,两者的数位和 si, sj 。
      • 终止条件: 当 ① 行列索引越界 或 ② 数位和超出目标值 k 或 ③ 当前元素已访问过 时,返回 00 ,代表不计入可达解。
      • 递推工作:
        • 标记当前单元格 :将索引 (i, j) 存入 Set visited 中,代表此单元格已被访问过。
        • 搜索下一单元格: 计算当前元素的 下、右 两个方向元素的数位和,并开启下层递归 。
        • 回溯返回值: 返回 1 + 右方搜索的可达解总数 + 下方搜索的可达解总数,代表从本单元格递归搜索的可达解总数。
    • 时间复杂度:O(MN),[MN为矩阵行列大小]
    • 空间复杂度:O(MN)
    class Solution(object):
    def movingCount(self, m, n, k):
    """
    :type m: int
    :type n: int
    :type k: int
    :rtype: int
    """
    visited = set()
    def dfs(i, j, si, sj):
    if i >= m or j >= n or k < si + sj or (i, j) in visited:
    return 0
    visited.add((i, j))
    return 1 + dfs(i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj) + dfs(i, j + 1, si, sj + 1 if (j + 1) % 10 else sj -8)
    return dfs(0, 0, 0, 0)
  • 思路2:

    • BFS
      • 初始化: 将机器人初始点 (0, 0)加入队列 queue ;
      • 迭代终止条件: queue 为空。代表已遍历完所有可达解。
      • 迭代工作:
      • 单元格出队: 将队首单元格的 索引、数位和 弹出,作为当前搜索单元格。
      • 判断是否跳过: 若 ① 行列索引越界 或 ② 数位和超出目标值 k 或 ③ 当前元素已访问过 时,执行 continue 。
      • 标记当前单元格 :将单元格索引 (i, j) 存入 Set visited 中,代表此单元格 已被访问过 。
      • 单元格入队: 将当前元素的 下方、右方 单元格的 索引、数位和 加入 queue 。
      • 返回值: Set visited 的长度 len(visited) ,即可达解的数量。
    class Solution(object):
    def movingCount(self, m, n, k):
    """
    :type m: int
    :type n: int
    :type k: int
    :rtype: int
    """
    queue, visited = [(0, 0, 0, 0)], set()
    while queue:
    i, j, si, sj = queue.pop(0)
    if i >= m or j >= n or k < si + sj or (i, j) in visited:
    continue
    visited.add((i, j))
    queue.append((i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj))
    queue.append((i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8))
    return len(visited)

剪绳子I

题目

  • 难度:中等

  • 题目(leetcode-面试题14-I):给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

  • 示例:

    输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1

    输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
  • 提示:2<=n<=582 <= n <= 58

题解

  • 思路状态转移方程dp[i]=max(dp[i],max((ij)j,jdp[ij]))dp[i] = max(dp[i], max((i - j) * j, j * dp[i - j])),其中dp[i]表示维持原状态不剪、(i-j) * j表示从j处剪,剪下来的部分就是i-j,i-j不再剪了,j * dp[i-j]表示从j处剪,剪下来的部分是i-j,i-j继续剪。

  • 时间复杂度:O(n)

  • 空间复杂度:O(1),仅用了有限长数组

  • 下面代码更适合面试时使用,即动态规划思路

class Solution(object):
def cuttingRope(self, n):
dp = [0, 1, 1]
for i in range(3, n + 1):
dp[i % 3] = max(max(dp[(i - 1) % 3], i - 1),
2 * max(dp[(i - 2) % 3], i - 2),
3 * max(dp[(i - 3) % 3], i - 3))
return dp[n % 3]
  • 时间复杂度:O(1)
  • 空间复杂度:O(1)
  • 下面代码适合了解学习,属于找规律,数学方法
class Solution(object):
def cuttingRope(self, n):
if n < 4:
return n - 1
a, b = n // 3, n % 3
if b == 0:
return pow(3, a)
elif b == 1:
return pow(3, a - 1) * 4
else:
return pow(3, a) * 2

剪绳子II

题目

  • 难度:中等

  • 题目(leetcode-面试题14II):给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]…k[m] 。请问 k[0]k[1]…k[m] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

    答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

  • 示例:

    输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1

    输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
  • 限制:2<=n<=10002 <= n <= 1000

题解

  • Tips:和面试题14I - 剪绳子I的解题思想是一样的,在此基础上,考虑大数越界情况下的求余问题。

  • 参考链接里介绍的求余方法:https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/mian-shi-ti-14-ii-jian-sheng-zi-iitan-xin-er-fen-f/

    class Solution(object):
    def cuttingRope(self, n):
    dp = [0, 1, 1]
    for i in range(3, n + 1):
    dp[i % 3] = max(max(dp[(i - 1) % 3], i - 1),
    2 * max(dp[(i - 2) % 3], i - 2),
    3 * max(dp[(i - 3) % 3], i - 3))
    return dp[n % 3] % 1000000007
    class Solution(object):
    def cuttingRope(self, n):
    if n < 4:
    return n - 1
    a, b = n // 3, n % 3
    if b == 0:
    return pow(3, a) % 1000000007
    elif b == 1:
    return pow(3, a - 1) * 4 % 1000000007
    else:
    return pow(3, a) * 2 % 1000000007

二进制中1的个数

题目

  • 难度:简单

  • 题目(leetcode-面试题15):请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

  • 示例:

    输入:00000000000000000000000000001011
    输出:3
    解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

    输入:00000000000000000000000010000000
    输出:1
    解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

    输入:11111111111111111111111111111101
    输出:31
    解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。

题解

  • Tips:(剑指offer)位运算的使用**。位运算总共只有五种运算:与、或、异或、左移、右移。与、或和异或运算的规律我们可以用下表总结:

    与(&) 0&0 = 0 1&0=0 0&1=0 1&1=1
    或(!) 0|0 = 0 1|0=1 0|1=0 1|1=1
    异或(^) 0^0 = 0 1^0=1 0^1=1 1^1=0
    • 左移运算符m<<n表示把m左移n位。左移n位的时候,最左边的n位将被丢弃,同时在最右边补上n个0。比如:
      • 00001010<<2 = 00101000
      • 10001010<<3=01010000
    • 右移运算符m>>n表示把m右移n位。右移n位的时候,最右边的n位将被丢弃。但右移时处理最左边位的情形要稍微复杂一点。如果数字是一个无符号数值,则用0填补最左边的n位。如果数字是一个有符号数值,则用数字的符号位填补最左边的n位。也就是说如果数字原先是一个正数,则右移之后在最左边补n个0;如果数字原先是负数,则右移之后在最左边补n个1。
      • 00001010>>2=00000010
      • 10001010>>3=11110001
    • 除法的效率比移位运算要低得多,在实际编程中应尽可能地用移位运算符代替乘除法。
    • 面试时候可以按照基本思路到下面代码思路进行描述:
      • 先判断整数二进制表示中最右边一位是不是1,只需要把整数与1做位与运算,是1就右移1位,直到整个整数为0(如果是有符号数,也就是如果输入负数,这样会产生死循环。
      • 把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0。那么一个整数的二进制表示中有多少个1,就可以进行多次这样的操作。
        • 例如,二进制数1100,它的第二位是从最右边数起的一个1。减去1后,第二位变成0,而前面的1保持不变,因此得到结果1011,然后再把1100与1011做位与运算,得到的结果是1000。我们把1100最右边的1变成了0,结果刚好就是1000。
    • 参考:https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/solution/mian-shi-ti-15-er-jin-zhi-zhong-1de-ge-shu-wei-yun/
  • 时间复杂度:O(n),n为整数二进制1的个数

  • 空间复杂度:O(1)

    class Solution(object):
    def hammingWeight(self, n):
    """
    :type n: int
    :rtype: int
    """
    res = 0
    while n:
    res += 1
    n &= n - 1
    return res
    #一行写法
    # -*- coding:utf-8 -*-
    class Solution:
    def NumberOf1(self, n):
    # write code here
    return sum(n >> i & 1 for i in range(0,32))

数值的整数次方

题目

  • 难度:中等

  • 题目(leetcode-面试题16):实现函数double Power(double base, int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。

  • 示例:

    输入: 2.00000, 10
    输出: 1024.00000

    输入: 2.10000, 3
    输出: 9.26100

    输入: 2.00000, -2
    输出: 0.25000
    解释: 2^-2 = 1/2^2 = 1/4 = 0.25
  • 说明:

    • -100.0 < x < 100.0
    • n 是 32 位有符号整数,其数值范围是 [−2^31, 2^31 − 1] 。

题解

  • Tips:把一个整数减去1之后再和原来的整数做位与运算,得到的结果相当于是把整数的二进制表示中的最右边一个1变成0。很多二进制问题都可以用这个思路解决。

  • 思路:

    • 考虑输入指数是负数和零的情况。
    • 考虑特殊用例:0的0次方,可以输出0或1
    • 细节:判断两个double或float类型数值是否相等。位运算代替乘除法以及求余运算。
  • 时间复杂度:O(logn)

  • 空间复杂度:O(1)

  • 下面代码可以通过leetcode,但是通过上述分析,我们可以知道,x是double类型,不能直接写 x == 0,因此可以定义一个equal函数进行判断(return abs(num1 - num2) <= 0.0000001)

    class Solution(object):
    def myPow(self, x, n):
    """
    :type x: float
    :type n: int
    :rtype: float
    """
    if x == 0:
    return 0
    if x == 0 and n == 0:
    return 0
    if n < 0:
    x = 1 / x
    n = -n
    res = 1
    while n:
    if n & 1:
    res *= x
    x *= x
    n >>= 1
    return res

打印从1到最大的n位数

题目

  • 难度:简单

  • 题目(leetcode-面试题17):输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。

  • 示例:

    输入: n = 1
    输出: [1,2,3,4,5,6,7,8,9]
  • 说明:

    • 用返回一个整数列表来代替打印
    • n 为正整数

题解

  • 思路:全排列递归求解

    • 从左边第一个非0位开始输出;
    • 要考虑0这个特殊值,否则答案会包括0 。
    class Solution:
    def __init__(self):
    self.result = [] # 用来保存结果

    def printNumbers(self, n: int) -> List[int]:
    if n <= 0:
    return []
    number = ["0"]*n
    number[-1] = "1"
    for i in range(0, 10):
    number[0] = chr(ord("0")+i) # ord 是将一个字符转换成 ASCII 码,chr 是将一个 ASCII 码转换成一个数字
    self.Print1ToMaxOfDigitsRecursively(number, n, 0)
    return (self.result[1:])

    def Print1ToMaxOfDigitsRecursively(self, number, length, index):
    if index == length - 1:
    self.PrintNumberNormal(number)
    self.result.append(int("".join(number)))
    return

    for i in range(10):
    number[index+1] = chr(ord("0")+i)
    self.Print1ToMaxOfDigitsRecursively(number, length, index+1)

    def PrintNumberNormal(self, number):
    number = int("".join(number))
    if number != 0:
    print(number)

删除链表的节点

题目

  • 难度:简单

  • 题目(leetcode-面试题18):给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。

    返回删除后的链表的头节点。

    **注意:**此题对比原题有改动

  • 示例:

    输入: head = [4,5,1,9], val = 5
    输出: [4,1,9]
    解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

    输入: head = [4,5,1,9], val = 1
    输出: [4,5,9]
    解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.
  • 说明:

    • 题目保证链表中节点的值互不相同
    • 若使用 C 或 C++ 语言,你不需要 freedelete 被删除的节点

题解

  • Tips:这道题有两种思路.

    • 第一个是得到需要删除结点的前面一个结点,然后执行pre.next = cur.next(数据输入类型是整型val)
    • 第二个是把需要删除结点的下一个结点的内容复制到需要删除的结点上,再把下一个结点删除(剑指offer思路,数据输入类型是链表ListNode)
  • 思路1:得到需要删除结点的前面一个结点,然后执行pre.next = cur.next

    • 初始化双指针,pre指向head,cur指向head.next
    • 当head为空时,返回head
    • 当head是要删除的结点,返回head.next
    • 遍历链表,当cur指向的结点是要删除的结点时,pre.next = cur.next,直到链表遍历完
  • 时间复杂度:O(n),n是链表长度

  • 空间复杂度:O(1)

    # Definition for singly-linked list.
    # class ListNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    class Solution(object):
    def deleteNode(self, head, val):
    """
    :type head: ListNode
    :type val: int
    :rtype: ListNode
    """
    pre = head
    cur = head.next
    if not head:
    return head
    if head.val == val:
    return head.next
    while cur:
    if cur.val == val:
    pre.next = cur.next
    pre = pre.next
    cur = cur.next
    return head
  • 单指针写法:

    # Definition for singly-linked list.
    # class ListNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    class Solution(object):
    def deleteNode(self, head, val):
    """
    :type head: ListNode
    :type val: int
    :rtype: ListNode
    """
    if not head:
    return head
    if head.val == val:
    return head.next
    cur = head
    while cur.next:
    if cur.next.val == val:
    cur.next = cur.next.next
    break
    cur = cur.next
    return head
  • 思路2:把需要删除结点的下一个结点的内容复制到需要删除的结点上,再把下一个结点删除。

正则表达式匹配

题目

  • 难度:困难

  • 题目(leetcode-面试题19):请实现一个函数用来匹配包含 '.''*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a""ab*ac*a"匹配,但与"aa.a""ab*a"均不匹配。

  • 示例:

    输入:
    s = "aa"
    p = "a"
    输出: false
    解释: "a" 无法匹配 "aa" 整个字符串。

    输入:
    s = "aa"
    p = "a*"
    输出: true
    解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。

    输入:
    s = "ab"
    p = ".*"
    输出: true
    解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

    输入:
    s = "aab"
    p = "c*a*b"
    输出: true
    解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

    输入:
    s = "mississippi"
    p = "mis*is*p*."
    输出: false
  • s 可能为空,且只包含从 a-z 的小写字母。

  • p 可能为空,且只包含从 a-z 的小写字母以及字符 .*,无连续的 '*'

题解

  • Tips:回溯法+动态规划

  • 思路1:回溯

  • 时间复杂度:O((T+P)2T+2p/2)O((T+P)2^T+2^{p/2}) ,其中T和P分别表示匹配串和模式串的长度。

  • 空间复杂度:O((T+P)2T+2p/2)O((T+P)2^T+2^{p/2})

    class Solution(object):
    def isMatch(self, s, p):
    """
    :type s: str
    :type p: str
    :rtype: bool
    """
    if not p:
    return not s
    # 第一个字母是否匹配
    first_match = bool(s and p[0] in {s[0],'.'})
    # 如果 p 第二个字母是 *
    if len(p) >= 2 and p[1] == "*":
    return self.isMatch(s, p[2:]) or \
    first_match and self.isMatch(s[1:], p)
    else:
    return first_match and self.isMatch(s[1:], p[1:])
  • 思路2:动态规划-自顶向下

  • 时间复杂度:O(TP)

  • 空间复杂度:O(TP)

    class Solution(object):
    def isMatch(self, s, p):
    """
    :type s: str
    :type p: str
    :rtype: bool
    """
    memo = {}
    def dp(i, j):
    if (i, j) not in memo:
    if j == len(p):
    ans = i == len(s)
    else:
    first_match = i < len(s) and p[j] in {s[i], '.'}
    if j+1 < len(p) and p[j+1] == '*':
    ans = dp(i, j+2) or first_match and dp(i+1, j)
    else:
    ans = first_match and dp(i+1, j+1)

    memo[i, j] = ans
    return memo[i, j]
    return dp(0, 0)

表示数值的字符串

题目

  • 难度:中等
  • 题目(leetcode-面试题20):请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+100"、“5e2”、"-123"、“3.1416”、“0123"都表示数值,但"12e”、“1a3.14”、“1.2.3”、“±5”、"-1E-16"及"12e+5.4"都不是。

题解

class Solution(object):
def isNumber(self, s):
"""
:type s: str
:rtype: bool
"""
# 除去两端空格
s = s.strip()
# 检查字符合法性
for c in s:
if c not in "0987654321+-e.":
return False
# 有e的情况
if 'e' in s:
# 检查e的个数
if s.count('e')>1:
return False
# 划分,并检查左右子串是否为空
p = s.index('e')
ls = s[:p]
rs = s[p+1:]
if len(ls)==0 or len(rs)==0:
return False
# 检查左右字串+-
if ('+' in ls and (ls[0]!='+' or len(ls)<2)) or ls.count('+')>1:
return False
if ('-' in ls and (ls[0]!='-' or len(ls)<2)) or ls.count('-')>1:
return False
if ('+' in rs and (rs[0]!='+' or len(rs)<2)) or rs.count('+')>1:
return False
if ('-' in rs and (rs[0]!='-' or len(rs)<2)) or rs.count('-')>1:
return False
# 检查左右字串小数点个数
if ls.count('.')>1 or rs.count('.')>0:
return False
dc = ls.count('.')
if dc>1:
return False
# 检查小数点左或右有没有数字
if dc==1:
p = ls.index('.')
if not((p-1>=0 and ls[p-1] in '0987654321') or (p+1<len(ls) and ls[p+1] in '0987654321')):
return False
# 没e的情况
else:
if len(s)<1:
return False
if ('+' in s and (s[0]!='+' or len(s)<2)) or s.count('+')>1:
return False
if ('-' in s and (s[0]!='-' or len(s)<2)) or s.count('-')>1:
return False
dc = s.count('.')
if dc>1:
return False
if dc==1:
p = s.index('.')
if not ((p-1>=0 and s[p-1] in '0987654321') or (p+1<len(s) and s[p+1] in '0987654321')):
return False
else:
return True
return True

调整数组顺序使奇数位于偶数前面

题目

  • 难度:简单

  • 题目(leetcode-面试题21):输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

  • 示例:

    输入:nums = [1,2,3,4]
    输出:[1,3,2,4]
    注:[3,1,2,4] 也是正确的答案之一。
  • 提示

    • 1 <= nums.length <= 50000
    • 1 <= nums[i] <= 10000

题解

  • Tips位运算比求余效率高。在《剑指offer》分析中,双指针方法适合初级程序员,高级一点的写法,应该把整个函数解耦成两部分,一是判断数字应该在数组前半部分还是后半部分的标准,二是拆分数组的操作,这样无论是奇数在偶数前面的数组划分,还是能被3整除的数划分就可以直接求解了,提高代码重用性。

  • 思路:双指针

    • 初始化双指针,i = 0j = len(nums) - 1
    • 遍历数组,指针i从左向右找偶数,指针j从右向左找奇数
    • 将偶数nums[i]和奇数nums[j]交换
  • 时间复杂度:O(n)

  • 空间复杂度:O(1)

    class Solution(object):
    def exchange(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    i, j = 0, len(nums) - 1
    while i < j:
    if i < j and nums[i] & 1 == 1:
    i += 1
    if i < j and nums[j] & 1 == 0:
    j -= 1
    nums[i], nums[j] = nums[j], nums[i]
    return nums
  • 一行代码

    # -*- coding:utf-8 -*-
    class Solution:
    def reOrderArray(self, array):
    # write code here
    return [n for n in array if n & 1 == 1] + [n for n in array if n & 1 == 0]
  • 高级一点写法

    class Solution(object):
    def exchange(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    if not nums or len(nums) == 0:
    return []
    pBegin = 0
    pEnd = len(nums) - 1
    while pBegin < pEnd:
    if pBegin < pEnd and not self.isEven(nums[pBegin]):
    pBegin += 1
    if pBegin < pEnd and self.isEven(nums[pEnd]):
    pEnd -= 1
    nums[pBegin], nums[pEnd] = nums[pEnd], nums[pBegin]
    return nums
    def isEven(self, n):
    return n & 1 == 0

链表中倒数第k个结点

题目

  • 难度:简单

  • 题目(leetcode-面试题22):输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

  • 示例:

    给定一个链表: 1->2->3->4->5, 和 k = 2.
    返回链表 4->5.

题解

  • Tips:这类找链表结点的题,通常可以用双指针法解决,如链表中点,链表是否有环等。

  • 思路:

    • 定义两个指针,pre和cur
    • 第一个指针cur从链表的头指针开始遍历向前走k-1,第二个指针pre保持不动
    • 从第k步开始,第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1,当cur指针到达链表的为尾结点时,pre正好是倒数第k个结点。
    • 这里要注意三个点:head为空、链表结点数少于k、k为0。
  • 时间复杂度:O(n)

  • 空间复杂度:O(1)

    # Definition for singly-linked list.
    # class ListNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.next = None

    class Solution(object):
    def getKthFromEnd(self, head, k):
    """
    :type head: ListNode
    :type k: int
    :rtype: ListNode
    """
    if not head or k == 0:
    return None
    pre = head
    cur = head
    for _ in range(k):
    if not cur:
    return None
    else:
    cur = cur.next
    while cur:
    pre = pre.next
    cur = cur.next
    return pre

反转链表

题目

  • 难度:简单

  • 题目(leetcode-面试题24):定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

  • 示例:

    输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL
  • 限制:0 <= 节点个数 <= 5000

题解

  • Tips:这道题有三种解法求解,双指针(最优)、辅助栈、递归。

  • 参考:https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/dong-hua-yan-shi-duo-chong-jie-fa-206-fan-zhuan-li/

  • 思路1:双指针

    • 定义3个指针,tmp,pre,cur,分别指向当前遍历结点、它的前一个结点和后一个结点
    • 遍历链表,将当前结点的下一个结点指向当前结点的前一个结点,即cur.next = pre
  • 时间复杂度:O(n)

  • 空间复杂度:O(1)

    # Definition for singly-linked list.
    # class ListNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.next = None

    class Solution(object):
    def reverseList(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    if not head:
    return head
    pre = None
    cur = head
    while cur:
    tmp = cur.next
    cur.next = pre
    pre = cur
    cur = tmp
    return pre
  • 思路2:辅助栈,遍历链表,将链表结点依次入栈,然后依次出栈,即实现反转链表

  • 时间复杂度:O(n)

  • 空间复杂度:O(n)

    # Definition for singly-linked list.
    # class ListNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.next = None

    class Solution(object):
    def reverseList(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    if not head:
    return head
    stack = []
    while head:
    stack.append(head)
    head = head.next
    h = stack.pop()
    p = h
    while stack:
    h.next = stack.pop()
    h = h.next
    h.next = None #防止链表循环
    return p
  • 思路3:递归

  • 时间复杂度:O(n)

  • 空间复杂度:O(n)

    # Definition for singly-linked list.
    # class ListNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.next = None

    class Solution(object):
    def reverseList(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    # 递归终止条件是当前为空,或者下一个节点为空
    if not head or not head.next:
    return head
    # 这里的cur就是最后一个节点
    cur = self.reverseList(head.next)
    # 如果链表是 1->2->3->4->5,那么此时的cur就是5
    # 而head是4,head的下一个是5,下下一个是空
    # 所以head.next.next 就是5->4
    head.next.next = head
    # 防止链表循环,需要将head.next设置为空
    head.next = None
    # 每层递归函数都返回cur,也就是最后一个节点
    return cur

合并两个排序链表

题目

  • 难度:简单

  • 题目(leetcode-面试题25):输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

  • 示例:

    输入:1->2->4, 1->3->4
    输出:1->1->2->3->4->4
  • 限制:0<=<=10000 <= 链表长度 <= 1000

题解

  • 思路:

    • 初始化:
      • 伪头结点new_head,结点cur指向new_head
      • 双指针,p1和p2,分别指向两个链表的头结点
    • 循环合并:当p1或p2为空跳出
      • p1.val < p2.val时,cur的后继结点指向l1,且l1向前一步
      • p1.val > p2.val时,cur的后继结点指向l2,且l2向前一步
      • 结点cur向前一步,即cur = cur.next
    • 合并剩余尾部:跳出时有两种情况,即p1为空或p2为空
      • 若p1不等于null,将p1剩余结点添加至cur后
      • 否则,将p2剩余结点添加至cur后
    • 返回new_head.next
  • 时间复杂度:O(M+N),M,N分别为两个链表的长度

  • 空间复杂度:O(1)

    # Definition for singly-linked list.
    # class ListNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.next = None

    class Solution(object):
    def mergeTwoLists(self, l1, l2):
    """
    :type l1: ListNode
    :type l2: ListNode
    :rtype: ListNode
    """
    new_head = ListNode(0)
    cur = new_head
    p1 = l1
    p2 = l2
    while p1 and p2:
    if p1.val < p2.val:
    cur.next = p1
    p1 = p1.next
    else:
    cur.next = p2
    p2 = p2.next
    cur = cur.next
    cur.next = p1 if p1 else p2
    return new_head.next

树的子结构

题目

  • 难度:中等

  • 题目(leetcode-面试题26):输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构),B是A的子结构, 即 A中有出现和B相同的结构和节点值。

  • 示例:

    例如:
    给定的树 A:
    3
    / \
    4 5
    / \
    1 2

    给定的树 B:
    4
    /
    1

    返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。

    示例1:
    输入:A = [1,2,3], B = [3,1]
    输出:false

    示例2:
    输入:A = [3,4,5,1,2], B = [4,1]
    输出:true
  • 限制:0<=<=100000 <= 节点个数 <= 10000

题解

  • Tips:先序遍历+包含判断+递归

  • 参考:https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/mian-shi-ti-26-shu-de-zi-jie-gou-xian-xu-bian-li-p/

  • 思路:

    • 第一步:在树A种找到和B的根节点的值一样的结点R(实质:树的遍历)
    • 第二步:判断树A中以R为根节点的子树是不是包含和树B一样的结构
  • 时间复杂度:O(MN),M和N分别为两棵树的节点数

  • 空间复杂度:O(M)

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

    class Solution(object):
    def isSubStructure(self, A, B):
    """
    :type A: TreeNode
    :type B: TreeNode
    :rtype: bool
    """
    if not (A and B):
    return False
    def dfs(A, B):
    if not B:
    return True
    if not A or A.val != B.val:
    return False
    return dfs(A.left, B.left) and dfs(A.right, B.right)
    return dfs(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)

二叉树的镜像

题目

  • 难度:简单

  • 题目(leetcode-面试题27):请完成一个函数,输入一个二叉树,该函数输出它的镜像。

  • 示例:

    例如输入:

    4
    / \
    2 7
    / \ / \
    1 3 6 9

    镜像输出:

    4
    / \
    7 2
    / \ / \
    9 6 3 1

    示例 1:
    输入:root = [4,2,7,1,3,6,9]
    输出:[4,7,2,9,6,3,1]
  • 限制:0<=<=10000 <= 节点个数 <= 1000

题解

  • Tips:求树的镜像的过程其实就是在遍历树的同时交换非叶结点的左右子结点。(递归 or 辅助栈)

  • 思路:前序遍历这棵树的每个结点,如果遍历到的结点有子结点,就交换它的两个子结点。当交换完所有非叶子节点的左右子结点之后,就得到了树的镜像。

  • 参考:https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/solution/mian-shi-ti-27-er-cha-shu-de-jing-xiang-di-gui-fu-/

  • 递归法

    • 根据二叉树镜像的定义,考虑递归遍历(dfs)二叉树,交换每个节点的左 / 右子节点,即可生成二叉树的镜像。
    • 递归解析:
      • 递归终止条件:当节点root为空的时候,返回null
      • 递推工作:
        • 初始化结点tmp,用于暂存root的左子结点
        • 开启递归右子结点,并将返回值给root的左子结点
        • 开启递归左子结点,并将返回值给root的右子结点
      • 返回当前结点root
  • 时间复杂度:O(N)

  • 空间复杂度:O(N)

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

    class Solution(object):
    def mirrorTree(self, root):
    """
    :type root: TreeNode
    :rtype: TreeNode
    """
    if not root:
    return root
    root.left, root.right = self.mirrorTree(root.right), self.mirrorTree(root.left)
    return root
  • 辅助栈:

    • 利用栈(或队列)遍历树的所有节点node ,并交换每个node的左 / 右子节点。
    • 算法流程:
      • 特例处理:当root为空,返回root
      • 初始化:栈,并加入根节点
      • 循环交换:当栈stack为空时跳出
        • 出栈:记为node
        • 添加子结点:将node的左右子结点入栈
        • 交换,交换node的左右子结点
    # Definition for a binary tree node.
    # class TreeNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None

    class Solution(object):
    def mirrorTree(self, root):
    """
    :type root: TreeNode
    :rtype: TreeNode
    """
    if not root:
    return root
    stack = [root]
    while stack:
    node = stack.pop()
    if node.left:
    stack.append(node.left)
    if node.right:
    stack.append(node.right)
    node.left, node.right = node.right, node.left
    return root

对称的二叉树

题目

  • 难度:简单

  • 题目(leetcode-面试题28):请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

  • 示例:

    例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

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

    但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
    / \
    2 2
    \ \
    3 3

    示例 1:
    输入:root = [1,2,2,3,4,4,3]
    输出:true

    示例 2:
    输入:root = [1,2,2,null,3,null,3]
    输出:false
  • 限制:0<=<=10000 <= 节点个数 <= 1000

题解

  • Tips:递归 or 队列

  • 参考:https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/solution/mian-shi-ti-28-dui-cheng-de-er-cha-shu-di-gui-qing/

    • 对称二叉树的定义:对于树中 任意两个对称节点 L和 R ,一定有:
      • L.val = R.val:即此两对称结点值相等
      • L.left.val = R.right.val:即L的左子结点和R的右子结点对称
      • L.right.val = R.left.val:即L的右子结点和R的左子结点对称
  • 思路:递归

    • 算法流程:
      • isSymmetric(root)
        • 特例处理:若根节点为空,则直接返回root
        • 返回值:recur(root.left,root.right)
      • recur(L, R)
        • 终止条件:
          • 当L和R同时越过叶结点,此树从顶至底的结点都对称,因此返回True
          • 当L和R中只有一个越过叶结点,此树不对称,因此返回False
          • 当节点L的值≠节点R的值,此树不对称,因此返回False
        • 递推工作:
          • 判断两节点 L.left和 R.right是否对称,即 recur(L.left, R.right)
          • 判断两节点 L.right和 R.left是否对称,即 recur(L.right, R.left)
        • 返回值: 两对节点都对称时,才是对称树,因此用与逻辑符 && 连接。
  • 时间复杂度:O(N)

  • 空间复杂度:O(N)

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

    class Solution(object):
    def isSymmetric(self, root):
    """
    :type root: TreeNode
    :rtype: bool
    """
    if not root:
    return True
    def recur(L, R):
    if not (L or R):
    return True
    if not (L and R) or L.val != R.val:
    return False
    return recur(L.left, R.right) and recur(L.right, R.left)
    return recur(root.left, root.right)
  • 思路:队列

    • 特例处理:如果root为空,返回True
    • 初始化:队列,并顺序加入root的左右结点
    • 循环判断:当队列为空时跳出
      • 出队列:依次记为left和right
      • 如果left和right都为空,说明穿过叶子节点,继续执行
      • 如果left或right其中一个为空,说明不对称,返回False
      • 如果left和right的值不相等,说明不对称,返回False
      • 入队:(成对加入)
        • 加入left的左节点和righ的右节点
        • 加入left的右节点和right的左节
    • 返回True
    # Definition for a binary tree node.
    # class TreeNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None

    class Solution(object):
    def isSymmetric(self, root):
    """
    :type root: TreeNode
    :rtype: bool
    """
    if not root:
    return True
    queue = [root.left, root.right]
    while queue:
    left = queue.pop(0)
    right = queue.pop(0)
    if not(left or right):
    continue
    if not(left and right) or left.val != right.val:
    return False
    queue.append(left.left)
    queue.append(right.right)
    queue.append(left.right)
    queue.append(right.left)
    return True

顺时针打印矩阵

题目

  • 难度:简单

  • 题目(leetcode-面试题29):输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

  • 示例:

    输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
    输出:[1,2,3,6,9,8,7,4,5]

    输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
    输出:[1,2,3,4,8,12,11,10,9,5,6,7]
  • 限制

    • 0 <= matrix.length <= 100
    • 0 <= matrix[i].length <= 100

题解

    • 参考:https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/solution/mian-shi-ti-29-shun-shi-zhen-da-yin-ju-zhen-she-di/
    • 剑指offer:
      • 当我们遇到一个复杂问题的时候,可以用图形来帮助我们思考。由于是以外圈到内圈的顺序依次打印,我们可以把矩阵想象成若干个圈,可以用一个循环来打印矩阵,每一次打印矩阵中的一个圈。
      • 分析循环结束的条件。假设这个矩阵的行数是rows,列数是columns。打印第一圈的左上角的坐标是(1,1),第二圈的左上角的坐标是(2,2),以此类推。我们注意到,左上角的坐标中行标和列标总是相同的,于是可以在矩阵中选取左上角为(start,start)的一圈作为我们分析的目标。
      • 对一个5 * 5的矩阵而言,最后一圈只有一个数字,对应的坐标为(2,2)。我们发现5 > 2 * 2。对于一个6 * 6的矩阵而言,最后一圈有4个数字,其左上角的坐标仍然为(2,2)。我们发现6 > 2 * 2依然成立。于是我们可以得出,让循环继续的条件是columns > startX * 2并且 rows > startX * 2。
      • 考虑如何打印一圈的功能。我们可以把打印一圈分为4步:第一步从左到右打印一行,第二步从上到下打印一列,第三步从右到左打印一行,第四步从下到上打印一列。每一步我们根据起始坐标和终止坐标用一个循环就能打印出一行或一列。不过值得注意的是,最后一圈有可能退化成只有一行,只有一列,甚至只有一个数字,因此打印这样的一圈就不再需要4步。
      • 分析打印时每一步的前提条件。第一步总是需要的,因为打印一圈至少有一步。如果只有一行,那么就不用第二步了。也就是需要第二步的前提条件是终止行号大于起始行号。需要第三步打印的前提条件是圈内至少有两行两列,也就是说除了要求终止行号大于起始行号之外,还要求终止列号大于起始列号。同理,需要打印第四步的前提条件是至少有三行两列,因此要求终止行号比起始起始行号至少大2,同时终止列号大于起始列号。
  • 时间复杂度:O(MN),M和N分别为矩阵的行列

  • 空间复杂度:O(1)

    class Solution(object):
    def spiralOrder(self, matrix):
    """
    :type matrix: List[List[int]]
    :rtype: List[int]
    """
    if not matrix:
    return []
    l, r, t, b, res = 0, len(matrix[0]) - 1, 0, len(matrix) - 1, []
    while True:
    for i in range(l, r + 1):
    res.append(matrix[t][i]) # left to right
    t += 1
    if t > b:
    break
    for i in range(t, b + 1):
    res.append(matrix[i][r]) # top to bottom
    r -= 1
    if l > r:
    break
    for i in range(r, l - 1, -1):
    res.append(matrix[b][i]) # right to left
    b -= 1
    if t > b:
    break
    for i in range(b, t - 1, -1):
    res.append(matrix[i][l]) # bottom to top
    l += 1
    if l > r:
    break
    return res

包含min函数的栈

题目

  • 难度:简单

  • 题目(leetcode-面试题30):定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

  • 示例:

    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.min(); --> 返回 -3.
    minStack.pop();
    minStack.top(); --> 返回 0.
    minStack.min(); --> 返回 -2.
  • 提示:各函数的调用总次数不超过 20000 次

题解

  • Tips:面试时,我们可以举例模拟压栈和弹出的几个数字,分析每次操作之后数据栈、辅助栈和最小值各是什么。让面试官更好地理解我们的思路。

  • 参考:https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution/mian-shi-ti-30-bao-han-minhan-shu-de-zhan-fu-zhu-z/

  • 思路:数据栈A压入数据,辅助栈B压入每次的最小元素(之前最小的元素和新压入栈的元素两者的较小值)

    • eg:首先往空的数据栈A里压入数字3,显然现在3是最小值,我们也把这个最小值压入辅助栈B。接下来往数据栈A里压入数字4,由于4大于之前的最小值3,因此仍然往辅助栈B里压入3。第三步继续往数据栈A里压入数字2,由于数字2小于之前的最小值3,因此我们把最小值更新为2,并把2压入辅助栈B。同样压入数字1时,也要更新最小值,并把新的最小值1压入辅助栈B。
  • 时间复杂度:O(1)

  • 空间复杂度:O(n)

    class MinStack(object):

    def __init__(self):
    """
    initialize your data structure here.
    """
    self.A = []
    self.B = []


    def push(self, x):
    """
    :type x: int
    :rtype: None
    """
    self.A.append(x)
    if not self.B or self.B[-1] >= x:
    self.B.append(x)

    def pop(self):
    """
    :rtype: None
    """
    y = self.A.pop()
    if y == self.B[-1]:
    return self.B.pop()

    def top(self):
    """
    :rtype: int
    """
    return self.A[-1]


    def min(self):
    """
    :rtype: int
    """
    return self.B[-1]

栈的压入、弹出序列

题目

  • 难度:中等

  • 题目(leetcode-面试题31):输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列 {1,2,3,4,5} 是某栈的压栈序列,序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列,但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

  • 示例:

    输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
    输出:true
    解释:我们可以按以下顺序执行:
    push(1), push(2), push(3), push(4), pop() -> 4,
    push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

    输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
    输出:false
    解释:1 不能在 2 之前弹出。
  • 提示:

    • 0 <= pushed.length == popped.length <= 1000
    • 0 <= pushed[i], popped[i] < 1000
    • pushed 是 popped 的排列

题解

  • Tips:辅助栈

    • 面试时,需要确定一个序列和弹出序列的长度是否一致,序列中数字是否有重复。
  • 思路:判断一个序列是不是栈的弹出序列的规律。如果下一个弹出的数字刚好是栈顶数字,那么直接弹出。如果一个弹出的数字不在栈顶,我们把压栈序列中还没有入栈的数字压入辅助栈,直到把下一个需要弹出的数字压入栈顶为止。如果所有的数字都压入栈了仍然没有找到下一个弹出的数字,那么该序列不可能是一个弹出序列。

    • 由于题目规定 栈的所有数字均不相等 ,因此在循环入栈中,每个元素出栈的位置的可能性是唯一的(若有重复数字,则具有多个可出栈的位置)。因而,在遇到 “栈顶元素 == 弹出序列的当前元素” 就应立即执行出栈。
  • 时间复杂度:O(N)

  • 空间复杂度:O(N)

    class Solution(object):
    def validateStackSequences(self, pushed, popped):
    """
    :type pushed: List[int]
    :type popped: List[int]
    :rtype: bool
    """
    stack, i = [], 0
    for num in pushed:
    stack.append(num) # num 入栈
    while stack and i < len(popped)and stack[-1] == popped[i]: # 循环判断与出栈
    stack.pop()
    i += 1
    return not stack

从上到下打印二叉树

题目

  • 难度:中等

  • 题目(leetcode-面试题32I):从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。

  • 示例:

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

    3
    / \
    9 20
    / \
    15 7

    返回:
    [3,9,20,15,7]
  • 提示:节点总数 <= 1000

题解

  • Tips

    • 队列
    • Python 中使用 collections 中的双端队列 deque() ,其 popleft() 方法可达到 O(1), 时间复杂度;列表 list 的 pop(0) 方法时间复杂度为 O(N) 。
    • BFS通常借助队列
  • 剑指offer:

    • 扩展:如何广度优先遍历一个有向图?这同样也可以基于队列实现。树是图的一种特殊退化形式,从上到下按层遍历二叉树,从本质上来说就是广度优先遍历二叉树
    • 举一反三:不管是广度优先遍历一个有向图还是一棵树,都要用到队列。第一步我们把起始起点(对树而言是根结点)放入队列。接下来每一次从队列的头部取出一个结点,遍历这个结点之后把它能到达的结点(对树而言是子结点)都依次放入队列。我们重复这个遍历过程,直到队列中的结点全部被遍历为止。
  • 思路:每一次打印一个结点的时候,如果该结点有子结点,则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点,重复前面的打印操作,直至队列中所有的结点都被打印出来为止。

  • 时间复杂度:O(N)

  • 空间复杂度:O(N)

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

    class Solution(object):
    def levelOrder(self, root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    if not root:
    return []
    queue = collections.deque()
    queue.append(root)
    tmp = []
    while queue:
    node = queue.popleft()
    if node:
    tmp.append(node.val)
    if node.left:
    queue.append(node.left)
    if node.right:
    queue.append(node.right)
    return tmp

从上到下打印二叉树II

题目

  • 难度:简单

  • 题目(leetcode-面试题32II):从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。

  • 示例:

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

    3
    / \
    9 20
    / \
    15 7

    返回其层次遍历结果:

    [
    [3],
    [9,20],
    [15,7]
    ]
  • 提示:节点总数 <= 1000

题解

  • 算法流程:

    • 特例处理:当前结点为空,则返回列表[]
    • 初始化: 打印结果列表 res = [] ,包含根节点的队列 queue = [root]
    • BFS 循环: 当队列 queue 为空时跳出;
      • 新建一个临时列表 tmp ,用于存储当前层打印结果;
      • 当前层打印循环: 循环次数为当前层节点数(即队列 queue 长度);
        • 出队: 队首元素出队,记为 node
        • 打印:node.val 添加至 tmp 尾部;
        • 添加子节点:node 的左(右)子节点不为空,则将左(右)子节点加入队列 queue
      • 将当前层结果 tmp 添加入 res
    • 返回值: 返回打印结果列表 res 即可。
  • 时间复杂度:O(N)

  • 空间复杂度:O(N)

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

    class Solution(object):
    def levelOrder(self, root):
    """
    :type root: TreeNode
    :rtype: List[List[int]]
    """
    if not root:
    return []
    queue = collections.deque()
    queue.append(root)
    res = []
    while queue:
    tmp = []
    for _ in range(len(queue)):
    node = queue.popleft()
    tmp.append(node.val)
    if node.left:
    queue.append(node.left)
    if node.right:
    queue.append(node.right)
    res.append(tmp)
    return res

从上到下打印二叉树III

题目

  • 难度:中等

  • 题目(leetcode-面试题32III):请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。

  • 示例:

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

    3
    / \
    9 20
    / \
    15 7

    返回其层次遍历结果:

    [
    [3],
    [20,9],
    [15,7]
    ]
  • 提示:节点总数 <= 1000

题解

  • 思路:之型打印二叉树,奇数层从左到右打印,偶数层从右到左打印,因此可以在面试题32II的基础上,判断层数是否是偶数层,如果是的话,把当前结点加在tmp头部,否则,加在尾部。或者,可以将偶数层的tmp结果倒序。

  • 时间复杂度:O(N)

  • 空间复杂度:O(N)

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

    class Solution(object):
    def levelOrder(self, root):
    """
    :type root: TreeNode
    :rtype: List[List[int]]
    """
    if not root:
    return []
    res, queue = [], collections.deque()
    queue.append(root)
    while queue:
    tmp = []
    for _ in range(len(queue)):
    node = queue.popleft()
    tmp.append(node.val)
    if node.left: queue.append(node.left)
    if node.right: queue.append(node.right)
    res.append(tmp[::-1] if len(res) % 2 else tmp)
    return res

二叉搜索树的后序遍历序列

题目

  • 难度:中等

  • 题目(leetcode-面试题33):输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

  • 示例:

    参考以下这颗二叉搜索树:

    5
    / \
    2 6
    / \
    1 3

    示例1:
    输入: [1,6,3,2,5]
    输出: false

    示例2:
    输入: [1,3,2,6,5]
    输出: true
  • 提示:数组长度 <= 1000

题解

  • Tips

    • 后序遍历定义:[ 左子树 | 右子树 | 根节点 ] ,即遍历顺序为 “左、右、根” 。
    • 二叉搜索树定义: 左子树中所有节点的值 <根节点的值;右子树中所有节点的值 > 根节点的值;其左、右子树也分别为二叉搜索树。
  • 思路:递归分治:根据二叉搜索树的定义,可以通过递归,判断所有子树的 正确性 (即其后序遍历是否满足二叉搜索树的定义) ,若所有子树都正确,则此序列为二叉搜索树的后序遍历。

    • 递归解析:
      • 终止条件:iji≥j,说明此子树结点数量≤1,无需判别正确性,因此直接返回true。
      • 递推工作:
        • 划分左右子树:遍历后序遍历[i,j]区间元素,寻找第一个大于根节点的节点,索引记为m。此时可划分出左子树区间[i,m-1],右子树区间[m,j-1],根节点索引j。
        • 判断是否为二叉搜索树:
          • 左子树区间[i,m-1]内的所有结点都应小于postorder[j]。而上一步划分左右子树的步骤,已经保证左子树区间的正确性,因此只需要判断右子树区间即可。
          • 右子树区间[m,j-1]内的所有结点都应大于postorder[j]。实现方式为遍历,当遇到小于等于postorder[j]的结点则跳出,否则可通过p=j判断是否为二叉搜索树。
      • 返回值:所有子树都需正确才可判定正确,因此使用 与逻辑符 &&连接
        • p = j:判断此树是否正确
        • recur(i, m-1):判断此树的左子树是否正确
        • recur(m, j - 1):判断此树的右子树是否正确
  • 时间复杂度:O(N^2)

  • 空间复杂度:O(N)

    class Solution(object):
    def verifyPostorder(self, postorder):
    """
    :type postorder: List[int]
    :rtype: bool
    """
    def recur(i, j):
    if i >= j:
    return True
    p = i
    while postorder[p] < postorder[j]:
    p += 1
    m = p
    while postorder[p] > postorder[j]:
    p += 1
    return p == j and recur(i, m - 1) and recur(m, j -1)
    return recur(0, len(postorder) - 1)
  • 思路2:单调辅助栈

    • 借助一个单调栈 stack存储值递增的节点;
    • 每当遇到值递减的节点 r_i,则通过出栈来更新节点 r_i 的父节点 root ;
    • 每轮判断 r_i和 root的值关系:
      • 若 r_i > root则说明不满足二叉搜索树定义,直接返回 false 。
      • 若 r_i < root则说明满足二叉搜索树定义,则继续遍历。
    • 算法流程:
      • 初始化: 单调栈 stack,父节点值 root = +∞ (初始值为正无穷大,可把树的根节点看为此无穷大节点的左孩子);
      • 倒序遍历 postorder:记每个节点为 r_i;
        • 判断: 若 r_i>root,说明此后序遍历序列不满足二叉搜索树定义,直接返回 false;
        • 更新父节点root,当栈不为空,且r_i < stack.pop()时,循环执行出栈,并将出栈结点赋给root
        • 入栈:将当前结点r_i入栈
      • 遍历完成,则说明满足二叉搜索树定义,返回true
  • 时间复杂度:O(N)

  • 空间复杂度:O(N)

    class Solution(object):
    def verifyPostorder(self, postorder):
    """
    :type postorder: List[int]
    :rtype: bool
    """
    stack, root = [], float("inf")
    for i in range(len(postorder) - 1, -1, -1):
    if postorder[i] > root:
    return False
    while(stack and postorder[i] < stack[-1]):
    root = stack.pop()
    stack.append(postorder[i])
    return True

二叉树中和为某一值的路径

题目

  • 难度:中等
  • 题目(leetcode-面试题34):输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

题解

  • 剑指offer:当用前序遍历的方式访问到某一结点时,我们把该结点添加到路径上,并累加该结点的值。如果该结点为叶结点并且路径中结点的值得和刚好等于输入的整数,则当前的路径符合要求,我们把它打印出来。如果当前结点不是叶结点,则继续访问它的子结点。当前结点访问结束后,递归函数将自动回到它的父节点。因此我们在函数退出之前要再路径上删除当前结点并减去当前结点的值,以确保返回父节点时路径刚好是从根节点到父节点的路径。
  • 参考:https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/solution/mian-shi-ti-34-er-cha-shu-zhong-he-wei-mou-yi-zh-5/
  • Tips:先序遍历+路径记录

  • 算法流程:

    • pathSum(root, sum) 函数:
      • 初始化: 结果列表 res ,路径列表 path
      • 返回值: 返回 res 即可。
    • recur(root, tar) 函数:
      • 递推参数: 当前节点 root ,当前目标值 tar
      • 终止条件: 若节点 root 为空,则直接返回。
      • 递推工作
        • 路径更新: 将当前节点值 root.val 加入路径 path
        • 目标值更新: tar = tar - root.val(即目标值 tarsum 减至 00 );
        • 路径记录: 当 ① root 为叶节点 ② 路径和等于目标值 ,则将此路径 path 加入 res
        • 先序遍历: 递归左 / 右子节点。
        • 路径恢复: 向上回溯前,需要将当前节点从路径 path 中删除,即执行 path.pop()
  • 值得注意的是,记录路径时若直接执行 res.append(path) ,则是将 path 对象加入了 res ;后续 path 改变时, res 中的 path 对象也会随之改变。正确做法:res.append(list(path)) ,相当于复制了一个 path 并加入到 res 。

  • 时间复杂度:O(N)

  • 空间复杂度:O(N)

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

    class Solution(object):
    def pathSum(self, root, sum):
    """
    :type root: TreeNode
    :type sum: int
    :rtype: List[List[int]]
    """
    res, path = [], []

    def recur(root, tar):
    if not root:
    return
    path.append(root.val)
    tar -= root.val
    if tar == 0 and not root.left and not root.right:
    res.append(list(path))
    recur(root.left, tar)
    recur(root.right, tar)
    path.pop()
    recur(root, sum)
    return res

复杂链表的复制

题目

  • 难度:中等

  • 题目(leetcode-面试题35:请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。

  • 示例:

    输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
    输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

    输入:head = [[1,1],[2,1]]
    输出:[[1,1],[2,1]]

    输入:head = [[3,null],[3,0],[3,null]]
    输出:[[3,null],[3,0],[3,null]]

    输入:head = []
    输出:[]
    解释:给定的链表为空(空指针),因此返回 null。
  • 提示:

    • -10000 <= Node.val <= 10000
    • Node.random 为空(null)或指向链表中的节点。
    • 节点数目不超过 1000 。

题解

  • Tips:在这里,复制的意思是指 深拷贝(Deep Copy),类似我们常用的“复制粘贴”,事实上,与此对应的还有 浅拷贝,它们的区别是:

    • 浅拷贝只复制指向某个对象的指针,而不复制对象本身,新旧对象还是共享同一块内存
    • 深拷贝会另外创造一个一模一样的对象,新对象跟原对象不共享内存,修改新对象不会改到原对象
  • 思路:这里考虑深度优先搜索和优化迭代两种方法

    • 深度优先搜索(DFS)

      • 从头结点head开始拷贝

      • 由于一个结点可能被多个指针指到,因此如果该结点已被拷贝,则不需要重复拷贝;

      • 如果还没拷贝该结点,则创建一个新的结点进行拷贝,并将拷贝过的结点保存在哈希表中;

      • 使用递归拷贝所有的 next 结点,再递归拷贝所有的 random 结点。

      • 时间复杂度:O(N)

      • 空间复杂度:O(N)

        """
        # Definition for a Node.
        class Node:
        def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random
        """
        class Solution(object):
        def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        visited = {}
        def dfs(head):
        if not head:
        return None
        if head in visited:
        return visited[head]

        #创建新结点
        copy = Node(head.val, None, None)
        visited[head] = copy
        copy.next = dfs(head.next)
        copy.random = dfs(head.random)
        return copy
        return dfs(head)
    • 优化迭代

      • 不使用哈希表的额外空间来保存已经拷贝过的结点,而是将链表进行拓展,在每个链表结点的旁边拷贝,比如 A->B->C 变成 A->A’->B->B’->C->C’,然后将拷贝的结点分离出来变成 A->B->C和A’->B’->C’,最后返回 A’->B’->C’。

      • 时间复杂度:O(N)

      • 空间复杂度:O(1)

        """
        # Definition for a Node.
        class Node:
        def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random
        """
        class Solution(object):
        def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
        return head
        cur = head
        while cur:
        new_node = Node(cur.val,None,None) # 克隆新结点
        new_node.next = cur.next
        cur.next = new_node # 克隆新结点在cur 后面
        cur = new_node.next # 移动到下一个要克隆的点
        cur = head

        while cur: # 链接random
        cur.next.random = cur.random.next if cur.random else None
        cur = cur.next.next

        cur_old_list = head # 将两个链表分开
        cur_new_list = head.next
        new_head = head.next
        while cur_old_list:
        cur_old_list.next = cur_old_list.next.next
        cur_new_list.next = cur_new_list.next.next if cur_new_list.next else None
        cur_old_list = cur_old_list.next
        cur_new_list = cur_new_list.next
        return new_head

二叉搜索树与双向链表

题目

  • 难度:中等

  • 题目(leetcode-面试题36):输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。

    输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。

    特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

题解

  • Tips:中序遍历

  • 参考:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solution/mian-shi-ti-36-er-cha-sou-suo-shu-yu-shuang-xian-5/

  • 思想:

    • 本文解法基于性质:二叉搜索树的中序遍历为 递增序列
    • 将 二叉搜索树 转换成一个 “排序的循环双向链表” ,其中包含三个要素:
      • 排序链表: 节点应从小到大排序,因此应使用 中序遍历 “从小到大”访问树的节点;
      • 双向链表:在构建相邻节点(设前驱节点pre,当前结点cur)关系时,应该满足pre.right = curcur.left = pre
      • 循环链表: 设链表头节点 head 和尾节点 tail,则应构建 head.left = tailtail.right = head。
  • 算法流程:

    • dfs(cur): 递归法中序遍历;
      • 终止条件: 当节点 cur为空,代表越过叶节点,直接返回;
      • 递归左子树,即 dfs(cur.left)
      • 构建链表:
        • 当 pre为空时: 代表正在访问链表头节点,记为 head 。
        • 当 pre 不为空时: 修改双向节点引用,即 pre.right = cur, cur.left = pre。
        • 保存cur:更新pre = cur,即节点cur是后继节点的pre
      • 递归右子树,即dfs(cur.left)
    • treeToDoublyList(root):
      • 特例处理: 若节点 root 为空,则直接返回;
      • 初始化: 空节点 pre ;
      • 转化为双向链表: 调用 dfs(root)
      • 构建循环链表: 中序遍历完成后,head指向头节点, pre指向尾节点,因此修改 head和 pre 的双向节点引用即可。
      • 返回值: 返回链表的头节点 head 即可。
  • 时间复杂度:O(N)

  • 空间复杂度:O(N)

    """
    # Definition for a Node.
    class Node(object):
    def __init__(self, val, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
    """
    class Solution(object):
    def treeToDoublyList(self, root):
    """
    :type root: Node
    :rtype: Node
    """
    def dfs(cur):
    if not cur:
    return
    dfs(cur.left) # 递归左子树
    if self.pre: # 修改节点引用
    self.pre.right, cur.left = cur, self.pre
    else: # 记录头节点
    self.head = cur
    self.pre = cur # 保存 cur
    dfs(cur.right) # 递归右子树

    if not root:
    return
    self.pre = None
    dfs(root)
    self.head.left, self.pre.right = self.pre, self.head
    return self.head
    # 牛客网解答
    # -*- coding:utf-8 -*-
    # class TreeNode:
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None
    class Solution:
    def Convert(self, pRootOfTree):
    # write code here
    if not pRootOfTree:
    return pRootOfTree
    if not pRootOfTree.left and not pRootOfTree.right:
    return pRootOfTree
    # 处理左子树
    self.Convert(pRootOfTree.left)
    left=pRootOfTree.left

    # 连接根与左子树最大结点
    if left:
    while(left.right):
    left=left.right
    pRootOfTree.left,left.right=left,pRootOfTree

    # 处理右子树
    self.Convert(pRootOfTree.right)
    right=pRootOfTree.right

    # 连接根与右子树最小结点
    if right:
    while(right.left):
    right=right.left
    pRootOfTree.right,right.left=right,pRootOfTree

    while(pRootOfTree.left):
    pRootOfTree=pRootOfTree.left
    return pRootOfTree

序列化二叉树

题目

  • 难度:困难

  • 题目(leetcode-面试题37):请实现两个函数,分别用来序列化和反序列化二叉树。

  • 示例:

    你可以将以下二叉树:

    1
    / \
    2 3
    / \
    4 5

    序列化为 "[1,2,3,null,null,4,5]"

题解

  • Tips:层序遍历 + BFS

  • 思路:

    • 序列化:借助队列,对二叉树做层序遍历,并将越过叶节点的 null也打印出来。
      • 特例处理:若root为空,直接返回空列表
      • 初始化:队列queue(包含根节点root);序列化列表res
      • 层序遍历:当queue为空时跳出:
        • 节点出队,记为node
        • 若node不为空,① 打印字符串 node.val,② 将左、右子节点加入 queue ;
        • 否则(若 node为空):打印字符串 "null"
      • 返回值: 拼接列表(用 ',' 隔开,首尾添加中括号)。
      • 时间复杂度:O(N)
      • 空间复杂度:O(N)
    • 反序列化:利用队列按层构建二叉树,借助一个指针 i指向节点 node的左、右子节点,每构建一个 node 的左、右子节点,指针 i就向右移动 1 位。
      • 特例处理:若data为空,直接返回null
      • 初始化: 序列化列表 vals(先去掉首尾中括号,再用逗号隔开),指针 i = 1,根节点 root(值为 vals[0] ),队列 queue(包含 root);
      • 按层构建:当queue为空时跳出:
        • 节点出队,记为node
        • 构建 node 的左子节点:node.left的值为 vals[i],并将 node.left入队;
        • 执行 i+=1 ;
        • 构建 node 的右子节点:node.right的值为 vals[i] ,并将 node.right入队;
        • 执行 i+=1 ;
      • 返回值: 返回根节点 root 即可
      • 时间复杂度:O(N)
      • 空间复杂度:O(N)
    # Definition for a binary tree node.
    # class TreeNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None

    class Codec:
    def serialize(self, root):
    if not root:
    return "[]"
    queue = collections.deque()
    queue.append(root)
    res = []
    while queue:
    node = queue.popleft()
    if node:
    res.append(str(node.val))
    queue.append(node.left)
    queue.append(node.right)
    else:
    res.append("null")
    return '[' + ','.join(res) + ']'

    def deserialize(self, data):
    if data == "[]":
    return
    vals, i = data[1:-1].split(','), 1
    root = TreeNode(int(vals[0]))
    queue = collections.deque()
    queue.append(root)
    while queue:
    node = queue.popleft()
    if vals[i] != "null":
    node.left = TreeNode(int(vals[i]))
    queue.append(node.left)
    i += 1
    if vals[i] != "null":
    node.right = TreeNode(int(vals[i]))
    queue.append(node.right)
    i += 1
    return root

字符串的排列

题目

  • 难度:中等

  • 题目(leetcode-面试题38):输入一个字符串,打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

  • 示例:

    输入:s = "abc"
    输出:["abc","acb","bac","bca","cab","cba"]
  • 限制:1 <= s 的长度 <= 8

题解

  • 思路:

    • 求所有可能出现在第一个位置的字符,即把第一个字符和后面所有的字符进行交换
    • 固定第一个字符,求后面所有字符的排列,这时候,可以把后面的所有字符分为两部分,后面字符的第一个字符,以及这个字符之后的所有字符,然后把第一个字符逐一和它后面的字符交换。
  • 时间复杂度:O(N!)

  • 空间复杂度:O(N^2)

    class Solution(object):
    def permutation(self, s):
    """
    :type s: str
    :rtype: List[str]
    """
    n = len(s)
    if n == 1:
    return [s]
    else:
    res = []
    for i in range(n):
    ch = s[i] #取出s中每一个字符
    dic = s[:i] + s[i + 1 :]
    for x in self.permutation(dic):
    res.append(ch + x) #将ch 和子问题的解依次组合
    return list(set(res))
  • 牛客网

    • 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
    • 输入描述:输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
    # -*- coding:utf-8 -*-
    class Solution:
    def Permutation(self, ss):
    # write code here
    n = len(ss)
    if n == 1:
    return [ss]
    if n < 1 or n > 9:
    return []
    res = []
    for i in range(n):
    ch = ss[i]
    tmp = ss[:i] + ss[i + 1 :]
    for x in self.Permutation(tmp):
    res.append(ch + x)
    return sorted(list(set(res)))

数组中出现次数超过一半的数字

题目

  • 难度:简单

  • 题目(leetcode-面试题39):数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

    你可以假设数组是非空的,并且给定的数组总是存在多数元素。

  • 示例:

    输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
    输出: 2
  • 限制:1 <= 数组长度 <= 50000

题解

  • Tips:面试时,要注意以下问题:

    • 是否可以修改数组?
    • 特例考虑,数组为空,或数组中不存在元素出现的次数超过数组长度一半
  • 思路:有三种思路

    • 第一种思路,对数组排序,数组n/2位置就是所求的数字。
      • 时间复杂度:O(nlogn)
      • 空间复杂度:O(1)
    • 第二种思路,哈希表,遍历一遍数组,记录每个元素出现的次数,返回次数超过数组长度一半的数字
      • 时间复杂度:O(n)
      • 空间复杂度:O(n)
    • 第三种思路,投票法,数组中有一个数字出现的次数超过数组长度的一半,也就是说它出现的次数比其他所有数字出现次数的和还要多。因此,我们可以考虑在遍历数组的时候保存两个值:一个是数组中的一个数字,一个是次数。当我们遍历到下一个数字的时候,如果下一个数字和我们之前保存的数字相同,则次数加1;如果下一个数字和我们之前保存的数字不同,则次数减一。如果次数为零,我们需要保存下一个数字,并把次数设置为1。由于我们要找的数字出现的次数比其他所有数字出现的次数和要多,那么要找的数字肯定是最后一次把次数设为1时的对应数字。
      • 时间复杂度:O(n)
      • 空间复杂度:O(1)
    #投票法
    class Solution(object):
    def majorityElement(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
    return
    vote = 0
    count = 0
    for num in nums:
    if vote == 0:
    x = num
    vote += 1 if num == x else -1
    for num in nums:
    if num == x:
    count += 1
    return x if count > len(nums) // 2 else 0
    #哈希表
    # -*- coding:utf-8 -*-
    class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
    # write code here
    dic = {}
    for num in numbers:
    if num in dic:
    dic[num] += 1
    else:
    dic[num] = 1
    if dic[num] > len(numbers) // 2:
    return num
    return 0

最小的k个数

题目

  • 难度:简单

  • 题目(leetcode-面试题40):输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

  • 示例:

    输入:arr = [3,2,1], k = 2
    输出:[1,2] 或者 [2,1]

    输入:arr = [0,1,2,1], k = 1
    输出:[0]
  • 限制:

    • 0 <= k <= arr.length <= 10000
    • 0 <= arr[i] <= 10000

题解(排序)

文章作者: Lesy
文章链接: https://lesylin.com/2020/06/02/%E5%89%91%E6%8C%87offer/
文章声明: 转载请注明文章链接
打赏
  • 微信
  • 支付宝

Comment