米鼠商城

多快好省,买软件就上米鼠网

最新项目

人才服务

靠谱的IT人才垂直招聘平台

算法习题笔记

  • Elli_ON
  • 2
  • 2019-08-30 18:44
算法习题笔记》
作者:蒋辉    
日期:2019/8/9
jianghui17g@ict.ac.cn

题目说明

  • 1~3题为腾讯2019春招笔试题
  • 4~7题为头条2019春招笔试题
  • 8~70题为《剑指offer》第二版中的习题

代码地址:https://github.com/jh0905/data_structure_and_algorithm

1. 硬币问题(贪心算法)

牛家村的货币是一种很神奇的连续货币,他们货币的最大面额是n,并且一共有面额为1,2,3,…,n,n种面额的硬币。牛牛每次购买商品都会带上所有面额的硬币,支付时会选择给出硬币数量最少的方案。(每种面额的硬币有无限多个)

输入为两个整数m和n,表示货币的最大面额和商品的价格,输出为牛牛最少给出的硬币数量。

分析】   显然这是一个贪心算法,即尽可能多的用最大面额的硬币,如果剩余的商品价格小于最大硬币的话,就用对应金额的一枚硬币来填充。分析完之后,这就是一个向上取整的问题,在Python3中,直接 return (m+n-1) // m 来实现。

2. 奇怪的数列(分情况讨论)

有这么一个数列, { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , . . . } \{-1, 2, -3, 4, -5, 6, -7, 8, ...\} {−1,2,−3,4,−5,6,−7,8,...},可以发现,第奇数个元素的值为负数,第偶数个元素的值为正数,现在给出一个区间 [ l , r ] [l, r] [l,r], l l l表示第 l l l个元素, r r r表示第 r r r个元素,请输出区间 [ l , r ] [l, r] [l,r]所有元素的累加和。

分析】   观察发现,数列中每相邻的两个元素的和为同一个数,要么为+1,要么为-1,于是我们可以将区间 [ l , r ] [l, r] [l,r]里的元素两两分组,这里分组也是有两种情况,要么就剩下最后一个元素,要么所有元素都配对完成,之后就是一个简单的求和了。【考察分情况讨论的能力

l,r = [int(x) for x in input().split()] # 获取输入的区间范围
n_groups = (r-l+1)//2 # 获取分组数
reset= 0
if l%2 == 0: # l为偶数,相邻元素和为-1
	res = -1*n_groups
else:
	res = n_groups
if (r-l+1)%2 == 1: # 如果区间为奇数,则还会剩下一个数,这里的 r 记得判断是正数还是负数!!!!!!
	print(res + r*pow(-1,r))
else:
	print(res)

3. 猜拳游戏(排列组合)

两人玩一个石头剪刀布的游戏,游戏用卡片来玩,每张卡片分别是石头、剪刀、布中的一种,每种类型的卡片数量有无数个,赢局得1分,输局或平局得0分,小A先出牌,把 n n n张卡片摆好,那么小B在看得到小A每张牌的摆放情况下,如果要得s分,有多少种摆牌的方法呢?

分析】   根据题意,小B要得 s s s分,就意味着他有 s s s张卡片要胜过小A的卡片,用组合数表示为 C n s C_n^s Cns​,剩下的 ( n s ) (n-s) (n−s)张卡片,则为平局或输掉,即有 2 n s 2^{n-s} 2n−s种可能,也就是说,一共有 C n s 2 n s C_n^s\cdot2^{n-s} Cns​⋅2n−s种摆法,那么我们剩下来要做的事情,就是如何在满足内存和时间限制的前提下,计算出这个结果的值。

  • 杨辉三角公式:(用递归来实现) C m n = C m 1 n 1 + C m 1 n C_m^n=C_{m-1}^{n-1}+C_{m-1}^{n} Cmn​=Cm−1n−1​+Cm−1n​
def f(m, n):
	# 一定要记得处理 n = 0 的特殊情况
    if n == 0:
        return 1
    elif n == 1:
        return m
    elif m == n:
        return 1
    else:
        return f(m - 1, n - 1) + f(m - 1, n)
  • 转换为对数: C m n = m ! n ! ( m n ) ! C_m^n=\frac{m!}{n!\cdot(m-n)!} Cmn​=n!⋅(m−n)!m!​

l n    C m n = l n m ! n ! ( m n ) ! ln \;C_m^n=ln\frac{m!}{n!\cdot(m-n)!} lnCmn​=lnn!⋅(m−n)!m!​

  展开 ln ( C m n ) = ln ( m ! ) ln ( n ! ) ln ( ( m n ) ! ) ln ( C m n ) = i = 1 m ln ( i ) i = 1 n ln ( i ) i = 1 m n ln ( i ) \begin{array}{l}{\ln \left(C_{m}^{n}\right)=\ln (m !)-\ln (n !)-\ln ((m-n) !)} \\\\ {\ln \left(C_{m}^{n}\right)=\sum_{i=1}^{m} \ln (i)-\sum_{i=1}^{n} \ln (i)-\sum_{i=1}^{m-n} \ln (i)}\end{array} ln(Cmn​)=ln(m!)−ln(n!)−ln((m−n)!)ln(Cmn​)=∑i=1m​ln(i)−∑i=1n​ln(i)−∑i=1m−n​ln(i)​

  消除相同项(大大降低了计算的复杂度) ln ( C m n ) = i = n + 1 m ln ( i ) i = 1 m n ln ( i ) \ln \left(C_{m}^{n}\right)=\sum_{i=n+1}^{m} \ln (i)-\sum_{i=1}^{m-n} \ln (i) ln(Cmn​)=i=n+1∑m​ln(i)−i=1∑m−n​ln(i)

  组合数还有一个性质 C m n = C m m n C_m^n=C_m^{m-n} Cmn​=Cmm−n​

  于是我们在正式计算之前,判断 n m 2 n \leq \frac{m}{2} n≤2m​,不满足的话,令n=m-n .最终把计算结果再取指数e,用round四舍五入得到最终值。

import math

def g(m, n):
	# 一定要记得处理 n = 0 的特殊情况
    if n == 0:
        return 1
    if n > m // 2:
        n = m - n
    sum_1 = sum_2 = 0
    for i in range(n + 1, m + 1):
        sum_1 += math.log(i)
    for j in range(1, m - n + 1):
        sum_2 += math.log(j)
    return math.exp(sum_1 - sum_2)

  经试验证明,当n较小的时候,两种方式时间差别不是很大,但是当n变大时,二者的时间可以相差好几个量级!因此,推荐第二种解法。

4. 气球游戏(滑动窗口)

小Q在玩射击气球的游戏,如果小Q在连续T枪内打爆了所有颜色的气球,则会获得奖励(每种颜色至少一只)。这个游戏中共有m种不同颜色的气球,编号1到m,小Q连续开了n枪,命中的话,第n枪在数组中对应的值为气球编号,未命中则为0.

输入格式 第一行输入由空格隔开的两个整数n, m 第二行有n个被空格隔开的整数 输入示例: 12 5 2 5 3 1 3 2 4 1 0 5 4 3 输出格式 输出一个整数,表示最小连续射中所有颜色气球的枪数

分析】   这道题是典型的滑动窗口问题,先对滑动窗口做个简要介绍:   它也叫双指针算法,开始时刻,前、后指针都位于数组的第一个元素。前指针每次移动一位,后指针每次移动若干位。更进一步地分析,一开始前指针不动,后指针往后移动一位,每移动一位时,都会进行判断两个指针之间的元素是否满足题目要求,当满足要求时,后指针暂时停止移动。然后前指针开始往后移动一位,判断两个指针区间的元素是否仍然满足要求,是的话,后指针不动,前指针继续往后移一位。直到前指针判断移动后,要求不再满足时,则前指针不移动,随后换后指针后移一位,然后前指针判断是否需要后移一位。就这么持续下去,直到后指针和前指针都停止移动为止。这个时间复杂度是线性的。

关于本题的解析:   根据上面的分析,我们判断的条件,就是窗口内是否包含了每一种气球的颜色,我们可以用判断colors == m,然后再用一个长度为m的数组,存储当前窗口内每种颜色的气球的个数。此外,我们这里是要输出满足条件的最小窗口大小,所以当colors == m成立时,更新一下min_window_size的值。(代码更加具体,这里要注意未命中的情况balls[i]=0,记得排查,我忘记了几次!)

n, m = [int(x) for x in input().split()]  # n为balls数组的长度,m为气球的颜色数
balls = [int(x) for x in input().split()]
i = j = 0  # i表示前指针,j表示后指针
colors = 0
color_list = [0] * (m + 1)  # 这里初始化为m+1,是为了保证编号为j的气球,对应color_list[j],把color_list[0]空出来

res = n + 1  # 初始化返回值

while j < n:
    # 如果击中了气球并且滑动窗口中没这个值
    if balls[j] != 0 and color_list[balls[j]] == 0:
        colors += 1
    color_list[balls[j]] += 1
    if colors == m:  # 判断前指针的移动情况
        # balls[i] == 0 表示第i枪未命中气球,color_list[balls[i]] > 1表示有重复颜色气球被打破
        while balls[i] == 0 or color_list[balls[i]] > 1: 
            color_list[balls[i]] -= 1
            i += 1
        res = min(res, j - i + 1)
    j += 1
print(res)

5. 变身程序员(BFS,多源最短路问题)

公司的程序员不够用了,决定把产品经理都转变为程序员以解决开发时间长的问题。 在给定的矩形网格中,每个单元格可以有以下三个值之一:

  • 值0表示空单元格
  • 值1表示产品经理
  • 值2表示程序员

每一分钟,程序员都会把他上下左右相邻的产品经理变成程序员(1变成2)。 返回直到单元格中没有产品经理为止所必须经过的最小分钟数,如果不可能,返回-1.   以下是一个四分钟转换的例子: [ 2 1 1 1 1 0 0 1 1 ] [ 2 2 1 2 1 0 0 1 1 ] [ 2 2 2 2 2 0 0 1 1 ] [ 2 2 2 2 2 0 0 2 1 ] [ 2 2 2 2 2 0 0 2 2 ] \left[\begin{array}{rrr}{2} &amp; {1} &amp; {1} \\ {1} &amp; {1} &amp; {0} \\ {0} &amp; {1} &amp; {1}\end{array}\right] \rightarrow \left[\begin{array}{rrr}{2} &amp; {2} &amp; {1} \\ {2} &amp; {1} &amp; {0} \\ {0} &amp; {1} &amp; {1}\end{array}\right] \rightarrow \left[\begin{array}{rrr}{2} &amp; {2} &amp; {2} \\ {2} &amp; {2} &amp; {0} \\ {0} &amp; {1} &amp; {1}\end{array}\right] \rightarrow \left[\begin{array}{rrr}{2} &amp; {2} &amp; {2} \\ {2} &amp; {2} &amp; {0} \\ {0} &amp; {2} &amp; {1}\end{array}\right] \rightarrow \left[\begin{array}{rrr}{2} &amp; {2} &amp; {2} \\ {2} &amp; {2} &amp; {0} \\ {0} &amp; {2} &amp; {2}\end{array}\right] ⎣⎡​210​111​101​⎦⎤​→⎣⎡​220​211​101​⎦⎤​→⎣⎡​220​221​201​⎦⎤​→⎣⎡​220​222​201​⎦⎤​→⎣⎡​220​222​202​⎦⎤​

分析】   题目的意思很好理解,在一个由 { 0 , 1 , 2 } \{0,1,2\} {0,1,2}三个数字填满的二维矩阵。每一轮,数字 2 2 2会把它上下左右相邻的 1 1 1变成 2 2 2,然后进入下一轮,上一轮被转变的 1 1 1会把它相邻的数字 1 1 1继续转换为 2 2 2,由此递归下去。这其实就是图搜索中的宽度优先搜索过程,由于我们可能会有多个起点(元素 2 2 2),所以它也可以归类为多源最短路问题。

关于本题的解析   多源最短路问题解法分为两步:    (1)所有起点(源)坐标插入队列 [ &ThickSpace; [ i 1 , j 1 ] , [ i 2 , j 2 ] , [ i 3 , j 3 ] , . . . , &ThickSpace; ] [ \;[i_1,j_1], [i_2,j_2], [i_3,j_3],...,\;] [[i1​,j1​],[i2​,j2​],[i3​,j3​],...,] 队列具有先进先出的性质;    (2)进行 b r e a d t h &ThickSpace; f i s r t &ThickSpace; s e a r c h breadth\;fisrt\;search breadthfisrtsearch ,每次弹出队列中的第一个元素queue.pop(0),然后搜索该元素相连的点(在本题中是上下左右四个点),搜索到满足要求的点,修改该点距离起点的距离,并把该点的坐标append到队列中;(当队列中的元素为空时,搜索结束)

import sys

lines = sys.stdin.readlines()
input_mat = []
for line in lines:
    input_mat.append([int(x) for x in line.strip().split()])

rows = len(input_mat)
columns = len(input_mat[0])

# 初始化distance矩阵,shape和输入矩阵一样,目的是存储矩阵中每个点距离起点的距离
dist_mat = [[-1 for i in range(columns)] for j in range(rows)]

# 第一步:把第一轮遍历的起点坐标加入到队列中
queue = []
for i in range(rows):
    for j in range(columns):
        if input_mat[i][j] == 2:
            dist_mat[i][j] = 0
            queue.append([i, j])

# 每一对[dx,dy]表示朝上下左右的某一个方向移动
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 第二步:开始 breadth first search
while queue:
    idx_x, idx_y = queue.pop(0)  # 弹出队列中的第一个元素
    for i in range(4):
        x = idx_x + dx[i]
        y = idx_y + dy[i]
        # 如果上下左右的点,索引没有越界,并且它对于的值为1,而且它还没被访问过dist_mat[x][y] == -1
        if 0 <= x < rows and 0 <= y < columns and input_mat[x][y] == 1 and dist_mat[x][y] == -1:
            dist_mat[x][y] = dist_mat[idx_x][idx_y] + 1  # 当前点距起点的距离,等于它上一点的距离值+1
            queue.append([x, y])  # 把这个点添加到队列中,之后继续执行bfs

# 第三步:遍历距离矩阵,找到-1则返回-1,否则返回矩阵中最大的值
res = 0
for i in range(rows):
    for j in range(columns):
        if dist_mat[i][j] == -1:
            res = -1
        else:
            res = max(res, dist_mat[i][j])
print(res)

6. 特征提取(暴力法的优化)

小明想从猫咪视频中挖掘一些猫咪的运动信息,为了提取运动信息,他需要从视频的每一帧中提取特征。 一个猫咪特征是一个二维的 v e c t o r &ThickSpace; vector\; vector<x, y>. 当 x 1 = x 2 , y 1 = y 2 x_1 = x_2, y_1 = y_2 x1​=x2​,y1​=y2​ 时,我们认为< x 1 x_1 x1​, y 1 y_1 y1​>和< x 2 x_2 x2​, y 2 y_2 y2​>为相同特征。 如果在连续的几个帧里面,都出现了相同的特征,它将构成特征运动。 小明期望找到最长的特征运动长度

输入格式 第一行为正整数M,代表视频的帧数 接下来的M行里,每行代表一帧,第一个数字代表该帧的特征个数,接下来的数字代表特征的取值,比如样例输入第三行里,2 1 1 2 2,表示2个特征,分别为<1, 1>、<2, 2> 输出格式 输出一个整数,表示最长特征运动长度

分析】   题目的意思是,在输入的连续帧中,遍历每一个特征连续出现的最大长度。我们可以直接用暴力法来尝试求解此题。注意哦,我们每一次搜索是从当前帧往上进行搜索!

暴力法求解思路

  • 第一层for循环,是对输入的所有帧进行遍历;
  • 第二层for循环,是对当前帧里的每一组特征进行遍历;
  • 第三层for循环;是从当前帧往上面的每一帧进行遍历;
  • 第四层for循环,是比较遍历的帧中是否包含此时的特征值。
# 接收输入,存储所有帧的信息
M = int(input())
frames = []
while M:
    frame = [int(x) for x in input().strip().split()]
    n = frame.pop(0)  # 提取出特征总数
    features = []  # 用来存储特征对
    for i in range(n):
        # 注意,这里把特征对保存为tuple形式,是为了之后让它作为dict的键,因为list不能作为键
        features.append(tuple(frame[2 * i: 2 * i + 2]))
    frames.append(features)
    M -= 1
# 当前帧是一定有该特征的,故初始长度为1,我们从当前层的上一帧开始查找
max_length = length = 1
for i in range(len(frames)):  # 第一层:从上到下,遍历每一帧
    for j in range(len(frames[i])):  # 第二层:遍历每一帧的每一个特征对
        for k in range(i - 1, -1, -1):  # 第三层:从当前帧的上一帧,往上查找
            if frames[i][j] in frames[k]:  # 第四层:判断当前特征是否在该帧出现
                length += 1
            else:
                break  # 退出第三层循环
        max_length = max(max_length, length)
        length = 1  # 退出第三层循环时,要把length重置为1
print(max_length)

暴力法的优化   上面写到的暴力法,会带来运行超时的问题,所以我们针对上面的做法进行优化。设置last_time和count两个字典变量,last_time[(x,y)]表示特征对(x,y)上一次出现的帧,count(x,y)表示特征对(x,y)的最长特征长度。   如果last_time[(x,y)] < i-1 (i-1表示当前帧的上一帧) 的话,说明特征不连续了,我们不需要往上进行查找,并更新last_time[(x,y)]和count(x,y)的值;   如果last_time[(x,y)] == i-1,那么当前特征的最长特征长度,则为count[(x, y)]+1,同样更新last_time[(x,y)]的值;

max_length = 0
last_time = dict()
count = dict()  # 初始化两个字典变量
for i in range(len(frames)):  # 第一层:从上到下,遍历每一帧
    for j in range(len(frames[i])):  # 第二层:遍历每一帧的每一个特征对
        feature_pair = frames[i][j]
        if feature_pair not in last_time:  # 如果当前特征第一次出现
            count[feature_pair] = 1
        elif last_time[feature_pair] == i - 1:  # 当前特征在上一帧中出现
            count[feature_pair] += 1
        elif last_time[feature_pair] < i - 1:  # 如果同一个帧中有两个相同的特征,则会出现last_time[feature_pair] == i > i-1
            count[feature_pair] = 1
        max_length = max(max_length, count[feature_pair])
        last_time[feature_pair] = i
print(max_length)

  Python里面尽量不要使用连等于赋值变量,很容易出问题。我这边一开始初始化last_time=count=dict(),结果一直出错,发现这两个变量被绑定在一起,我对last_time赋值的时候,count也被赋值了,所以变量初始化的话,就不要用连等了,容易出错。

7. 机器人跳跃问题(二分法)

