目录
  1. 1. 数据流中的中位数
    1. 1.1. 题目
    2. 1.2. 题解
  2. 2. 连续子数组的最大和
    1. 2.1. 题目
    2. 2.2. 题解
  3. 3. 1~n整数中1出现的次数
    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. 题目
    2. 8.2. 题解
  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. 在排序数组中查找数字I
    1. 13.1. 题目
    2. 13.2. 题解
  14. 14. 0~n-1中缺失的数字
    1. 14.1. 题目
    2. 14.2. 题解
  15. 15. 二叉搜索树第k大节点
    1. 15.1. 题目
    2. 15.2. 题解
  16. 16. 二叉树的深度
    1. 16.1. 题目
    2. 16.2. 题解
  17. 17. 平衡二叉树
    1. 17.1. 题目
    2. 17.2. 题解
  18. 18. 数组中数字出现的次数
    1. 18.1. 题目
    2. 18.2. 题解
  19. 19. 数组中数字出现的次数II
    1. 19.1. 题目
    2. 19.2. 题解
  20. 20. 和为s的两个数字
    1. 20.1. 题目
    2. 20.2. 题解
  21. 21. 和为s的连续正数序列
    1. 21.1. 题目
    2. 21.2. 题解
  22. 22. 翻转单词顺序
    1. 22.1. 题目
    2. 22.2. 题解
  23. 23. 左旋转字符串
    1. 23.1. 题目
    2. 23.2. 题解
  24. 24. 滑动窗口的最大值
    1. 24.1. 题目
    2. 24.2. 题解
  25. 25. 队列的最大值
    1. 25.1. 题目
    2. 25.2. 题解
  26. 26. n个骰子的点数
    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. 求1+2+…+n
    1. 30.1. 题目
    2. 30.2. 题解
  31. 31. 不用加减乘除做加法
    1. 31.1. 题目
    2. 31.2. 题解
  32. 32. 构建乘积数组
    1. 32.1. 题目
    2. 32.2. 题解
  33. 33. 把字符串转换成整数
    1. 33.1. 题目
    2. 33.2. 题解
  34. 34. 二叉搜索树的最近公共祖先
    1. 34.1. 题目
    2. 34.2. 题解
  35. 35. 二叉树的最近公共祖先
    1. 35.1. 题目
    2. 35.2. 题解
剑指offer1

数据流中的中位数

题目

  • 难度:困难

  • 题目(leetcode-面试题41):如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

  • 示例:

    例如,

    [2,3,4] 的中位数是 3

    [2,3] 的中位数是 (2 + 3) / 2 = 2.5

    设计一个支持以下两种操作的数据结构:

    void addNum(int num) - 从数据流中添加一个整数到数据结构中。
    double findMedian() - 返回目前所有元素的中位数。

    示例1
    输入:
    ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
    [[],[1],[2],[],[3],[]]
    输出:[null,null,null,1.50000,null,2.00000]

    示例2
    输入:
    ["MedianFinder","addNum","findMedian","addNum","findMedian"]
    [[],[2],[],[3],[]]
    输出:[null,null,2.00000,null,2.50000]
  • 限制:最多会对 addNum、findMedia进行 50000 次调用。

题解

  • Tips:优先队列/堆

    • 什么是优先队列
      • 优先队列也是一种队列,与队列不同的是,优先队列不再遵循先入先出的原则,而是分成了两种情况:
        • 最大优先队列,无论入队顺序,当前最大的元素优先出队。
        • 最小优先队列,无论入队顺序,当前最小的元素优先出队。
      • 事实上,优先队列的本质上是一个堆,它是一棵完全二叉树,分为小顶堆和大顶堆:
        • 小顶堆是每一个根节点小于左右子节点的完全二叉树,堆顶元素最小,对应最小优先队列;
        • 大顶堆是每一个根节点大于左右子节点的完全二叉树,堆顶元素最大,对应最大优先队列;
      • 由于删除堆顶元素时的时间复杂度为 O(logN),因此在优先队列中入队和出队操作的时间复杂度也是 O(logN)。
    • 注意:Python 中没有大顶堆,只能将值取负保存在小顶堆来模拟。为了方便理解,将堆用优先队列表示。即Python 中 heapq 模块是小顶堆。实现 大顶堆 方法: 小顶堆的插入和弹出操作均将元素 取反 即可。
  • 思路:

    • 首先,建立一个小顶堆A和大顶堆B,各保存列表的一半元素,且规定:
      • A保存较大的一半,长度为N/2(N为偶数)或(N+1)/2(N为奇数)
      • B保存较小的一半,长度为N/2(N为偶数)或(N+1)/2(N为奇数)
    • 然后,中位数可仅根据A,B的堆顶元素计算得到。
      • 小顶堆A(存储较大的一半):am,am1,...,a3,a2,a1a_m,a_{m-1},...,a_3,a_2,a_1a1a_1是堆顶。
      • 大顶堆B(存储较小的一半):b1,b2,b3,...,bn1,bnb1,b2,b3,...,b_{n-1},b_nb1b_1是堆顶。
    • 设共有N = m + n个元素,规定添加元素时保证:
      • m = n + 1 = (N + 1)/ 2 (N为奇数)
      • m = n = N / 2(N为偶数)
      • 当m≠n,中位数是a1
      • 当m=n,中位数是(a1 + b1)/ 2
  • 算法流程:

    • 设元素总数为 N = m + n ,其中 m和 n分别为 A和 B中的元素个数。
    • addNum(num) 函数
      1. 当 m = n(即 N为 偶数):需向 A添加一个元素。实现方法:将新元素 num插入至 B ,再将 B堆顶元素插入至 A。
      2. 当m≠n(即N为奇数):需向B添加一个元素。实现方法将新元素插入至A,再将A堆顶元素插入至B。
        • 假设插入数字 num遇到情况 1. 。由于 num可能属于 “较小的一半” (即属于 B ),因此不能将 nums 直接插入至 A 。而应先将 num 插入至 B,再将 B 堆顶元素插入至 A 。这样就可以始终保持 A 保存较大一半、 B保存较小一半。
    • findMedian() 函数:
      • 当m≠n,(N为奇数):则中位数是A堆顶的元素
      • 当m=n,(N为偶数):则中位数是(A堆顶元素 + B堆顶元素) / 2
  • 时间复杂度:

    • 查找中位数O(1):获取堆顶元素使用O(1)时间
    • 添加数字O(logN):堆的插入和弹出操作需要O(logN)时间
  • 空间复杂度:O(N)

    from heapq import *
    class MedianFinder(object):

    def __init__(self):
    """
    initialize your data structure here.
    """
    self.A = [] #小顶堆,保存较大的一半
    self.B = [] #大顶堆,保存较小的一半

    def addNum(self, num):
    """
    :type num: int
    :rtype: None
    """
    if len(self.A) != len(self.B):
    heappush(self.B, -heappushpop(self.A, num))
    else:
    heappush(self.A, -heappushpop(self.B, -num))

    def findMedian(self):
    """
    :rtype: float
    """
    return self.A[0] if len(self.A) != len(self.B) else (self.A[0] - self.B[0]) / 2.0
  • 牛客网python写法,GetMedian需要加个参数,否则python版会报错。

    # -*- coding:utf-8 -*-
    from heapq import *
    class Solution:
    def __init__(self):
    self.min_heap = [] #小顶堆,保存较大的一半
    self.max_heap = [] #大顶堆,保存较小的一半
    def Insert(self, num):
    # write code here
    if len(self.min_heap) != len(self.max_heap):
    heappush(self.max_heap, -heappushpop(self.min_heap, num))
    else:
    heappush(self.min_heap, -heappushpop(self.max_heap, -num))
    def GetMedian(self, n = None):
    # write code here
    return self.min_heap[0] if len(self.min_heap) != len(self.max_heap) else (self.min_heap[0] - self.max_heap[0]) / 2.0

连续子数组的最大和

题目

  • 难度:简单

  • 题目(leetcode-面试题42):输入一个整型数组,数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

    要求时间复杂度为O(n)。

  • 示例:

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

    • 1 <= arr.length <= 10^5
    • -100 <= arr[i] <= 100

