Jichen個人小站

剑指offer

发表于 更新于

我会在这部分记录剑指offer的题目及个人做题经验，可能会日常更新。

终于做完了！撒花！准备有空二刷

[3-数组中重复的数字]：找出数组中任意一个重复的数字

方法1：遍历一遍，用字典存储，若key出现过则直接return O(n)

方法2：排序，若nums[i]==nums[i+1]，则return O(nlogn)但不需要额外空间

[4-二维数组中的查找]在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

从右上角元素看，像是一个二分搜索树。所以当前元素<target 向下，当前元素>target向左。超出边界时没搜到返回False

[5-替换空格]请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

难点：1. 注意python中字符串是不可修改的，所以需要转化成list 2. list转字符串'str'.join(s)其中str代表用什么字符连接每个s里面的元素

[6-从尾到头打印链表]

方法1：按顺序记录进list，之后list.reverse()

方法2：借用栈的特性反转

方法3：写递归算法，注意的是res.append()一样要放在递归调用之后，这样才能达到反转的目的。

[7-重建二叉树]给定一个二叉树的前序遍历list和中序遍历list，重构这个树

题目分析：

前序遍历特点： 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序，以题目示例为例：[ 3 | 9 | 20 15 7 ]
中序遍历特点： 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序，以题目示例为例：[ 9 | 3 | 15 20 7 ]

根据题目描述输入的前序遍历和中序遍历的结果中都不含重复的数字，其表明树中每个节点值都是唯一的。
根据以上特点，可以按顺序完成以下工作：

  1. 前序遍历的首个元素即为根节点 root 的值；
  2. 在中序遍历中搜索根节点 root 的索引 ，可将中序遍历划分为 [ 左子树 | 根节点 | 右子树 ] 。
  3. 根据中序遍历中的左（右）子树的节点数量，可将前序遍历划分为 [ 根节点 | 左子树 | 右子树 ] 。

子树的前序和中序遍历仍符合以上特点，我们可以通过同样的方法对左（右）子树进行划分，每轮可确认三个节点的关系 。此递推性质让我们联想到用 递归方法 处理。

注意递归终止条件是preoder==[]
root = Treenode(preorder[0])
root.left = 递归（找到前序和中序对应的list）
root.right = 递归（找到前序和中序对应的list）
return(root)
[7*-重建二叉树]给定一个二叉树的后序遍历list和中序遍历list，重构这个树

完全一样的思路

[09-使用两个栈来构造队列，实现appendTail和deleteHead]

思路：stack1作为进入队列存储的，stack2作为删除时候需要用的

  1. append方法可以由stack1.append(value)实现
  2. delete：若stack2为空，则stack2.append(stack1.pop())将已经入队的元素逆序排进Stack2，此时res = stack2.pop() if stack2!= [] else -1

技巧：stack2弹出后不必再重建stack1，因为stack2的顺序就是未来队列出队的顺序，当stack2里面没有元素之后再搬运stack1累积加入的这些元素进入stack2.

[10斐波那契数列、上n级台阶的方式总数]：动态规划

[11-旋转数组中的最小元素]把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素

我的想法是每次二分法，找左右哪部分是乱序的，这个旋转点一定是在乱序数组中的。当i==j时返回

难点：严格找乱序的位置，注意各种边界条件比较难，一个是乱序的位置一直到哪,mid+1还是mid。第二是如果相等的话说明不能判断左右哪部分乱序，需要r=r-1

mid = (l+r)//2
if numbers[mid]<numbers[r]:r = mid
elif numbers[mid]>numbers[r]:l = mid+1
else:r = r-1

之后再写一遍，用上次那个二分法的总结

[12-矩阵中的数字]请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。

思路：设置全局变量self.sech来代表是否搜索到，idx矩阵代表当前位置是否已经搜索过。最初遍历row和col，发现对应单词第一个位置相同的时候，开始dfs搜索，dfs结束后if self.sech == True: return(True)，else: idx[i][j]=0，row和col全部遍历完还没找到的话return(false)

难点：1. dfs要对是否越界和是否搜索过做出判断 2. dfs搜索不到的时候要把对应的idx改为0 3.dfs搜索到的话迅速一层层返回

[13-机器人的运动范围]地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。请问该机器人能够到达多少个格子？

思路：和上一题非常相似但是更为简单，dfs回溯的时候不需要改idx，单独写一个计算数位之和的函数，最后统计idx里面1的个数，这一步我用的是sum([i.count(1) for i in idx])

[14-割绳子]把长度为n的绳子分为m段，每段是整数，m个数乘积最大

思路：这其实是一个数学题目，找到规律就可以解决了。发现5<2*3,4 = 2*2，所以尽可能分解成2和3的乘积，又因为2*2*2<3*3所以最好是3更多，但是不要出现1

解决方法1（动态规划）： res = [0,1,2,4,6,9]，之后每一个都是res.append(res[i-3]*3)