机器人正在玩一个古老的基于DOS的游戏,游戏中有N+1座建筑,从0到N编号,从左到右排列。 编号为0的建筑高度为0个单位,编号为 i i i的建筑为 h ( i ) h(i) h(i)个单位。 起初,机器人在编号为0的建筑处,每一步,它要跳到下一个建筑。 假设机器人在第k个建筑,且它的能量值为E,下一步它将跳到第k+1个建筑。 如果 h ( k + 1 ) &gt; E h(k+1)&gt;E h(k+1)>E,它将失去 h ( k + 1 ) E h(k+1)-E h(k+1)−E的能量,否则它将获得 E h ( k + 1 ) E-h(k+1) E−h(k+1) 的能量。 游戏目标是到底第N个建筑,在这个过程中,机器人的能量不能为负数。 现在的问题是,机器人初始时以多少能量值开始游戏,才可以保证成功完成这个游戏。

输入格式 第一行输入正数 N N N, 第二行为N个空格隔开的整数, 1 N , &ThickSpace; H ( i ) 1 0 5 1 \leq N, \;H(i) \leq 10^5 1≤N,H(i)≤105 输出格式 一个整数,表示最小的能量值

分析

  题目的要求是,机器人的能量不能为负数,即假设机器人到达第 k k k个建筑的时候,它的能量值为 ϵ \epsilon ϵ,那么它跳到第k+1个建筑的时候,能量值则变为 ϵ + [ ϵ h ( k + 1 ) ] = 2 ϵ h ( k + 1 ) \epsilon+[\epsilon-h(k+1)]=2\epsilon-h(k+1) ϵ+[ϵ−h(k+1)]=2ϵ−h(k+1) 。

  于是我们可以用二分查找法,在 区间内,找到一个值,使得低于它的无法通过游戏,高于或等于它的都能通过游戏。

N = int(input())
h = [int(x) for x in input().strip().split()]


# 判断能量值e能否跳完所有建筑
def check(e):
    for i in range(N):
        e = 2 * e - h[i]
        if e < 0:
            return 0
    return 1


# log N的时间复杂度很低,我们直接设置搜索区间为[0,10010]
l = 0
r = 10010
while l < r:
    mid = (l + r) // 2
    # 如果mid成立,那么说明答案在左区间,用模板1(见下文)
    if check(mid):
        r = mid
    else:
        l = mid + 1
print(l)

  【注】上面代码使用的前提是,在查找区间里,一定有符合题意的搜索结果!上面代码,可以作为二分查找的一个模板,但是要记得使用前提。

  二分查找法的时间复杂度为 O ( l o g N ) O(log N) O(logN),是时间复杂度最低的算法, O ( l o g 1 0 5 ) 5 2.3 10 O(log 10^5) \approx 5*2.3 \approx 10 O(log105)≈5∗2.3≈10,也就是说哪怕搜索空间扩大一个量级,搜索次数也没扩大多少。


  二分查找模板总结

  假设目标值在闭区间 [ l , r ] [l,r] [l,r]中,每次将区间长度缩小一半,当 l = r l=r l=r时,我们就找到了目标值。

  • 模板一如果check条件成立,答案在左区间并且mid也可能是答案时,用此模板:
def bsearck_1(l, r):
    while l < r:
        mid = (l + r) // 2
        if check(mid):
            r = mid
        else:
            l = mid + 1
    return l
  • 模板二如果check条件成立,答案在右区间并且mid也可能是答案时,用此模板:
def bsearck_2(l, r):
    while l < r:
        mid = (l + r + 1) // 2 # 避免死循环,解决l=r-1的情况
        if check(mid):
            l = mid
        else:
            r = mid - 1
    return l

8. 找出数组中重复的数字(n个坑,n个数)

在一个长度为n的数组里的所有数字都在 [ 0 , n 1 ] [0,n-1] [0,n−1]的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的,也不知道每个数字重复几次。 请找出数组中任意一个重复的数字! 注意:如果某些数字不在 0 n 1 0 \sim n-1 0∼n−1范围内,输出 -1

分析】   数组的特性是,所有值都在 [ 0 , n 1 ] [0,n-1] [0,n−1]内,一共有 n n n个数,如果没有重复数字的话,那么每个元素应该在它对应的下标位置。于是我们从前往后遍历,如果当前元素不在正确位置上,那就swap nums[i] 和 nums[nums[i]],一直进行下去,直到交换后的两个数都在其正确位置上。当退出while循环的时候,如果当前位置的元素不在其正确位置上,而它想交换的元素已经在正确位置上,那就找到重复元素了。

class Solution:
    def duplicate(self, numbers):
        if numbers is None:
            return -1
        # 题目要求输入的数组在[0,n-1]区间内
        for i in range(len(numbers)):
            if numbers[i] < 0 or numbers[i] > len(numbers) - 1:
                return -1
        # 时间复杂度为O(n)
        for i in range(len(numbers)):
            # 当前索引与它对应的元素不等,并且以该元素作为索引指向的值也不等于该元素时,则交换两个元素
            while i != numbers[i] and numbers[i] != numbers[numbers[i]]:
                temp = numbers[i]
                numbers[i] = numbers[numbers[i]]
                numbers[temp] = temp  # 这里交换的时候,得小心点
            # 当前索引与它对应的元素不等,并且以该元素作为索引指向的值等于该元素时,则发现重复元素
            if i != numbers[i] and numbers[numbers[i]] == numbers[i]:
                return numbers[i]
        return -1 

9. 不修改数组找出重复的数字(n个坑,n+1个数)

给定一个长度为n+1的数组,数组中所有的数均在1~n的范围内,其中n \ge ≥ 1 请找出数组中任意一个重复的数,但不能修改输入的数组

分析】   数组中所有的数都在 [ 1 , n ] [1,n] [1,n]内,说明我们有n个坑,数组长度为n+1,说明我们有n+1个数。这就体现了抽屉原理,我们有3个苹果,放在2个抽屉里,那么肯定有一个抽屉里的苹果数超过1。   我们可以用分治的思想来做,把整个区间(所有的坑)一分为二,那么至少有一边,里面数的个数,肯定大于坑的个数。我们按照这个思想,用二分法来做。

class Solution:
    def find_duplicate(self, numbers):
        l = 1
        r = len(numbers) - 1
        while l < r:
            mid = (l + r) // 2
            if self.check(numbers, l, mid):
                r = mid
            else:
                l = mid + 1
        return l

    def check(self, numbers, l, mid):
        count = 0
        for i in range(len(numbers)):
            if l <= numbers[i] <= mid:
                count += 1
        if count > mid - l + 1:
            return 1
        else:
            return 0

10. 重建二叉树(DFS)

根据一棵树的前序遍历与中序遍历构造二叉树。 注意:你可以假设树中没有重复的元素

输入: 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 输出:   3  / \ 9   20   /  \   15  7

分析】   已知 preorder : root left right \text{preorder}:\text{root}\rightarrow \text{left}\rightarrow \text{right} preorder:root→left→right, inorder : left root right \text{inorder}:\text{left}\rightarrow \text{root}\rightarrow \text{right} inorder:left→root→right,所以先序遍历的第一个元素,即为根结点的值,找到根结点的值之后,可以将中序遍历数组分成两部分,得到左子树的元素个数和右子树的元素个数,按照此思路递归下去。核心在于设定递归式,我们这里用dfs(self, pl, pr, il, ir)完成递归,pl表示前序遍历左区间的下标,pr表示前序遍历右区间的下标,il表示中序遍历左区间的下标,il表示中序遍历右区间的下标。   本题的难点在于区间下标的设定,不能混淆数组下标和数组分片,否则边界肯定会出问题,我们这里只用数组下标,并且用闭区间进行表示(不考虑数组分片)。

  还有一个问题是,类变量的使用,我之前没这么玩过,在类的方法中,调用类变量时,记得要在前面加上self关键字!