题解

  • Tips:动态规划

  • 参考:https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/mian-shi-ti-42-lian-xu-zi-shu-zu-de-zui-da-he-do-2/

  • 动态规划解析:

    • 状态定义:设动态规划列表dp,dp[i]代表以元素nums[i]为结尾的连续子数组最大和。
      • 为何定义最大和 dp[i]中必须包含元素 nums[i]:保证 dp[i]递推到 dp[i+1] 的正确性;如果不包含 nums[i] ,递推时则不满足题目的 连续子数组 要求。
    • 转移方程:若dp[i-1]≤0,说明dp[i -1]对dp[i]产生负贡献,即dp[i-1] + nums[i]还不如nums[i]本身大。
      • 当dp[i-1]≤ 0时:执行dp[i] = nums[i]
      • 当dp[i-1]>0时:执行dp[i] = dp[i-1] + nums[i]
    • 初始状态:dp[0] = nums[0],即以nums[0]结尾的连续子数组最大和为 nums[0]。
    • 返回值: 返回 dp 列表中的最大值,代表全局最大值。
  • 时间复杂度:O(n)

  • 空间复杂度:O(1)

    class Solution(object):
    def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    max_sum = nums[0] #保存连续子数组最大和
    cur_sum = nums[0] #保存当前连续子数组最大和
    for i in range(1,len(nums)):
    if nums[i] > cur_sum + nums[i]:
    cur_sum = nums[i]
    else:
    cur_sum = cur_sum + nums[i]
    max_sum = max(cur_sum, max_sum)
    return max_sum
    #动态规划分析写法
    class Solution(object):
    def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    for i in range(1, len(nums)):
    nums[i] += max(nums[i - 1], 0)
    return max(nums)

1~n整数中1出现的次数

题目

  • 难度:中等

  • 题目(leetcode-面试题43):输入一个整数 n ,求1~n这n个整数的十进制表示中1出现的次数。

    例如,输入12,1~12这些整数中包含1 的数字有1、10、11和12,1一共出现了5次。

  • 示例:

    输入:n = 12
    输出:5

    输入:n = 13
    输出:6
  • 限制:1n<2311 ≤ n < 2^{31}

题解

  • Tips:数字规律 + 递归

  • 剑指offer:

    • 用一个稍微大一点的数字:21345为例。我们把从1到21345的所有数字分为两段,一段是从1到1345,另一段是从1346到21345。
      • 原因:因为把21345的最高位去掉就变成1345,便于采用递归思路。
    • 先看从1346到21345中1出现的次数。1的出现分为两种情况。
      • 首先分析1出现在最高位(例子是万位)的情况。从1346到21345的数字中,1出现在10000~19999这10000个数字的万位,一共出现了10000(10410^4)个。
        • 值得注意的是,并不是对所有5位数而言在万位出现的次数都是10000个。对于万位是1的数字比如输入12345,1只出现在10000~12345的万位,出现的次数不是10000次,而是2346次,也就是除去最高数字之后剩下的数字再加上1(即2345+1=2346次)
      • 接着分析1出现在除最高位之外的其他四位数中的情况。例子中134621345这20000个数字中后4位中1出现的次数是2000次。由于最高位是2,我们可以再把1345621345分为两段,134611345和1134621345。每一段剩下4位数字中,选择其中其中一位是1,其余三位可以在0~9这10个数字中任意选择,因此根据排列组合原则,总共出现的次数是2000次。
      • 从1~1345中1的出现次数,可以用递归求得。

    参考:https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/pythondi-gui-by-rainiee-pan/

  • 时间复杂度:O(logn),循环内的计算操作使用 O(1)时间;循环次数为数字 n的位数,即log10nlog_{10}n

  • 空间复杂度:O(1)

    class Solution(object):
    def countDigitOne(self, n):
    """
    :type n: int
    :rtype: int
    """
    if n<=0:
    return 0
    num_s = str(n)
    high = int(num_s[0])
    Pow = 10 ** (len(num_s) - 1)
    last = n - high * Pow

    if high == 1:
    return self.countDigitOne(Pow - 1) + self.countDigitOne(last) + last + 1
    else:
    return Pow + high * self.countDigitOne(Pow - 1) + self.countDigitOne(last)
  • 第一个return:举例:1234,countDigitOne(pow-1)表示 0-999 出现过多少次 1,countDigitOne(last)指 1000-1234 后三位出现过多少次 1(与 0-234 出现的次数相同),last 表示 1001-1234 最高位的 1 出现了多少次 1,最后一个 1 表示 1000 这个数最高位的 1。

  • 第二个return: 举例:2234 ,high*self.countDigitOne(pow-1)就是指,从 1~999 以及 1001~1999 这两个阶段后三位出现了多少次 1,self.countDigitOne(last)是指从 2000 到 2234 出现了多少次 1(和 0~234 相同,因为首位不为 1),Pow 指是指从 1000~1999 最高位一共出现了 1000 次 1

数字序列中某一位的数字

题目

  • 难度:中等

  • 题目(leetcode-面试题44):数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位是4,等等。

    请写一个函数,求任意第n位对应的数字。

  • 示例:

    输入:n = 3
    输出:3

    输入:n = 11
    输出:0
  • 限制:0 <= n < 2^31

题解

  • Tips:数字规律 + 迭代+求整/求余

  • 参考:

  • 思路:

    • 规律:

      123456789 1011…9899 100101…998999
      9个数 90个数 900个数
      9*1位 90*2位 900*3位
    • 对于第 n 位对应的数字,我们令这个数字对应的数为 target,然后分三步进行。

      1. 首先找到这个数字对应的数是几位数,用 digits 表示;
      2. 然后确定这个对应的数的数值 target
      3. 最后确定返回值是 target 中的哪个数字。
    • 举例:输入365

      • 经过第一步计算我们可以得到第365个数字表示的是三位数,digits = 3n = 365 - 9 - 90*2 = 176。这时n = 176表示目标数字是三位数中的第176个数字。
      • 我们设目标数字所在的数为 number,计算得到 number=100+176/3=158,idx 是目标数字在 number 中的索引,如果 idx = 0,表示目标数字是 number 中的最后一个数字。
      • 根据步骤2,我们可以计算得到 idx = n % digits = 176 % 3 = 2,说明目标数字应该是 number = 158 中的第二个数字,即输出为 5。
    • 掌握了方法之后可以对代码进行简化,思路与之前一样,这里注意的是 first_num 表示每组数的第一个数。即1位数的组的1,二位数的组的10,三位数的组的100…

  • 时间复杂度:O(logn)

  • 空间复杂度:O(logn),将数字转为字符串需要O(logn)

    class Solution(object):
    def findNthDigit(self, n):
    """
    :type n: int
    :rtype: int
    """
    digit, start, count = 1, 1, 9 #digit是位数+=1、start是起始数字 = start*10、count是数位数量=9*digit*start
    while n > count: # 1. 确定n所在数字的位数,循环执行n减去一位数、两位数的数位数量,因此n是从start开始计数的
    n -= count
    start *= 10
    digit += 1
    count = 9 * start * digit # 结论:所求数位①在某个digit位数中;②为从数字start开始的第n个数位。
    num = start + (n - 1) // digit # 2.确定所求数位所在的数字,结论:所求数位在数字 num中,start为第0个数
    return int(str(num)[(n - 1) % digit]) # 3.确定所求数位在num的哪一数位,数字的首个数位为第0位,所求数位是 res

把数组排成最小的数

题目

  • 难度:中等

  • 题目(leetcode-面试题45):输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

  • 示例:

    输入: [10,2]
    输出: "102"

    输入: [3,30,34,5,9]
    输出: "3033459"
  • 提示:0 < nums.length <= 100

题解

  • Tips:排序规则

  • 剑指offer:

    • 根据题目要求,两个数字m和n能拼接成数字mn和nm。如果mn<nm,那么我们应该打印出mn,也就是m应该排在n的前面,我们定义此时m小于n;反之,如果nm<mn,我们定义n小于m。如果mn=nm,m等于n。在下文中符号"<",">“和”="表示常规意义的数值的大小关系,而文字“大于”、“小于”和等于表示我们新定义的大小关系。
    • 接下来考虑怎么去拼接数字,即给出数字m和n,怎么得到数字mn和nm并比较它们的大小。直接用数值计算不难办到,但需要考虑到一个潜在的问题就是m和n都在int能表达的范围内,但把它们拼起来的数字mn和nm用int表示就有可能溢出了,所以还隐藏大数问题。
    • 一个非常直观的解决大数问题的方法就是把数字转换成字符串。另外,由于把数字m和n拼接起来得到mn和nm,它们的位数肯定是相同的,因此比较它们的大小只需要按照字符串大小的比较规则就可以了

    参考:https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solution/mian-shi-ti-45-ba-shu-zu-pai-cheng-zui-xiao-de-s-4/

  • 思路:

    • 特例判断:当数组为空,返回空字符串
    • 将数组每个元素依次转换为字符串
    • 两两组合,小的放前面,再拼接起来,如5+3>3+5,把3放5前面
  • 时间复杂度:O(N^2)

  • 空间复杂度:O(N)

    class Solution(object):
    def minNumber(self, nums):
    """
    :type nums: List[int]
    :rtype: str
    """
    n = len(nums)
    if n == 0:
    return ""
    for i in range(n):
    nums[i] = str(nums[i])
    for i in range(n):
    for j in range(i + 1, n):
    if nums[i] + nums[j] > nums[j] + nums[i]:
    nums[i], nums[j] = nums[j], nums[i]
    return "".join(nums)

把数字翻译成字符串