解决方法2：n%3余1的时候拿出一个3拆分成两个2，pow(3, n//3-1)*2*2；余2，pow(3,n//3)*2，余0，pow(3,n//3)

[14*-割绳子]n的取值更大了，可能出现很大的数，但由于语言特性，理论上 Python 中的变量取值范围由系统内存大小决定（无限大），因此在 Python 中其实不用考虑大数越界问题。
[15-二进制后1的个数]

思路1(代码最简单):return(bin(n).count(‘1’))

思路2(手写二进制转换的同时用一个内部计数器counter计数)

思路3(位运算，这个是真的不熟悉) while n: n = n & (n-1) count += 1最后return count

[16-数值的整数次方]

这一题如果暴力递归的话复杂度是O(n)，想法是$x^{100} = {x^{50}}^{2}$这种方式去达到O(logn)的复杂度。另外定义一个递归函数，去调用它即可

def fastpow(x,n):
  if n==1: return(x)
  if n%2==0:
    return(fastpow(x,n/2)**2 )
  else:
    return(fastpow(x,n//2)**2 *x)

思考：熟悉统计里面最大化似然函数方法的话，立马会想到先取对数再取指数，复杂度降低到O(1)。虽然精度上稍微差一点，但实际问题往往是这样去处理的。没必要为了算法而算法

[17-打印1到最大的n位数]

这道题据说在考大数问题；但并没有遇到之类的报错，就当是重温列表推导式res = [i for i in range(1,10**n)]

[18-删除链表的节点]：给定链表head，删除值为val的节点。假定val一定存在且唯一

考察链表基本操作，设定一个cur指针就可以完成。注意的是边界条件删除head或者最后一个。

下面两个与正则表达式有关的题目真的太恶心了，不准备做了！

[19-正则表达式]（我选择放弃！）
请实现一个函数用来匹配包含'. '和`’‘的正则表达式。模式中的字符‘.’表示任意一个字符，而‘‘`表示它前面的字符可以出现任意次（含0次）。
[20-表示数值的字符串]（我也选择放弃）请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”、”5e2”、”-123”、”3.1416”、”0123”及”-1E-16”都表示数值，但”12e”、”1a3.14”、”1.2.3”、”+-5”及”12e+5.4”都不是。
[21-调整数组顺序使得奇数在偶数前面]

思路：这一题就和快排子问题一样，用快慢指针就可以了。

[22-链表中倒数k个节点]：输入一个链表，输出该链表中倒数k个节点。

思路：快慢指针，先让快的走k步，然后快慢一起走，快的走到终点的时候，慢指针就是我们需要的。

[24-反转链表]：双指针可以做

我死活想不明白为啥用栈+node无法实现，找人请教

[25合并两个有序链表，使其合并完依然有序]

思路用两个头指针去做，哪个小，新的合并哪个，当其中一个为None是，直接把剩下的并上

下面几道二叉树的题值得再做一遍，写递归一定要小心，注意条件，注意递归调用的前后，注意返回值

[26判断树的子结构]：输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构）。B是A的子结构， 即 A中有出现和B相同的结构和节点值。

这道题值得再写一遍，因为一点细节卡了很久。首先是准备工作，先回顾一下如何判断两棵树完全相同

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p==None and q==None: return(True)
        if p==None or q==None: return(False)
        if p.val != q.val: return(False)
        return(self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right))

原题逻辑：需要两个函数 (1)dfs搜索，发现A的某一节点值和Broot值相同时开始判断B是不是A的子结构 (2)判断子结构

解决方案：

  1. 因为dfs递归的返回值很绕很头晕，所以我宁愿加入一个初始值为FALSE的self.flag变量来记录存在子结构相同，最后直接去return这个值

  2. 我自己认为最恶心的地方在于子结构不是子树，最初大意忽略这一点debug好久，子结构判断方式如下，和子树有区别。主要是如何判断为TRUE

def isSub(p,q):
    if q == None: return(True)
    if p == None: return(False)
    if p.val != q.val: return(False)
    return(isSub(p.left,q.left) and isSub(p.right,q.right))
[27反转二叉树]

之前做过，递归就完事了！

[28-对称二叉树]：检查一个二叉树是否是中心轴对称的

做过一次，但还是易错：轴对称意味着left.left对称right.right和left.right对称right.left

两种差不多的思路：(1)加入self.flag，不满足条件时去更新它，最后返回flag值就可以。 (2) 递归函数最后一行return dfs(left.left,right.right) and dfs(left.right,right.left)

这种判断True FALSE的题目，我越来越喜欢使用flag了…很清晰

[29-顺时针打印矩阵]：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。（一层一层剥开）

首先运动顺序是右下左上，没有碰壁时一直运动，将当前位置打印。每次碰壁后就更换顺序，将现有顺序取出来并且放在顺序队列的最后(队列思想)。
判断碰壁：遇到边框，或者遇到以前已经打印过的值。
使用变量counter作为flag出现：没有打印但是连续四次转向说明已经打印完了。

[30-包含min函数的栈]：设计一个栈，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

思路：使用一个辅助栈，长度与原栈相同，每个位置代表原栈cut到这个长度时的最小值。

每次push时候同样需要更新辅助栈：新元素更小则append新元素，否则append辅助栈最后一个元素(意味着新加入一个元素后再cut到这一位，最小值还是之前那个)。pop时候同时pop两个栈，这样的结构就可以保证随时查询到最小值。

[31-栈的压入与弹出]输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

思路：模拟一遍操作（核心在于没有重复数字的假设）。每个元素按顺序入栈后，

while stack!= [] and stack[-1]==popped[0]:
    stack.pop()
    popped.pop(0)

之后检查stack是否为空，不为空则说明poped顺序不合法。

[32-从上到下广度优先打印二叉树]：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

广度优先搜索+queue。加入队列之前先判断是不是None

[32-从上到下分层打印二叉树]

大体和上面一样，注意每一层打印的数量其实就是上层打印完之后队列的长度，记录这个值就很方便完成。

[32-从上到下分层打印二叉树，第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，以此类推]

和上面一样，多一个flag来判断当前层的结果subres是否需要reverse

整体上来看：如果这个题一上来就是最难版本，也要意识到一层一层打印就算顺序有变化，也应该是BFS去实现。

[33-二叉搜索树的后续遍历list]：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。数组没有重复数字

强烈建议再做一遍！（递归和迭代）

第一眼要能看到的：后续遍历最后一个位置是根节点，左子树全部小于root，右子树全部大于root

思路：递归时：len(postorder)<=1说明True

从左到右判断第一个大于root的值，左边是左子树（全部小于root），右边是右子树(不一定全部大)。判断右边是不是全部大。如果不成立返回false，成立的话递归调用判断两个子树的postorder是否合格。

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

坑比题目：最初理解为所有节点可能作为起点的路径，后来才发现这道题指的路径一定是路径一定是root完整到leaf的路径，相对我的理解更简化了。但是坑在于判断一个节点是leaf的方式是他的左右子树都是None。

思路：还是dfs，但是多一个参数是记录从root到当前节点的路径，到了leaf处求和判断是否是target。

缺点：每个节点都存路径的话，可能空间复杂度比较大？之后可以考虑下能不能改进

[35-复杂链表的deepcopy] 深度复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

一定再做一遍

方法1（hash表）：辅助的字典+clone函数。clone：每次先判断旧链表当前节点是否出现过，如果出现则直接从字典中拿出，没有出现的话就新建一个；从头遍历旧链表，把next和random都指向对应的新的node。遍历完就成功了。空间复杂度O(n)

方法2：(a)旧链表每个节点后面连接 一个相同值的node形成 (b)新node的random节点全部更新（连接到新node）(c)解编织：新节点的next不再和旧节点相连，而是连接到合适的新节点。

[36-将二叉搜索树转化为排序好的双向链表]：将一个二叉搜索树就地转化为一个已排序的双向循环链表。可以将左右孩子指针作为双向循环链表的前驱和后继指针。特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

这一题把我给整懵逼了。第一步：读懂题目滤清思路 第二步：实现代码

  1. 根据二叉搜索树的特点，可以用中序遍历将其排序 （之前不熟悉这一点！），所以我们的操作主要会基于一个中序遍历的dfs递归函数。
  2. 确定中序遍历后，难点在于根节点处如何操作。我们需要一个记录前序节点的变量pre，在根节点处操作是pre.right = root, root.left = pre, pre = pre.right
  3. 上面这个步骤很坑，递归的时候会有函数嵌套这种事发生，所以希望pre是一个相对全局的变量（不是定义在局部递归函数中的），那么在函数中修改这个相对全局的变量就需要我们比较熟悉变量定义空间的知识。学习完这部分后可以发现，需要在dfs函数中声明 nonlocal pre，且pre不是dfs的参数。这样方能实现。

[37二叉树的序列化和反序列化]：序列化是将一个数据结构或者对象转换为list，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

序列化：比较简单，任意顺序的dfs递归即可。在这里我们采用前序遍历，但是需要注意的是如果左子树或者右子树为None，那么序列中一定要用#记录下来，不然没法重构。

反序列化：将list读入后利用前序的递归来生成树，遇到#时root=None，其余情况都root = TreeNode(data.pop(0))，然后左子树，右子树。

[38-字符串的全排列]

这道题本质上是全排列，所以我们用dfs即可，并且每一步都会在dfs的参数里面记录还可以搜索的范围和已经经过的路径。直到根节点再统计。
重复值可以用排序的方法来解决，排序好之后，在展开一个分支去搜索之前，若发现和前一个完全一样，则跳过。

一个比较有用的函数是str.join(list)，把list转化为以str连接的字符串

[39-数组中出现超过一半的数字]

  1. 消除法：相等加1，不等减1，等于0重新赋值，抵消掉非众数。空间+时间复杂度最优

  2. Return快排后中间位置

  3. 字典计数
[40-返回list最小的k个数]

这个题和找最大的第k个数完全对称。找最大的k可以用最小堆，因为可以把小数字优先pop。所以找最小的k就用最大堆，把大数字优先pop

  1. 快排 O(nlogn)
  2. 构建最小堆，然后取前k个：O(n+k*logn)
  3. 维护一个k个元素的最大堆：每遇到一个新元素进行比较，比最大的小就替换掉最大的进入堆，否则不变。O(nlogk)

这里总结一下heapq！！！

[41-数据流中的中位数]：要实现两个函数，添加数字和获取中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

思路1：只用一个list，新来的数字通过二分插入，保证list有序。然后获取中位数可以迅速实现

思路2：使用最大堆和最小堆，分别存放小于中位数的值和大于中位数的值。要点是每次进来一个数如果二者长度相等怎么添加，长度不等怎么添加。（都是先pushpop(A)，然后push(B)）

if len(self.maxheap) == len(self.minheap):
    heapq.heappush(self.maxheap, -heapq.heappushpop(self.minheap,num))
else:
    heapq.heappush(self.minheap, -heapq.heappushpop(self.maxheap, -num))

[42-连续子数组的最大和]输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

题目提示可以用分治法，

但是动态规划显然更加简单，我们在原地修改数组，将数组每个位置的值更改为当前位置上的最大和。

nums[i] = max(nums[i-1],0)+nums[i]

[43- 1～n整数中1出现的次数] 给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。这个题真的有点恶心，很难自己想到做法

# #想法一：每个数转化为字符串然后.count('1')，发现超时，所以应该是找规律
# class Solution:
#     def countDigitOne(self, n: int) -> int:
#         count = 0
#         for i in range(1,n+1):
#             count = count+ str(i).count('1')
#         return (count)

#想法2：把数字写成最高位和最低位，然后递归
class Solution:
    def countDigitOne(self, n: int) -> int:
        if n<1:return 0
        if n<10:return 1
        last = int(str(n)[1:])
        power = 10**(len(str(n))-1)
        first = int(str(n)[0])

        if first ==1: 
            return(last+1 + self.countDigitOne(power-1)+ self.countDigitOne(last))
        if first >1: 
            return(power + first*self.countDigitOne(power-1)+ self.countDigitOne(last) )

我们可以将一个数字拆分为最高位和其右边 ，比如3452，拆成3000和 452， 最高位high=3, last=452, 数的范围是几千的数字，那么power=1000

先看最高位贡献了多少个1， 如果最高位大于1， 那么最高位贡献1000个1，1000~1999

那么剩余位贡献多少个1呢，只要看0-999的个、十、百位贡献了多少个1， 那么 1000~1999，2000~2999， 的个、十、百位贡献的1的个数都是一样的 即high * countDigitOne(power-1)个1

最后还剩下3000~3452 这last+1个数字的个、十、百位贡献的1的数量，即countDigitOne(last)

全部加起来即可

如果最高位等于1，那么最高位贡献last+1个1，只要看剩余位贡献多少个1：countDigOne(last) + countDitOne(power-1)

[44- 数字序列中的某一位数字] 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。

思路比较清晰，就是实现时候需要debug，因为数字可能多一个或者少一个。

  1. 一位数1+9*1个位置，两位数2*90个位置，三位数3*900个位置，以此类推找到我们目标数字是几位数。
  2. 减去前面位数用掉的位置，判断目标数字应该在哪个数当中target = 10**(i-1)+ (n-(num-9*(10**(i-1))*(i)))//(i)
  3. 然后判断在这个数的第几位res = int(str(target)[(n-(num-9*(10**(i-1))*(i)))%i])

[45-把数组排成最小的数]：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个

这道题非常不错，这其实是排序的变种，由简单的比较a<b变成去比较ab<ba 数字之间连接，使用快排可以O(nlogn)时间复杂度和O(logn)的空间复杂度

技巧：字符串可以直接比较大小，比如’123’<’231’

技巧2：sorted函数key参数可以传入一个class，用于比较，如下，这种写法很给力（如果不这么写要么手动实现快排，要么手动实现更好写的冒泡排序）

class cmp(str):
    def __lt__(x, y):
        return(x+y<y+x)
class Solution:
    def minNumber(self, nums: List[int]) -> str:
        nums = sorted([str(_) for _ in nums], key = cmp)
        return(''.join(nums))

[46-把数字翻译成字符串]给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。(比如12258可以按照不同切分方式分成5种字符串)

思路1(自己想到的)：这个题有点像寻找全部子集，只不过要按照顺序而且下一个有可能是1位或者两位，所以直接用dfs去搜索，每次到根节点的时候在计数。(被坑的点：判断两位时不能只判断<'25'一定还要>'10'不然06这种不能算一个字符)

思路2(动态规划)：有点像爬楼梯，一次一个或者两个(爬两个需要条件满足！)

#初始条件
dp[0]=1
dp[1] = 2 if ('10' <= num[:] < "26") else 1
#迭代条件
if num[i-1:]>='10' and num[i-1:]<'26': dp[i] = dp[i-1]+dp[i-2]
else: dp[i] = dp[i-1]

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

思路1：dfs，两个方向等价于二叉树，直接搜，到右下角时统计值。然后找最大值。矩阵一大就超时

思路2：很标准的动态规划，初始化第一列和第一行后，dp[i][j] = max(dp[i-1][j],dp[i][j-1])+grid[i][j]，通过

[48-最长的不包含重复字符的子串]请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

这道题之前做过，但是第一时间还是没能想起思路

思路：使用双指针构造移动窗口，j先移动且一直在i的右边，i负责缩减窗口，j负责extend。比如例题中的 abcabcbb，先从右端开始extend窗口， 发现 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。那么从左端缩减，直到不重复。保持上述过程直到j到最后一个位置。注意：每次有满足要求的窗口时，maxlen = max(maxlen,j-i+1)

remark：不能无脑移动j，起码要保证当前i到j位置没有重复才可以移动j，不然滑动窗口没有意义。

Remark：判断s[j]是否出现时如果直接用in会导致总体复杂度变成O(n^2)，所以在过程进行中使用hash表来将in查询变成O(1)，注意dict删除元素的操作是dict.pop(key)

[49-第n个丑数]：我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

最初我想到了每次拓展三个，但是发现顺序不合适。所以进一步就是使用三个指针，每次比较2 3 *5的数哪个更小就append哪个。

小技巧：本想使用dict来判断之前是否有出现重复元素，后来发现使用if语句恰好可以避免判断，无论添加的是哪一个，但凡是其余的倍数，指针也变化。

if temp ==res[i]*2: i = i+1
if temp ==res[j]*3: j = j+1
if temp ==res[k]*5: k = k+1
[50-第一个只出现一次的字符]

Easy: 遍历生成字典统计次数，然后遍历字典找值为1的第一个数

但是这道题很有启发：按顺序生成字典，字典key的顺序也是按照顺序的，并不会按照名称排序

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

这道题很有启发，其实可以通过归并排序来完成。

先分成小组计算逆序对，然后合并小组的时候再计算组间的（归并过程中完成计数）。注意比较容易错的一点是归并排序判断条件是< 或者<=都可以，但是这道题在left[i]>right[i]的时候计算，所以要求归并排序判断条件不能随意二选一，而是严格小于大于。

归并本质就是2分，在左右数组合并的时候，检测左严格大于右的次数，即可以组成有序对的个数。左大于右时，左剩下的元素也一定大于右，所以计数是len(left)-i

[52-两个链表的公共节点]：输入两个链表，找出它们的第一个公共节点

这道题之前做过，思路很清晰但是在写code的时候还是遇上了一些bug所以记录一下

思路1：hash表，先遍历第一个链表，把所有node加入字典，然后遍历第二个，查找是否有相同的node。空间复杂度O(n)

思路2：A末尾连接B，B末尾连接A之后二者等长，可以同时用两个指针来遍历，如果到了末尾还是没有相同的则返回None，有相同的则直接返回。

需要仔细想一下的：如果二者等长，那么有公共的会提前发现，所以连接二者也是可行的。如果不等长一定要遍历经过None节点，不然没办法判断什么时候该停止（二者同时达到None停止，只有一个达到None就去末尾连接新链表）

[53-在排序数组中查询X出现了几次]

思路1（不要再去看这种思路，二分法踏踏实实用while循环去写，方便确定具体的index）：因为是排序数组，所以二分查找更合适，只要用一个self.count计数即可。难点在于手写二分查找不报错（递归），之后再写一下。 这种写法的好处在于完美符合我们题目原意。但当需要求X出现的左右坐标时就不适用。

def search(self, nums: List[int], target: int) -> int:
    #递归的停止条件
    if len(nums) == 0: return 0
    #binary search
    mid = len(nums)//2
    if nums[mid]==target:
        self.count = self.count+1
        self.search(nums[:mid],target)
        self.search(nums[mid+1:],target)
    if nums[mid]<target:
        self.search(nums[mid+1:],target)
    if nums[mid]>target:
        self.search(nums[:mid],target)
    return(self.count)

思路2（启发非常大，以后二分法全部按照这样去写）：和leetcode34题一样，求左右坐标。

基础铺垫：强烈安利一种超简洁，bug free的写法。即使不存在，区间为空，搜索上下界均可实现，诀窍是左闭右开。广义的二分查找分两种：第一个>= target的位置（lower bound），和第一个>target的位置（upper bound），所有都可以基于这两种，所以不需要考虑小于的情况。

# 因为是左开右闭区间，所以右端点直接设置为len(nums)！
# mid = left +(right-left)//2的好处在于即使区间长度为1时，mid=left也可以落在[left,left+1)这个区间中，这是 (left+right)//2远不能及的，所以一定用mid = left +(right-left)//2
# lower和upper的区别: 收缩左右端点时的判断条件 是<还是<=，<的话left=mid+1会对应 >= (看一看代码很好理解)
# while条件是while left < right: 这说明停止时返回right和left都一样
				def lower_bound(nums,target):
            left,right = 0, len(nums)
            while left < right: #等于时候停止
                mid = left +(right-left)//2
                if nums[mid] < target: left = mid+1
                else: right = mid
            return left
          
				def upper_bound(nums,target):
            left,right = 0, len(nums)
            while left < right: #等于时候停止
                mid = left +(right-left)//2
                if nums[mid]<= target: left = mid+1
                else: right = mid
            return left

利用上述办法找到lower和upper后，就可以确定X重复出现的位置。

trick：先使用lower bound，寻找第一个>=target的数的index。所以如果lower == len(nums) or nums[left]!= target那就分别说明没有找到，只有大于号成立。

所以最普通的查找情况可以通过lowerbound然后判断等号是否成立来实现。

[53*- 0~n-1中缺失的数字]：比如给定[0,1,2,3,4,5,6,7,9]这样的数组，发现8缺失

有了上面的铺垫其实很好完成了，特点是如果不乱序应当nums[i]=i

判断条件其实就是if nums[mid]==mid: left = mid+1 else: right = mid，每次把区间锁定在乱序的一侧，然后不断缩减到一个位置。（与上面代码非常相似，一通全通）

class Solution(object):
    def missingNumber(self, nums):
        left, right = 0, len(nums)
        while left < right:
            mid = left+(right-left)//2
            if nums[mid]==mid: left = mid+1
            else: right = mid
        return(left)
[54-二叉搜索树的第K大节点]

根据二叉搜索树性质可以知道，中序遍历可以从小到大排列好，所以第一个想法就是递归中序遍历，然后返回[-k]元素。考虑到K可能比较小，所以可以反中序遍历。（我感觉如果写递归的话，总会是O(n)时间复杂度，正反区别不大）

另外手动使用stack写了下，可以在第K个停止，感觉对中序遍历理解更深入了。（这样复杂度为O(K)），但面试时候肯定写递归，不容易错！

[55-二叉树的最大深度]

（这种dfs以后只在求全集或者集合的题目中去用，二叉树的常规题目还是不用）思路：dfs的同时记录当前深度，到达叶子节点时 self.depth = max(self.depth,level)，全部搜索完返回self.depth。（这种写法我比较习惯了，但是对于递归锻炼不大，下面的写法是标准递归）

思路2：递归height = max(leftheight,rightheight)+1（我认为树递归的核心就在于把当前节点问题写成左右子节点属性的函数） 时间复杂度应该是O(n)

#方便与下面的题目比较
    def maxDepth(self, root: TreeNode) -> int:
        if root == None: return(0)
        left = self.maxDepth(root.left)
        right =self.maxDepth(root.right)
        height = max(left,right)+1
        return(height)

[55*-判断是否是平衡二叉树]：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

做过上一题后，最基础的想法就是直接去判断root是否平衡，如果判断为True就再看子树是否平衡。（可以注意到，子树会重复计算，所以可以改进！）

if abs(maxDepth(root.left)-maxDepth(root.right))>1: return False
else: return (self.isBalanced(root.left) and self.isBalanced(root.right))

想法：求树高的同时判断其左右是否平衡，如果不平衡则返回-1，最后就可以根据根节点处树高是正数还是-1来判断之前计算的子树中是否出现不平衡的情况(这道题可以再写一下)

def treeDepth(root: TreeNode) -> int:
    if root == None: return(0)
    left = treeDepth(root.left)
    right= treeDepth(root.right)
    #区别在这里
    if left >= 0 and right >= 0 and abs(left - right) <= 1:return(max(left,right)+1)
    else: return(-1) #-1代表不平衡

下面是3道位运算的题目（模板是数组中除了target其余数字出现多少次，找target）

异或的性质：两个数字异或的结果a^b是将 a 和 b 的二进制每一位进行运算，得出的数字。 运算的逻辑是
如果同一位的数字相同则为 0，不同则为 1

异或的规律：任何数和本身异或则为0，任何数和 0 异或是本身

[56*-在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了2次。请找出那个只出现一次的数字。]

思路1(数学法)：return (sum(set(nums))*2-sum(nums))第一项是所有数求和乘2，第二项是nums求和（除了target出现一次，其余出现2次）。所以相减就可以得到我们的目标。

思路2（位运算）：所有元素异或运算，由于交换律和任何数和 0 异或是本身，最后直接可以得到结果

[56*-在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。]

思路1（数学法）：return (sum(set(nums))*3-sum(nums))/2第一项是所有数求和乘3，第二项是nums求和（除了target出现一次，其余出现3次）。所以除以2就可以得到我们的目标。之所以//是因为直接除法会出现小数点。

思路2(位运算)：从题目已知最大32位，那我们的思路就是从000...000一位一位的恢复出来这个数。每一位判断有几个1，然后如果cnt % 3 != 0就说明这个bit上我们寻找的target也是1,res = res|bit(按位或操作)。判断完32个位置之后得到结果

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for i in range(32):
            cnt = 0
            idx = 1<<i
            for num in nums:
                if num &idx != 0:
                    cnt = cnt+1
            if cnt%3==1:
                res = res|idx
        return(res)

[56-数组中除了两个元素只出现一次，剩下所有元素出现了两次，找到这两个元素]

我们进行一次全员异或操作，得到的结果就是那两个只出现一次的不同的数字的异或结果。

我们刚才讲了异或的规律中有一个任何数和本身异或则为0， 因此我们的思路是能不能将这两个不同的数字分成两组 A 和 B。分组需要满足两个条件. (1)两个只出现一次的数字分成不同组 (2)相同的数字分成相同组。这样每一组的数据进行异或即可得到那两个数字。

问题的关键点是我们怎么进行分组呢：由于异或的性质是，同一位相同则为 0，不同则为 1. 我们将所有数字异或的结果一定不是 0，也就是说至少有一位是 1. 我们从右向左找到第一个1出现的位置idx = 1; while idx & res == 0: idx = idx << 1，分组的依据就来了，遍历nums，你取的那一位是 0 分成 1 组，那一位是 1 的分成一组。这样肯定能保证 相同的数字分成相同组, 不同的那两个数字也会被分成不同组。

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        res = 0
        for i in nums:
            res = res^i

        idx = 1
        while idx & res == 0:
            idx = idx << 1
    
        a,b = 0,0
        for i in nums:
            if i & idx==0:
                a = a^i
            else:
                b = b^i
        return([a,b])

总结：只有一个target时，数学方法很直观。如果有两个target那么就需要最后一种做法

[57-排序数组中和为s的两个数]输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

思路1：按照两数之和去做，找个hash表，注意一定要判断dict中没有想找的元素后才加入现在的元素，不然可能会出现寻找48，然后重复选取24.

思路2：由于数据是排序的，所以用双指针指向两段，判断大小，缩小区间。（但我没理解这种贪心算法为什么一定可行，比如说太大时候为什么不能缩减左边，而是缩减右边，值得继续思考下）

if nums[i]+nums[j]==target: return(nums[i], nums[j])
if nums[i]+nums[j]>target:j=j-1
else: i=i+1

[57*-和为s的连续正数数组]：输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

用滑动窗口去做，记录符合要求的区间直到j达到末尾。（这道题还可以拓展为递增数列中和为s的连续子列）

[58-反转单词顺序]：例如输入字符串 “a good example”，则输出”example good a”。

思路：去除两端空格，中间按空格split开然后reverse这个list，最后再' '.join(s)

学到的：1. s.strip()如果不指定参数则会把两边的空格，换行符等都删除

  1. s.split()如果不指定参数那么默认为所有的空格，换行等。所以不指定参数的时候可以一次删除句内多个连续空格，然后返回list

[59-滑动窗口最大值]给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

这道题做过但是依然想不起来方法2，建议以后再写一遍。

思路一：暴力解，移动窗口，每次求sum。复杂度为O(nk)

思路二：使用一个双向队列q来记录大小信息，q[0]代表当前window最大值的index。每次window往后移动一位则需要维护队列，使得其从左向右是递减的。（使用deque来替换list可以提高效率，因为需要从两端操作）

  1. 查看q[0]这个坐标是否在当前窗口内，否则移出while q and q[0]<=j-k: q.popleft()。
  2. 当前元素如果比q末尾代表的元素要大，就移出末尾元素while q and nums[j]>nums[q[-1]]: q.pop()。
  3. 然后将当前元素index append到q的末尾。
  4. 每次进行队列维护之后输出nums[q[0]]作为当前window最大值。

启发：from collections import deque

复杂度是O(n)

[59*-队列的最大值]：请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

要做到入队和出队都是O(1)则不能使用list，得使用双端队列deque。这道题想法就是要使用一个辅助队列来保存当前最大值，且维护辅助队列是递减的。每次新增一个元素后，辅助队列末端比它小的全部pop，然后append新元素。弹出时如果弹出元素和helper[0]相等那么helper[0]也需要弹出。

学到的：from collections import deque deque存在以下操作，pop(), popleft(), append(), appendleft()

判断deque为空不能是if deque ==[]而应该是if not deque

[60-n个骰子的点数]：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

首先，我们需要意识到，n个骰子的点数之和的情况只能$\in [n, 6*n]$，而排列组合的形式有$6^n$种类。记dp[n][j]为n个骰子点数和为j的排列组合形式的个数，那么一定是dp[j][i] = dp[j-1][i-1]+...+dp[j-1][i-6]（可能到中间某一项就截断了，若i-k<0），根据这个我们就可以动态规划。最后返回的概率只要除以$6^n$即可

细节：第N行前N-1个元素为0，动态规划要注意截断到i-k>=0

[61-五张扑克牌是否为顺子]从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

想法：先排序，按顺序遍历。当前为0时king = king+1，当前与后一个相等时，return False，其余情况利用间隔来判断需要用几个king去补king = king-(nums[i+1]-nums[i]-1)，最后判断king的正负来返回。

[62-圆圈中最后剩下的数字（约瑟夫环）]：0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

数学题，难点在于找到递推关系。

首先，记f(n)为游戏结束后最后一个数字的index，那么关键在于找到f(n,start=0)和f(n-1,start=0)的关系。显然，第一次扔出去的元素是(m-1)%n，记作k，那么根据游戏规则f(n,start=0)=f(n-1,start = k+1)。接下来我们可以看到f(n-1,start = k+1) = (f(n-1,start=0)+k+1)%n。有了这个中间桥梁，可知f(n,start=0) = (f(n-1,start=0)+k+1)%n = (f(n-1,start=0)+m)%n。然后从f(1)=0推广过去即可。

这类问题凭空很难找到规律，建议记住f(n) = (f(n-1)+m)%n的大概形式，再去推导会比较有方向。数学归纳法都是扯淡，都是有了公式强行去归纳，要是不知道递推公式怎么能从n=1,n=2,n=3找到取模规律，反正我不行🐶！

[63-买卖股票最佳时机] 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。

这题之前做过，但第一时间没能想出来，太菜了

动态规划：遍历一遍数组，每遇到一个值就更新：截止目前最大的profit和截至目前的最小价格

  1. 前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}
  2. if prices[i]<low： low = prices[i]

[64-求 1+2+...+n ]：要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）

想法：使用递归代替循环，使用and短路特性来实现判断。对道题对于and理解更深入了

def sumNums(self, n: int) -> int:
    return(n and n + self.sumNums(n-1))

0 and 3：返回0；10 and 3 返回3，就是说左边为0返回0，左边不为0就返回右边。迭代到0停止

[65]使用二进制及位运算代替加法（强行背下来吧）

a+b，等价于(a^b)+((a&b)<<1)，其中加法需要结合&预算递归一次次完整处理掉。

知识点：a^b，异或运算等价于不带进位的加法！ (a&b<<1)：等价于每一位的进位数，直观就能理解

#这道题的核心在于下面的位运算，b记录进位数，a记录不进位数，直到b为0时返回a的值（不再进位），难点在于python中不会溢出，所以需要最初 a &= 0xffffffff, b &= 0xffffffff。最终返回值return a if a < 0x80000000 else ~(a^0xffffffff)
				while b != 0:
            carry = ((a & b) << 1) & 0xffffffff
            a ^= b
            b = carry

[66-构建乘积数组]给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

思路：通过观察B[i]可以发现可以分为两个部分的乘积，那我们将这两部分叫做C[i]，D[i]，而且这两个数组都可以动态规划写出来。最后 for i in range(len(a)): res.append(C[i]*D[i]) 即可。

边界条件容易出bug：建议写A = [2,3,4,5]来手推一下每一项到底是什么。D[i] = D[i+1] * a[i+1] C[i] = C[i-1] * a[i-1]

[67-把字符串转化为整数]：解决开头是空值，开头是字母，结尾是字母等一些列乱七八糟的bug

思路：将问题一个一个解决，期间用到了str.strip，也用到了try:except语句总之是个肯写就一定能写出来的题目，各种奇葩测试用例挨个修复就可以了

[68-二叉搜索树的最近公共祖先]：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。（可以是自身）

思路：二叉树的公共祖先，满足 小的<=祖先<=大的，同时小于两个搜索右子树，同时大于搜索左子树

[68*-二叉树的公共节点]：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。（可以是自身）

思路：dfs，但是相对较难。dfs(root)实现功能：查找在root为根的二叉树中找给定节点p和q的最近公共祖先。

第一步，写清楚递归结束条件 

if root == None: return None
if root.val == p.val or root.val == q.val: return root

第二步，在左子树找，在右子树找

先在找root的左子树的最近公共祖先得到返回值left， 再从右子树中查找最近公共祖先得到返回值right。
若left为NULL，因为题目保证有解，所以答案必在右边
若left不为NULL，则看right是否为NULL，若right为NULL， 则答案一定是左边这个left。
若左右都不为NULL， 说明root在中间，p和q在两边。该根结点一定是最近公共祖先。

left = dfs(root.left)
right = dfs(root.right)
#递归结束条件
if left and right: return(root)
if right== None:return(left)
if left == None:return(right)