class Solution(object):
    preorder = []
    inorder = []

    def buildTree(self, _preorder, _inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int] 
        :rtype: TreeNode
        """
        self.preorder = _preorder
        self.inorder = _inorder
        return self.dfs(0, len(self.preorder) - 1, 0, len(self.inorder) - 1)

    def dfs(self, pl, pr, il, ir):
        """
        数组范围是闭区间
        pl:前序遍历左边界
        pr:前序遍历右边界
        il:中序遍历左边界
        ir:中序遍历右边界
        """
        if pl > pr:
            return
        root = TreeNode(self.preorder[pl])
        idx = self.inorder.index(self.preorder[pl])
        left = self.dfs(pl + 1, pl + idx - il, il, idx - 1)
        right = self.dfs(pl + idx - il + 1, pr, idx + 1, ir)
        root.left = left
        root.right = right
        return root

11. 二叉树中的下一个节点(分情况讨论)

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。 注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针

分析】   观察下图,我把图中节点用三种颜色表示:

  橙色节点:存在右子树,它的下一个节点为右子树中最左侧的节点;   绿色节点:不存在右子树,但是它为父节点的左儿子,它的下一个节点为 node.father   蓝色节点:不存在右子树,但是它为父节点的右儿子,往上遍历,直到它的父节点为它父节点的左儿子(如E的父节点为B,B的父节点为A,它为A的左儿子)或者父节点为None(如G的父节点为C,C的父节点为A,A的父节点为None

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.father = None


class Solution:
    def getNext(self, pNode):
        if pNode.right:
            p = pNode.right
            while p.left:
                p = p.left
            return p
        while pNode.next and pNode.next.right == pNode:
            pNode = pNode.next
        return pNode.next

12. 寻找旋转排序数组中的最小值(二分法)

假设按照升序排序的数组在预先未知的某个点上进行了旋转。 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 你可以假设数组中可能存在重复元素。

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

分析】   根据题意,我们绘制图像如下:

  如图所示,原始数组是一个升序数组,可能存在重复元素,在某个点旋转之后,得到一个旋转数组(绿色部分与橙色部分),如果我们把绿色可能存在的与橙色数组首元素相当的项(图中黑线表示)去除点,那么我们得到的数组就符合二分法的要求了,即所求元素将数组分为两个区间,左区间内的所有元素均大于等于数组中第一个元素,右区间内的所有元素均小于数组中的第一个元素

  另外要注意考虑特殊情况,即右边数组可能为空,这时候直接返回第一个元素!

class Solution:

    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray) == 0:
            return -1
        n = len(rotateArray) - 1
        # 1.去重
        while rotateArray[n] == rotateArray[0]:
            n -= 1
        # 2.如果剩下数组为递增序列,直接返回首元素
        if rotateArray[n] >= rotateArray[0]:
            return rotateArray[0]
        # 3.否则使用二分查找法
        l = 0
        r = n
        while l < r:
            mid = (l + r) // 2
            if rotateArray[mid] < rotateArray[0]:
                r = mid
            else:
                l = mid + 1
        return rotateArray[l]

  题目稍作修改,如果要返回旋转数组中最大的元素,将二分查找做一些变化即可。(这里只讨论二分法部分的代码)

# 使用二分查找法找到最大的元素
l = 0
r = n
while l < r:
    mid = (l + r + 1) // 2 # 避免死循环
    if rotateArray[mid] < rotateArray[0]:
        r = mid - 1
    else:
        l = mid
return rotateArray[l]

13. 矩阵中的路径(回溯法 && DFS)

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。

  如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。 例如 b b c e s f  c s a d e e 这样的 3 × 4 3 \times 4 3×4 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

【分析】   本题考察的是一个回溯问题。回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。 但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

  回溯问题一般会用到暴力法,枚举思路很重要。

   我们先枚举单词的起点(遍历输入矩阵中的每一个字母),然后使用深度优先遍历,如果矩阵中的当前元素等于单词中的当前字母,并且当前单词的index不等于单词最后一个字母的index的话,就DFS该单词的下一个字母(上下左右进行搜索)。

  需要注意的是:过程中需要将已经使用过的字母改成一个特殊字母,以避免重复使用字符。

class Solution(object):
    def hasPath(self, matrix, path):
        """
        :type matrix: List[List[str]]
        :type path: str
        :rtype: bool
        """
        if len(matrix) == 0 or len(matrix[0]) == 0 or len(path) == 0:
            return False
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                if self.dfs(matrix, path, 0, row, col):
                    return True
        return False

    def dfs(self, matrix, path, path_idx, x, y):
        """
        :param matrix: 输入矩阵
        :param path: 输入路径
        :param path_idx: 待查找路径中的元素下标
        :param x: 暴搜法的矩阵元素横坐标
        :param y: 暴搜法的矩阵元素纵坐标
        :return:
        """
        if matrix[x][y] != path[path_idx]:
            return False
        if path_idx == len(path) - 1:
            return True
        temp = matrix[x][y]
        matrix[x][y] = "*"  # 把矩阵中的元素设为不存在的元素,避免它被重复使用
        dx = [-1, 1, 0, 0]
        dy = [0, 0, 1, -1]
        # 寻找上下左右四个方向,是否存在一个点为路径中的下一个元素
        for i in range(4):
            a = x + dx[i]
            b = y + dy[i]
            if 0 <= a < len(matrix) and 0 <= b < len(matrix[0]):
                if self.dfs(matrix, path, path_idx + 1, a, b):
                    return True
        matrix[x][y] = temp  # 还原矩阵原始值
        return False

14. 机器人的运动范围(BFS)

地上有一个 m 行和 n 列的方格,横纵坐标范围分别是 0∼m−1 和 0∼n−1。 一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格。 但是不能进入行坐标和列坐标的数位之和大于 k 的格子。 请问该机器人能够达到多少个格子?

输入:k=18, m=40, n=40 输出:1484 解释:当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。 但是,它不能进入方格(35,38),因为3+5+3+8 = 19。

分析】   本题考察的是一个宽搜的问题,机器人不能进入到行坐标和列坐标的数位之和大于k,可理解为矩阵中,部分网格存在障碍物,机器人无法移动

  如上图所示,机器人在一个 13 × 14 13 \times 14 13×14的网格里,起点位置为 ( 0 , 0 ) (0,0) (0,0),按照题意要求,我们将矩阵下标的数位之和小于或等于 3 3 3的网格,用绿色标识,其他网格用障碍物标识。

  很明显可以看到,满足条件的网格被分为四块区间,中间被障碍物阻隔开,如果机器人初始位置在 ( 0 , 0 ) (0,0) (0,0)的话,则只能在一块绿色区域中移动,其他位置到达不了。

  前面说过这是一个BFS的问题,BFS有固定的解题模板,BFS要有一个维护一个队列Queue,每次循环pop出队首元素,判断当前元素是否被访问过或者是否满足题意要求,条件不成立的话,continue,成立的话,则往上下左右四个方向进行延伸,如果新节点在矩阵范围内,且未被访问,我们就将其添加到队列末尾。

  具体编写代码如下:

class Solution:
    def get_num(self, x):
        num = 0
        while x:
            num += x % 10
            x = x // 10
        return num

    def check(self, threshold, x, y):
        """
        判断当前格子下标的数值和是否大于阈值
        :param threshold:
        :param x:
        :param y:
        :return: bool
        """
        if self.get_num(x) + self.get_num(y) > threshold:
            return True
        return False

    def movingCount(self, threshold, rows, cols):
        res = 0
        if threshold < 0 or rows <= 0 or cols <= 0:
            return res
        label_mat = [[0] * cols for _ in range(rows)]  # 初始化label矩阵,用来标记当前元素是否已访问
        queue = [[0, 0]]  # 初始化BFS搜索队列,首先喂进去矩阵中的第一个元素
        dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
        while queue:
            x, y = queue.pop(0)  # 弹出队列中的队首元素的坐标
            # 检查当前元素是否已访问(因为搜索队列中某个元素可能被重复添加)or 矩阵下标大于阈值,为障碍物,不能移动!
            if label_mat[x][y] == 1 or self.check(threshold, x, y):
                continue
            res += 1
            label_mat[x][y] = 1  # 将矩阵中的当前元素标记为已访问
            for i in range(4):
                a = x + dx[i]
                b = y + dy[i]
                if 0 <= a < rows and 0 <= b < cols and label_mat[a][b] == 0:
                    queue.append([a, b])
        return res

15. 剪绳子(整数划分)

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

分析】   本题是一个经典的整数划分问题,里面有一些重要的结论,我们下面具体来分析!

  考虑把一个整数 N N N分成 m m m段,即 N = n 0 + n 1 + n 2 + + n m N=n_0+n_1+n_2+\cdots+n_m N=n0​+n1​+n2​+⋯+nm​

  如果存在 n i 5 n_i \geq5 ni​≥5 ,则 3 × ( n i 3 ) &gt; n i 3\times(n_i-3)&gt;n_i 3×(ni​−3)>ni​ 式子变形可得 n i &gt; 4.5 n_i&gt;4.5 ni​>4.5,必成立。 这说明了一个重要的结论,如果要让划分的段的乘积尽可能大,则每一段的长度一定要小于 5 5 5。那我们划分的段的长度,只能在 2 3 4 2,3,4 2,3,4中取得。

  长度 4 4 4也可以划分为 2 × 2 2\times 2 2×2所以进一步缩小范围,我们划分的段的长度只能在2,3中取得。

  然而, 2 × 2 × 2 &lt; 3 × 3 2\times2\times2&lt;3\times3 2×2×2<3×3我们再次得出一个结论,划分完的段中,长度为 2 2 2的段最多只有 2 2 2个。

  因此,结论如下:

  把一个整数 N N N划分为 m m m段,最多有 2 2 2个长度为 2 2 2的段,其余全部为 3 3 3;

  我们令 n = N m o d &ThinSpace;&ThinSpace; 3 n = N\mod 3 n=Nmod3:

  • 如果 n = 0 n = 0 n=0,则把 N N N全部划分为长度为3的段;
  • 如果 n = 1 n=1 n=1,则把 N N N划分出2个长度为2的段,其余长度全部为3;
  • 如果 n = 2 n=2 n=2,则把 N N N划分出1个长度为2的段,其余长度全部为3;
class Solution(object):
    def maxProductAfterCutting(self, n):
        if n <= 3:
            return 1 * (n - 1)
        a = n % 3
        if a == 0:  # 能被3整除,直接全部划分为3
            return pow(3, n // 3)
        elif a == 1:  # 模为1,则划分出2个长度为2的段,其余全部为3
            return pow(3, (n - 4) // 3) * 4
        else:  # 模为2,则划分出1个长度为2的段,其余全部为3
            return pow(3, (n - 2) // 3) * 2

16. 二进制中1的个数(位运算)

输入一个32位整数,输出该数二进制表示中1的个数。 注意: 负数在计算机中用其绝对值的补码来表示。

输入:-2 输出:31 解释:-2在计算机里会被表示成11111111 11111111 11111111 11111110, 一共有31个1。

分析】   首先了解一下补码的概念,简单明了的说,在计算机中,如果两个数互为补码,那就意味着它们的二进制数之和为 10000...0000 1 0000...0000 10000...0000, 1 1 1的后面一共有 32 32 32个 0 0 0。

  我们知道, 2 2 2的补码是 2 -2 −2, 2 2 2 的二进制表示为 00000000 &ThickSpace; 00000000 &ThickSpace; 00000000 &ThickSpace; 00000010 00000000 \;00000000 \;00000000 \;00000010 00000000000000000000000000000010, 2 -2 −2 的表示则为 11111111 &ThickSpace; 11111111 &ThickSpace; 11111111 &ThickSpace; 11111110 11111111\; 11111111\; 11111111\; 11111110 11111111111111111111111111111110,二者之和,满足上述性质。

  说回本题,思路很简单,我们只需要把输入整数转为无符号整数即可,python中用 num&amp;0xffffffff \text{num\&amp;0xffffffff} num&0xffffffff来实现。

  对于一个无符号整数 num \text{num} num, num&amp;1 \text{num\&amp;1} num&1表示取 num \text{num} num二进制表示最右边一位的值。 num&gt;&gt;1 \text{num&gt;&gt;1} num>>1表示将 num \text{num} num右移一位。

  具体代码如下:

class Solution(object):
    def NumberOf1(self,n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        # 直接转换为32位的无符号整数,排除负数的影响
        n = n & 0xffffffff
        while n:
            count += n&1
            n = n >> 1
        return count

17. 删除链表中重复的节点(双指针法)

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留。

样例1 输入:1->2->3->3->4->4->5 输出:1->2->5

样例2 输入:1->1->1->2->3 输出:2->3

分析】   首先呢,对于这种删除链表中的节点类型的题,我们要考虑头节点可能会被删除的情况,因此,第一步是创建一个虚拟头节点,指向真实的头节点。dummy=ListNode(-1) dummy.next=head

  其次呢,这里说的删除重复的节点,是指把所有重复的节点都删除,而不是保留一个,注意理解题意。

  然后,这题可以用双指针法来做,这是一个排序的链表,所以重复节点一定相邻。让一个指针 p \text{p} p指向链表中,按从前往后遍历的顺序,未重复出现的第一个节点,所以这里 p \text{p} p初始时指向 dummy \text{dummy} dummy节点,指针 q \text{q} q指向 p \text{p} p的下一个节点。

  while循环,如果 q \text{q} q 存在,且 q \text{q} q 指向的节点值与 p \text{p} p 的下一个节点指向的值相等,则 q = q.next,当 while 不满足时,进行if判断,如果p.next.next = q,说明p.next指向的节点为下一个不重复的节点,则令 p = p.next,否则说明p.next指向的节点为重复出现的节点,需要将这些重复节点删除,令p.next = q

  具体代码如下:

class Solution(object):
    def deleteDuplication(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 创建一个虚拟头节点,避免真正的头节点被删掉
        dummy = ListNode(-1)
        dummy.next = head
        # python分为可变对象赋值和不可变对象赋值
        # 此处是可变对象赋值,p和dummy指向的同一块内存区域,p发生修改,dummy的内容也会跟着修改
        p = dummy
        while p.next: # 此处的while判断是一个细节,省去了很多麻烦!!!
            q = p.next
            # 初始时,p.next和q指向同一个节点,所以如果q存在,循环一定会执行一次
            while q and p.next.val == q.val:
                q = q.next
            if p.next.next == q:
                p = p.next
            else:
                p.next = q
        return dummy.next

18. 调整数组顺序使偶数位于奇数之后(双指针法)

输入一个整数数组,实现一个函数来调整该数组中数字的顺序。 使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分。

输入:1 2 3 4 5 输出:1 5 3 4 2

分析】   本题是一个双指针的问题,一个指针 i i i指向数组头部,一个指针 j j j指向数组尾部。

  我们要保证 i i i之前的每一个元素都是奇数, j j j之后的每一个元素都是偶数。 于是两个指针开始移动,当 i i i遇到偶数时停止,当 j j j遇到奇数时停止,然后把两个指针的元素交换(交换前提是)。

  整个过程中,始终要保证 i &lt; = j i&lt;=j i<=j。

class Solution:
    def reorder_array(self, nums):
        i = 0
        j = len(nums) - 1
        while i <= j:
            while i <= j and nums[i] % 2 == 1:
                i += 1
            while i <= j and nums[j] % 2 == 0:
                j -= 1
            if i <= j:
                nums[i], nums[j] = nums[j], nums[i]
        return nums

19. 返回链表中倒数第k个节点(双指针法)

输入一个链表,输出该链表中倒数第k个结点。 注意: k &gt; 1 k&gt;1 k>1,如果 k k k大于链表长度,那么返回None

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

分析】   本题有两种做法,第一种做法是我比较喜欢的做法,双指针法,我们思考一下,如果求倒数第 k k k个节点,那么我们只需要定义两个指针,一个指针指向链表头,另一个指针指向链表头的下一个节点,也就是说两个指针之间的间隔为 k 1 k-1 k−1,然后两个指针一起向后移动,当指针 q q q移到链表尾部的时候,指针 p p p也就到了倒数第 k k k个节点的位置。

  第一步,我们把指针 q q q后移 k 1 k-1 k−1位,这里存在一个 k k k可能大于表长的问题,所以在后移时进行判断, q q q 是否会移到None的位置;

  第二步,同时将指针 p p p和 q q q向后移到,当指针 q q q移到链表尾的时候,指针 q q q 到达了倒数第 k k k个节点的位置。

class Solution:
    def FindKthToTail(self, pListHead, k):
        if not pListHead or k < 1:
            return None
        p = pListHead
        q = pListHead
        k -= 1
        while k:
            if not q.next:
                return None
            q = q.next
            k -= 1
        while q.next:
            q = q.next
            p = p.next
        return p

  第二种解法是,我们要从前往后遍历一下整个链表的长度,然后也就能知道从头部到倒数第 k k k的节点的长度了。

class Solution:
    def findKthToTail_2(self, pListHead, k):
        n = 0
        p = pListHead
        while p:
            n += 1
            p = p.next
        if n == 0 or k < 1 or k > n:
            return None
        p = pListHead
        while k < n:
            p = p.next
            k += 1

20. 链表中环的入口位置(快慢指针,找规律)

给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出None。

分析】   之前我们一定听说过如果判断一个单链表中是否存在环的问题,一个好的思路就是快慢指针法,一个指针每次走一步,另一个每一次走两步。如果存在环,那么两个指针一定会相遇,如果不存在环,那么快指针一定会到达尾节点(如何判断尾结点? node.next is None)。

  现在的问题,是上面一个问题的进阶版,如果存在环,返回入口节点;如果不存在环,返回None。

  我们通过下图展开详细分析链表中存在环的情况。

  图中我们标记了三个节点,A表示链表头节点,B表示环的入口节点,C表示快慢指针相遇的节点。我们用 x x x 表示 A B A\rightarrow B A→B 的距离,用 y y y 表示 B C B\rightarrow C B→C 的距离,用 z z z 表示 C B C\rightarrow B C→B 的距离。(我们定义慢指针为 p p p ,快指针为 q q q

  当两个指针相遇时,有:

  • 慢指针走了 x + y x+y x+y 距离
  • 快指针走了 x + ( y + z ) n + y x+(y+z)\cdot n+y x+(y+z)⋅n+y 距离(假设快指针已经在环里面循环了 n n n 圈, n 1 n\geq 1 n≥1)

  快指针每次走两步,慢指针每次走一步,因此有: x + ( y + z ) n + y 2 = x + y \frac{x+(y+z)\cdot n + y}{2}=x+y 2x+(y+z)⋅n+y​=x+y

x = ( n 1 ) ( y + z ) + z x = (n-1)\cdot(y+z)+z x=(n−1)⋅(y+z)+z

  于是: x + y = ( n 1 ) ( y + z ) + z x+y=(n-1)\cdot(y+z)+z x+y=(n−1)⋅(y+z)+z

= n ( y + z ) &ThickSpace;&ThickSpace;&ThickSpace;&ThickSpace;&ThickSpace;&ThickSpace; =n \cdot (y+z)\;\;\;\;\;\; =n⋅(y+z)

  也就是说,在相遇点C的位置,走 x x x 步,就必能到达节点 B 。

  怎么找到 x x x 呢?注意到头节点到环的入口节点的长度就是 x x x,我们把一个指针重置到头节点,两个指针同时移动,每次移动一步,那么相遇的时候,即为环的入口节点!

class Solution(object):
    def entryNodeOfLoop(self, head):
        p = head
        q = head
        while p and q:
            p = p.next
            q = q.next
            if q:
                q = q.next
            else: # 说明不存在环,q抵达尾节点
                return None
            if p == q: # 说明链表存在环
                p = head
                while p != q:
                    p = p.next
                    q = q.next
                return p
        return None

21. 反转链表(三指针法)

定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。

输入:1->2->3->4->5->NULL 输出:5->4->3->2->1->NULL

分析

  反转一个单链表,它的核心在于,我们要用一个指针保存当前节点的前驱节点。

  有了前驱节点之后,思路就比较简单了, post \text{post} post指针指向当前节点的下一个节点, cur \text{cur} cur指针指向它的前驱节点, pre \text{pre} pre指针再往后移到当前节点, cur \text{cur} cur后移到它的下一个节点。当 cur \text{cur} cur指向None时, pre \text{pre} pre即为我们反转之后链表的头节点。

  有一个小坑,在初始化 pre \text{pre} pre的时候,我一开始采取pre=ListNode(None)的形式,结果在输出结果时,链表中多了一个值为None的节点,这是不符合题意的,我们应该用pre=None这种方式进行初始化。

class Solution:
    def reverseList(self, head):
        if not head:
            return head
        cur = head
        pre = None
        while cur:
            post = cur.next
            cur.next = pre
            pre = cur
            cur = post
        return pre

22. 合并两个有序的链表(双指针法)

输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。

输入:1->3->5 , 2->4->5 输出:1->2->3->4->5->5

分析】   首先创建一个虚拟头节点 dummy \text{dummy} dummy,用来维护新链表的头。然后用两个指针指向输入的两个链表的表头,当两个指针都不为None的时候,我们比较两个指针所指向的节点的值,把较小的值对应的节点添加到新的链表中,并把对应的指针后移一位。

  当至少有一个指针指向None时,循环终止,并将不为None的指针指向的剩余的链表,添加到新链表中。

class Solution(object):
    def merge(self, l1, l2):
        dummy = ListNode(None)
        cur = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        if l1:
            cur.next = l1
        if l2:
            cur.next = l2
        return dummy.next

23. 树的子结构(双重递归)

输入两棵二叉树A,B,判断B是不是A的子结构。 我们规定空树不是任何树的子结构。

树A:    8   /  \   8   7  /   \ 9   2   /  \   4  7

树B:   8  /   \ 9   2

分析

  判断树B是不是树A的子结构,需要分两步走:

  • 第一步,在树A中找到与树B根结点的值一样的节点 p \text{p} p;
  • 第二步,判断树A中以 p \text{p} p 为根结点的子树,是否包含和树B一样的子结构;

  具体分析详见代码:

class Solution(object):

    def isSame(self, root1, root2):
        if not root2:  # 树B中无待匹配节点,说明树B中该分支已匹配完
            return True
        if not root1 or root1.val != root2.val:  # 树B还有待匹配节点,树A中无节点了 或者 根结点的值不相等
            return False
        # 如果当前点匹配了,递归判断左右子树是否同样匹配
        return self.isSame(root1.left, root2.left) and self.isSame(root1.right, root2.right)

    def hasSubtree(self, pRoot1, pRoot2):
        """
        :type pRoot1: TreeNode
        :type pRoot2: TreeNode
        :rtype: bool
        """
        if not pRoot1 or not pRoot2:  # 空子树排除
            return False
        # 判断以pRoot1为根结点的树是否与以pRoot2为根结点的树相同(可以包含,但根节点必须相同)
        if self.isSame(pRoot1, pRoot2):  
            return True
        else:
            return self.hasSubtree(pRoot1.left, pRoot2) or self.hasSubtree(pRoot1.right, pRoot2)

24. 对称的二叉树(二叉树镜像 && DFS)

请实现一个函数,用来判断一棵二叉树是不是对称的。 如果一棵二叉树和它的镜像一样,那么它是对称的。

下面这棵树就是一棵对称二叉树    1   /  \   2     2  /  \    /  \ 3  4  4   3

分析】   先聊一聊二叉树的镜像,二叉树和它的镜像二叉树有什么特点呢?特点在于把原来的二叉树每一个节点的左右节点互相交换,就能得到它的镜像二叉树。

  我们观察示例中的对称二叉树,可以发现,根结点的左、右子树互为镜像二叉树!

class Solution(object):

    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        return self.dfs(root.left, root.right)

    def dfs(self, p1, p2):
        if not p1 or not p2:  # p1,p2一个为空一个不为空或两个同时为空时成立
            return not p1 and not p2  # 只有一个为空返回False,同为空则返回True
        if p1.val != p2.val:  # 两棵树中,对应位置的节点值不相等,直接返回False
            return False
        return self.dfs(p1.left, p2.right) and self.dfs(p1.right, p2.left)

25. 顺时针打印矩阵(蛇形遍历)

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

输入: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] 输出:[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

分析】   我们起点是 matrix[0][0] \text{matrix[0][0]} matrix[0][0]。

  • 开始后,一直向右移动,即横坐标加 0 0 0,纵坐标加 1 1 1,一直到 matrix[0][5] \text{matrix[0][5]} matrix[0][5],发生数组越界,换方向移动;
  • 于是向下移动,即横坐标加 1 1 1,纵坐标加 0 0 0,一直到 matrix[3][4] \text{matrix[3][4]} matrix[3][4],发生数组越界,换方向移动;
  • 于是向左移动,即横坐标加 0 0 0,纵坐标减 1 1 1,一直到 matrix[2][-1] \text{matrix[2][-1]} matrix[2][-1],发生数组越界,换方向移动;
  • 于是向上移动,即横坐标减 1 1 1,纵坐标加 0 0 0,一直到 matrix0][0] \text{matrix0][0]} matrix0][0],该网格已访问,于是换方向移动;
  • 周而复始 \cdots

  于是我们得出一个解题思路,首先指定一个移动的方向dx=[0,1,0,-1],dy=[1,0,-1,0],遇到边界溢出或者元素已访问,则调整方向。

class Solution(object):
    def printMatrix(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix:
            return matrix
        m = len(matrix)
        n = len(matrix[0])
        label_mat = [[0] * n for _ in range(m)] # 标记是否已访问
        res = []
        dx = [0, 1, 0, -1] # 定义 左下右上 四个方向
        dy = [1, 0, -1, 0]
        x, y, direction = 0, 0, 0
        for i in range(0, m * n):
            res.append(matrix[x][y])
            label_mat[x][y] = 1
            a = x + dx[direction]
            b = y + dy[direction]
            if a < 0 or a >= m or b < 0 or b >= n or label_mat[a][b]:
                direction = (direction + 1) % 4
                a = x + dx[direction]
                b = y + dy[direction]
            x = a
            y = b
        return res

26. 包含min 函数的栈(辅助栈,单调递减栈)

设计一个支持push,pop,top等操作并且可以在O(1)时间内检索出最小元素的堆栈。 push(x) 将元素x插入栈中 pop() 移除栈顶元素 top() 得到栈顶元素 getMin() 得到栈中最小元素

  此题考察的是辅助栈的使用,我们在普通栈的基础上,再添加一个辅助栈(单调递减栈)。

  具体实现见代码:

class MinStack(object):

    def __init__(self):
        self.stack = []  # 普通栈
        self.min_stack = []  # 辅助栈,单调递减栈

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.stack.append(x)  # 普通栈,直接将元素入栈
        # 如果辅助栈为空或者它的栈顶元素不小于当前元素,则将元素入栈
        if not self.min_stack or self.min_stack[-1] >= x:
            self.min_stack.append(x)

    def pop(self):
        """
        :rtype: void
        """
        x = self.stack.pop()
        if x == self.min_stack[-1]:
            self.min_stack.pop()

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

    def getMin(self):
        """
        :rtype: int
        """
        return self.min_stack[-1]

27. 栈的压入、弹出序列(出栈顺序)

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。(假设压入栈的所有数字均不相等。)   例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。   注意:若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空,则视为是一个栈的压入、弹出序列。

分析】   本题有点小成就感,按照自己的思路,一步一步修改,然后AC了,所以蛮爽~

  我的思路:

  创建一个 bool \text{bool} bool 变量 flag \text{flag} flag,表示本轮中是否发生了入栈或者出栈的操作,如果发生了,则将 flag \text{flag} flag 置为 False;

  每一轮中,首先判断,栈是否为空、弹出序列是否为空、栈顶元素与弹出序列的第一个元素是否相等;

  三个条件都满足了的话,则弹出栈顶元素stack.pop(),并弹出 弹出序列中的第一个元素popV.pop(0),并将 flag \text{flag} flag 置为 False;

  前面条件不成立的话,再进行判断输入序列是否为空,不为空的话,将输入序列的第一个元素弹出,并添加到栈中。

  最后修改 flag \text{flag} flag 的值,flag = True if not flag else False.

class Solution(object):
    def isPopOrder(self, pushV, popV):
        """
        :type pushV: list[int]
        :type popV: list[int]
        :rtype: bool
        """
        stack = []
        flag = True  # 如果本轮中未发生插入或弹出操作,则停止循环
        while flag:
            if stack and popV and stack[-1] == popV[0]:
                flag = False
                stack.pop()
                popV.pop(0)
            elif pushV:
                stack.append(pushV.pop(0))
                flag = False
            flag = True if not flag else False # 或 flag = not flag
        if stack:
            return False
        return True

28. 分行从上往下打印二叉树(BFS)

从上到下按层打印二叉树,同一层的结点按从左到右的顺序打印,每一层打印到一行。

输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]   8  /  \ 12  2    /    6   /   4 输出:[[8], [12, 2], [6], [4]]

分析】   看到BFS类型的题,要第一反应构建一个遍历队列!

  一个比较好的思路是,我们在每一层的节点遍历完之后,插入一个None,作为标记该层遍历完毕,并将该层的节点值存到 res \text{res} res 中。

  初始的时候,如果 root \text{root} root 不为 None,我们令 queue=[root, None],然后进行BFS。

class Solution(object):
    def printFromTopToBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        if not root:  # 异常情况排除
            return res
        queue = [root, None]
        level = []
        while queue:
            node = queue.pop(0)
            if not node:  # 遇到我们设定的None,说明本层节点遍历完毕
                if not level:  # 如果level为空,说明队列遍历完毕,结束循环
                    break  
                res.append(level.copy())
                level.clear()
                queue.append(None)  # 插入到遍历队列中,作为一层结束的标记
                continue  # 结束本轮循环
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return res

  本题有一个变种,以“之字形”,从上到下打印二叉树,如下示例:

输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]     8    /  \   12  2   /  \    \   1 5  6   /  / \   7  9  4 输出:[[8], [2, 12], [1, 5, 6], [4, 9, 7]]  

  只需要在上面代码的基础上,做一点小小的变化即可。

class Solution(object):
     def printFromTopToBottom_2(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        if not root:  
            return res
        queue = [root, None]
        level = []
        i = 1  # 用来控制每层添加的level,是顺序还是逆序!
        while queue:
            node = queue.pop(0)
            if not node:  
                if not level:
                    break  
                i += 1
                res.append(level[::pow(-1, i)]) # 与上一份代码的区别
                level = []
                queue.append(None)  
                continue  
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return res

29. 二叉搜索树的后序遍历(DFS)

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。 如果是则返回true,否则返回false。 对于输入为空,返回True 假设输入的数组的任意两个数字都互不相同。

分析】   二叉搜索树的特点在于,左子树所有节点的值 &lt; &lt; < 根结点的值 &lt; &lt; < 右子树所有节点的值。

  后序遍历的特点是:左子树 、右子树、根结点

  结合这两条性质,我们可以得出一个重要结论:

  如果一棵树是一个合法的二叉搜索树,那么它的后序遍历中,最后一个元素为该序列的根结点,并且该值可以将序列分为左、右两部分,左边部分的所有值均小于最后一个元素的值,右边部分的所有值均大于最后一个元素的值。划分完之后,左边部分的序列和右边部分的序列,也仍需要满足上述特性。

class Solution:
    seq = []

    def verifySequenceOfBST(self, sequence):
        """
        :type sequence: List[int]
        :rtype: bool
        """
        self.seq = sequence
        if not self.seq:  # 空二叉树
            return True
        return self.dfs(0, len(self.seq) - 1)

    def dfs(self, l, r):
        if l >= r:  # 说明当前分支的节点数为空
            return True
        k = l
        for i in range(l, r):
            if self.seq[i] >= self.seq[r]:
                break
            k += 1 # k为序列中,从左往右,第一个大于最后一个元素值的下标

        for j in range(k, r):
            if self.seq[j] <= self.seq[r]: # 右边部分存在不大于最后一个元素的值
                return False
        return self.dfs(l, k - 1) and self.dfs(k, r - 1)

30. 二叉树中的所有路径(DFS && 回溯法)

定义二叉树中的路径为:从根结点到叶子结点的所经过的所有节点的值。

输入:如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]     8    /  \   12  2   /  \    \   1 5  6   /  / \   7  9  4 输出:[[8, 12, 1], [8, 12, 5, 7], [8, 2, 6, 9], [8, 2, 6, 4]]

分析】   叶子结点的特点是 not node.left and not node.right条件成立。

  我们的思路是,递归的遍历一棵二叉树,首先当前节点的值,添加到路径中。如果该节点为叶子结点,则将路径添加到返回结果中,否则,如果该节点有左子树,就 dfs \text{dfs} dfs它的左子树,如果该节点有右子树,就 dfs \text{dfs} dfs它的右子树。

  回溯法体现在,当前节点对应的 dfs \text{dfs} dfs 返回之后,从路径中要删除该节点的值。

class Solution(object):
    res = []
    path = []

    def findAllPath(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return self.res
        self.dfs(root)
        return self.res

    def dfs(self, root):
        if not root:
            return
        self.path.append(root.val)
        if not root.left and not root.right:
            self.res.append(self.path.copy())  # 这里必须用path.copy(),否则值会被修改
        self.dfs(root.left)
        self.dfs(root.right)
        self.path.pop()

31. 二叉树中和为S的路径(DFS && 回溯法)

输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。 从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

分析】   此题和上面那道题十分相似,相当于在所有路径的基础上,增加了一层过滤。

  第一种思路是,获取所有路径,然后返回和为S的路径。

  第二种思路,我们在到达了一条路径的叶节点的时候,判断当前路径的和是否为S,是的话,就添加到 res \text{res} res 中。

  我们这里采取思路二进行代码实现,而且有两种实现方式。

  • 方式一:到达了一条路径的叶节点的时候,判断当前路径的和是否为S
class Solution(object):
    res = []
    path = []
    target = 0

    def findPath(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        if not root or not sum:
            return self.res
        self.target = sum
        self.dfs(root)
        return self.res

    def dfs(self, root):
        if not root:
            return
        self.path.append(root.val)
        if not root.left and not root.right and sum(self.path) == self.target:
            self.res.append(self.path.copy())
        self.dfs(root.left)
        self.dfs(root.right)
        self.path.pop()
  • 方式二:遍历某节点时,如果它不为空,把它添加到路径中,并执行S = S - node.val,如果它为叶节点,且 S == 0,那么说明该条路径的和为S
class Solution(object):
    res = []
    path = []

    def findPath(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        if not root or not sum:
            return self.res
        self.dfs(root, sum)
        return self.res

    def dfs(self, root, sum):
        if not root:
            return
        self.path.append(root.val)
        sum -= root.val
        if not root.left and not root.right and sum == 0:
        	# 因为进行pop操作,path会修改,所以这里要用path.copy()
            self.res.append(self.path.copy()) 
        self.dfs(root.left, sum)
        self.dfs(root.right, sum)
        self.path.pop()

32. 二叉树中根结点到某一结点的路径(DFS && 回溯法)

输入一棵二叉树和一个结点,打印出从根结点到该结点到路径。

分析】   这一题和上面两道都是类似的题型,我们 dfs \text{dfs} dfs 到某个结点时,如果它不为空,就把它添加到路径中,并判断它的值和目标结点的值是否相等,是的话,返回True,否则 dfs \text{dfs} dfs 它的左右子树。

class Solution:
    res = []
    path = []

    def find_path(self, root, target):
        self.res = [] # 避免多次输入时,res中还保留上一个输入的结果
        if not root or not target:
            return self.res
        self.dfs(root, target)

    def dfs(self, root, target):
        if not root:
            return
        self.path.append(root.val)
        if root.val == target.val:
            self.res = self.path.copy()
            return # 树中无重复节点,所以只有一条路径,找到了则返回本轮递归
        self.dfs(root.left, target)
        self.dfs(root.right, target)
        self.path.pop()

33. 复杂链表的复制(链表插入与删除)

请实现一个函数可以复制一个复杂链表。 在复杂链表中,每个结点除了有一个指针指向下一个结点外,还有一个额外的指针指向链表中的任意结点或者null。

分析

  上图是一个复杂链表的示例,实线表示next指针,虚线表示random指针,它也可以指向 None,在图中省略。

  一个直观的思路是,分两步完成,第一步复制原始链表中的每一个节点,并用next指针连接起来;第二步是设置每个节点的random指针,这一步比较麻烦,假设某个节点的random指向节点S,那么定位S的位置需要从头节点开始查找,这种方法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。

  一种优化的思路是,分三步完成:

  • 第一步:复制原始链表中的每一个节点,并将它链接到原节点之后。
  • 第二步:如果原始链表中,某节点的random指针指向节点S,那么它对应的复制节点指向S.next
  • 第三步:分离链表,把奇数位置的节点用next指针链接起来,就是原始链表,把偶数位置的节点用next指针链接起来,就是复制的新链表。
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        # 第一步,复制新节点在原节点之后
        cur = head
        while cur:
            p = ListNode(cur.val)
            p.next = cur.next
            cur.next = p
            cur = p.next
        # 第二步,复制新节点的random指针
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next  # cur每次都指向原节点,跨一个节点移动
        # 第三步,分离链表
        dummy = ListNode(None)
        cur = dummy
        p = head
        while p:
            cur.next = p.next
            cur = cur.next
            p = p.next.next  # 跨节点移动
        return dummy.next

34. 二叉搜索树与双向链表(DFS && 分情况讨论)

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。 要求不能创建任何新的结点,只能调整树中结点指针的指向。 注意:   返回双向链表中,最左侧的节点。

例如

分析】   本题的思路是,我们设置一个pair = [l_node,r_node],表示当前的树结构中,最左侧的节点和最右侧的节点。

  分情况讨论:以node作为根结点的树中

  • 如果它不存在左、右子树,那么返回[node, node]
  • 如果它存在左、右子树,则 dfs \text{dfs} dfs root.left,获得左子树的l_pair,再 dfs \text{dfs} dfs root.right,获得右子树的r_pair,然后把l_pair[1]node进行双向链接,把r_pair[0]node进行双向链接,并返回[l_pair[0], r_pair[1]]
  • 如果它只存在左子树,则 dfs \text{dfs} dfs root.left,获得左子树的l_pair,然后把l_pair[1]node进行双向链接,并返回[l_pair[0], node]
  • 如果它只存在右子树,则 dfs \text{dfs} dfs root.right,获得右子树的r_pair,然后把r_pair[0]node进行双向链接,并返回[node, r_pair[1]]

  具体代码实现如下:

class Solution(object):
    def convert(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return root
        pair = self.dfs(root)
        return pair[0]

    def dfs(self, node):  # 以node为根结点的树中,返回 [最左侧的节点,最右侧的节点]
        if not node.left and not node.right:  # 1. 左、右子树均不存在
            return [node, node]
        if node.left and node.right: # 2. 左、右子树均存在
            l_pair = self.dfs(node.left) 
            r_pair = self.dfs(node.right) 
            l_pair[1].right = node 
            node.left = l_pair[1]
            node.right = r_pair[0]
            r_pair[0].left = node
            return [l_pair[0], r_pair[1]]
        if node.left: # 3. 只有左子树存在
            l_pair = self.dfs(node.left)
            l_pair[1].right = node
            node.left = l_pair[1]
            return [l_pair[0], node]
        if node.right: # 4. 只有右子树存在
            r_pair = self.dfs(node.right)
            node.right = r_pair[0]
            r_pair[0].left = node
            return [node, r_pair[1]]

35. 数字的全排列(DFS && 二进制标记 )

输入一组数字(可能包含重复数字),输出其所有的排列方式。

样例输入:[1,2,3] 输出: [   [1,2,3],   [1,3,2],   [2,1,3],   [2,3,1],   [3,1,2],   [3,2,1] ]

分析】   我们先考虑一下,数组中不存在重复元素的情况!

  假设输入的数组为 [1, 2, 3, 4] \text{[1, 2, 3, 4]} [1, 2, 3, 4],也就是说,我们有4个坑需要填。

  我们按顺序将数组中的元素,填到坑中,假设第一个待填的元素为1,那么它有四个可以填的坑;接下来的待填的元素为2,可以看到它有三个可以填入的坑;然后待填的元素为3,可以看到它有两个可以填入的坑;最后一个待填的元素为4,只剩一个坑可以填。

  这里我们用二进制数来标记哪个坑已被占用,哪个坑未被占用,如 11 = 0b1011,意味着从右往左数,从0开始计数,第2个坑未被占用。

  state >> i & 1,在 state 中,从右往左数,从 0 开始,第 i i i 个元素的值。

  state + (1 << i) 表示从右往左数,从 0 开始,将 state 中的第 i i i 个元素的值 + 1 +1 +1。

  python 中运算符的优先级顺序:(从上到下逐渐降低)

  可以看到,+ 的优先级,大于 >> 和 << 的优先级,大于 & 的优先级。逻辑运算 not and or 的优先级是最低的。

  因此,state + (1 << i)中需要将左移运算用小括号括起来。

  具体实现代码如下:(输入数组无重复)

class Solution:
    res = [] # 返回的结果
    holes = [] # 待填的坑

    def permutation(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return self.res
        self.holes = [None] * len(nums)  # 初始化坑的状态
        self.dfs(nums, 0, 0)
        return self.res

    def dfs(self, nums, idx, state):
        """
        :param nums: 输入的数组
        :param idx: idx 表示当前待填入holes中的元素的下标
        :param state: 当前holes的状态,换成二进制表示,1表示已有元素,0表示暂无元素
        """
        if idx == len(nums):
            self.res.append(self.holes.copy()) # 需要用copy(),因为后续holes会被修改
            return
        for i in range(0, len(nums)): # 设定枚举范围,从0开始,到len(nums)-1
            if not state >> i & 1:  # 从右往左,第i个位置第值是否为1,从i=0开始
                self.holes[i] = nums[idx]
                self.dfs(nums, idx + 1, state + (1 << i))

  我们接下来考虑,数组中存在重复元素的情况!

  大致实现思路和上面一致,唯一要考虑的是,如果元素存在重复,我们增加一个约束条件,它必须填到重复元素的坑的后面。

  为此,我们需要先对输入数组进行排序操作,这样使得重复元素的位置相邻,便于我们判断当前元素是否重复。

class Solution:
    res = [] # 返回的结果
    path = [] # 待填的坑

    def permutation(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return self.res
        self.path = [None] * len(nums) # 初始化坑,即holes数组
        nums = sorted(nums)  # 排序,保证重复的元素相邻
        self.dfs(nums, 0, 0, 0)
        return self.res

    def dfs(self, nums, idx, start, state):
        """
        :param nums: 输入的数组
        :param idx: idx 表示当前待填入holes中的元素的下标
        :param start: 当前元素应该从哪个位置开始枚举
        :param state: 当前"坑"的状态,换成二进制表示,1表示已有元素,0表示暂无元素
        """
        if idx == len(nums):
            self.res.append(self.path.copy())
            return
        # 如果当前元素为第一个元素,或者当前元素与上一个元素不重复,则从第0个坑开始枚举
        if idx == 0 or nums[idx] != nums[idx - 1]:
            start = 0 
        for i in range(start, len(nums)): # 设定枚举范围,从start开始,到len(nums)-1
            if not state >> i & 1:  # 从右往左,第i个位置第值是否为1,从i=0开始
                self.path[i] = nums[idx]
                self.dfs(nums, idx + 1, i + 1, state + (1 << i))

36. 数组中出现次数超过一半的数字(消除法)

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 假设数组非空,并且一定存在满足条件的数字。

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

分析】   如果某个数字出现的次数超过数组长度的一半,那么就是说,它出现的次数,比其他所有数字出现的总次数还要多。

  因此,我们在遍历数组的时候,可以保存两个值,一个是数组中的某个元素,另一个是该元素出现的次数。

  如果遍历到的元素与保存的元素值相同,则次数加1,反之次数减1。

  当次数为零的时候,我们需要保存下一个数字,并把次数设为1。

  最后保存的元素,一定是次数超过一半的元素。

class Solution(object):
    def moreThanHalfNum_Solution(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = nums[0]
        count = 1
        for i in range(1, len(nums)):
            if count == 0:
                res = nums[i]
                count += 1
                continue
            if nums[i] == res:
                count += 1
            else:
                count -= 1
        return res

37. 最小的k个数(最大堆)

输入n个整数,找出其中最小的k个数。 注意:   数据保证k一定小于等于输入数组的长度;   输出数组内元素请按从小到大顺序排序;

样例 输入:[1,2,3,4,5,6,7,8] , k=4 输出:[1,2,3,4]

分析】   从输入的 n \text{n} n个数中,返回最小的 k \text{k} k个数,或者最大的 k \text{k} k个数,像这种问题,我们可以用最大堆或者最小堆来实现。

  • 最小堆:父堆元素小于或等于其子堆的每一个元素( python \text{python} python中, heapq \text{heapq} heapq模块实现)
  • 最大堆:父堆元素大于或等于其子堆的每一个元素

  我们来详细了解一下 python \text{python} python中的 heapq \text{heapq} heapq模块:

  • heapq.heappop(list): 弹出 list \text{list} list 所代表的最小堆中的堆顶元素(list中最小的元素)
  • heapq.heappush(list,x): 将元素 x 插入到 list \text{list} list 所代表的最小堆中
  • heapq.nlargest(k, list): 返回最小堆 list \text{list} list 中最大的 k \text{k} k 的元素(递减排序)
  • heapq.nsmallest(k, list): 返回最小堆 list \text{list} list 中最小的 k \text{k} k 的元素(递增排序)

  需注意,heapq.heappush(list,x) 操作,是直接对 list \text{list} list 进行修改,无返回值。

  如果我们想用 heapq \text{heapq} heapq 模块来实现最大堆,一种思路是,将 list \text{list} list 中的每一个元素,取其相反数,那么heapq.heappop(list) 返回的是原 list \text{list} list 中最大值的相反数,其他操作类似,不再赘述。

  具体实现代码:

import heapq


class Solution(object):
    def getLeastNumbers_Solution(self, input, k):
        """
        :type input: list[int]
        :type k: int
        :rtype: list[int]
        """
        heap = []  # 维护一个元素个数为k的最大堆结构
        for x in input:
            heapq.heappush(heap, -x)
            if len(heap) > k:
                heapq.heappop(heap)  # 弹出最小元素,即实际上最大元素的相反数
        res = heapq.nlargest(k, heap)  # 从大到下排列的k个值,如[-1,-2,-3]
        return [-x for x in res]

  此外,也可以直接调用return heapq.nsmallest(k,input),一行代码搞定。

38. 连续子数组的最大和(一维动态规划)

输入一个 非空 整型数组,数组里的数可能为正,也可能为负。 数组中一个或连续的多个整数组成一个子数组。 求所有子数组的和的最大值。 要求时间复杂度为O(n)。

输入:[1, -2, 3, 10, -4, 7, 2, -5] 输出:18

分析】   我们初始化一个元素值全为零的 dp \text{dp} dp 数组dp=[0] * len(nums),其中 dp[i] \text{dp[i]} dp[i] 表示从第 0 个到第 i i i 个元素中,连续子数组(包含第 i i i 个元素)的最大和。

  dp[i-1]<0 时,则令 dp[i-1]=0,任何一个数加上一个负数,都一定小于它本身,所以这里将dp[i-1]置为0。

  然后执行 dp[i] = dp[i-1] + nums[i],求出包含第 i i i 个元素在内的连续子数组的最大和。

  最后将 res \text{res} res 和 dp[i] \text{dp[i]} dp[i] 中较大的元素保存在 res \text{res} res 中res = max(res, dp[i])因为输入的数组中,可能存在负数,所以初始化res = float(’-inf’)

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = float('-inf')  # 初始化 res 为负无穷
        dp = [0] * len(nums)
        for i in range(len(nums)):
            if dp[i - 1] < 0:
                dp[i - 1] = 0
            dp[i] = dp[i - 1] + nums[i]
            res = max(dp[i], res)
        return res

39. 从1到n的整数中1出现的次数(分情况讨论)

输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。 例如 输入12,从1到12这些整数中包含“1”的数字有1,10,11和12,其中“1”一共出现了5次。

分析】   考虑一个整数 abcde \text{abcde} abcde ,如下图所示:

  我们从左往右逐次遍历,当遍历到 c c c 的位置的时候,它左边的值 left = a × 10 + b \text{left} = a \times10+b left=a×10+b,右边的值 right = d × 10 + e \text{right} = d \times10+e right=d×10+e,右边的元素个数 t = 2 t=2 t=2。

   c c c 前面的数值取 0 left-1 0\sim \text{left-1} 0∼left-1, c c c 必定可以取到 1 ,此时共有 left × 1 0 t \text{left}\times10^t left×10t 个 可能。

  当 c 前面的数值取 left \text{left} left 时,分三种情况讨论:

  • c > 1时,则 c 后面的取值无约束,共有 1 0 t 10^t 10t 种可能;
  • c == 1时,则 c 后面的取值只能在 0 right 0\sim \text{right} 0∼right,共有 right + 1 \text{right}+1 right+1 种可能;
  • c < 1时,则不满足 c = 1,0 种可能。

  具体实现代码如下:

class Solution(object):
    def numberOf1Between1AndN_Solution(self, n):
        """
        :type n: int
        :rtype: int
        """
        nums = []
        res = 0
        if not n:  # 输入为0
            return res
        while n:
            nums.append(n % 10)
            n //= 10
        nums.reverse()  # 1999 变为[1,9,9,9]
        for i in range(len(nums)):
            left = 0  # 第i个元素左边的数值,如i=2时,left=19
            right = 0  # 第i个元素右边的数值,如i=2时,right=9
            t = 0  # 第i个元素右边的元素个数
            for j in range(0, i):
                left = left * 10 + nums[j]
            for j in range(i + 1, len(nums)):
                right = right * 10 + nums[j]
                t += 1
            res += left * 10 ** t
            if nums[i] > 1:
                res += 10 ** t
            elif nums[i] == 1:
                res += right + 1
        return res

40. 数字序列中某一位的数字(分情况讨论)

数字以0123456789101112131415…的格式序列化到一个字符序列中。 在这个序列中,第5位(从0开始计数)是5,第13位是1,第19位是4,等等。 请写一个函数求任意位对应的数字。

分析

  我们来讨论一下:

  • 0 9 0\sim9 0∼9 以内的数字,元素个数为 10 10 10 ,索引区间为 0 9 0\sim9 0∼9;
  • 10 99 10\sim99 10∼99 以内的数字,元素个数为 90 90 90,每个元素占 2 2 2 位,索引区间为 10 189 10\sim189 10∼189;
  • 100 999 100\sim999 100∼999 以内的数字,元素个数为 900 900 900,每个元素占 3 3 3 位,它的索引区间为 190 2889 190\sim2889 190∼2889;
  • \cdots\cdots ⋯⋯

  我们根据输入的 n n n,需要知道 第 n n n 个元素是对应的是一个几位数,一位数的分界点为10(小于分界点),二位数的分界点为190,三位数的分界点为2890,以此类推 \cdots

  假设第 n 个元素,对应的是一个三位数中的某一位,那么我们需要求出,它是第几个三位数,此时用(n-190)//3进行求解;

  知道是第几个三位数之后,我们还需要知道它是该三位数的第几个元素,此时用(n-190)%3

  最终整理代码如下:

class Solution(object):
    def digitAtIndex(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 10:  # 10以内的输入单独处理,便于后面实现
            return n
        pos = 10  # 用来确定第n个数字的区间,从二位数开始
        i = 1  # 用来确定第n个数字的位数
        while n >= pos:
            last_pos = pos
            pos = pos + 9 * pow(10, i) * (i + 1)
            i += 1
        p = (n - last_pos) // i  # 向下取整,确定第p个i位数
        q = (n - last_pos) % i  # 第p个i位数的第q位元素,为返回结果
        num = pow(10, i - 1) + p
        return int(str(num)[q])

41. 把数组排成最小的数(自定义排序)

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 例如输入数组[3, 32, 321],则打印出这3个数字能排成的最小数字321323。

输入:[3, 32, 321] 输出:321323 输出数字的格式为字符串

分析】   假设输入的数组中,每个元素都是 10 10 10 以内的数,如 [ 1 , 3 , 2 , 5 , 7 , 0 ] [1,3,2,5,7,0] [1,3,2,5,7,0],那么它拼接起来最小的数字是 012357 012357 012357,它是怎么排的呢?

  不难发现,在数字 012357 012357 012357 中,任意两个位置的对应的数字组成的数 ij \text{ij} ij,都比 ji \text{ji} ji 要小。

  于是,当我们输入的数组中,存在元素大于 10 10 10的数,最终得到的最小的数中,也应该满足此性质,即对于任意一个元素a,如果它在元素b之前, 必须满足ab < ba。

  因为最终拼接起来的数字,很有可能会大于 int \text{int} int 的上限,所以我们将输入的数组中的每一个元素转成字符串类型,nums = [str(x) for x in nums]

   python3 \text{python3} python3 中,有提供自定义排序规则的函数,首先需要导入模块,from functools import cmp_to_key,我们的 nums \text{nums} nums 列表的每一个元素都是字符串,所以 元素 a 和元素 b 拼接后的数字为int(a+b)

  调用的排序函数为nums = sorted(nums, key=cmp_to_key(lambda x, y: int(x + y) - int(y + x))),如果 int(x + y) - int(y + x) < 0,那么说明 x < y

  整体实现代码:

class Solution(object):
    def printMinNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        if not nums:
            return ''
        nums = [str(x) for x in nums]
        from functools import cmp_to_key
        nums = sorted(nums, key=cmp_to_key(lambda x, y: int(x + y) - int(y + x)))
        return ''.join(nums).lstrip('0') or '0'  # 去除输入中可能存在的0,如果只有'0',则返回'0'

42. 把数字翻译成字符串(一维动态规划)

给定一个数字,我们按照如下规则把它翻译为字符串: 0翻译成”a”,1翻译成”b”,……,11翻译成”l”,……,25翻译成”z”。 一个数字可能有多个翻译。例如12258有5种不同的翻译,它们分别是”bccfi”、”bwfi”、”bczi”、”mcfi”和”mzi”。 请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

输入:“12258” 输出:5

分析】   统计个数类型的问题,可以考虑用动态规划法来做。

  动态规划法,需要考虑三个因素:

  • 状态表示 本题 dp[i] \text{dp[i]} dp[i] 表示前 i i i 个元素共有多少种不同的翻译方法;
  • 状态转移方程 i \text{i} i 个元素,必定可以翻译成一个字母,所以 dp[i] = dp[i-1] 是无条件转移的,如果把第 i \text{i} i 个元素和第 i-1 \text{i-1} i-1 个元素,合在一起,用一个字母进行翻译,则必须这个合在一起的组成数字,值在 10 25 10\sim25 10∼25之间才可以转移,此时dp[i] += dp[i-2],此时考虑一种特殊的情况, i = 1 \text{i = 1} i = 1时,如果它和第 0 0 0个元素组成的值在 [ 10 , 25 ] [10,25] [10,25]区间,则需要加上 1 1 1 ,于是我们初始化时,考虑令 dp[-1]=1
  • 边界条件 i=0 \text{i=0} i=0 时,它没有和前面的元素组成一个两位数的情况,需要单独提出来,我们直接初始化dp[0]=1

  因为这里,dp[0] 和 dp[-1] 都需要初始化为1,而从 dp[1] 开始,到 dp[-1] 结束的每一个元素值都会被覆盖掉,于是我们可以直接初始化dp数组的值全为1。

class Solution:
    def getTranslationCount(self, s):
        """
        :type s: str
        :rtype: int
        """
        # 计数问题,可以尝试动态规划法
        if not s:
            return -1
        dp = [1] * len(s)  # 初始化为1,dp[0]=1,在计算dp[1]时,会用到dp[-1],此时它的值为1
        for i in range(1, len(s)):
            dp[i] = dp[i - 1]
            if 10 <= int(s[i - 1:i + 1]) <= 25:
                dp[i] += dp[i - 2]
        return dp[-1]

43. 棋盘的最大价值(二维动态规划)

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

输入: [ [2,3,1], [1,7,1], [4,6,1] ] 输出:19 解释:沿着路径 2→3→7→6→1 可以得到拿到最大价值礼物。

分析】   统计个数类型的问题,可以考虑用动态规划法来做。

  动态规划法,需要考虑三个因素:

  • 状态表示 本题 dp[i][j] \text{dp[i][j]} dp[i][j] 表示到达第 i \text{i} i 行第 j \text{j} j 列网格时,所得到的最大礼物价值;
  • 状态转移方程 题中规定了每次只能向下或者向右移动,所以 dp[i][j] \text{dp[i][j]} dp[i][j] 只能由 dp[i-1][j] \text{dp[i-1][j]} dp[i-1][j] 或者 dp[i][j-1] \text{dp[i][j-1]} dp[i][j-1] 转移得到,取二者中较大的一个元素即可,然后再加上当前网格的礼物价值,即 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
  • 边界条件 在第 0 行或者第 0 列的网格中,只能从某一个方向转移得到,我们可以直接初始化 dp 矩阵中的每一个元素的值为 0 即可,使得 dp[-1][j]=0 \text{dp[-1][j]=0} dp[-1][j]=0 和 dp[i][-1]=0 \text{dp[i][-1]=0} dp[i][-1]=0,不会影响状态转移的计算。(当然,更保险的办法是,在原始矩阵的上边和左边再增加一行和一列,并初始化为0,然后行、列都是从1开始遍历
class Solution(object):
    def getMaxValue(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)  # 棋盘的行数
        n = len(grid[0])  # 棋盘的列数

        dp = [[0] * n for _ in range(m)]  # 初始化为0
        for i in range(0, m):
            for j in range(0, n):
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        return dp[m - 1][n - 1]

44. 最长不含重复字符的子字符串(一维动态规划)

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 假设字符串中只包含从’a’到’z’的字符。

输入:“abcabc” 输出:3

分析】   统计个数类型的问题,可以考虑要动态规划法来做。

  动态规划法,需要考虑三个因素:

  • 状态表示 本题 dp[i] \text{dp[i]} dp[i] 表示以第 i \text{i} i 个元素结尾的不含重复字符的最大子串长度;
  • 状态转移方程 如果第 i \text{i} i 个元素,在前 i-1 \text{i-1} i-1 个元素中未出现,我们可以直接将第 i \text{i} i 个元素加入到上一个最大子串中,此时 dp[i] = dp[i-1]+1;如果第 i \text{i} i 个元素,在前 i-1 \text{i-1} i-1 个元素中已出现,那么我们需要计算,在前 i-1 \text{i-1} i-1 个元素中,最近一次出现第 i \text{i} i 个元素的位置,并计算出二者的间距 distance \text{distance} distance。如果 distance&gt;dp[i-1] \text{distance&gt;dp[i-1]} distance>dp[i-1],说明重复的元素不影响当前不含重复字符的最大子串长度,所以 dp[i] = dp[i-1]+1,如果 distance dp[i-1] \text{distance}\leq\text{dp[i-1]} distance≤dp[i-1],说明以第 i \text{i} i 个元素结尾的,最大无重复字符的子串,是从上一个重复元素的下一位开始,到当前第 i \text{i} i 位元素结束,此时dp[i] = distance
  • 边界条件 i=0 \text{i=0} i=0 时, dp[0] = 1 \text{dp[0] = 1} dp[0] = 1

  在本题中,需要记录第 i \text{i} i 个元素有无出现过,如果出现过,它最近一次出现的位置在哪,所以我们可以创建一个字典结构,来保存上述信息。

class Solution:
    def longestSubstringWithoutDuplication(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        dp = [0] * len(s)  # dp[i]表示以第i个元素结尾的不含重复字符的最大子串长度
        d = dict()  # 用来保存26个字母,上一次出现的位置
        res = 0
        for i in range(0, len(s)):
            if s[i] not in d.keys():  # 判断第i个元素在之前有没有出现过
                dp[i] = dp[i - 1] + 1
            else:
                distance = i - d[s[i]]
                if distance > dp[i - 1]:
                    dp[i] = dp[i - 1] + 1
                else:
                    dp[i] = distance
            d[s[i]] = i  # 更新第i个元素最后出现的位置
            res = max(res, dp[i])
        return res

45. 丑数(三路归并)

我们把只包含因子2、3和5的数称作丑数(Ugly Number)。 例如6、8都是丑数,但14不是,因为它包含因子7。 求第n个丑数的值。

注意:习惯上我们把1当做第一个丑数。

分析】   本题是有暴力解法的,但是时间开销特别大,我们可以从1开始依次枚举每一个正整数,如果它是丑数,则把当前丑数的个数加1,直到达到指定的丑数个数为止,代码一目了然,不再赘述。

class Solution(object):
    # 用时间换空间
    def getUglyNumber(self, n):
        if n <= 1:
            return n
        ugly_count = 0
        number = 0
        while True:
            number += 1
            if self.is_ugly(number):
                ugly_count += 1
            if ugly_count == n:
                break
        return number

    def is_ugly(self, number):
        while number % 2 == 0:
            number //= 2
        while number % 3 == 0:
            number //= 3
        while number % 5 == 0:
            number //= 5
        return True if number == 1 else False

  除了上述的暴力做法以外,本题还可以用空间换时间,获得更加优化的解法。

  本题可以考虑为一个三路归并的问题,我们将一个只由丑数构成的集合,分成三个子集:

  • 第一路是包含质因子2的所有丑数的集合
  • 第二路是包含质因子3的所有丑数的集合
  • 第三路是包含质因子5的所有丑数的集合

  每轮进行一次比较,取出三个集合中最小的一个元素,并将它添加到丑数集合之中,再把对应集合的指针往后移动一位。

  有一种很巧妙的实现方式,具体代码如下

class Solution(object):
    # 用空间换时间
    def getUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 1:
            return n
        nums = [1]
        i, j, k = 0, 0, 0
        n -= 1
        while n:
            t = min(nums[i] * 2, nums[j] * 3, nums[k] * 5) # 取出三路中,最小的丑数
            if t == nums[i] * 2: # 该丑数来自第一路,指针后移一位
                i += 1
            if t == nums[j] * 3: # 该丑数来自第二路,指针后移一位
                j += 1
            if t == nums[k] * 5: # 该丑数来自第三路,指针后移一位
                k += 1
            nums.append(t)
            n -= 1
        return nums[-1]

46. 正整数分解成质因子表示(分解质因子)

质数又称素数,它是一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数,否则称为合数。 输入一个正整数n,返回它的质因子的集合,如果输入1,则返回 1。

输入:90 输出: [2, 3, 3, 5]

分析】   我们考虑一个正整数 n n n , n n n 满足 n 2 n\geq2 n≥2,那么它的质因子肯定在 2 n 2\sim n 2∼n 区间内。

  我们从 i = 2 i=2 i=2 开始遍历,如果 n % 2 == 0,那么说明 2 是 n n n 的一个因子,我们再修改 n n n 的值 n = n // 2

  当我们把 n n n 中所有的 2 2 2 取出来之后,如果 n &gt; i n&gt;i n>i 仍成立,则将i += 1,此时再可以把 n n n 中所有的 3 3 3 取出来。

  如果 n &gt; i n&gt;i n>i 仍成立,执行i += 1,此时 i = 4 i = 4 i=4,显然 n % 4 == 0不可能成立,因为 i = 2 i = 2 i=2 时,以及把所有含 2 2 2 的因子取了出来,依次类推,再次执行i += 1 \cdots

  具体实现代码:

class Solution(object):

    def get_prime_factors(self, number, res):
        if number == 1:
            return res.append(number)
        n = 2
        while number != 1: # 最终number会被整除为1
            if number % n == 0:
                res.append(n)
                number //= n
            else:
                n += 1
        return res

47. 判断一个数是否为质数(质数判别)

输入一个正整数n,判断从2到n的区间内,质数的总个数。 n &gt; = 2 n &gt;= 2 n>=2

输入:17 输出:False

分析】   本题的难点,在于判断一个数是不是质数,一个基本的思路是,从 2 2 2 到 sqrt(number) \text{sqrt(number)} sqrt(number) 的区间内进行遍历,如果存在一个数可以被 number \text{number} number 整除,那就说明这个数不是质数,否则说明该数是质数。

  实现代码:

class Solution(object):
    def is_prime(self, number):
        # ceil向上取整,floor向下取整,int是向下取整,round是四舍五入
        from math import ceil, sqrt
        for i in range(2, ceil(sqrt(number)) + 1):
            if number % i == 0:
                return False
        return True

  然而上面这个过程可以进行优化 !

  我们继续分析,其实质数还有一个特点,就是它总是等于 6x-1 或者 6x+1,其中 x 是大于等于1的自然数。

  如何论证这个结论呢,其实不难。首先 6x 肯定不是质数,因为它能被 6 整除;其次 6x+2 肯定也不是质数,因为它还能被2整除;依次类推,6x+3 肯定能被 3 整除;6x+4 肯定能被 2 整除。那么,就只有 6x+1 和 6x+5 (即等同于6x-1) 可能是质数了。

  因此,如果对某个大于 4 4 4 的正整数 n n n,如果 n % 6 != 1 and n % 6 != 5,那就说明它一定不是质数。 根据这个结论,可以进行第一次过滤。

  如果上面条件不满足,说明 n % 6 == 1 or n % 6 != 5,如 5 , 7 , 11 , 13 , 17 , 19 , 23 , 25 , 29 , 31 , 35 , 37 , 5,7,11,13,17,19,23,25,29,31,35,37,\cdots 5,7,11,13,17,19,23,25,29,31,35,37,⋯对于这些数字,我们遍历在 5 到 sqrt(number) \text{sqrt(number)} sqrt(number) 区间内,所有分布在6两侧的数字,如果能被其整除,说明该数不是质数。

   具体代码如下:

class Solution(object):
    def is_prime_2(self, number):
        if number <= 3:  # 考虑number=2,3的情况
            return number > 1

        # 不在6的倍数两侧的数,一定不是质数
        if number % 6 != 1 and number % 6 != 5:
            return False
        from math import sqrt
        i = 5
        while i <= sqrt(number):
            if number % i == 0 or number % (i + 2) == 0:  
                return False
            i += 6
        return True

48. 字符串中第一个只出现一次的字符(哈希表)

在字符串中找出第一个只出现一次的字符。 如输入"abaccdeff",则输出b。 如果字符串中不存在只出现一次的字符,返回#字符。(输入可能为空或都是重复字符)

分析】   本题的思路较为简单,直接从前往后遍历一次字符串,第一次出现的字符,value=1,否则 value+=1

  记录本题的目的是为了巩固对 python3 \text{python3} python3 字典结构的使用。

   d = {‘a’: 3, ‘d’: 1, ‘b’: 2}:

  • ’a’ in d,返回 True
  • ’a’ in d.keys(),返回 True
  • 1 in d,返回 False
  • 1 in d.values(),返回 True
  • sorted(d),返回列表[‘a’, ‘b’, ‘d’]
  • sorted(d.keys()),返回列表[‘a’, ‘b’, ‘d’]
  • sorted(d.values()),返回列表[1, 2, 3]
  • sorted(d.items()),返回列表[(‘a’, 3), (‘b’, 2), (‘d’, 1)]
  • sorted(d.items(),key=lambda item:item[1]),返回列表[(‘d’, 1), (‘b’, 2), (‘a’, 3)]

  本题解答代码如下:

class Solution:
    def firstNotRepeatingChar(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return '#'
        d = dict()
        for ch in s:
            if ch in d.keys():
                d[ch] += 1
            else:
                d[ch] = 1
        d = sorted(d.items(), key=lambda item: item[1])
        if d[0][1] == 1:
            return d[0][0]
        return '#'

49. 字符流中第一个只出现一次的字符(哈希表,队列)

请实现一个函数用来找出字符流中第一个只出现一次的字符。 例如,当从字符流中只读出前两个字符”go”时,第一个只出现一次的字符是’g’。 当从该字符流中读出前六个字符”google”时,第一个只出现一次的字符是’l’。 如果当前字符流没有存在出现一次的字符,返回#字符。

输入:“google” 输出:“ggg#ll” 解释:每当字符流读入一个字符,就进行一次判断并输出当前的第一个只出现一次的字符。

分析】    本题和上一题的区别在于,它的字符串不是固定的,如果我们按照上面的方法,每传入一个字符,整理一遍哈希表,再从哈希表中找出第一个 value=1 \text{value=1} value=1 的 key \text{key} key,每次查询的时间复杂度为 n n n , n n n 个字符的时间复杂度则为 O ( n 2 ) O(n^2) O(n2)。

   一种把时间复杂度降为 O ( n ) O(n) O(n) 的做法是,我们维护一个队列,队列的第一个元素,是当前字符流中,第一个没有重复出现的字符。

   当传入新字符的时候,如果该字符前面未出现过,则将它存在哈希表中,对应的 value=1 \text{value=1} value=1 ,并将其添加到队列里;如果该字符在前面出现过,将它对应的 value+=1 \text{value+=1} value+=1。

   每轮插入新字符时,都要检查,队列头部的元素是否为重复元素,是的话,则将前弹出,直到头部元素不再为重复元素为止。

class Solution:
    d = dict()
    queue = list()

    def firstAppearingOnce(self):
        """
        :rtype: str
        """
        if not self.queue:
            return "#"
        else:
            return self.queue[0]

    def insert(self, char):
        """
        :type char: str
        :rtype: void
        """
        if char in self.d.keys():
            self.d[char] += 1
        else:
            self.d[char] = 1
            self.queue.append(char)
        while self.queue and self.d[self.queue[0]] > 1:  # 队首元素必须为不重复的元素
            self.queue.pop(0)

50. 数组中的逆序对(二路归并)

在数组中的两个数字如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。 输入一个数组,求出这个数组中的逆序对的总数。

输入:[1,2,3,4,5,6,0] 输出:6  因为逆序对有(1,0), (2,0), (3,0), (4,0), (5,0), (6,0)

分析】   本题存在暴力解法的, n n n 个数字,两两组对,有 C n 2 C_n^2 Cn2​ 种组队方式(因为先后顺序是固定的),我们遍历每一种组队情况,如果是逆序对,则把逆序对的总数加1即可。

class Solution(object):
    # 暴力解法,时间复杂度为O(n^2)
    def inversePairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                if nums[i] > nums[j]:
                    res += 1
        return res

  上面的实现方式,时间复杂度为 O ( n 2 ) O(n^2) O(n2),我们可以进行优化,把时间复杂度优化到 O ( n l o g n ) O(nlogn) O(nlogn)。

  具体思路是用到二路归并排序的思想,想象一下,我们把一个数组划分成左、右两部分,那么逆序对的总个数等于左边部分逆序对的个数 + 右边逆序对的个数,除此之外,我们将左右两部分进行升序排列,那么总的逆序对的个数,还包括左边元素与右边元素组成逆序对的个数,即逆序对的总个数由上述三部分组成,并且三个部分之间是没有交集的。

class Solution(object):
    def merge(self, nums, l, r):
        if l >= r:
            return 0
        mid = l + r >> 1
        # 左边的逆序对的个数 + 右边逆序对的个数
        res = self.merge(nums, l, mid) + self.merge(nums, mid + 1, r)
        i, j = l, mid + 1
        sorted_nums = []
        # 统计归并之前,左边元素与右边元素构成逆序对的个数
        while i <= mid and j <= r:
            if nums[i] <= nums[j]:
                sorted_nums.append(nums[i])
                i += 1
            else:
                sorted_nums.append(nums[j])
                # print('{} {}'.format(nums[i:mid+1],nums[j]))
                j += 1
                res += mid - i + 1  # 统计左边有多少个大于右边当前值的元素
        while i <= mid:
            sorted_nums.append(nums[i])
            i += 1
        while j <= r:
            sorted_nums.append(nums[j])
            j += 1
		nums[l:r + 1] = sorted_nums  # 把进行归并所对应的原数组部分,用有序数组替代
        return res

    # 二路归并,时间复杂度为O(nlogn)
    def inversePairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return self.merge(nums, 0, len(nums) - 1)

51. 两个链表的第一个公共结点(找规律)

输入两个链表,找出它们的第一个公共结点。 当不存在公共节点时,返回None。

给出两个链表如下所示: A: a1 → a2           ↘             c1 → c2 → c3             ↗ B: b1 → b2 → b3 输出第一个公共节点c1

分析

  两个链表分为两种情况,第一种情况是存在公共节点,第二种情况是不存在公共节点,我们分别进行讨论。

  • 两链表存在公共节点

  如上图所示,A,B两个链表存在公共节点,链表A的长度为 x + z x+z x+z,链表B的长度为 y + z y+z y+z,我们定义两个指针,同时从A,B两个链表的头节点开始走,当走到所在链表的尾结点时,再从另一个链表的头节点开始走,这时我们发现, x + z + y = y + z + x x+z+y = y+z+x x+z+y=y+z+x,两个指针必定在第一个公共节点处相遇!

  • 两链表不存在公共节点

  如上图所示,A,B两个链表不存在公共节点,链表A的长度为 a a a,链表B的长度为 b b b,我们定义两个指针,同时从A,B两个链表的头节点开始走,当走到所在链表的尾结点时,再从另一个链表的头节点开始走,这时我们发现, a = b a = b a=b,两个指针必定会同时走向空节点!

  具体实现代码如下:

class Solution(object):
    def findFirstCommonNode(self, headA, headB):
        """
        :type headA, headB: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        p = headA
        q = headB
        while p != q:  # 当 p 和 q 相遇的位置,即为第一个公共节点的位置
            p = p.next
            q = q.next
            if not p and not q:  # 同时走到空节点,说明不存在公共节点
                return None
            if not p:  # 只有p走到空节点,让p再去走链表B
                p = headB
            if not q:  # 只有q走到空节点,让q再去走链表A
                q = headA
        return p