题目

  • 难度:中等

  • 题目(leetcode-面试题46):给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。

  • 示例:

    输入: 12258
    输出: 5
    解释: 12258有5种不同的翻译,分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
  • 提示:0 <= num < 2^31

题解

  • Tips:动态规划

  • 参考:https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/mian-shi-ti-46-ba-shu-zi-fan-yi-cheng-zi-fu-chua-6/

  • 动态规划解析:

    • 记数字num第i位数字为xix_i,数字num的位数为n
      • 例如,num=12258,n=5,xi=1x_i=1
    • 状态定义:设动态规划列表 dp ,dp[i]代表以 xix_i为结尾的数字的翻译方案数量。
    • 转移方程:若xix_ixi1x_{i-1}组成的两位数字可以被翻译,则dp[i]=dp[i1]+dp[i2]dp[i] = dp[i - 1] + dp[i - 2],否则,dp[i]=dp[i1]dp[i] = dp[i - 1]
      • 可被翻译的两位数区间:当xi1=0x_{i-1} = 0时,组成的两位数是无法被翻译的,(例如:00,01…),因此区间为[10,25]。
      • dp[i]=dp[i1]+dp[i2]10xi1+xi[10,25]dp[i] = dp[i -1] + dp[i -2], 10x_{i-1} + x_i∈[10,25]
      • dp[i]=dp[i1]10xi1+xi[0,10)(25,99]dp[i] = dp[i - 1], 10x_{i-1} + x_i ∈[0,10)∪(25,99]
    • 初始状态dp[0]=dp[1]=1dp[0] = dp[1] = 1,即无数字和第1位数字的翻译方法数均为1
    • 返回值:dp[n]
  • 无数字情况 dp[0] = 1 从何而来?

    • 当 num第 1, 2 位的组成的数字∈[10,25] 时,显然应有 2种翻译方法,即 dp[2] = dp[1] + dp[0] = 2 ,而显然 dp[1] = 1,因此推出 dp[0] = 1 。
  • 为方便获取数字的各位xix_i,考虑先将数字 num转化为字符串 s ,通过遍历 s 实现动态规划。

  • 通过字符串切片s[i-2:i]获取组合数字10xi1+xi10x_{i-1} + x_i,通过对比字符串ASCII码判断字符串对应数字区间

  • 空间优化:由于dp[i]只和dp[i-1]有关,因此可使用两个变量 a, b分别记录 dp[i], dp[i - 1],两变量交替前进即可。此方法可省去 dp列表使用的 O(N)的额外空间。

  • 时间复杂度:O(N), N为字符串 s的长度(即数字 num的位数log(num) ),其决定了循环次数。

  • 空间复杂度:O(N),字符串使用O(N)额外空间

    class Solution(object):
    def translateNum(self, num):
    """
    :type num: int
    :rtype: int
    """
    s = str(num)
    a = b = 1
    for i in range(2, len(s) + 1):
    a, b = (a + b if "10" <= s[i - 2:i] <= "25" else a), a
    return a

礼物的最大价值

题目

  • 难度:中等

  • 题目(leetcode-面试题47):在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?

  • 示例:

    输入: 
    [
    [1,3,1],
    [1,5,1],
    [4,2,1]
    ]
    输出: 12
    解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
  • 提示:

    • 0 < grid.length <= 200
    • 0 < grid[0].length <= 200