52. 数字在排序数组中出现的次数(二分法)

统计一个数字在排序数组中出现的次数。 例如输入排序数组 [ 1 , 2 , 3 , 3 , 3 , 3 , 4 , 5 ] [1, 2, 3, 3, 3, 3, 4, 5] [1,2,3,3,3,3,4,5]和数字 3 3 3,由于 3 3 3在这个数组中出现了 4 4 4次,因此输出 4 4 4。

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

分析】   一个简单的思路是,我们之间遍历一遍数组,将元素存在哈希表中,就可以直接得到某个数字出现的次数,它的时间复杂度是 O ( n ) O(n) O(n)。

  我们观察这个数组的特点,它是一个排序数组,如果我们想要查询 3 3 3出现的次数,只需要找到 3 3 3第一次出现的位置 i i i,和 3 3 3最后一次出现的位置 j j j,那么3出现的次数则为 j i + 1 j-i+1 j−i+1。

  可以用二分法来解决此问题, 3 3 3第一次出现的位置,满足它左边的所有元素均小于 3 3 3,它右边所有的元素均大于等于 3 3 3。如果nums[mid] < 3,那么说明最终的 l l l 应该在 mid \text{mid} mid 的左边,即l = mid+1,否则 r = mid

   3 3 3最后一次出现的位置,满足它右边的所有元素均大于 3 3 3,它左边所有的元素均小于等于 3 3 3。如果nums[mid] > 3,那么说明最终的 r r r 应该在 mid \text{mid} mid 的左边,即r = mid-1,否则 l = mid

  具体实现代码:

class Solution(object):
    def getNumberOfK(self, nums, k):
        """
        :type nums: list[int]
        :type k: int
        :rtype: int
        """
        if not nums or k not in nums:
            return 0
        l, r = 0, len(nums) - 1
        while l < r:
            mid = l + r >> 1
            if nums[mid] < k:  # 我们要求的值,是第一个等于k的元素的下标
                l = mid + 1
            else:
                r = mid
        temp = l  # 把l的值存起来
        l, r = 0, len(nums) - 1
        while l < r:
            mid = l + r + 1 >> 1
            if nums[mid] > k:  # 我们要求的值,是最后一个等于k的元素的下标
                r = mid - 1
            else:
                l = mid
        return l - temp + 1

53. 有序数组中数值和下标相等的元素(二分法)

假设一个单调递增的数组里的每个元素都是整数并且是唯一的。 请编程实现一个函数找出数组中任意一个数值等于其下标的元素。 如果不存在,则返回 -1

输入 [ 3 , 1 , 1 , 3 , 5 ] [-3, -1, 1, 3, 5] [−3,−1,1,3,5] 输出:3

分析】   简单的思路是直接从头到尾遍历一次,找到第一个数值和下标相等的元素,再返回,时间复杂度为 O ( n ) O(n) O(n),我们下面进行优化,把时间复杂度降到 O ( l o g n ) O(logn) O(logn)

  输入的数组是一个严格单调递增的整数数组,并且每一个元素都是唯一的,即 nums[i]-nums[i-1] 1 \text{nums[i]-nums[i-1]}\geq1 nums[i]-nums[i-1]≥1,于是: (nums[i]-i) - (nums[i-1]-(i-1))=nums[i]-nums[i-1]-1 0 \text{(nums[i]-i) - (nums[i-1]-(i-1))=nums[i]-nums[i-1]-1}\geq0 (nums[i]-i) - (nums[i-1]-(i-1))=nums[i]-nums[i-1]-1≥0

  所以 nums[i]-i \text{nums[i]-i} nums[i]-i 是一个(不严格)单调递增的整数数组,我们想要找到数组中第一次为0的元素,那么它左边的所有元素都一定小于0,右边的所有元素均大于等于0,我们可以用二分法进行求解。

class Solution(object):
    def getNumberSameAsIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return -1
        l, r = 0, len(nums) - 1
        while l < r:
            mid = l + r >> 1
            if nums[mid] - mid < 0:
                l = mid + 1
            else:
                r = mid
        if nums[l] - l == 0:
            return l
        return -1

54. 二叉搜索树的第k小节点(中序遍历 && DFS)

给定一棵二叉搜索树,请找出其中的第k小的结点。 你可以假设树和k都存在,并且1≤k≤树的总结点数。

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

分析】   本题给的是一棵二叉搜索树,它的特点在于中序遍历的结果,是单调递增的,由此可知,第k小的节点,也就是我们第 k k k 轮中序遍历时的对应的节点。

  中序遍历的模板是:

def in_oder(root):
	if not root:
		return
	in_order(root.left)
	# do something
	in_order(root.right) 

  也就是说,我们想要做的操作,应该写在 do something \text{do something} do something 的位置,我们每到达一次这个位置,就将 k 减 1,当 k 为 0 的时候,即为我们中序遍历到第k个节点的时候。

  完整代码如下:

class Solution(object):
    ans = TreeNode(-1)
    k = 0  # 必须将k存为全局变量,因为每轮递归回退时的k不是同一个k值

    def dfs(self, root):
        if not root:
            return
        self.dfs(root.left)
        self.k -= 1
        if not self.k:
            self.ans = root
            return  # 找到第k小的节点之后,可以提前返回,不需要再往下遍历了
        self.dfs(root.right)

    def kthNode(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: TreeNode
        """
        self.k = k
        self.dfs(root)
        return self.ans

  这里值得一提的是,我第一次写的时候,把 k 作为 dfs 函数中的一个参数传进去的,这样子是不对的。因为在python中,每轮递归完之后,回退到上一次进入递归的位置时,它的 k 值还是原来的 k 值,没有发生变化。因此,我们需要将每轮递归中共享的变量,单独作为全局变量提出来。

55. 平衡二叉树(DFS优化)

输入一棵二叉树的根结点,判断该树是不是平衡二叉树。 如果某二叉树中任意结点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。 注意:   规定空树也是一棵平衡二叉树。

分析】   在上一题中,我们掌握了如何求解一棵树的深度,于是看到本题之后,我的第一想法是,进行层次遍历,分别求解每一个节点左子树的高度,和右子树的高度,如果相差超过1,直接返回 False,否则进行往下遍历,直到最后一个叶子节点为止。

  实现代码如下:

class Solution(object):
    def treeDepth(self, node):
        if not node:
            return 0
        return max(self.treeDepth(node.left), self.treeDepth(node.right)) + 1

    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        queue = [root]
        while queue:
            node = queue.pop(0)
            if abs(self.treeDepth(node.left) - self.treeDepth(node.right)) > 1:
                return False
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return True

  上面这种思路,有值得优化的地方,我们在求解子树深度的时候,就已经递归到叶子节点,再往上返回,得到了每一个节点作为根结点时的树的高度,所以我们完全可以把比较操作,直接放到求解树的深度的代码中,详细如下:

class Solution(object):
    ans = True

    def treeDepth(self, node):
        if not node:
            return 0
        left = self.treeDepth(node.left)
        right = self.treeDepth(node.right)
        if abs(left - right) > 1: # 将 ans 置为 False
            self.ans = False
        return max(left, right) + 1

    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        self.ans = True
        self.treeDepth(root)
        return self.ans

56. 数组中只出现一次的两个数字(位运算)

一个整型数组里除了两个数字之外,其他的数字都出现了两次。 请写程序找出这两个只出现一次的数字。 你可以假设这两个数字一定存在

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

分析】   我们知道,异或运算的逻辑是,相同为0,不同为1。如果 n 个数中,只有一个数字出现了一次,其他数字均出现了两次,我们把所有的数进行异或操作,那么最后得到的就是那个独一无二的数字。

  本题中,考察的是存在两个只出现了一次的数字,假设为 x , y x,y x,y,那么所有的数进行异或运算之后,得到的结果为 s = x ^ y。

  我们找到 s 中,某一位为1的数字,它是 x 和 y 中不同的部分,我们利用这个性质,可以将原集合划分成两个部分,那么x 和 y 则必定在不同的集合中,并且集合内,除了 x 或 y 的其他所有元素,必定是重复的,这时我们再次进行异或操作,就能得出 x 的值,x ^ s 就能得出 y 的值。

class Solution(object):
    def findNumsAppearOnce(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums:
            return []
        s = 0
        # 假设返回的是x,y,那么所有数字进行异或操作之后,只剩下x^y
        for num in nums:
            s ^= num
        k = 0
        while s >> k & 1 != 1:  # s的二进制表示中,从右往左第k个数为1
            k += 1
        x = 0
        for num in nums:
            if num >> k & 1 == 1:
                x ^= num
        return [x, s ^ x]

57. 数组中唯一只出现一次的数字(二进制统计)

在一个数组中除了一个数字只出现一次之外,其他数字都出现了三次。 请找出那个只出现一次的数字。 你可以假设满足条件的数字一定存在。 思考题:   如果要求只使用 O(n) 的时间和额外 O(1) 的空间,该怎么做呢?

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

分析】   本题的条件是,除了一个数组出现了一次,其余都出现了三次,那么就不能直接进行异或求解。

  我们换个思路,某个数字出现了三次,那么该数字的二进制表示中,如果某一位为1,因为出现了三次,所以累加起来应该为3,而只出现了一次的数字,它的某一位为1,则该位只能加1。

  也就是说,我们创建一个长度为32的数组 count,每一个元素用来统计整个数组中,当前位置所对应二进制位的1的个数,按照题目要求,count[i] % 3要么为0,要么为1。我们把整个数组模3,即为只出现一次的数字的二进制表示(从右往左),然后我们把它转成十进制数即可。

  具体代码如下:

class Solution(object):
    def findNumberAppearingOnce(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = [0] * 32  # 统计每1个二进制位上,1出现的次数
        for num in nums:
            k = 0
            while k < 32:
                count[k] += num >> k & 1
                k += 1
        res = 0
        for i in range(32):
            # 因为其他数字都出现了三次,只有一个数字出现了一次
            # 也就说明count[i]%3等于0或1
            res += count[i] % 3 * 2 ** i
        return res

  除此之外,还有超神版代码,仅供了解:

class Solution(object):
    def findNumberAppearingOnce_2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ones, twos = 0, 0
        for num in nums:
            ones = (ones ^ num) & ~ twos
            twos = (twos ^ num) & ~ ones
        return ones

  大致思路是一个状态机表示,如果某个数字出现了三次,就会变成 0。换个问题,如果传入的数组中,只有一个元素出现了两次,其余都出现了三次,那就返回 twos 即为所求。

58. 和为S的两个数字(哈希表)

输入一个数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。 如果有多对数字的和等于s,输出任意一对即可。 你可以认为每组输入中都至少含有一组满足条件的输出。

输入:[1,2,3,4] , sum=7 输出:[3,4]

分析】   本题可以构建一个哈希表来快速实现,遍历数组中的每一个数字,如果它不在哈希表中,我们就把target - num作为key,存到哈希表里,值可以随意指定,不妨设为num。如果遍历到某个数字是属于哈希表的 key 的话,直接返回 [target-num, num]

class Solution(object):
    def findNumbersWithSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = dict()
        for num in nums:
            if num in d.keys():
                return [target - num, num]
            else:
                d[target - num] = num

58. 和为S的连续正整数序列(高斯求和,双指针法)

输入一个正数s,打印出所有和为s的连续正数序列(至少含有两个数)。 例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以结果打印出3个连续序列1~5、4~6和7~8。

输入:15 输出:[[1,2,3,4,5],[4,5,6],[7,8]]

分析】   关于连续正整数的和,我们可以想到高斯求和公式,或者说等差数列求和公式,即 s = a 1 + a n 2 × n s = \frac{a_1+a_n}{2}\times n s=2a1​+an​​×n,它的时间复杂度为 O ( 1 ) O(1) O(1)。

  也就是说,我们可以定义两个指针,一个表示起始项 a 1 a_1 a1​,另一个表示 a n a_n an​,然后不断的枚举即可。

  分析数列的规律,可以发现两个指针的区间不会是全部区间,对于一个正整数 n n n,如果它是奇数,那么两个指针可以到达最大的位置分别是 n 2 \lfloor{\frac{n}{2}}\rfloor ⌊2n​⌋、 n 2 \lceil{\frac{n}{2}}\rceil ⌈2n​⌉,如果它是偶数,也可以同样指定上述的范围。此外,第二个指针的范围必定在第一个指针之后,于是我们将暴力搜索的区间进行限制,编写代码如下:

class Solution(object):
    # 暴力搜索,对搜索空间进行了优化
    def findContinuousSequence(self, sum):
        """
        :type sum: int
        :rtype: List[List[int]]
        """
        res = []
        for i in range(1, sum // 2 + 1):  # i的最后一个取值是sum/2向下取整
            for j in range(i + 1, (sum + 1) // 2 + 1):  # j从i+1开始,j的最后一个取值是sum/2向上取整
                s = (i + j) * (j - i + 1) // 2  # 高斯求和公式
                if s == sum:
                    res.append(list(range(i, j + 1)))
        return res

  实际上呢,该问题还有一个规律,那就是假设两个指针 i, j \text{i, j} i, j 当前的位置已经满足,高斯和等于目标值,如果 i \text{i} i 继续增大得到 i \text{i}^\prime i′,假设存在一个 j \text{j}^\prime j′,满足 i , j \text{i}^\prime, \text{j}^\prime i′,j′区间内的所有正整数之和等于目标值,那么必有 j &gt; j \text{j}^\prime &gt; \text{j} j′>j 成立。根据这个特性,我们可以进一步缩小搜索区间。

  用双指针法实现上述思想:

class Solution(object):
    def findContinuousSequence_2(self, sum):
        """
        :type sum: int
        :rtype: List[List[int]]
        """
        res = []
        i = 1
        j = 2
        while i <= sum // 2 + 1 and j <= (sum + 1) // 2 + 1:
            s = (i + j) * (j - i + 1) / 2
            if s == sum:
                res.append(list(range(i, j + 1)))
                i += 1
                j += 1
            elif s < sum:
                j += 1
            else:
                i += 1
        return res

59. 最长递增子序列(动态规划或二分法)

给定一个无序的整数数组,找到其中最长上升子序列的长度。

输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

分析】   统计个数类型的问题,可以考虑要动态规划法来做。

  动态规划法,需要考虑三个因素:

  • 状态表示 本题 dp[i] \text{dp[i]} dp[i] 表示以第 i \text{i} i 个元素结尾的子序列的最大长度;
  • 状态转移方程 在本题中, dp[i] \text{dp[i]} dp[i] 的取值,不再是像往常一样,只与前面几个状态有关,而是和前面 dp[0] \text{dp[0]} dp[0], dp[1] \text{dp[1]} dp[1], dp[2] \text{dp[2]} dp[2], \cdots ⋯, dp[i-1] \text{dp[i-1]} dp[i-1]每一个状态有关。所以需要进行一次遍历,如果 nums[i]&gt;nums[j] \text{nums[i]&gt;nums[j]} nums[i]>nums[j],那么 dp[i]=max(dp[i], dp[j] + 1) \text{dp[i]=max(dp[i], dp[j] + 1)} dp[i]=max(dp[i], dp[j] + 1),如果 nums[i]==nums[j] \text{nums[i]==nums[j]} nums[i]==nums[j],那么 dp[i] = max(dp[i], dp[j]) \text{dp[i] = max(dp[i], dp[j])} dp[i] = max(dp[i], dp[j]) 。
  • 边界条件 i=0 \text{i=0} i=0 时, dp[0] = 1 \text{dp[0] = 1} dp[0] = 1,因为每一个 dp[i] \text{dp[i]} dp[i] 必定存在一个子序列,所以我们把dp数组初始化全为1。

  具体实现代码如下:(时间复杂度为 O ( n 2 ) O(n^2) O(n2))

class Solution:
    res = 1

    def lengthOfLIS(self, nums):
        if not nums:
            return 0
        dp = [1] * len(nums)
        dp[0] = 1
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
                elif nums[j] == nums[i]:
                    dp[i] = max(dp[i], dp[j])
            self.res = max(self.res, dp[i])
        return self.res

  实际上存在时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn),需要用到二分法,我们下面进行详细探讨。

  假设我们输入的无序数组为 nums=[4,5,6,3] \text{nums=[4,5,6,3]} nums=[4,5,6,3]:

  • 所有长度为1的递增子序列为 [ [ 4 ] , [ 5 ] , [ 6 ] , [ 3 ] ] [[4], [5], [6], [3]] [[4],[5],[6],[3]];
  • 所有长度为2的递增子序列为 [ [ 4 , 5 ] , [ 4 , 6 ] , [ 5 , 6 ] ] [[4, 5], [4, 6], [5, 6]] [[4,5],[4,6],[5,6]];
  • 所有长度为3的递增子序列为 [ [ 4 , 5 , 6 ] ] [[4, 5, 6]] [[4,5,6]];

  我们定义一个数组 tails \text{tails} tails,其中 tails[i] \text{tails[i]} tails[i] 来保存长度为 i i i的所有递增子序列中的尾部元素的最小值。有点绕,我们结合上面实例来看。

  • tails[0] = 3 \text{tails[0] = 3} tails[0] = 3,因为所有长度为1的递增子序列中,尾部元素最小为3;
  • tails[1] = 5 \text{tails[1] = 5} tails[1] = 5,因为所有长度为2的递增子序列中,尾部元素最小为5;
  • tails[2] = 6 \text{tails[2] = 6} tails[2] = 6,因为所有长度为3的递增子序列中,尾部元素最小为6;

  不难发现规律,如果 tails \text{tails} tails 数组不断增长,那么它一定是单调递增的序列,这就是二分法使用的关键。

  我们从前往后依次遍历数组中的每一个元素 num \text{num} num,查找 num \text{num} num 在 tails \text{tails} tails 数组中的具体位置,具体是找到 tails \text{tails} tails 数组中,第一个大于 num \text{num} num 的下标 idx \text{idx} idx,然后tails[idx]=num进行替换操作,修改 当前长度为 idx+1 \text{idx+1} idx+1的递增子序列的尾部元素的最小值。

  当然,有特殊情况需要进行判断,因为初始时 tails 数组为空,所以当它为空时,直接把元素 num \text{num} num添加到 tails 数组中;另外一种情况是,我们二分查找得到的 idx 是tails 数组中的最后一个元素,这时我们进行比较,如果该元素小于 tails 数组中的最后一个元素,执行替换操作,否则把该元素追加到 tails 数组的尾部。

  具体实现代码如下:(时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn))

class Solution:
    def lengthOfLIS(self, nums):
        if not nums:
            return 0
        tails = []  # tails是一个递增数组,tails[i]存储所有长度为i+1的子序列中的尾部元素的最小值
        for num in nums:
            l = 0
            r = len(tails) - 1
            while l < r:
                mid = l + r >> 1
                if tails[mid] < num: # 要找的元素,它的左边全部小于它,不包含mid
                    l = mid + 1
                else:
                    r = mid
            if not tails or tails[l] < num:  # tails数组中的所有元素均小于num,则将num添加到tails中
                tails.append(num)
            else:  # 否则把tails中,第一个大于num的元素修改为num
                tails[l] = num
        return len(tails)

60. 翻转字符串(操作分解)

输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。 为简单起见,标点符号看成普通字母一样。 例如输入字符串"I am a student.",则输出"student. a am I"。

输入:“I am a student.” 输出:“student. a am I”

  本题解法不难,调用python的语法,return ’ '.join(s.split()[::-1]) 一行代码即可实现,但也失去了本题考察的目的。

  记录本题的目的有两个,一是了解操作分解的思想,二是熟悉python字符串的操作。

  • 操作分解 我们可以把翻转字符串的操作,分成两个子操作。第一步,对整个字符串进行翻转,得到 .tneduts a ma I;第二步,把里面的每一个单词进行翻转,得到 student. a am I ,完成本题要求。
  • python 字符串处理
    • 修改字符串一个或连续多个字符 s = s.replace(s[i], ‘$’)s = s.replace(s[i:j], ‘$$$$$$’)
    • 字符串转列表 s = ‘i o u’,list(s) = [‘i’, ’ ', ‘o’, ’ ', ‘u’]
    • 字符转ASCII码 ord(‘a’) = 97
    • ASCII码转字符 chr(97) = 'a’
class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        s = s[::-1]
        i = 0
        while i < len(s):
            # 字符串划分模板
            j = i
            while j < len(s) and s[j] != ' ':
                j += 1
            s = s.replace(s[i:j], s[i:j][::-1])  # 将单词进行翻转,并覆盖原单词
            i = j + 1
        return s

  本题还有一个姊妹题,给定一个字符串,一个整数n,如何把字符串的前 n 位按顺序转移到字符串的尾部。

输入:“abcdefg” , 3 输出:“defgabc”

  同样可以采用操作分解的思想进行实现,第一步,把前n个字符反转,把第n位及其之后字符进行反转,第二步,把整个字符串进行反转。

class Solution(object):
    def leftRotateString(self, s, n):
        """
        :type s: str
        :type n: int
        :rtype: str
        """
        s = s.replace(s[:n], s[:n][::-1])
        s = s.replace(s[n:], s[n:][::-1])
        return s[::-1]

  最后再多聊几句 操作分解 的思想,给定一个矩阵,如果要把它顺时针进行翻转90度,180度,270度,可以把这个过程分解成两部分完成。

  • 矩阵顺时针旋转90度 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 1 ] [ 5 ] [ 9 ] [ 3 ] [ 2 ] [ 6 ] [ 0 ] [ 4 ] [ 3 ] [ 7 ] [ 1 ] [ 5 ] [ 4 ] [ 8 ] [ 2 ] [ 6 ] [ 3 ] [ 9 ] [ 5 ] [ 1 ] [ 4 ] [ 0 ] [ 6 ] [ 2 ] [ 5 ] [ 1 ] [ 7 ] [ 3 ] [ 6 ] [ 2 ] [ 8 ] [ 4 ] \begin{array}{l}{[1][2][3][4]} \\ {[5][6][7][8]} \\ {[9][0][1][2]} \\ {[3][4][5][6]}\end{array}\rightarrow\begin{array}{l}{[1][5][9][3]} \\ {[2][6][0][4]} \\ {[3][7][1][5]} \\ {[4][8][2][6]}\end{array} \rightarrow \begin{array}{l}{[3][9][5][1]} \\ {[4][0][6][2]} \\ {[5][1][7][3]} \\ {[6][2][8][4]}\end{array} [1][2][3][4][5][6][7][8][9][0][1][2][3][4][5][6]​→[1][5][9][3][2][6][0][4][3][7][1][5][4][8][2][6]​→[3][9][5][1][4][0][6][2][5][1][7][3][6][2][8][4]​

  第一步,把对角线两边的元素交换,即 matrix[i][j] = matrix[j][i] \text{matrix[i][j] = matrix[j][i]} matrix[i][j] = matrix[j][i]

  第二步,把每一行的元素,进行翻转,定义首尾指针,对应两两交换即可。

  • 矩阵逆时针旋转90度 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 1 ] [ 5 ] [ 9 ] [ 3 ] [ 2 ] [ 6 ] [ 0 ] [ 4 ] [ 3 ] [ 7 ] [ 1 ] [ 5 ] [ 4 ] [ 8 ] [ 2 ] [ 6 ] [ 4 ] [ 8 ] [ 2 ] [ 6 ] [ 3 ] [ 7 ] [ 1 ] [ 5 ] [ 2 ] [ 6 ] [ 0 ] [ 4 ] [ 1 ] [ 5 ] [ 9 ] [ 3 ] \begin{array}{l}{[1][2][3][4]} \\ {[5][6][7][8]} \\ {[9][0][1][2]} \\ {[3][4][5][6]}\end{array}\rightarrow\begin{array}{l}{[1][5][9][3]} \\ {[2][6][0][4]} \\ {[3][7][1][5]} \\ {[4][8][2][6]}\end{array} \rightarrow \begin{array}{l}{[4][8][2][6]} \\ {[3][7][1][5]} \\ {[2][6][0][4]} \\ {[1][5][9][3]}\end{array} [1][2][3][4][5][6][7][8][9][0][1][2][3][4][5][6]​→[1][5][9][3][2][6][0][4][3][7][1][5][4][8][2][6]​→[4][8][2][6][3][7][1][5][2][6][0][4][1][5][9][3]​

  第一步,把对角线两边的元素交换,即 matrix[i][j] = matrix[j][i] \text{matrix[i][j] = matrix[j][i]} matrix[i][j] = matrix[j][i]

  第二步,把每一列的元素,进行翻转,定义首尾指针,对应两两交换即可。

  • 矩阵顺/逆时针旋转180度 [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 4 ] [ 3 ] [ 2 ] [ 1 ] [ 8 ] [ 7 ] [ 6 ] [ 5 ] [ 2 ] [ 0 ] [ 1 ] [ 9 ] [ 6 ] [ 5 ] [ 4 ] [ 3 ] [ 6 ] [ 5 ] [ 4 ] [ 3 ] [ 2 ] [ 0 ] [ 1 ] [ 9 ] [ 8 ] [ 7 ] [ 6 ] [ 5 ] [ 4 ] [ 3 ] [ 2 ] [ 1 ] \begin{array}{l}{[1][2][3][4]} \\ {[5][6][7][8]} \\ {[9][0][1][2]} \\ {[3][4][5][6]}\end{array}\rightarrow\begin{array}{l}{[4][3][2][1]} \\ {[8][7][6][5]} \\ {[2][0][1][9]} \\ {[6][5][4][3]}\end{array} \rightarrow \begin{array}{l}{[6][5][4][3]} \\ {[2][0][1][9]} \\ {[8][7][6][5]} \\ {[4][3][2][1]}\end{array} [1][2][3][4][5][6][7][8][9][0][1][2][3][4][5][6]​→[4][3][2][1][8][7][6][5][2][0][1][9][6][5][4][3]​→[6][5][4][3][2][0][1][9][8][7][6][5][4][3][2][1]​

  第一步,反转矩阵中每一行的元素。

  第二步,反转矩阵中每一列的元素。

61. 滑动窗口的最大值(单调、双向队列)

给定一个数组和滑动窗口的大小,请找出所有滑动窗口里的最大值。 例如,如果输入数组[2, 3, 4, 2, 6, 2, 5, 1]及滑动窗口的大小3,那么一共存在6个滑动窗口,它们的最大值分别为[4, 4, 6, 6, 6, 5]。

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

分析】   一个直观的思路是,我们维护一个长度为k的队列,每次从中取出队列中的最大值,时间复杂度为O(kn),因为每轮要从k个数中找到最大值。

class Solution(object):
    # 直观解法,时间复杂度为O(kn),每轮要从k个数中找到最大值
    def maxInWindows(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        res = []
        queue = []
        for num in nums:
            if len(queue) < k:
                queue.append(num)
            if len(queue) == k:
                res.append(max(queue))
                queue.pop(0)
        return res

  实际上,本题的时间复杂度可以优化到 O ( n ) O(n) O(n),核心在于维护一个单调递减的双向队列。

  我们在队列中,保存元素的下标,当有一个元素需要入队时,我们进行几轮判断:

  • 1. 队首元素是否需要出队?  判断依据,当前元素的下标 减去 队列头元素的下标 是否等于 k,是的话,说明队列头元素需要出队。
  • 2. 当前元素的下标插入到队列尾部之后,能否保证队列依然是递减的?  为什么要让队列保持递减呢?假如某个元素值与队列中其他元素大,那么队列中比它小的元素,永远不可能成为当前队列中的最大元素,所以可以直接删除掉。
  • 3. 是否需要把队列头元素对应的最大值添加到输出结果中?  直接比较 当前元素的下标是否大于或等于 k-1 即可,很明显我们的滑动窗口从第 k-1 个元素开始输出,队列第一个元素的下标即为当前窗口的最大值。

  具体实现代码:

class Solution(object):
    def maxInWindows(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        res = []
        queue = []
        for i, num in enumerate(nums):
            if queue and i - queue[0] == k:  # 判断队列头元素是否需要弹出
                queue.pop(0)
            while queue and nums[queue[-1]] <= num:  # 维护队列单调递减
                queue.pop()  # 队列尾部小于num的元素陆续出队
            queue.append(i)
            if i >= k - 1:  # 队列的头元素始终为当前窗口内最大值的下标
                res.append(nums[queue[0]])
        return res

62. n个骰子的点数(递归或动态规划)

将一个骰子投掷n次,获得的总点数为s,s的可能范围为n~6n。 掷出某一点数,可能有多种掷法,例如投掷2次,掷出3点,共有[1,2],[2,1]两种掷法。 请求出投掷n次,掷出n~6n点分别有多少种掷法

输入:n=2 输出:[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1] 解释:投掷2次,可能出现的点数为2-12,共计11种。每种点数可能掷法数目分别为1,2,3,4,5,6,5,4,3,2,1。 所以输出[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]。

分析】   本题是一类特别经典的题型,所以我会重点进行分析。

  对于连续重复某种操作,并且操作结果必定是已知取值空间中的一种,求 n 次操作最终的取值类型的题,如掷骰子、爬台阶等问题,我们都可以考虑用递归或者动态规划来做。

  我们先聊一聊递归与动态规划的区别,再用两种解法来解决本题。

  • 递归的特点

    • 一个问题的解可以分解为几个子问题的解;
    • 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样
    • 存在递归终止条件,即必须有一个明确的递归结束条件,称之为递归出口
  • 递归的解法

    • 找到如何将大问题分解为小问题的规律
    • 通过规律写出递推公式
    • 通过递推公式的临界点推敲出终止条件
    • 编写代码实现递归过程
  • DP的特点

    • 动态规划法试图只解决每个子问题一次(递归则是多次)
    • 旦某个子问题的解已经算出,则将其存储,下次需要同一个子问题的解时直接查表
  • DP的解法

    • 状态表示
    • 状态转移方程
    • 边界处理

  根据我个人的学习感受,我认为递归和动态规划的思路还是蛮接近的,能用递归解决的问题,基本上可以用动态规划来解决。递归是一个自上而下的过程,存在多次子问题求解的冗余计算,故时间复杂度是指数级的,优点在于代码简洁,实现简单;而动态规划是一个自底向上的过程,可以保存每个子问题的解,上层需要求解时,直接查表即可,不需要再计算一遍,优点是时间复杂度低,但是存储子问题的解需要开辟新的空间,典型的以空间换时间的做法。

  回到本题中来,我们先用递归进行求解。

  • 大问题分解成小问题 我们假设用 f(n,S) 来表示n个骰子的和为S的情况总数,那它可以分解为n-1个骰子的和为S-1,n-1个骰子的和为S-2, \cdots ⋯,n-1个骰子的和为S-6,这6个子问题来求解。
  • 递推公式 根据上方规律,可知f(n,S)=f(n-1,S-1)+f(n-1,S-2)+f(n-1,S-3)+f(n-1,S-4)+f(n-1,S-5)+f(n-1,S-6)
  • 递归终止条件 显然,当 n == 1 and 0 < S < 7 时,我们要返回1;如果 n < 1 or S <= 0 时,返回 0。
  • 编写代码实现递归过程
class Solution(object):
    def numberOfDice(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        if not n:
            return 0
        res = []
        for i in range(n, 6 * n + 1):
            res.append(self.dfs(i, n))
        return res

    # 递归两个要素:1.递归表示 2.递推公式 ,自上而下的顺序
    def dfs(self, s, n):
        if n < 1 or s <= 0:
            return 0
        if n == 1 and 0 < s < 7:
            return 1
        res = 0
        for i in range(1, 7):
            res += self.dfs(s - i, n - 1)
        return res

  我们接下来再用动态规划进行求解。

  • 状态表示 我们用 dp[i][j] \text{dp[i][j]} dp[i][j] 表示 i 个骰子和为 j 的总情况数
  • 状态转移方程 根据前面的分析,我们知道, dp[i][j] += dp[i-1][j-k] \text{dp[i][j] += dp[i-1][j-k]} dp[i][j] += dp[i-1][j-k],其中 k \text{k} k 的取值为 1 , 2 , 3 , 4 , 5 , 6 {1,2,3,4,5,6} 1,2,3,4,5,6
  • 边界处理 在本题中,我们的边界是骰子数为1的情况,我们可以直接把 dp[1][1],dp[1][2],dp[1][3],dp[1][4],dp[1][5],dp[1][6] \text{dp[1][1],dp[1][2],dp[1][3],dp[1][4],dp[1][5],dp[1][6]} dp[1][1],dp[1][2],dp[1][3],dp[1][4],dp[1][5],dp[1][6]的取值全部初始为1。

  在本题中,动态规划还需要注意的一点是二维数组的初始化,因为骰子数为1的和只有6种取值,骰子数为2有11种取值,骰子数为3有16种取值 \cdots \cdots ⋯⋯ 本来我的想法是按照每个骰子的取值情况初始化数组,但是会发生数组越界的情况,如dp[3][15] += dp[2][13]的时候,而dp[2]最多只能到dp[2][12],此时就会报数组越界了。

  因此,我们直接初始化 dp数组 为一个 n+1 行,6*n +1 列的二维矩阵。

  详细代码如下:

class Solution(object):
    def numberOfDice(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        if not n:
            return 0
        dp = [[0] * (6 * n + 1) for _ in range(0, n + 1)]  # 创建一个(n+1)* 6n 的二维矩阵
        for i in range(1, 7):  # 边界处理,1个骰子和的取值为1,2,3,4,5,6的情况数全为1
            dp[1][i] = 1
        for i in range(2, n + 1):  # 枚举骰子个数,从2开始
            for j in range(i, 6 * i + 1):  # 枚举i个骰子和的取值
                for k in range(1, 7):  # k取1,2,3,4,5,6
                    dp[i][j] += dp[i - 1][j - k]
        return dp[-1][n:]  # 最后一层,从第n个元素开始,即为所求。

63. 扑克牌中的顺子(抽象建模,逆向思维)

从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。 2~10为数字本身,A为1,J为11,Q为12,K为13,大小王可以看做任意数字。 为了方便,大小王均以0来表示,并且假设这副牌中大小王均有两张。

输入:[3,2,0,6,5] 输出:true

分析

  像这种类型的题目,找到了内在原理之后,编写代码其实很简单,主要难点在于考虑周全存在的各种输入情况。

  想到的第一件事,应该是把输入数组中的 0 单独拎出来,那么剩余的数组必须满足什么条件才能组成“顺子”呢?

  或者我们可以逆向思维,哪些的情况,必然不能组成顺子?

  如果剩余数组中的存在重复元素,那这五张牌必然不会组成顺子,此外,如果最大值和最小值的差大于4,那这五张牌同样不可能组成顺子。

  编写代码如下:

class Solution(object):
    def isContinuous(self, numbers):
        """
        :type numbers: List[int]
        :rtype: bool
        """
        if not numbers:
            return False
        numbers.sort()
        k = 0
        while not numbers[k]:  # 找到第一个不为0的元素下标
            k += 1
        for i in range(k + 1, len(numbers)):
            if numbers[i] == numbers[i - 1]:  # 有序数组,重复元素必相邻
                return False
        return numbers[-1] - numbers[k] <= 4

64. 圆圈中最后剩下的数字(抽象建模,约瑟夫环)

0, 1, …, n-1这n个数字(n>0)排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字。 求出这个圆圈里剩下的最后一个数字。

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

  本题可以直接用一个环形链表进行模拟,但是实现的代码复杂度比较高,我们对问题进行探索,看能否找到问题内在的规律。

  观察下图:

  我们一开始有 n n n 个数字,每轮淘汰第 m m m 个数字,所以在第一轮,被淘汰的数字是下标为 m 1 m-1 m−1 的数字。

  那么第二轮是从下标为 m m m 的数字开始,我们按照顺序,从零开始对数组进行重新编号,结尾数字的下标为 n 2 n-2 n−2。

  可以发现,同一个数字,新的下标 j \text{j} j 和旧的下标 i \text{i} i 存在一个映射关系: i = ( j + m ) % n i = (j+m) \% n i=(j+m)%n

  这个发现是解决本题的关键!

  我们定义 f ( n , m ) f(n,m) f(n,m) 来表示每次在 n n n 个数中,删除第 m m m 个数字之后,最后剩下的数字。这个数字 必定等于 删除第 m m m 个数字之后,从下标为 m m m 的数字开始的 n 1 n-1 n−1 个数字之中,每次删除第 m m m 个数字之后,最后剩下的数字。

  也就是说,最后一轮剩下的数字,我们可以一层一层倒着推回去,从 i = 1 i = 1 i=1 开始,推到 i = n i = n i=n。

  在 i = 1 i = 1 i=1 时,因为只剩一个元素,所以最后一个数字的编号为 0 0 0 ,我们按照上面的映射关系,推导该数字在 i = 2 i = 2 i=2 时的下标,即 (0+m) % 2,依次类推 \cdots\cdots ⋯⋯

  实现代码如下:

class Solution(object):
    def lastRemaining(self, n, m):
        """
        :type n: int
        :type m: int
        :rtype: int
        """
        dp = [0] * (n + 1)
        dp[1] = 0
        for i in range(1, n + 1):
            dp[i] = (dp[i - 1] + m) % i
        return dp[-1]

65. 股票的最大利润(抽象建模)

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖一次该股票可能获得的利润是多少? 例如一只股票在某些时间节点的价格为[9, 11, 8, 5, 7, 12, 16, 14]。 如果我们能在价格为5的时候买入并在价格为16时卖出,则能收获最大的利润11。

输入:[9, 11, 8, 5, 7, 12, 16, 14] 输出:11

分析】   暴力的解法是,从输入的数字中,每次随机选取两个数字,数字之间是有先后顺序的,所以一共有 C n 2 C_n^2 Cn2​ 组数字,然后返回差值最大的结果,时间复杂度为 O ( n 2 ) O(n^2) O(n2)。

  实际上我们可以进行优化,只进行一次遍历即可,遍历到第 i \text{i} i 个元素的时候,用它的值减去它前面 i-1 \text{i-1} i-1 个元素中的最小值,即为当前元素的最大收益,时间复杂度为 O ( n ) O(n) O(n),空间复杂度为 O ( 1 ) O(1) O(1)。

  实现代码如下:

class Solution(object):
    def maxDiff(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 2:
            return 0
        res = 0
        min_v = nums[0]
        for num in nums[1:]:  # 从第2个数字开始枚举
            res = max(num - min_v, res)
            min_v = min(num, min_v)
        return res

66. 求1+2+…+n ( a and b )

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

输入:10 输出:55

分析】   我们先来想想,常规做法有哪些。

  • 高斯求和 1 + n 2 × n \frac{1+n}{2}\times n 21+n​×n
  • 循环 for num in nums: res += num
  • 递归 f(n) = f(n-1) + n

  编程语言中,编译器在执行代码时,会做一些省时的操作,我们来逐个分析执行下列命令时的实际情况。

  • a and b 如果 a 为 0 或 False 则不会执行 b 语句,直接返回 0 或 False。 在python3中,假设x,y不为0,0 and yx and 0会直接返回 0,x and y返回y。
  • a or b 如果 a 为 非零值 或 True 则不会执行 b 语句,直接返回 a 或 True。 在python3中,假设x,y不为0,x or 00 or y会直接返回 x或y,x or y返回x。

  在本题中,我们可以利用 a and b 来实现递归求和。

class Solution(object):
    def getSum(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = n
        res += n and self.getSum(n - 1)
        return res

67. 不用加减乘除做加法(位运算)

写一个函数,求两个整数之和,要求在函数体内不得使用+、-、×、÷ 四则运算符号。

输入:num1 = 1 , num2 = 2 输出:3

分析】   

  我们考虑两个二进制数中,同一个位置的两个元素 a 和 b 的加法情况:

  • a : 0 1 0 1 \text{a}:0 \qquad1 \qquad0 \qquad1 a:0101
  • b : 0 0 1 1 \text{b}:0 \qquad0 \qquad1 \qquad1 b:0011

  一共有上述四种情况,我们把加完之后的位置用字母c表示,进位用d表示

  • c : 0 1 1 0 \text{c}:0 \qquad1 \qquad1 \qquad0 c:0110
  • d : 0 0 0 1 \text{d}:0 \qquad0 \qquad0 \qquad1 d:0001

  不难发现, c, d \text{c, d} c, d 都可以用 a \text{a} a 和 b \text{b} b 通过位运算得到,即 c = a &amp; b c = a\&amp;b c=a&b, d = a b d=a^{\wedge} b d=a∧b。

  上面的讨论,是针对于单个二进制的加法,实际上它也可以拓展到多个二进制位的加法。

  两个数的加法可以分为两步,第一步,计算两个数字不进位的和,第二步,把上一步的结果,加上进位的值,可以不断循环下去,直到进位为零即可。

  不进位的和,即为两个数的异或,sum = num1 ^ num2

  进位的值,即为两个数的&运算,再左移一位(进一位),carry = (num1 & num2) << 1

  c++代码为:(比较简洁,不用考虑负数的特殊情况)

class Solution {
public:
    int add(int num1, int num2){
        while (num2) {
            int sum = num1 ^ num2;
            int carry = (num1&num2)<<1;
            num1 = sum;
            num2 = carry;
        }
        return num1;
    }
};

  根据我们前面的学习,Python整数类型可以表示无限位,所以需要人为设置边界,避免死循环,我们这里需要把它控制在32位,故实际做的时候把sum和carry加了一层转换,限制边界。

   python3代码为:

class Solution:
    def add(self, num1, num2):
        while num2:
            sum = (num1 ^ num2) & 0xffffffff  # 限制为32位,但是对应的32位的数不变
            carry = ((num1 & num2) << 1) & 0xffffffff
            num1 = sum
            num2 = carry
        if num1 < 0x7fffffff:  # 在32位的int中,如果第32位不为1,说明它是一个正数
            return num1
        else:
            return ~(num1 ^ 0xffffffff)

  补充说明一下,如何把 num1 还原成原来的负数:

  因为我们之前限定了边界 0xffffffff \text{0xffffffff} 0xffffffff,把 num1 转成了正值,所以要进行处理,把它还原成原来的负数。

  我们把 num1 分成两部分,左边部分为32位之前的高二进制位,全部是0,用A表示;右边部分为剩下的32位,用B表示。

  我们想做的就是把A中的0全部变成1,并保持B不变,num1 ^ 0xffffffff表示先把后32位按位取反,最终再全部取反,负数还原完毕。

68. 构建乘积数组(操作分解)

给定一个数组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]。 不能使用除法,空间复杂度为O(1)

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

【分析】   本题有两重限制,一是不能使用除法(否则我们直接求出连乘积,再逐一做除法即可),二是空间复杂度为 O ( 1 ) O(1) O(1)(否则我们可以开辟两个数组,一个是每个元素左边的连乘积,另一个是每个元素右边的连乘积)

  实际上,我们是可以把空间复杂度优化为 O ( 1 ) O(1) O(1) 的,我们要计算 B[i] \text{B[i]} B[i] 的值,可以分成两次完成。

  • 第一轮是把 A[i] \text{A[i]} A[i] 左边的所有元素的积赋给 B [ i ] B[i] B[i],按照从前往后的顺序,从下标为 1 1 1 的元素开始;
  • 第二轮是把 A[i] \text{A[i]} A[i] 右边的所有元素的积乘上 B [ i ] B[i] B[i],按照从后往前的顺序,从下标为 n-2 \text{n-2} n-2 的元素开始。

  我们用一个 temp 值来保存累乘的结果,最终实现代码如下:

class Solution(object):
    def multiply(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        if not A:
            return []
        B = [1] * len(A)
        temp = 1
        for i in range(1, len(A)):  # B[i] 先逐项乘以左边的A[0],A[1],...,A[i-1]
            temp *= A[i - 1]
            B[i] = temp
        temp = 1
        for i in range(len(A) - 2, -1, -1):  # B[i] 再逐项乘以右边的A[i+1],A[i+2],...,A[n-1]
            temp *= A[i + 1]
            B[i] *= temp
        return B

69. 把字符串转换成整数(字符与digit)

请你写一个函数StrToInt,实现把字符串转换成整数这个功能。 当然,不能使用atoi或者其他类似的库函数。

输入:“123” 输出:123

注意: 你的函数应满足下列条件: (1)忽略所有行首空格,找到第一个非空格字符,可以是 ‘+/−’ 表示是正数或者负数,紧随其后找到最长的一串连续数字,将其解析成一个整数; (2)整数后可能有任意非数字字符,请将其忽略; (3)如果整数长度为0,则返回0; (4)如果整数大于INT_MAX( 2 31 2^{31} 231 − 1),请返回 2 31 2^{31} 231 − 1;如果小于INT_MIN( 2 31 −2^{31} −231) ,请返回 2 31 −2^{31} −231;

分析】   本题考察了两点,一是处理各种异常输入,二是不用任何库函数处理字符串。

  • 判断一个字符是不是数字,我们用 if ‘0’ <= str[i] <= '9’
  • 求解一个字符的数值,我们用 ord(str[i]) - ord(‘0’)

  完整代码如下:

class Solution(object):
    def strToInt(self, str):
        """
        :type str: str
        :rtype: int
        """
        if not str:
            return 0
        k = 0
        while str[k] == ' ':  # 1.去开头空格
            k += 1
        str = str[k:]
        is_positive = True
        if str[0] == '-':  # 2. 如果存在正负号,记录下来,并去掉
            is_positive = False
            str = str[1:]
        elif str[0] == '+':
            str = str[1:]
        number = 0
        for i in range(len(str)):  # 将数值部分的字符串转成int存储
            if '0' <= str[i] <= '9':  # 判断字符是否为数值
                number = number * 10 + ord(str[i]) - ord('0')
            else:
                break
        if number <= 2 ** 31 - 1:
            return number if is_positive else -number
        else:
            return 2 ** 31 - 1 if is_positive else -2 ** 31

70. 二叉树中两个节点的最低公共祖先(DFS)

给定一棵二叉树,以及树中一定存在的两个节点,要求返回这两个节点的最低公共祖先。

  本题我们可以拆分成两个子问题,一是二叉搜索树中两个节点的最低公共祖先,二是普通二叉树中两个节点的最低公共祖先。

  关于两个节点的最低公共祖先,它一共只有两种情况,第一种情况是,两个节点分布在最低公共祖先的两侧;第二种情况是,其中的某个节点就是最低公共祖先。

  我们先来讨论二叉搜索树的情况。

  一般来说,二叉树类型的问题,考虑用递归来做,我们前面分析了递归的解题步骤。

  • 大问题分解成小问题 我们假设用 dfs(root,p,q) 来表示以 root \text{root} root 为根结点的二叉搜索树中,节点 p \text{p} p和 q \text{q} q的最低公共祖先,我们可以先进行预处理,如果节点 p \text{p} p的值大于节点 q \text{q} q的值,就把两个节点交换。那么,如果 p.val > root.val,说明最低公共祖先在右子树中;如果 q.val < root.val,说明最低公共祖先在右子树中,如果 p.val < root.val < q.val,说明最低公共祖先就是 root;
  • 递推公式 根据上面分析,我们得出 dfs(root,p,q) 在不同的 if 条件下,等于 dfs(root.left,p,q)dfs(root.right,p,q)root 中的一种。
  • 递归终止条件root 为空时,返回 None
  • 编写代码实现递归过程
class Solution:
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        return self.dfs(root, p, q)

    def dfs(self, root, p, q):
        if not root:
            return None
        if p.val > q.val:  # 保证我们进行搜索时,p的值小于q,简单的交换位置即可
            return self.dfs(root, q, p)
        if p.val <= root.val <= q.val:  # 两个结点在根结点的两边
            return root
        if p.val > root.val:  # 两个结点都在根结点的右侧
            return self.dfs(root.right, p, q)
        if q.val < root.val:  # 两个结点都在根结点的左侧
            return self.dfs(root.left, p, q)

  我们再来讨论普通二叉树的情况。

  同样,我们按照递归的思路来求解。

  • 大问题分解成小问题 我们假设用 dfs(root,p,q) 来表示以 root \text{root} root 为根结点的二叉搜索树中,节点 p \text{p} p和 q \text{q} q的最低公共祖先。节点 p \text{p} p和 q \text{q} q要么同时分布在左子树中,要么同时分布在右子树中,要么分布在根结点的两侧。当我们遍历到某个节点等于 p \text{p} p或 q \text{q} q时,可以直接返回该节点,在前两种情况下,该节点就是公共祖先,在第三种情况时, root \text{root} root 即为公共祖先。
  • 递推公式 根据上面分析,我们可以得出 left=dfs(root.left,p,q)right=dfs(root.right,p,q),如果 leftright 同时不为空,说明为第三种情况;否则返回 left 和 **right**中不为空的那一个节点。
  • 递归终止条件root 为空时,返回 None,说明 p \text{p} p和 q \text{q} q都不在该子树中; 当 root==p or root==q 为空时,返回 root
  • 编写代码实现递归过程
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        return self.dfs(root, p, q)

    def dfs(self, root, p, q):
        if not root or p == root or q == root:
            return root
        left = self.dfs(root.left, p, q)
        right = self.dfs(root.right, p, q)
        if left and right:
            return root
        return left if left else right


这里给大家推荐一个在线软件复杂项交易平台:米鼠网 https://www.misuland.com

米鼠网自成立以来一直专注于从事软件项目人才招聘软件商城等,始终秉承“专业的服务,易用的产品”的经营理念,以“提供高品质的服务、满足客户的需求、携手共创双赢”为企业目标,为中国境内企业提供国际化、专业化、个性化、的软件项目解决方案,我司拥有一流的项目经理团队,具备过硬的软件项目设计和实施能力,为全国不同行业客户提供优质的产品和服务,得到了客户的广泛赞誉。



如有侵权请联系邮箱(service@misuland.com)

猜你喜欢

评论留言