题解

  • Tips:动态规划

  • 时间复杂度:O(MN)

  • 空间复杂度:O(1)

    class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
    for i in range(len(grid)):
    for j in range(len(grid[0])):
    if i == 0 and j == 0: continue
    if i == 0: grid[i][j] += grid[i][j - 1]
    elif j == 0: grid[i][j] += grid[i - 1][j]
    else: grid[i][j] += max(grid[i][j - 1], grid[i - 1][j])
    return grid[-1][-1]
  • 以上代码逻辑清晰,和转移方程直接对应,但仍可提升效率:当 grid矩阵很大时, i = 0 或 j = 0的情况仅占极少数,相当循环每轮都冗余了一次判断。因此,可先初始化矩阵第一行和第一列,再开始遍历递推。

    class Solution(object):
    def maxValue(self, grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    m, n = len(grid), len(grid[0])
    for j in range(1, n): # 初始化第一行
    grid[0][j] += grid[0][j - 1]
    for i in range(1, m): # 初始化第一列
    grid[i][0] += grid[i - 1][0]
    for i in range(1, m):
    for j in range(1, n):
    grid[i][j] += max(grid[i][j - 1], grid[i - 1][j])
    return grid[-1][-1]

最长不含重复字符的子字符串

题目

  • 难度:中等

  • 题目(leetcode-面试题48):请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

  • 示例:

    输入: "abcabcbb"
    输出: 3
    解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

    输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

    输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
      请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
  • 提示:s.length <= 40000

题解

  • Tips:滑动窗口 + 双指针

  • 参考:https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/tu-jie-hua-dong-chuang-kou-shuang-zhi-zhen-shi-xia/

  • 思路:

    • 题目中要求答案必须是 子串 的长度,意味着子串内的字符在原字符串中一定是连续的。因此我们可以将答案看作原字符串的一个滑动窗口,并维护窗口内不能有重复字符,同时更新窗口的最大值。
    • 我们可以使用哈希表记录每个字符的下一个索引,然后尽量向右移动尾指针来拓展窗口,并更新窗口的最大长度。如果尾指针指向的元素重复,则将头指针直接移动到窗口中重复元素的右侧。
    • 算法步骤:
      • tail 指针向末尾方向移动;
      • 如果尾指针指向的元素存在于哈希表中:head 指针跳跃到重复字符的下一位;
      • 更新哈希表和窗口长度。
  • 时间复杂度:O(n)

  • 空间复杂度:O(1), 字符的 ASCII 码范围为 0 ~ 127,哈希表 dic 最多使用 O(128) = O(1) 大小的额外空间。

    class Solution(object):
    def lengthOfLongestSubstring(self, s):
    """
    :type s: str
    :rtype: int
    """
    if not s:
    return 0
    head, res = 0, 0
    dic = {}
    for tail in range(len(s)):
    if s[tail] in dic:
    head = max(dic[s[tail]], head)
    dic[s[tail]] = tail + 1
    res = max(res, tail - head + 1)
    return res

丑数

题目

  • 难度:中等

  • 题目(leetcode-面试题49):我们把只包含因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。

  • 示例:

    输入: n = 10
    输出: 12
    解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
  • 说明:

    • 1 是丑数。
    • n 不超过1690

题解

第一个只出现一次的字符

题目

  • 难度:简单

  • 题目(leetcode-面试题50):在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。

  • 示例:

    s = "abaccdeff"
    返回 "b"

    s = ""
    返回 " "
  • 限制:0 <= s 的长度 <= 50000

题解

  • Tips哈希表

  • 剑指offer:如果需要判断多个字符是不是在某个字符串里出现过或统计多个字符在某个字符串出现的次数,我们可以考虑基于数组创建一个简单的哈希表。

  • 思路:遍历一遍字符串,统计每个字符出现的次数;再遍历一次字符串,确定每个字符串出现的次数,即可找到第一个只出现一次的字符。

  • 时间复杂度:O(2N)

  • 空间复杂度:O(N)

    class Solution(object):
    def firstUniqChar(self, s):
    """
    :type s: str
    :rtype: str
    """
    n = len(s)
    if n <= 0:
    return " "
    dic = {}
    for i in s:
    if i in dic:
    dic[i] += 1
    else:
    dic[i] = 1
    for i in s:
    if dic[i] == 1:
    return i
    return " "

数组中的逆序对

题目

  • 难度:困难

  • 题目(leetcode-面试题51):在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

  • 示例:

    输入: [7,5,6,4]
    输出: 5
  • 限制:0 <= 数组长度 <= 50000

题解

class Solution(object):
def reversePairs(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
self.cnt = 0
def merge(nums, start, mid, end):
i, j, temp = start, mid + 1, []
while i <= mid and j <= end:
if nums[i] <= nums[j]:
temp.append(nums[i])
i += 1
else:
self.cnt += mid - i + 1
temp.append(nums[j])
j += 1
while i <= mid:
temp.append(nums[i])
i += 1
while j <= end:
temp.append(nums[j])
j += 1

for i in range(len(temp)):
nums[start + i] = temp[i]

def mergeSort(nums, start, end):
if start >= end: return
mid = (start + end) // 2
mergeSort(nums, start, mid)
mergeSort(nums, mid + 1, end)
merge(nums, start, mid, end)
mergeSort(nums, 0, len(nums) - 1)
return self.cnt

两个链表的第一个公共节点

题目

  • 难度:简单
  • 题目(leetcode-面试题52):输入两个链表,找出它们的第一个公共节点。
  • 注意:
    • 如果两个链表没有交点,返回 null.
    • 在返回结果后,两个链表仍须保持原有的结构。
    • 可假定整个链表结构中没有循环。
    • 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

题解

  • Tips:双指针

  • 思路:有四种方法

    1. 可以暴力求解,分别遍历两个链表,看是否有重合的结点,时间复杂度:O(mn)
    2. 利用辅助栈:可以将两个链表放入栈中,比较栈顶元素(链表长度相同)
    3. 分别得到两个链表的长度,计算链表差n,然后设置双指针,让长链表先走n步,然后两个链表一起走,看是否有相同的点。
    4. 设置双指针指向两个链表头,然后一起走,指针A遍历完一个链A后,指向另一个链B的头,指针B同理,直到两个指针指向的结点相同,即若存在公共节点则返回公共节点,若不存在,两个指针都会指向null节点。
      • 假设链表A长度是m,链表B是n,公共部分是b,那么走过m+n+b步之后一定会相遇,返回结果。 如果没有公共部分,b=0, 那么走过m+n都指向None,返回None
  • 时间复杂度:O(m+n),m,n分别为两个链表的长度

  • 空间复杂度:O(1)

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

    class Solution(object):
    def getIntersectionNode(self, headA, headB):
    """
    :type head1, head1: ListNode
    :rtype: ListNode
    """
    l1 = headA
    l2 = headB
    while l1 != l2:
    l1 = l1.next if l1 else headB
    l2 = l2.next if l2 else headA
    return l1

在排序数组中查找数字I

题目

  • 难度:简单

  • 题目(leetcode-面试题53I):统计一个数字在排序数组中出现的次数。

  • 示例:

    输入: nums = [5,7,7,8,8,10], target = 8
    输出: 2

    输入: nums = [5,7,7,8,8,10], target = 6
    输出: 0
  • 限制:0 <= 数组长度 <= 50000

题解

  • Tips:二分查找

  • 思路:有两种

    • 遍历一遍数组,用哈希表记录每个数出现的次数,返回target出现的次数。时间复杂度和空间复杂度都是O(n)
    • 用二分查找确定数组第一个target和最后一个target的位置,计算两个位置的下标之差。时间复杂度:O(logn),空间复杂度:O(1)
  • 参考:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/

    class Solution(object):
    def search(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    # 搜索右边界 right
    i, j = 0, len(nums) - 1
    while i <= j:
    m = (i + j) // 2
    if nums[m] <= target: i = m + 1
    else: j = m - 1
    right = i
    # 若数组中无 target ,则提前返回
    if j >= 0 and nums[j] != target: return 0
    # 搜索左边界 left
    i = 0
    while i <= j:
    m = (i + j) // 2
    if nums[m] < target: i = m + 1
    else: j = m - 1
    left = j
    return right - left - 1
  • 简化代码:helper() 函数旨在查找数字 tar在数组 nums 中的 插入点 ,且若数组中存在值相同的元素,则插入到这些元素的右边。即找target的右边界和target-1的右边界。

    class Solution(object):
    def search(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    def helper(tar):
    i, j = 0, len(nums) - 1
    while i <= j:
    m = (i + j) // 2
    if nums[m] <= tar: i = m + 1
    else: j = m - 1
    return i
    return helper(target) - helper(target - 1)

0~n-1中缺失的数字

题目

  • 难度:简单

  • 题目(leetcode-面试题53II):一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。

  • 示例:

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

    输入: [0,1,2,3,4,5,6,7,9]
    输出: 8
  • 限制:1 <= 数组长度 <= 10000

题解

  • Tips:二分法,排序数组中的搜索问题,首先想到 二分法 解决。

  • 参考:https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/solution/mian-shi-ti-53-ii-0n-1zhong-que-shi-de-shu-zi-er-f/

  • 思路:

    • 根据题意,数组可以按照以下规则划分为两部分。
      • 左子数组:nums[i] = i
      • 右子数组:nums[i] ≠ i
    • 缺失的数字等于 “右子数组的首位元素” 对应的索引;因此考虑使用二分法查找 “右子数组的首位元素” 。
  • 算法流程:

    • 初始化左边界,i = 0, 右边界, j = len(nums) - 1,代表闭区间[i,j]。
  • 循环二分:当i <= j时循环(当闭区间i,j为空时,跳出)

    • 计算中点 m = (i + j) // 2,其中 “//” 为向下取整除法;
    • 若 nums[m] = m ,则 “右子数组的首位元素” 一定在闭区间 [m + 1, j]中,因此执行 i = m + 1;
    • 若 nums[m] ≠ m ,则 “左子数组的末位元素” 一定在闭区间 [i, m - 1]中,因此执行 j = m - 1;
    • 返回值: 跳出时,变量 i和 j 分别指向 “右子数组的首位元素” 和 “左子数组的末位元素” 。因此返回 i 即可。
  • 时间复杂度:O(logn)

  • 空间复杂度:O(1)

    class Solution(object):
    def missingNumber(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    i, j = 0, len(nums) - 1
    while i <= j:
    m = (i + j) // 2
    if nums[m] == m:
    i = m + 1
    else:
    j = m - 1
    return i

二叉搜索树第k大节点

题目

  • 难度:简单

  • 题目(leetcode-面试题54):给定一棵二叉搜索树,请找出其中第k大的节点。

  • 示例:

    输入: root = [3,1,4,null,2], k = 1
    3
    / \
    1 4
    \
    2
    输出: 4

    输入: root = [5,3,6,2,4,null,null,1], k = 3
    5
    / \
    3 6
    / \
    2 4
    /
    1
    输出: 4
  • 限制:1 ≤ k ≤ 二叉搜索树元素个数

题解

  • Tips二叉搜索树的中序遍历为递增序列(中序遍历+提前返回)

  • 参考:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/solution/mian-shi-ti-54-er-cha-sou-suo-shu-de-di-k-da-jie-d/

  • 思路:求 “二叉搜索树第 k大的节点” 可转化为求 “此树的中序遍历倒序的第 k个节点”。

    • 为求第 k 个节点,需要实现以下 三项工作 :
      1. 递归遍历时计数,统计当前节点的序号;
      2. 递归到第 k个节点时,应记录结果 res;
      3. 记录结果后,后续的遍历即失去意义,应提前终止(即返回)。
  • 递归解析

    • 终止条件: 当节点 root为空(越过叶节点),则直接返回;
    • 递归右子树: 即 dfs(root.right);
    • 三项工作
      1. 提前返回: 若 k = 0 ,代表已找到目标节点,无需继续遍历,因此直接返回;
      2. 统计序号: 执行 k = k - 1 (即从 k减至 0 );
      3. 记录结果: 若 k = 0 ,代表当前节点为第 k大的节点,因此记录 res = root.val ;
    • 递归左子树: 即 dfs(root.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 kthLargest(self, root, k):
    """
    :type root: TreeNode
    :type k: int
    :rtype: int
    """
    self.k, self.res = k, None
    def inorder(root):
    if not root:
    return
    inorder(root.right)
    if self.k == 0:
    return
    self.k -= 1
    if self.k == 0:
    self.res = root.val
    inorder(root.left)
    inorder(root)
    return self.res

二叉树的深度

题目

  • 难度:简单

  • 题目(leetcode-面试题55I):输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。

  • 示例:

    例如:

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

    3
    / \
    9 20
    / \
    15 7

    返回它的最大深度 3 。
  • 提示:节点总数 <= 10000

题解

  • Tips:后序遍历/层序遍历

    • 树的遍历方式总体分为两类:深度优先搜索(DFS)、广度优先搜索(BFS);
      • 常见的 DFS : 先序遍历、中序遍历、后序遍历;
      • 常见的 BFS : 层序遍历(即按层遍历)。
    • 树的后序遍历/深度优先搜索往往利用递归或栈
      • 关键点: 此树的深度和其左(右)子树的深度之间的关系。显然,此树的深度 等于 左子树的深度右子树的深度 中的 最大值 +1 。
    • 树的层序遍历 / 广度优先搜索往往利用 队列 实现。
      • 关键点: 每遍历一层,则计数器 +1 ,直到遍历完成,则可得到树的深度。
  • 思路:递归-后序遍历

    • 终止条件:当 root 为空,说明已越过叶节点,因此返回 深度 0 。
    • 递推工作:本质上是对树做后序遍历
      • 计算结点root的左子树深度,即调用maxDepth(root.left)
      • 计算节点 root右子树的深度 ,即调用 maxDepth(root.right)
    • 返回值: 返回 此树的深度 ,即 max(maxDepth(root.left), maxDepth(root.right)) + 1
  • 时间复杂度: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 maxDepth(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    if not root:
    return 0
    return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
  • 思路:队列-层序遍历

    • 特例处理:当root为空,直接返回深度0
    • 初始化: 队列 queue (加入根节点 root ),计数器 res = 0
    • 循环遍历:queue 为空时跳出。
      • 初始化一个空列表 tmp ,用于临时存储下一层节点;
      • 遍历队列: 遍历 queue 中的各节点 node ,并将其左子节点和右子节点加入 tmp
      • 更新队列: 执行 queue = tmp ,将下一层节点赋值给 queue
      • 统计层数: 执行 res += 1 ,代表层数加 11;
    • 返回值: 返回 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 maxDepth(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    if not root:
    return 0
    queue = [root]
    res = 0
    while queue:
    tmp = []
    for node in queue:
    if node.left:
    tmp.append(node.left)
    if node.right:
    tmp.append(node.right)
    queue = tmp
    res += 1
    return res

平衡二叉树

题目

  • 难度:简单

  • 题目(leetcode-面试题55II):输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

  • 示例:

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

    3
    / \
    9 20
    / \
    15 7

    返回 true 。

    给定二叉树 [1,2,2,3,3,null,null,4,4]

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

    返回 false 。
  • 1 <= 树的结点个数 <= 10000

题解

  • 思路

    • 先序遍历+判断深度(自顶向下),比较容易想到。
      • 构造一个depth函数递归计算二叉树的左右子树高度
      • 比较左右子树高度差是否≤1,判断某子树是否是二叉平衡树。若所有子树都平衡,则此树平衡。
  • 时间复杂度:O(NlogN),最差情况下(为 “满二叉树” 时), isBalanced(root) 遍历树所有节点,判断每个节点的深度 depth(root) 需要遍历 各子树的所有节点 。

    • 满二叉树高度的复杂度 O(log N) ,将满二叉树按层分为 log (N+1) 层;
    • 总体时间复杂度 == 每层执行复杂度× 层数复杂度 = O(N×logN) 。
  • 空间复杂度: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 isBalanced(self, root):
    """
    :type root: TreeNode
    :rtype: bool
    """
    if not root: return True
    return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

    def depth(self, root):
    if not root: return 0
    return max(self.depth(root.left), self.depth(root.right)) + 1
  • 思路:后序遍历+剪枝(从底至顶):

    • 思路是对二叉树做后序遍历,从底至顶返回子树深度,若判定某子树不是平衡树则 “剪枝” ,直接向上返回。
    • 算法流程:
      • recur(root) 函数:
        • 返回值
          • 当节点root左/右子树的深度差<=1:则返回当前子树的深度,即节点root的左/右子树的深度最大值 + 1
          • 当节点root左/右子树的深度差>2:则返回-1,代表此子树不是平衡树
        • 终止条件
          • root 为空:说明越过叶节点,因此返回高度 0
          • 当左(右)子树深度为-1,代表此树的 左(右)子树 不是平衡树,因此剪枝,直接返回 -1;
      • isBalanced(root) 函数:
        • 返回值:recur(root) != -1 ,则说明此树平衡,返回 true ; 否则返回 false 。
  • 时间复杂度: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 isBalanced(self, root):
    """
    :type root: TreeNode
    :rtype: bool
    """
    def recur(root):
    if not root:
    return 0
    left = recur(root.left)
    if left == -1:
    return -1
    right = recur(root.right)
    if right == -1:
    return -1
    return max(left, right) + 1 if abs(left - right) <= 1 else -1
    return recur(root) != -1

数组中数字出现的次数

题目

  • 难度:中等

  • 题目(leetcode-面试题56I):一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

  • 示例:

    输入:nums = [4,1,4,6]
    输出:[1,6] 或 [6,1]

    输入:nums = [1,2,10,4,1,4,3,3]
    输出:[2,10] 或 [10,2]
  • 限制:2 <= nums.length <= 10000

题解

  • 思路:

    • 异或有这样的性质:
      • 0a=a,aa=0,aaa=a
    • 设所求的两个数为x,y,先将所有元素都异或,得到结果r,r其实就是x与y的异或。由于x!=y,r肯定不为0,即在其二进制形式中存在1,我们从右向左找第一个为1的位置(其实只要能找到任意一位为1的位置即可),记录其位置为i。这样通过i便可将数组分为两部分,一部分元素的二进制在i处为0,另一部分为1。x与y必定分散在这两部分中,而且相同的数都会在同一部分。将这两部分分别异或,结果便为x,y。
  • 时间复杂度:O(N)

  • 空间复杂度:O(1)

    class Solution(object):
    def singleNumbers(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    ret = 0 # 所有数字异或的结果
    a = 0
    b = 0
    for n in nums:
    ret ^= n
    # 找到第一位不是0的
    h = 1
    while(ret & h == 0):
    h <<= 1
    for n in nums:
    # 根据该位是否为0将其分为两组
    if (h & n == 0):
    a ^= n
    else:
    b ^= n

    return [a, b]

数组中数字出现的次数II

题目

  • 难度:中等

  • 题目(leetcode-面试题56II):在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。

  • 示例:

    输入:nums = [3,4,3,3]
    输出:4

    输入:nums = [9,1,7,9,7,9,7]
    输出:1
  • 限制:

    • 1 <= nums.length <= 10000
    • 1 <= nums[i] < 2^31

题解

  • Tips:位运算 / 字典 / 排序 /数学方法

  • 参考:https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/pythonti-jie-san-chong-fang-shi-man-zu-mian-shi-gu/

  • 思路:位运算

    • 我们想一下如果一个数字出现三次,那么他的二进制位表示的每一位(0或1)也出现了三次.如果把所有出现三次的数字的二进制表示的每一位都分别加起来,那么每一位的和都能被3整除
    • 我们把所有数字的二进制位的每一位加起来.若果某一位的和能被3整除,那么那个只出现一次的数字二进制表示中对应的那一位为0,否则为1
    • 步骤:
      • 统计所有数字二进制位的和
      • 判断每一位的和能否被3整除,求解最后结果
  • 时间复杂度:O(n)

  • 空间复杂度:O(1)

    class Solution(object):
    def singleNumber(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    bitSum = [0] *32 #定义存储各个位的数组

    for i in nums: #统计各位之和
    mask = 1
    for j in reversed(range(32)):
    if mask & i:
    bitSum[j] += 1
    mask = mask << 1

    result = 0
    for i in range(32):#得到最终结果
    result = result << 1
    result += bitSum[i] % 3

    return result

和为s的两个数字

题目

  • 难度:简单

  • 题目(leetcode-面试题57I):输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

  • 示例:

    输入:nums = [2,7,11,15], target = 9
    输出:[2,7] 或者 [7,2]

    输入:nums = [10,26,30,31,47,60], target = 40
    输出:[10,30] 或者 [30,10]
  • 限制:

    • 1 <= nums.length <= 10^5
    • 1 <= nums[i] <= 10^6

题解

  • Tips:双指针 / 字典

  • 思路:双指针:

    • 根据题意,是递增排序数组,可以初始化两个指针,分别指向数组的第一个元素和最后一个元素,即i = 0, j = len(nums) - 1
    • 当i < j时,判断nums[i] + nums[j]的和是否等于target,如果等于,则输出这两个数,如果大于,将j前移。如果小于,将i后移。
  • 时间复杂度:O(n)

  • 空间复杂度:O(1)

    class Solution(object):
    def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    i, j = 0, len(nums) - 1
    while i < j:
    s = nums[i] + nums[j]
    if s == target:
    return nums[i], nums[j]
    elif s < target:
    i += 1
    else:
    j -= 1
    return None
    #字典,空间复杂度:O(n)
    class Solution(object):
    def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    dic = {}
    for num in nums:
    a = target - num
    if a in dic:
    return dic[a], num
    else:
    dic[num] = num
    return None

和为s的连续正数序列

题目

  • 难度:简单

  • 题目(leetcode-面试题57II):输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

  • 示例:

    输入:target = 9
    输出:[[2,3,4],[4,5]]

    输入:target = 15
    输出:[[1,2,3,4,5],[4,5,6],[7,8]]
  • 限制:1 <= target <= 10^5

题解

  • 思路:双指针滑动窗口法

    • 针对目前这个题,我们可以把左指针i指向1,右指针j指向2,然后就能计算出当前窗口范围各数字的和,cur_sum = sum(list(range(i,j+1))),如果cur_sum小于target,说明当前窗口数字之和过小,这时候咱们可以令j += 1,这样我们的新窗口就向右边扩大了。同样的道理,如果cur_sum大于target,这说明我们当前窗口数字之和过大,这时候就令i += 1,这样窗口的左边界就向右边移动了一个单位,就使得窗口变小了。
  • 参考:https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/xiang-jie-hua-dong-chuang-kou-fa-qiu-gen-fa-jian-g/

  • 时间复杂度:O(n)

  • 空间复杂度:O(1)

    class Solution(object):
    def findContinuousSequence(self, target):
    """
    :type target: int
    :rtype: List[List[int]]
    """
    # 初始化窗口指针和输出列表
    i, j, res = 1,2, []

    # 滑动窗口的右边界不能超过target的中值
    while j <= target//2 + 1:
    # 计算当前窗口内数字之和
    cur_sum = sum(list(range(i,j+1)))
    # 若和小于目标,右指针向右移动,扩大窗口
    if cur_sum < target:
    j += 1
    # 若和大于目标,左指针向右移动,减小窗口
    elif cur_sum > target:
    i += 1
    # 相等就把指针形成的窗口添加进输出列表中
    # 别忘了,这里还要继续扩大寻找下一个可能的窗口哦
    else:
    res.append(list(range(i,j+1)))
    # 这里用j+=1,i+=1,i+=2都可以的
    j += 1

    return res

翻转单词顺序

题目

  • 难度:简单

  • 题目(leetcode-面试题58I):输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串"I am a student. “,则输出"student. a am I”。

  • 示例:

    输入: "the sky is blue"
    输出: "blue is sky the"

    输入: "  hello world!  "
    输出: "world! hello"
    解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。

    输入: "a good   example"
    输出: "example good a"
    解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。
  • 说明:

    • 无空格字符构成一个单词。
    • 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
    • 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

题解

  • Tips:双指针滑动窗口确定单词

  • 剑指offer:可以进行两次反转,第一次反转所有字符,第二次依次反转每个单词的字符。

  • 思路:

    • 去除字符串首尾空格
    • 初始化两个指针,i,j指向字符串最后一个字符
    • 当i大于等于0时,如果当i>=0且s[i]不是空格,i继续前移,如果遇到空格,说明扫描了一个单词,将这个单词加入res,当遇到空格,i前移,并且让j指向i此刻位置,重新开始扫描下一个单词。
    • 最后将列表转为字符串
  • 时间复杂度:O(n)

  • 空间复杂度:O(n)

    class Solution(object):
    def reverseWords(self, s):
    """
    :type s: str
    :rtype: str
    """
    if not s:
    return ""
    s = s.strip()
    i = j = len(s) - 1
    res = []
    while i >= 0:
    while i >= 0 and s[i] != ' ':
    i -= 1
    res.append(s[i + 1 : j + 1])
    while s[i] == ' ':
    i -= 1
    j = i
    return ' '.join(res)

左旋转字符串

题目

  • 难度:简单

  • 题目(leetcode-面试题58II):字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab"。

  • 示例:

    输入: s = "abcdefg", k = 2
    输出: "cdefgab"

    输入: s = "lrloseumgh", k = 6
    输出: "umghlrlose"
  • 限制:1 <= k < s.length <= 10000

题解

  • 思路:字符串切片、列表遍历拼接、字符串遍历拼接

    • 字符串切片

      • 应用字符串切片函数,可方便实现左旋转字符串。

      • 获取字符串 s[n:]切片和 s[:n] 切片,使用 “+” 运算符拼接并返回即可。

      • 时间复杂度:O(N)

      • 空间复杂度:O(N)

        class Solution(object):
        def reverseLeftWords(self, s, n):
        """
        :type s: str
        :type n: int
        :rtype: str
        """
        if not s or n < 0:
        return ""
        return s[n:] + s[:n]
    • 列表遍历拼接

      • 若面试不允许字符串切片,可以使用该方法

      • 新建一个 list(Python) ,记为 res ;

      • 先向 res 添加 “第 n + 1 位至末位的字符” ;

      • 再向 res添加 “首位至第 n 位的字符” ;

      • 将 res 转化为字符串并返回。

      • 时间复杂度:O(N)

      • 空间复杂度:O(N)

        class Solution(object):
        def reverseLeftWords(self, s, n):
        """
        :type s: str
        :type n: int
        :rtype: str
        """
        if not s or n < 0:
        return
        res = []
        for i in range(n,len(s)):
        res.append(s[i])
        for i in range(n):
        res.append(s[i])
        return ''.join(res)
    • 字符串遍历拼接

      • 若面试不允许用join,可以使用该方法

      • 新建一个str,记为res

      • 遍历字符串,用"+"依次拼接字符串

      • 时间复杂度:O(N)

      • 空间复杂度:O(N)

        class Solution(object):
        def reverseLeftWords(self, s, n):
        """
        :type s: str
        :type n: int
        :rtype: str
        """
        if not s or n < 0:
        return
        res = ""
        for i in range(n, len(s)):
        res += s[i]
        for i in range(n):
        res += s[i]
        return res
    • 剑指offer方法

      class Solution(object):
      def reverseLeftWords(self, s, n):
      """
      :type s: str
      :type n: int
      :rtype: str
      """
      if not s or n < 0:
      return
      s = list(s)
      self.reverse(s, 0, n - 1)
      self.reverse(s, n, len(s) - 1)
      self.reverse(s, 0, len(s) - 1)
      return ''.join(s)

      def reverse(self, s, start, end):
      while start < end:
      s[start], s[end] = s[end], s[start]
      start += 1
      end -= 1

滑动窗口的最大值

题目

  • 难度:简单

  • 题目(leetcode-面试题59I):给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。

  • 示例:

    输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
    输出: [3,3,5,5,6,7]
    解释:

    滑动窗口的位置 最大值
    --------------- -----
    [1 3 -1] -3 5 3 6 7 3
    1 [3 -1 -3] 5 3 6 7 3
    1 3 [-1 -3 5] 3 6 7 5
    1 3 -1 [-3 5 3] 6 7 5
    1 3 -1 -3 [5 3 6] 7 6
    1 3 -1 -3 5 [3 6 7] 7
  • 提示:你可以假设 k 总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小。

题解

  • Tips:单调队列

  • 参考:https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/mian-shi-ti-59-i-hua-dong-chuang-kou-de-zui-da-1-6/

  • 思路:

    • 初始化:双端队列deque,结果列表res,数组长度n
    • 滑动窗口:左边界范围i∈[1-k, n+1-k],右边界范围j∈[0, n-1]
      • 若i>0且队首元素deque[0]=被删除元素nums[i-1],则队首元素出队
      • 删除deque内所有<nums[j]的元素,以保持deque递减
      • 将nums[j]添加至deque尾部
      • 若已形成窗口(即i≥0),将窗口最大值(即队首元素deque[0])添加至列表res
    • 返回值:返回结果列表res
  • 时间复杂度:O(n),其中 n为数组 nums长度;线性遍历 nums占用 O(N);每个元素最多仅入队和出队一次,因此单调队列 deque占用 O(2N) 。

  • 空间复杂度:O(k),双端队列 deque中最多同时存储 k个元素(即窗口大小)。

    class Solution(object):
    def maxSlidingWindow(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: List[int]
    """
    if not nums or k == 0:
    return []
    deque = collections.deque()
    #未形成窗口
    for i in range(k):
    while deque and deque[-1] < nums[i]:
    deque.pop()
    deque.append(nums[i])
    res = [deque[0]]
    #形成窗口后
    for i in range(k, len(nums)):
    if deque[0] == nums[i - k]: # 删除 deque 中对应的 nums[i-1]
    deque.popleft()
    while deque and deque[-1] < nums[i]:
    deque.pop()
    deque.append(nums[i])
    res.append(deque[0])
    return res

队列的最大值

题目

  • 难度:中等

  • 题目(leetcode-面试题59II):请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

    若队列为空,pop_frontmax_value 需要返回 -1

  • 示例:

    输入: 
    ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
    [[],[1],[2],[],[],[]]
    输出: [null,null,null,2,1,2]

    输入:
    ["MaxQueue","pop_front","max_value"]
    [[],[],[]]
    输出: [null,-1,-1]
  • 提示:

    • 1 <= push_back,pop_front,max_value的总操作数 <= 10000
    • 1 <= value <= 10^5

题解

  • 思路:

    • 我们知道对于一个普通队列,push_back 和 pop_front 的时间复杂度都是 O(1),因此我们直接使用队列的相关操作就可以实现这两个函数。
    • 使用一个双端队列 deque,在每次入队时,如果 deque 队尾元素小于即将入队的元素 value,则将小于 value的元素全部出队后,再将 value 入队;否则直接入队。这时,辅助队列 dequedeque 队首元素就是队列的最大值。
    class MaxQueue(object):

    def __init__(self):
    from collections import deque
    self.que = deque()
    self.sort_que = deque()

    def max_value(self):
    """
    :rtype: int
    """
    return self.sort_que[0] if self.sort_que else -1

    def push_back(self, value):
    """
    :type value: int
    :rtype: None
    """
    self.que.append(value)
    while self.sort_que and self.sort_que[-1] < value:
    self.sort_que.pop()
    self.sort_que.append(value)

    def pop_front(self):
    """
    :rtype: int
    """
    if not self.que: return -1
    res = self.que.popleft()
    if res == self.sort_que[0]:
    self.sort_que.popleft()
    return res
  • 时间复杂度:O(1)

  • 空间复杂度:O(n)

n个骰子的点数

题目

  • 难度:简单

  • 题目(leetcode-面试题60):把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

  • 示例:

    输入: 1
    输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

    输入: 2
    输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
  • 限制:1 <= n <= 11

题解

  • 剑指offer:骰子一共6个面,每个面上都有一个点数,对应的是1~6之间的一个数字。所以n个骰子的点数和的最小值为n,最大值为6n。另外根据排列组合的知识,我们还知道n个骰子的所有点数的排列数位6n。要解决这个问题,我们需要先统计出每一个点数出现的次数,然后把每一个点数出现的次数除以6n,就能求出每个点数出现的概率。
    • 基于递归求骰子点数,时间效率不够高
      • 可以先把n个骰子分为两堆:第一堆只有一个,另一个有n-1个。单独的那一个有可能出现从1到6的点数。我们需要计算1到6的每一种点数和剩下的n-1个骰子来计算点数和。接下来把剩下的n-1个骰子还是分成两堆,第一堆只有一个,第二堆有n-2个。我们把上一轮那个单独骰子的点数和这一轮单独骰子的点数相加,再和剩下的n-2骰子来计算点数和。递归的思路,递归结束条件就是最后只剩下一个骰子。我们可以定义一个长度为6n-n+1的数组,和为s的点数出现的次数保存到数组第s-n个元素里。
    • 基于循环求骰子点数,时间性能好
      • 我们可以考虑用两个数组来存储骰子点数的每一个总数出现的次数。在一次循环中,第一个数组中的第n个数字表示骰子和为n出现的次数。下一循环中,我们加上一个新的骰子,此时和为n的骰子出现的次数应该等于上一次循环中骰子点数和为n-1、n-2、n-3、n-4、n-5与n-6的次数的总和,所以我们把另一个数组的第n个数字设为前一个数组对应的第n-1、n-2、n-3、n-4、n-5与n-6之和。
  • 参考:https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/solution/rong-yi-li-jie-de-pythondong-tai-gui-hua-fang-fa-b/
  • 思路:动态规划

    • 表示状态:dp[i][j],表示投掷完i个骰子后,点数j的出现次数

    • 找出状态转移方程:找状态转移方程也就是找各个阶段之间的转化关系,同样我们还是只需分析最后一个阶段,分析它的状态是如何得到的。最后一个阶段也就是投掷完 n枚骰子后的这个阶段,我们用 dp[n][j]来表示最后一个阶段点数 j 出现的次数。单单看第 n枚骰子,它的点数可能为 1 , 2, 3, … , 6 ,因此投掷完 n 枚骰子后点数 j出现的次数,可以由投掷完 n-1 枚骰子后,对应点数 j-1, j-2, j-3, … , j-6 出现的次数之和转化过来。

      for (第n枚骰子的点数 i = 1; i <= 6; i ++) {
      dp[n][j] += dp[n-1][j - i]
      }
      • 写成数学公式:

        • dp[n][j]=i=16dp[n1][ji]dp[n][j] = \sum^{6}_{i = 1}dp[n-1][j-i]

        • n表示阶段,j表示投掷完n枚骰子之后的点数和,i表示第n枚骰子会出现的六个点数

    • **边界处理:**这里的边界处理很简单,只要我们把可以直接知道的状态初始化就好了。我们可以直接知道的状态是啥,就是第一阶段的状态:投掷完 1 枚骰子后,它的可能点数分别为 1, 2, 3, … , 6,并且每个点数出现的次数都是 1.

      for (int i = 1; i <= 6; i ++) {
      dp[1][i] = 1;
      }
      class Solution(object):
      def twoSum(self, n):
      """
      :type n: int
      :rtype: List[float]
      """
      dp = [[0 for _ in range(6 * n + 1)] for _ in range(n + 1)] #表示i个骰子投掷出s点的次数
      for i in range(1,7):
      dp[1][i] = 1 #表示一个骰子投掷出i点的次数为1
      for i in range(2, n + 1): #表示骰子的个数
      for j in range(i, i * 6 + 1): #表示可能会出现的点数之和
      for k in range(1,7):
      if j >= k + 1:
      dp[i][j] += dp[i - 1][j - k] #当前n个骰子出现的点数之和等于前一次出现的点数之和加上这一次出现的点数
      res = []
      for i in range(n,n * 6 + 1): #投掷n次点数出现的所有情况
      res.append(dp[n][i] * 1.0 / 6 ** n)
      return res
  • 时间复杂度:O(n^2)

  • 空间复杂度:O(n)

扑克牌中的顺子

题目

  • 难度:简单

  • 题目(leetcode-面试题61):从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12,K为13,而大、小王为 0 ,可以看成任意数字。A 不能视为 14。

  • 示例:

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

    输入: [0,0,1,2,5]
    输出: True
  • 限制:

    • 数组长度为 5
    • 数组的数取值为 [0, 13] .

题解

  • 剑指offer:首先把数组排序,再统计数组中0的个数,最后统计排序之后的数组中相邻数组之间的空缺总数。如果空缺的总数小于或等于0的个数,那么这个数组就是连续的,反之则不连续。
  • Tips:根据题意,此5张牌是顺子的充分条件如下:

    • 除大小王外,所有牌无重复
    • 设此5张牌中最大的牌为max,最小的牌为min(大小王除外),则需满足:max-min<5
  • 思路:集合set+遍历 、 排序+遍历

    • 集合set+遍历

      • 遍历5张牌,遇到大小王(即0)直接跳过

      • 判别重复牌,利用 set实现遍历判重,set的查找方法的时间复杂度为O(1)

      • 获取最大牌和最小牌,借助辅助遍历ma和mi,遍历统计即可。

      • 时间复杂度: O(N) = O(5) = O(1), 其中 N为 nums 长度,本题中 N≡5 ;遍历数组使用 O(N) 时间。

      • 空间复杂度:O(N)=O(5)=O(1) ,用于判重的辅助 Set 使用 O(N)额外空间。

        class Solution(object):
        def isStraight(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        repeat = set()
        ma, mi = 0, 14
        for num in nums:
        if num == 0: continue # 跳过大小王
        ma = max(ma, num) # 最大牌
        mi = min(mi, num) # 最小牌
        if num in repeat: return False # 若有重复,提前返回 false
        repeat.add(num) # 添加牌至 Set
        return ma - mi < 5 # 最大牌 - 最小牌 < 5 则可构成顺子
    • 排序+遍历(剑指):

      class Solution(object):
      def isStraight(self, nums):
      """
      :type nums: List[int]
      :rtype: bool
      """
      nums.sort()
      zero = 0
      for i in range(4):
      if nums[i] == 0:
      zero += 1
      elif nums[i] == nums[i + 1]:
      return False
      return nums[4] - nums[zero] < 5
      • 时间复杂度 O(N log N) = O(5 log 5) = O(1), 其中 N 为 nums 长度,本题中 N≡5 ;数组排序使用O(NlogN) 时间。
      • 空间复杂度 O(1) ,变量 joker 使用 O(1)大小的额外空间。

圆圈中最后剩下的数字

题目

  • 难度:简单

  • 题目(leetcode-面试题62):0,1,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

    例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。

  • 示例:

    输入: n = 5, m = 3
    输出: 3

    输入: n = 10, m = 17
    输出: 2
  • 限制:

    • 1 <= n <= 10^5
    • 1 <= m <= 10^6

题解

股票的最大利润

题目

  • 难度:中等

  • 题目(leetcode-面试题63):假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?

  • 示例:

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

    输入: [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
  • 限制:0 <= 数组长度 <= 10^5

题解

  • 思路:动态规划

    • 状态定义:设动态规划列表 dp ,dp[i] 代表以 prices[i]为结尾的子数组的最大利润(以下简称为 前 i 日的最大利润 )。
    • 转移方程:由于题目限定 “买卖该股票一次” ,因此前 i日最大利润 dp[i] 等于前 i - 1日最大利润 dp[i-1]和第 i 日卖出的最大利润中的最大值。
      • i日最大利润=max(前(i−1)日最大利润,第i日价格−前i日最低价格)
      • dp[i] = max(dp[i - 1] , prices[i] - min(prices[0:i]))
    • 初始状态:dp[i] = 0,首日利润为0
    • 返回值:dp[n-1],其中n为dp列表长度
    • 效率优化
      • 时间复杂度降低: 前 i 日的最低价格 min(prices[0:i]) 时间复杂度为 O(i) 。而在遍历 prices时,可以借助一个变量(记为成本 cost )每日更新最低价格。优化后的转移方程为:
        • dp[i] = max(dp[i - 1] , prices[i] - min(cost, prices[i]))
      • 空间复杂度降低:由于dp[i]只与dp[i-1],pirces[i],cost有关,因此可以用一个变量(记为profit)代表dp列表:
        • profit = max(profit, prices[i] - min(cost, prices[i]))
    • 时间复杂度:O(n)
    • 空间复杂度:O(1)
    class Solution(object):
    def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    if len(prices) == 0 or len(prices) > 10**5:
    return 0
    profit = 0
    cost = float('inf')
    for price in prices:
    cost = min(cost, price)
    profit = max(profit, price - cost)
    return profit

求1+2+…+n

题目

  • 难度:中等

  • 题目(leetcode-面试题64):求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

  • 示例:

    输入: n = 3
    输出: 6

    输入: n = 9
    输出: 45
  • 限制:1 <= n <= 10000

题解

  • Tips:通常求1+2+3+…+n,除了用公式n(n+1)/2之外,无外乎循环和递归两种思路。

  • 参考:

  • 思路:递归使用if判断的写法:

    def sumNums(n):
    if n == 1: return 1
    n += sumNums(n - 1)
    return n
    • 如何替代if做判断?可以用逻辑运算符
  • 时间复杂度:O(n)

  • 空间复杂度:O(n)

    class Solution(object):
    def __init__(self):
    self.res = 0
    def sumNums(self, n):
    """
    :type n: int
    :rtype: int
    """
    n > 1 and self.sumNums(n - 1)
    self.res += n
    return self.res
  • 思路:快速乘

    • 回到本题,由等差数列求和公式我们可以知道 1+2+3+…+n等价于n(n+1)2\frac{n(n+1)}{2} ,对于除以 2 我们可以用右移操作符来模拟,那么等式变成了 n(n+1)>>1,剩下不符合题目要求的部分即为 n(n+1),根据上文提及的快速乘,我们可以将两个数相乘用加法和位运算来模拟,但是可以看到上面的 C++ 实现里我们还是需要循环语句,有没有办法去掉这个循环语句呢?答案是有的,那就是自己手动展开,因为题目数据范围 n 为 [1,10000],所以 n 二进制展开最多不会超过 14 位,我们手动展开 14层代替循环即可,至此满足了题目的要求,具体实现可以参考下面给出的代码。

    • https://leetcode-cn.com/problems/qiu-12n-lcof/solution/pythonkuai-su-jia-de-jie-fa-by-user3935a/

    • 时间复杂度:O(logn)

    • 空间复杂度:O(1)

      class Solution(object):
      res = 0
      def add_a(self, a):
      self.res += a

      def sum_by_recursive(self, a, b):
      b & 1 and self.add_a(a)
      b and self.sum_by_recursive(a << 1, b >> 1)


      def sumNums(self, n):
      a = n
      b = n + 1
      self.sum_by_recursive(a, b)

      return self.res >> 1

不用加减乘除做加法

题目

  • 难度:简单

  • 题目(leetcode-面试题65):写一个函数,求两个整数之和,要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

  • 示例:

    输入: a = 1, b = 1
    输出: 2
  • 提示:

    • a, b 均可能是负数或 0
    • 结果不会溢出 32 位整数

题解

构建乘积数组

题目

  • 难度:简单

  • 题目(leetcode-面试题66):给定一个数组 A[0,1,…,n-1],请构建一个数组 B[0,1,…,n-1],其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

  • 示例:

    输入: [1,2,3,4,5]
    输出: [120,60,40,30,24]
  • 提示:

    • 所有元素乘积之和不会溢出 32 位整数
    • a.length <= 100000

题解

  • 思路:列表格,根据表格的主对角线(全为 11 ),可将表格分为 上三角下三角 两部分。分别迭代计算下三角和上三角两部分的乘积,即可 不使用除法 就获得结果。

    • 算法流程:
      1. 初始化:数组 B ,其中 B[0] = 1 ;辅助变量 tmp = 1 ;
      2. 计算 B[i]的 下三角 各元素的乘积,直接乘入 B[i] ;
      3. 计算 B[i] 的 上三角 各元素的乘积,记为 tmp ,并乘入 B[i] ;
      4. 返回 B 。
  • 时间复杂度:O(n)

  • 空间复杂度:O(1)

    class Solution(object):
    def constructArr(self, a):
    """
    :type a: List[int]
    :rtype: List[int]
    """

    b, tmp = [1] * len(a), 1
    for i in range(1, len(a)):
    b[i] = b[i - 1] * a[i - 1] # 下三角
    for i in range(len(a) - 2, -1, -1):
    tmp *= a[i + 1] # 上三角
    b[i] *= tmp # 下三角 * 上三角
    return b

把字符串转换成整数

题目

  • 难度:中等

  • 题目(leetcode-面试题67):写一个函数 StrToInt,实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

    首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。

    当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。

    该字符串除了有效的整数部分之后也可能会存在多余的字符,这些字符可以被忽略,它们对于函数不应该造成影响。

    注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换。

    在任何情况下,若函数不能进行有效的转换时,请返回 0。

    说明:

    假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围,请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

  • 示例:

    输入: "42"
    输出: 42

    输入: " -42"
    输出: -42
    解释: 第一个非空白字符为 '-', 它是一个负号。
      我们尽可能将负号与后面所有连续出现的数字组合起来,最后得到 -42

    输入: "4193 with words"
    输出: 4193
    解释: 转换截止于数字 '3' ,因为它的下一个字符不为数字。

    输入: "-91283472332"
    输出: -2147483648
    解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
      因此返回 INT_MIN (−231) 。

题解

二叉搜索树的最近公共祖先

题目

  • 难度:简单

  • 题目(leetcode-面试题68I):给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

    百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

  • 示例:

    例如,给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

    示例1:
    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
    输出: 6
    解释: 节点 2 和节点 8 的最近公共祖先是 6。

    示例2:
    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
    输出: 2
    解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
  • 说明:

    • 所有节点的值都是唯一的。
    • p、q 为不同节点且均存在于给定的二叉搜索树中。

题解

  • 祖先的定义: 若节点 p 在节点 root的左(右)子树中,或 p = root,则称 root是 p的祖先。

  • 最近公共祖先的定义: 设节点 root为节点 p,q的某公共祖先,若其左子节点 root.left和右子节点 root.right都不是 p,q的公共祖先,则称 root是 “最近的公共祖先” 。

  • 根据以上定义,若 root 是 p,q的 最近公共祖先 ,则只可能为以下情况之一:

    • p 和 q在 root 的子树中,且分列 root 的 异侧(即分别在左、右子树中);
    • p = root,且 q 在 root的左或右子树中;
    • q = root,且 p在 root的左或右子树中;
  • 本题给定了两个重要条件:① 树为 二叉搜索树 ,② 树的所有节点的值都是 唯一 的。根据以上条件,可方便地判断 p,q与 root 的子树关系,即:

    • 若 root.val < p.val,则 p在 root右子树 中;
    • 若 root.val > p.val,则 p 在 root 左子树 中;
    • 若 root.val = p.val,则 p 和 root 指向 同一节点 。
  • 思路:迭代

    • 时间复杂度:O(n)

    • 空间复杂度:O(1)

      # 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 lowestCommonAncestor(self, root, p, q):
      """
      :type root: TreeNode
      :type p: TreeNode
      :type q: TreeNode
      :rtype: TreeNode
      """
      while root:
      if root.val < p.val and root.val < q.val: # p,q 都在 root 的右子树中
      root = root.right # 遍历至右子节点
      elif root.val > p.val and root.val > q.val: # p,q 都在 root 的左子树中
      root = root.left # 遍历至左子节点
      else: break
      return root
    • 优化:若可保证 p.val < q.val ,则在循环中可减少判断条件。

      # 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 lowestCommonAncestor(self, root, p, q):
      """
      :type root: TreeNode
      :type p: TreeNode
      :type q: TreeNode
      :rtype: TreeNode
      """
      if p.val > q.val: p, q = q, p # 保证 p.val < q.val
      while root:
      if root.val < p.val: # p,q 都在 root 的右子树中
      root = root.right # 遍历至右子节点
      elif root.val > q.val: # p,q 都在 root 的左子树中
      root = root.left # 遍历至左子节点
      else: break
      return 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 lowestCommonAncestor(self, root, p, q):
      """
      :type root: TreeNode
      :type p: TreeNode
      :type q: TreeNode
      :rtype: TreeNode
      """
      if root.val < p.val and root.val < q.val:
      return self.lowestCommonAncestor(root.right, p, q)
      if root.val > p.val and root.val > q.val:
      return self.lowestCommonAncestor(root.left, p, q)
      return root

二叉树的最近公共祖先

题目

  • 难度:简单

  • 题目(leetcode-面试题68II):给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

    百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

  • 示例:

    例如,给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

    输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
    输出: 3
    解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

    输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
    输出: 5
    解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
  • 说明:

    • 所有节点的值都是唯一的。
    • p、q 为不同节点且均存在于给定的二叉树中。

题解

  • 思路:

    • 考虑通过递归对二叉树进行后序遍历,当遇到节点 p 或 q 时返回。从底至顶回溯,当节点 p, q在节点 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 lowestCommonAncestor(self, root, p, q):
    """
    :type root: TreeNode
    :type p: TreeNode
    :type q: TreeNode
    :rtype: TreeNode
    """
    if not root or root == p or root == q: return root
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    if not left: return right
    if not right: return left
    return root
文章作者: Lesy
文章链接: https://lesylin.com/2020/06/13/%E5%89%91%E6%8C%87offer1/
文章声明: 转载请注明文章链接
打赏
  • 微信
  • 支付宝

Comment