每个题目标题链接到 github，可以查看其他的解题思路、测试用例以及拓展题目
这里只贴上书中题目的最优解法和代码
另外，这里参考的是《剑指offer》第一版的题目顺序
补充部分添加的是《剑指offer》第二版多出来的几道题目
二维数组中的查找
题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
最优题解
时间（O（m + n）），空间（O（1））
从右上角或左下角开始查找，这里选择右上角
如果当前元素大于 target，剔除 target 所在列（col 左移 - 1）
如果当前元素小于 target，剔除 target 所在行（row 下移 + 1）
否则等于，结束查找
每一次查找都在数组的查找范围中剔除一行或一列，每一步都缩小了查找的范围
直到找到要查找的数字，或者查找范围为空
代码
class Solution:
def Find(self, target, array):
if array is None: return False
i , j = 0, len(array[0]) - 1
while i < len(array) and j >= 0:
if array[i][j] > target:
j -= 1
elif array[i][j] < target:
i += 1
else:
return True
return False
拓展题目
替换空格
题目描述
请实现一个函数，将一个字符串中的空格替换成 “%20”。
例如，当字符串为 “We Are Happy”，则经过替换之后的字符串为 “We%20Are%20Happy”。
最优题解
使用内置方法 replace() 最佳，这里给出书上的解法：
原地替换，需要移动替换位置之后的字符，若从左到右扫描，一边移动一边替换，时间复杂度为 O（n^2）
可以考虑从右到左扫描，使用两个索引
一个指向源字符串的末尾 oldIdx，另一个指向替换后字符串的末尾 newIdx
没碰到空格时直接复制，碰到空格时 newIdx 左移 3 格写入 ‘20%’，oldIdx 左移一格
（每替换一个空格，长度增加 2，因此替换后字符串的长度 = 原来长度 + 2 * 空格数目）
直到 newIdx 越过 oldIdx 来到 oldIdx 的左边则扫描结束
注：如果是 c / c++ 可以实现原地替换，但 python 中的 str 为不可变对象，只能返回新的字符串
所以这里的原地替换只是模拟书中的方法，实际上还是返回一个新的字符串
代码
class Solution:
def replaceSpace(self, s):
if s is None: return ''
spaceCount = sum(ch == ' ' for ch in s)
newIdx = len(s) + spaceCount * 2 - 1
oldIdx = len(s) - 1
newStr = list(s) + [''] * (spaceCount * 2)
while 0 <= oldIdx < newIdx:
if newStr[oldIdx] == ' ':
newStr[newIdx - 2: newIdx + 1] = '%20'
newIdx -= 3
else:
newStr[newIdx] = newStr[oldIdx]
newIdx -= 1
oldIdx -= 1
return ''.join(newStr)
从尾到头打印链表
题目描述
输入一个链表，从尾到头打印链表每个节点的值（不能改变原链表结构）
最优题解
时间（O（n）），空间（O（n））
可以自己用 list 模拟栈，也可以使用递归借助系统栈，这里使用递归实现
代码
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
# 返回从尾部到头部的列表值序列
def ListReverse(self, listNode):
def recursive(node):
if node:
recursive(node.next)
res.append(node.val)
res = []
recursive(listNode)
return res
重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
最优题解
前序的第一个元素是根结点的值，在中序中找到该值
中序中该值的左边的元素是根结点的左子树，右边是右子树，然后递归的处理左边和右边
代码
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
def build(preL, preR, tinL, tinR):
if preL > preR or tinL > tinR: return
idx = tin.index(pre[preL])
node = TreeNode(pre[preL])
node.left = build(preL + 1, idx + preL - tinL, tinL, idx - 1)
node.right = build(idx + preL - tinL + 1, preR, idx + 1, tinR)
return node
return build(0, len(pre) - 1, 0, len(tin) - 1)
举一反三
用两个栈实现队列
题目描述
用两个栈来实现一个队列，完成队列的入队和出队操作
最优题解
stack1 用来入队，stack2 用来出队
出队时若 stack2 有数据直接弹出，无数据就要把 stack1 中的全部弹出并压入 stack2，然后 stack2 继续出队
入队时不管 stack1 有没有数据，直接压入
代码
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def In(self, x): # 入队时不管stack1有没有数据，直接压入
self.stack1.append(x)
def Out(self):
if not self.stack1 and not self.stack2:
return
if not self.stack2: # stack2无数据就要把stack1中的全部弹出并压入stack2
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop() # stack2继续出队
举一反三
旋转数组的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转
输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素
例如数组 [3, 4, 5, 1, 2] 为 [1, 2, 3, 4, 5] 的一个旋转，该数组的最小值为 1
最优题解
部分排序，则可用二分查找，注意在等于的时候让 high - 1，顺序查找，退化成 O(n)
（注意到 [1, 0, 1, 1, 1] 和 [1, 1, 1, 0, 1] 的区别，此时无法判断最小值在哪边，故只能用顺序查找）：
array[mid] > array[high]
出现这种情况的 array 类似 [3, 4, 5, 6, 0, 1, 2]
此时最小数字一定在 mid 的右边
low = mid + 1
array[mid] == array[high]
出现这种情况的 array 类似 [1, 0, 1, 1, 1] 或者[1, 1, 1, 0, 1]
此时最小数字不好判断在 mid 左边还是右边,这时只好一个一个试
high = high - 1
array[mid] < array[high]
出现这种情况的 array 类似[2, 2, 3, 4, 5, 6, 6]
此时最小数字一定就是 array[mid] 或者在 mid 的左边，因为右边必然都是递增的
若 mid = 0 ,说明 low 与 high 之间未发生旋转，最小数字就是 array[mid]
或者 array[mid - 1] > array[mid]，则最小数字也是 array[mid]
否则 mid 不为零且 array[mid - 1] <= array[mid]，最小数字在 mid 的左边，high = mid - 1
代码
class Solution:
def minNumber(self, rotateArray):
if not rotateArray: return 0
l, r = 0, len(rotateArray) - 1
while l <= r:
m = l + ((r - l) >> 1)
if rotateArray[m] > rotateArray[-1]:
l = m + 1
elif rotateArray[m] < rotateArray[-1]:
if m == 0 or rotateArray[m - 1] > rotateArray[m]:
return rotateArray[m]
else:
r = m - 1
else:
r -= 1
斐波那契数列
题目描述
输入一个整数 n，输出斐波那契数列的第 n 项 f(n)（n 从 0 开始，f(0) = 0，f(1 )= 1）
最优题解
a, b = b, a + b
代码
class Solution:
def Fibonacci(self, n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
举一反三
二进制中1的个数
题目描述
输入一个整数，输出该数二进制表示中 1 的个数。其中负数用补码表示。
最优题解
利用一个位运算技巧：一个整数减 1 后总是把它二进制表示的最右边的 1 变为 0
这里有两种情况：最右边的 1 在最末位和不在最末位
但无论怎样，减一后的数与原数相与就一定可以把最右的 1 变为 0
有一点要注意：由于 c / c++ / java 中 int 位数限定 32 位
所以 n 最后一定被全部变为 0，循环退出
但 python 就有区别了，python 的整数位数不止 32 位
所以在负数情况下 1 的位数会多出很多，所以应先 &0xffffffff，保留后面 32 位，前面全部变成 0
代码
class Solution:
def NumberOf1(self, n):
n &= 0xffffffff
count = 0
while n:
n &= n - 1
count += 1
return count
举一反三
数值的整数次方
题目描述
给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent。求 base 的 exponent 次方
最优题解
注意点：
base = 0 且 exponent < 0 时发生除零错误；
exponent < 0 时要作倒数；
0 ^ 0 = 1
判断 base 是否等于 0 时不能直接 == ，因为 base 为浮点数，有误差
如果两个小数的差的绝对值很小，比如小于 0.0000001，就可以认为它们相等；
乘方可以考虑用快速幂（递归实现）
代码
class Solution:
def Power(self, base, exponent):
def is_equal(num1, num2):
return abs(num1 - num2) < 0.0000001
def PowerWithUnsignedExponent(base, exponent):
if exponent == 0:
return 1
if exponent == 1:
return base
result = PowerWithUnsignedExponent(base, exponent >> 1) # 除2用位运算
result *= result
if exponent & 1 == 1: # 判奇偶模2用位运算
result *= base
return result
if is_equal(base, 0.0) and exponent < 0:
return
result = PowerWithUnsignedExponent(base, abs(exponent))
if exponent < 0:
return 1.0 / result
return result
打印1到最大的n位数
题目描述
输入数字 n, 按顺序打印从 1 最大的 n 位十进制数，比如输入 3, 则打印出 1、2、3、到最大的 3 位数即 999
（这里不打印，而是返回一个 list）
最优题解
由于没有位数限制，所以要考虑大数问题，用字符串或数组表示大数
需要注意的问题是字符串或者数组的最高位对于数字上的最低位
在字符串表达的数字上模拟加法，然后将字符串表达的数值打印出来
代码
class Solution:
def Print1ToMaxOfNDigits(self, n):
def RmStartZero(number): # 去掉前面多余的0
if int(''.join(number)) == 0: # 全0直接返回
return number
num = number[:] # 拷贝，因为pop操作会修改number的长度
while not int(num[0]):
num.pop(0)
return num
def Increment(number):
isOverflow = False
nTakeOver = 0
nLength = len(number)
for i in range(nLength - 1, -1, -1):
nSum = int(number[i]) + nTakeOver
if i == nLength - 1:
nSum += 1
if nSum >= 10:
if i == 0:
isOverflow = True
else:
nSum -= 10
nTakeOver = 1
number[i] = str(nSum)
else:
number[i] = str(nSum)
break
return isOverflow
if n <= 0: return
res = []
number = ['0'] * n
while not Increment(number):
res.append(''.join(RmStartZero(number)))
return res
在O(1)时间删除链表节点
题目描述
给定单向链表的头指针和一个结点指针,定义一个函数在 O(1) 时间删除该结点
最优题解
不必顺序查找到结点 i 的前一个节点再删除，这样是 O(n)
要删除结点 i，可以先把 i 的下一个结点 j 的内容复制到 i，然后把 i 的指针指向 j 的下一个结点
最后再删除结点 j，其效果刚好是把结点 i 给删除了
即：当我们想删除一个结点时，并不一定要删除这个结点本身
可以先把下一个结点的内容复制出来覆盖被删除结点的内容，然后把下一个结点删除
考虑两种特殊情况：
1. 如果要删除的是尾结点，它没有下一个结点，此时只能从头开始顺序遍历得到该节点的前序结点，并完成删除
2. 如果链表中只有一个结点，即要删除的节点是头结点（它连前序结点都没有），需要单独处理（删除后设为 NULL）
代码
class ListNode:
def __init__(self, x=None):
self.val = x
self.next = None
def delete(self):
self.val = None
self.next = None
class Solution:
def DeleteNode(self, ListHead, ToBeDeleted):
# 返回删除后链表的头结点
if not ListHead or not ToBeDeleted: return # 头结点和要删除结点都为空返回None
if ToBeDeleted.next is not None: # 要删除的结点不是尾结点
Next = ToBeDeleted.next
ToBeDeleted.val = Next.val
ToBeDeleted.next = Next.next
Next.delete()
elif ListHead == ToBeDeleted: # 要删除的结点是头结点
ListHead.delete()
else: # 要删除的结点是尾结点
Node = ListHead
while Node.next is not ToBeDeleted:
Node = Node.next
Node.next = None
ToBeDeleted.delete()
return ListHead
使奇数位于偶数前面
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序
使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分
并保证奇数和奇数，偶数和偶数之间的相对位置不变。
最优题解
时间（O（n）），空间（O（n））
首先统计奇数的个数 i，然后新建一个等长数组，遍历原数组
设置两个指针， 奇数从 0 开始复制，偶数从 i 开始（奇数末尾）
稳定排序，时间复杂度降下来了，但空间复杂度提高了
代码
class Solution:
def reOrderArray(self, array):
odd = 0 # 奇数开始位置
even = sum(i & 1 for i in array) # 统计奇数个数，为偶数开始位置
res = [0] * len(array)
for i in array:
if i & 1:
res[odd] = i
odd += 1
else:
res[even] = i
even += 1
return res
链表倒数第 k 个结点
题目描述
输入一个单向链表，输出该链表中倒数第 k 个结点。
最优题解
双指针问题
定义两个指针，第一个先从头开始走 k 步，第二个保持不动；从第 k 步开始，第二个指针也开始从头遍历
由于两个指针的距离保持在 k，所以当第一个指针遍历完整个链表时，第二个指针正好来到倒数第 k 个结点
代码
class Solution:
def FindKthToTail(self, head, k):
if not head: return
l = r = head
while k and r:
r = r.next
k -= 1
if k != 0 and r is None: return # k 大于链表长度
while r:
l, r = l.next, r.next
return l
举一反三
反转链表
题目描述
输入一个链表的头结点，反转该链表并输出反转后链表的头结点
最优题解
定义三个指针，分别指向当前遍历到的结点、它的前一个结点以及后一个结点
指向后一个结点的指针是为了防止链表断裂，因为需要把当前结点的下一个指针指向前一个结点
代码
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
pre, cur = None, pHead
while cur:
cur.next, cur, pre = pre, cur.next, cur
# 上面的一行相当于下面四行
# next = cur.next # 先保存下一个结点防止断裂
# cur.next = pre
# pre = cur
# cur = next
return pre
合并两个排序的链表
题目描述
合并两个单调递增的链表，使得合并后的链表仍然单调递增
最优题解
使用一个尾指针，每次比较把较小的结点连接到尾结点后面，记得最后将剩余的链表链接到尾结点后面
代码
class Solution:
# 返回合并后的链表头结点
def Merge(self, pHead1, pHead2):
dummy = tail = ListNode(0)
while pHead1 and pHead2:
if pHead1.val <= pHead2.val:
tail.next = pHead1
pHead1 = pHead1.next
else:
tail.next = pHead2
pHead2 = pHead2.next
tail = tail.next
tail.next = pHead1 or pHead2 # 记得将剩余的链表链接到尾结点后面
return dummy.next # 伪结点的下一个结点才是真正的头结点
树的子结构
题目描述
输入两棵二叉树 A，B，判断 B 是不是 A 的子结构（空树不是任意一个树的子结构）
最优题解
先递归遍历（先序遍历）树A，找到相同的根结点子树
再用递归分别判断该子树的左右子树是否与 B 一样，递归结束的条件是来到 B 的叶结点
代码
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# pRoot1是A的根节点，pRoot2是B的根节点
def HasSubtree(self, pRoot1, pRoot2):
def check(root1, root2):
# 用于递归判断树的每个节点是否相同
# 需要注意的地方是: 前两个if语句不可以颠倒顺序
# 如果颠倒顺序, 会先判断root1是否为None,
# 其实这个时候root2的结点已经遍历完并确定相等了,但是返回了False
if root2 is None: return True
if root1 is None: return False
if root1.val != root2.val: return False
return check(root1.left, root2.left) and check(root1.right, root2.right)
if not pRoot1 or not pRoot2: return False
if check(pRoot1, pRoot2): return True
return self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)
二叉树的镜像
题目描述
将给定的二叉树变换为原二叉树的镜像。
最优题解
递归实现，前序遍历二叉树的每个结点
如果遍历到的结点有子结点，就交换它的两个子结点
当交换完所有的非叶子结点的左右子结点之后，就得到了树的镜像
代码
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回镜像树的根节点
def Mirror(self, root):
if root is None: return
root.left, root.right = root.right, root.left
self.Mirror(root.left)
self.Mirror(root.right)
return root
顺时针打印矩阵
题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字
例如，如果输入如下矩阵：
[[ 1, 2, 3, 4],
[ 5, 6, 7, 8],
[ 9, 10, 11, 12],
[13, 14, 15, 16]]
则依次打印出数字 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10.
最优题解
时间 O（n * m）, 空间 O（1）
一个圈其实只要左上角（startR, startC）和右下角（endR, endC）确定了整个圈也就确定了，
因此外层循环控制左上角和右下角的变化，内层循环根据这两个坐标分情况绕圈打印就可以了
外层循环如何控制两个坐标？只需每次让 （startR++, startC++）和 （endR–, endC–）
什么时候退出？当右下角来到左上角的左上方时退出，换句话讲就是当
startR <= endR and startC <= endC 时我们才可以进入内层循环打印圈
那内层循环如何分情况打印圈？情况就三种：
- 当 startR == endR 时，说明只剩一行
- 当 startC == endC 时，说明只剩一列
- 否则为一般情况，绕圈打印即可
代码
class Solution:
# matrix类型为二维列表，需要返回列表
def PrintMatrix(self, matrix):
def printEdge(startR, startC, endR, endC):
if startR == endR: # 只剩一行
for col in range(startC, endC + 1):
res.append(matrix[startR][col])
elif startC == endC: # 只剩一列
for row in range(startR, endR + 1):
res.append(matrix[row][startC])
else: # 一般情况
curR, curC = startR, startC
while curC != endC: # 从左到右
res.append(matrix[curR][curC])
curC += 1
while curR != endR: # 从上到下
res.append(matrix[curR][curC])
curR += 1
while curC != startC: # 从右到左
res.append(matrix[curR][curC])
curC -= 1
while curR != startR: # 从下到上
res.append(matrix[curR][curC])
curR -= 1
if not matrix: return
startR, startC, endR, endC = 0, 0, len(matrix) - 1, len(matrix[0]) - 1
res = []
while startR <= endR and startC <= endC:
printEdge(startR, startC, endR, endC)
startR += 1
startC += 1
endR -= 1
endC -= 1
return res
举一反三
包含min函数的栈
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的 min 函数。
在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)
最优题解
设置一个辅助栈，每次入栈时把最小元素
（之前的最小值（辅助栈栈顶）和新压入栈的元素两者的较小值）保存在辅助栈中
出栈时辅助栈一起出栈，这样就可以保证辅助栈的栈顶是最小值
代码
class Solution:
def __init__(self):
self.stack = []
self.minstack = []
def push(self, node):
self.stack.append(node)
if not self.minstack or node <= self.min():
self.minstack.append(node)
else:
self.minstack.append(self.min())
def pop(self):
if not self.stack: return
self.minstack.pop()
return self.stack.pop()
def top(self):
return self.stack[-1] if self.stack else None
def min(self):
return self.minstack[-1] if self.minstack else None
栈的压入弹出序列
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序
假设压入栈的所有数字均不相等
例如序列 1, 2, 3, 4, 5 是某栈的压入顺序，序列 4, 5, 3, 2, 1 是该压栈序列对应的一个弹出序列
但 4, 3, 5, 1, 2 就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
最优题解
设置一个辅助栈，用来装压栈序列，不断压入压栈序列的数，每压入一次
就看一下当前栈顶元素是否为当前弹出数，是的话弹出并遍历下一个弹出数
继续检查，直到辅助栈空或者当前栈顶元素不为弹出序列第一个
就继续压入压栈序列的数，直到压完所有的数，最终检查辅助栈是否为空，空则说明该序列为弹出序列
即：如果下一个弹出的数字刚好是栈顶数字，那么直接弹出。如果下一个弹出的数字不在栈顶
就把压栈序列中还没入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止
如果所有的数字都压入栈了仍然没有找到下一个弹出的数字，那么该序列就不可能是一个弹出序列
代码
class Solution:
def IsPopOrder(self, pushV, popV):
if not pushV or not popV or len(pushV) != len(popV):
return False
stack, i = [], 0
for num in pushV:
stack.append(num)
while stack and stack[-1] == popV[i]:
i += 1
stack.pop()
return stack == []
从上往下打印二叉树
题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
最优题解
相当于宽度优先搜索（BFS），用队列来实现
每次从头部取出一个结点时，如果该结点有子结点
就把该结点的子结点从左到右依次放入队列末尾
重复前面的步骤，直到队列为空
代码
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回从上到下每个节点值列表，例：[1,2,3]
def PrintFromTopToBottom(self, root):
if root is None: return []
res, level = [], [root]
while level:
next_level = []
for node in level:
res.append(node.val)
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
level = next_level
return res
二叉搜索树的后序遍历序列
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果
假设输入的数组的任意两个数字都互不相同。
最优题解
二叉搜索树对于每一个非叶子节点, 均有结点左子节点 < 当前节点 < 结点右子结点
后序序列的最后一个值为二叉搜索树根节点的值，前面含有左子树和右子树结点
根据二叉搜索树的特性，根节点前面的序列分为两个区域，左边为左子树区
值都比根节点小，右边为右子树区，值都比根节点大
不满足该特性的序列就不是某二叉搜索树的后序遍历的结果
注意左子树区域和右子树区域分别又是一棵二叉搜索树，因此递归检查这两个区域
代码
class Solution:
def VerifySquenceOfBST(self, sequence):
def verify(seq):
if not seq or len(seq) == 1: return True
for i in range(len(seq)):
if seq[i] > seq[-1]: break
# 如果是前序遍历就必须加上 i+=1
# 这里不用的原因在于seq[-1]是哨兵
# i一定会在小于区的右边界的右边元素停下
for j in range(i, len(seq) - 1):
if seq[j] < seq[-1]: return False
return verify(seq[:i]) and verify(seq[i:-1])
if not sequence: return False
return verify(sequence)
举一反三
二叉树中和为某一值的路径
题目描述
输入一颗二叉树和一个整数，输出二叉树中结点值的和为输入整数的所有路径
路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径
最优题解
前序遍历，每来到一个结点就检查当前和是否为期望和，所以需要把当前和作为参数传递。
代码
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
def find(root, cursum):
if not root: return
path.append(root.val)
cursum += root.val
if not root.left and not root.right and cursum == expectNumber:
res.append(path[:])
find(root.left, cursum)
find(root.right, cursum)
path.pop() # 结点返回时记得把当前结点从路径中删除
res, path = [], []
find(root, 0)
return res
复杂链表的复制
题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针
next指向下一个节点，random指向任意一个节点）
返回结果为复制后复杂链表的head
最优题解
时间复杂度 O(n)，空间复杂度 O(1)
第一步，复制原链表的结点N并创建新结点N’，再把N’链接到N的后面
第二步，设置每个N’的random。如果原链表上的结点N的random指向S，则它对应的复制结点N’的random指向S的下一个结点S’
第三步，把这个长链表拆分成两个链表，奇数位置上的结点组成原链表，偶数位置上的结点组成复制链表
代码
class RandomListNode:
def __init__(self, x):
self.label = x
self.next = None
self.random = None
class Solution:
def Clone(self, pHead):
def clone(head):
while head:
cloneNode = RandomListNode(head.label)
cloneNode.next = head.next
head.next = cloneNode
head = cloneNode.next
def connect(head):
clone = head.next
while head:
clone.random = head.random.next if head.random else None
head = clone.next
clone = head.next if head else None
def split(head):
clone = cloneHead = head.next
while head:
head.next = clone.next
head = head.next
clone.next = head.next if head else None
clone = clone.next
return cloneHead
if pHead is None: return
clone(pHead)
connect(pHead)
return split(pHead)
二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表
要求不能创建任何新的结点，只能调整树中结点指针的指向
最优题解
中序遍历，同时设置一个指针指向当前双向链表的最后一个结点
每个被遍历到的结点都与当前双向链表的最后一个结点互相连接
同时更新该指针为当前被遍历到的结点
代码
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def __init__(self):
self.last = None
def Convert(self, pRootOfTree):
def convert(root):
if not root: return
convert(root.left)
self.last.right = root
root.left = self.last
self.last = root
convert(root.right)
if not pRootOfTree: return
dummy = self.last = TreeNode(0)
convert(pRootOfTree)
dummy.right.left = None # 去掉伪结点
return dummy.right # 伪结点的右边是真正的头结点
字符串的排列
题目描述
输入一个字符串，按字典序打印出该字符串中字符的所有排列
例如输入字符串 abc，则打印出由字符 a, b, c 所能排列出来的所有字符串 abc, acb, bac, bca, cab和 cba
输入描述：
输入一个字符串，长度不超过 9 (可能有字符重复)，字符只包括大小写字母
最优题解
递归，从头到尾逐个字符抽出来，剩下字符的进行排列
最后再把抽出来的那个字符与排列好的字符串拼在一起返回即可
只剩下一个字符时直接返回该字符
代码
class Solution:
def Permutation(self, ss):
def permutation(ss):
if len(ss) == 1: return [ss]
res = []
for i in range(len(ss)):
for s in permutation(ss[:i] + ss[i + 1:]):
res.append(ss[i] + s)
return res
if not ss: return []
return sorted(list(set(permutation(ss))))
举一反三
数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字
例如输入一个长度为 9 的数组 [1, 2, 3, 2, 2, 2, 5, 4, 2]
由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。如果不存在则输出 0
最优题解
时间 O（n），空间 O（1）
采用阵地攻守的思想
先让第一个数作为守阵地的士兵，HP = 1
遇到相同元素，相当于支援兵，补血，HP + 1
遇到不相同元素，相当于敌人，掉血，HP - 1
当 HP 削减为 0 时，以下一个数作为守阵地的士兵
继续下去，到最后还留在阵地上的士兵，有可能是最强士兵（士兵个数超过一半）
为防止该士兵坐收渔翁之利，需再加一次循环，检查该士兵个数是否真的超过一半
代码
class Solution:
def MoreThanHalfNum(self, numbers):
if not numbers: return 0
master = numbers[0]
hp = 1
for num in numbers[1:]:
if hp == 0:
master = num
hp = 1
elif num == master:
hp += 1
else:
hp -= 1
isHalf = sum(num == master for num in numbers) > len(numbers) >> 1
return master if isHalf else 0
最小的K个数
题目描述
输入 n 个整数，找出其中最小的 K 个数。例如输入 4, 5, 1, 6, 2, 7, 3, 8 这 8 个数字，则最小的 4 个数字是 1, 2, 3, 4
最优题解
时间 O(nlogk)，空间 O(1)
基于 Partition 的算法，只有当我们可以修改输入的数组时可用
利用 Partition 找到第 (k - 1) 小的数 (从 0 开始)，则数组左边的k个数字就是最小的 k 个数字（这 k 个数字不一定是排序的）
代码
class Solution:
def GetLeastNumbers(self, tinput, k):
def partition(l, r): # 基于快排的partition
pivot = tinput[l] # 首元素为枢轴标杆
while l < r:
while l < r and tinput[r] >= pivot: r -= 1
tinput[l] = tinput[r]
while l < r and tinput[l] <= pivot: l += 1
tinput[r] = tinput[l]
tinput[l] = pivot
return l
if not tinput or k <= 0 or len(tinput) < k: return []
l, r = 0, len(tinput) - 1
# 以下类似二分， 只不过分界线不再是mid，而是通过partition求得
while l <= r:
idx = partition(l, r)
if idx < k - 1:
l = idx + 1
elif idx > k - 1:
r = idx - 1
else:
return sorted(tinput[:k])
连续子数组的最大和
题目描述
输入一个整型数组，数组中一个或连续的多个整数组成一个子数组。
求所有子数组的和的最大值，要求时间复杂度为 O(n)
最优题解
动态规划，设 f(i) 为以第 i 个数结尾的连续子数组的最大和，则状态转移方程为：
f(i) = max(f(i-1)+array[i], array[i])
最后结果为 max(f(i))
优化：f(i) 只与 f(i - 1) 有关，即只与前一状态有关，所以空间上可以由 O(n) 降为 O(1)
该状态转移方程的意义是：
如果以第 i - 1 个数字结尾的子数组中所有数字的和加上当前第 i 个数字比当前第 i 个数字本身还要小
那么就舍弃前面的累加而直接选择第 i 个数字本身作为最大值
最后求所有以第 i 个数结尾的连续子数组最大和的最大值
代码
class Solution:
def FindGreatestSumOfSubArray(self, array):
if not array: return
curSum = maxSum = array[0]
for num in array[1:]:
curSum = max(num, curSum + num)
maxSum = max(maxSum, curSum)
return maxSum
从 1 到 n 中 1 出现的次数
题目描述
原题：输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数
扩展：改成 X 出现的次数，X ∈ [1, 9]
最优题解
链接：https://www.nowcoder.net/questionTerminal/bd7f978302044eee894445e244c7eee6
来源：牛客网
参考博文：http://www.cnblogs.com/nailperry/p/4752987.html ，主要就是从数字出发找规律。
一、1的数目
编程之美上给出的规律：
如果第 i 位（自右至左，从 1 开始标号）上的数字为 0，则第 i 位可能出现 1 的次数由更高位决定
（若没有高位，视高位为 0），等于更高位数字 * 当前位数的权重 10 ^ (i - 1)
如果第 i 位上的数字为 1，则第 i 位上可能出现 1 的次数不仅受更高位影响，还受低位影响
（若没有低位，视低位为 0），等于更高位数字 * 当前位数的权重 10 ^ (i - 1) + (低位数字 + 1）
如果第 i 位上的数字大于 1，则第 i 位上可能出现 1 的次数仅由更高位决定（若没有高位，视高位为 0）
等于（更高位数字 + 1）* 当前位数的权重10 ^ (i - 1)
二、X的数目
这里的 X ∈ [1, 9]，因为 X = 0 不符合下列规律，需要单独计算
首先要知道以下的规律：
从 1 至 10，在它们的个位数中，任意的 X 都出现了 1 次
从 1 至 100，在它们的十位数中，任意的 X 都出现了 10 次
从 1 至 1000，在它们的百位数中，任意的 X 都出现了 100 次
依此类推，从 1 至 10 ^ i，在它们的左数第二位（右数第 i 位）中，任意的 X 都出现了 10 ^ (i - 1)次
这个规律很容易验证，这里不再多做说明
接下来以 n = 2593, X = 5 为例来解释如何得到数学公式。从 1 至 2593 中，数字 5 总计出现了 813 次
其中有 259 次出现在个位，260 次出现在十位，294 次出现在百位，0 次出现在千位
现在依次分析这些数据，首先是个位。从 1 至 2590 中，包含了 259 个 10，因此任意的 X 都出现了 259 次
最后剩余的三个数 2591, 2592 和 2593，因为它们最大的个位数字 3 < X，因此不会包含任何 5
（也可以这么看，3 < X，则个位上可能出现的 X 的次数仅由更高位决定，等于更高位数字（259） * 10 ^ (1 - 1) = 259）
然后是十位。从 1 至 2500 中，包含了 25 个 100，因此任意的 X 都出现了 25 * 10 = 250 次
剩下的数字是从 2501 至 2593，它们最大的十位数字 9 > X，因此会包含全部 10 个 5
最后总计 250 + 10 = 260。（也可以这么看，9 > X，则十位上可能出现的 X 的次数仅由更高位决定
等于更高位数字(25 + 1) * 10 ^ (2 - 1) = 260）
接下来是百位。从 1 至 2000 中，包含了 2 个 1000，因此任意的 X 都出现了 2 * 100 = 200 次
剩下的数字是从 2001 至 2593，它们最大的百位数字 5 == X，这时情况就略微复杂
它们的百位肯定是包含 5 的，但不会包含全部 100 个。如果把百位是 5 的数字列出来
是从 2500 至 2593，数字的个数与百位和十位数字相关，是 93 + 1 = 94。最后总计 200 + 94 = 294
（也可以这么看，5 == X，则百位上可能出现X的次数不仅受更高位影响，还受低位影响，
等于更高位数字（2） * 10 ^ (3 - 1) + (93 + 1) = 294）
最后是千位。现在已经没有更高位，因此直接看最大的千位数字 2 < X，所以不会包含任何 5
（也可以这么看，2 < X，则千位上可能出现的 X 的次数仅由更高位决定，等于更高位数字 (0) * 10 ^ (4 - 1) = 0）
到此为止，已经计算出全部数字 5 的出现次数
总结一下以上的算法，可以看到，当计算右数第 i 位包含的 X 的个数时：
取第i位左边（所有高位）的数字，乘以 10 ^ (i - 1) ，得到基础值 a
取第i位数字，计算修正值：
如果小于 X，则结果为 a
如果大于 X，则结果为 a + 10 ^ (i - 1)
如果等于 X，则取第 i 位右边（所有低位）数字，设为 b ，最后结果为 a + b + 1
相应的代码非常简单，效率也非常高，时间复杂度只有 O( log n)
代码
class Solution:
def NumberOf1Between1AndN(self, n):
count, weight = 0, 1
while weight <= n:
low = n % weight
high = n // weight
cur = high % 10
base = (high // 10) * weight
if cur < 1:
count += base
elif cur > 1:
count += base + weight
else:
count += base + low + 1
weight *= 10
return count
把数组排成最小的数
题目描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如输入数组 [3, 32, 321]，则打印出这三个数字能排成的最小数字为 321323。
最优题解
最直接的做法就是把数组中所有数字进行全排列，然后把每个排列拼接起来，最后求出拼起来的数字的最小值
易知算法复杂度高达 O(n!)，所以不推荐。这里定义一个新的比较规则：
对于两个数字 m, n，可以拼接成 mn 和 nm
若 mn < nm，则定义 m < n；
若 mn > nm，则定义 m > n；
若 mn = nm，则定义 m = n
将数组中的数按照上述比较规则从小到大进行排序，最后将排序的数组进行拼接即为数组所能拼成的最小数
证明见书第一版P179~180
代码
from functools import cmp_to_key
class Solution:
def PrintMinNumber(self, numbers):
return ''.join(sorted([str(num) for num in numbers], key = cmp_to_key(lambda x, y: int(x + y) - int(y + x))))
丑数
题目描述
把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）
例如 6、8 都是丑数，但 14 不是，因为它包含质因子7
习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 N 个丑数。
最优题解
创建数组保存已经找到的丑数并排好序，关键在于如何生成下一个丑数
数组中最后一个丑数最大，记为M。设置 index2，标记该位置的数乘以 2 大于 M
同理设置 index3、index5，这样每次只需求min(A[index2] * 2, A[index3] * 3, A[index5] * 5)
就可求出下一个丑数，然后更新三个标记
这样关键就在于如何更新这三个标记
仔细推敲可以发现其实只需让那些指向的数乘相应因子等于当前 M 的标记往后移一位即可
因为 M = min(A[index2] * 2, A[index3] * 3, A[index5] * 5)，则至少有个标记是要往后移的
且移一位即可，后面那个数乘以相应的因子一定大于M
那么其他指向的数乘相应因子不等于当前M的标记为什么没有必要移动呢？
还是因为 M = min(A[index2] * 2, A[index3] * 3, A[index5] * 5)， 既然M是其中最小的
那么其他的标记所指向的数乘以相应因子一定就比 M 大了，没有必要更新
这样就可以把三个并列的 while 简化成三个并列的if
这里谈谈为什么要使用这三个 index，且为什么这样做可以保证按顺序产生下一个丑数
按照正常的理解，后面的丑数都是由前面已经产生的某个丑数乘 2 或乘 3 或乘 5 得到
为了按照顺序，必须把前面每个丑数乘 2 或乘 3 或乘 5 得到的值中取大于当前最后一个丑数的最小值
那么问题来了，有必要把每个丑数都乘这三个因子然后取最小值?
我们发现每个丑数都要经历乘 2 乘 3 乘 5 的过程，但却没有必要在同一次竞争下一个丑数中乘
所以我们反过来，标记上那些需要乘 2 或乘 3 或乘 5 的数，使得 index2 指向的数就要乘 2
因为它在下一次竞争中可能会胜利，index3 和 index5 同理。为了满足以上规则
我们让这三个标记从左向右各自独立遍历，这样也就让每个数都会经历乘 2 或乘 3 或乘 5 的过程
且如果标记的数乘以相应因子后竞争胜利了，那么该标记就要往后挪 1 位
因为新的丑数是该标记因子乘以它指向的数竞争胜利而生成的
所以该数乘以该因子已经没有参与下一次竞争的机会了，相应的因子标记就该往后挪
使得下一个数参与新的竞争。而其他竞争失败的标记不用动，因为它们还有竞争胜利的机会
毕竟每次胜利的是那个乘积最小的
代码
class Solution:
def GetUglyNumber(self, index):
if not index: return 0
idx2 = idx3 = idx5 = 0
uglynums = [1]
for _ in range(index-1):
uglynums.append(min(uglynums[idx2]*2, uglynums[idx3]*3, uglynums[idx5]*5))
# 可能会有多个标记竞争胜利，即丑数恰好是前面标记所在值的公倍数
# 因此必须是并列的if，不能if...elif...else
if uglynums[-1] == uglynums[idx2]*2: idx2 += 1
if uglynums[-1] == uglynums[idx3]*3: idx3 += 1
if uglynums[-1] == uglynums[idx5]*5: idx5 += 1
return uglynums[-1]
第一个只出现一次的字符
题目描述
在一个字符串(1 <= 字符串长度 <= 10000，全部由字母组成)中找到第一个只出现一次的字符
并返回它的位置，不存在就返回 -1
最优题解
时间复杂度 O(n)，空间复杂度 O(1)（不会超过 256 个键值对）
利用 python 的字典建立哈希表，键记录字母，值记录字母出现的次数
第一次遍历建立哈希表，第二次遍历找到第一个值为 1 的键（字母）
代码
from collections import OrderedDict
class Solution:
def FirstNotRepeatingChar(self, s):
table = OrderedDict()
for ch in s:
table[ch] = table.setdefault(ch, 0) + 1
for ch, v in table.items():
if v == 1:
return s.index(ch)
return -1
举一反三
数组中的逆序对
题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对
输入一个数组, 求出这个数组中逆序对的总数
最优题解
归并排序，在合并时统计逆序对个数
设合并的两个数组为 a1 和 a2，用两个指针 p1，p2，指向 a1 和 a2 的末尾元素，并每次比较两个指针指向的数字。
如果 p1 数字大于 p2，则构成逆序对，并且逆序对的数目等于 p2 之前的元素个数(包括 p2 指向的元素)
因为 a2 是已经排好序的，则 p2 之前的数都小于 p1 指向的数。
反之，如果 p1 数字小于等于 p2，则不构成逆序对
每一次比较都把较大的数从后往前复制到一个辅助数组里,确保辅助数组里的数字是递增排序的
然后把较大的数的指针往前移一位，进行下一轮比较
所以总的逆序对数就是先把数组分隔成子数组，先统计出两个子数组内部的逆序对数
然后统计出两个相邻子数组之间的逆序对数，三者之和
代码
class Solution:
def merge(data, copy, l, r):
if l == r: return 0
m = (l + r) // 2
# 注意这里的copy和data位置交换了，这样就能保证递归回来时，上一层拿到的data是下一层已经排好序的copy
left = merge(copy, data, l, m) # 左区域的逆序对个数
right = merge(copy, data, m + 1, r) # 右区域的逆序对个数
i, j = m, r # i初始化为前半段最后一个数字的下标，j初始化为后半段最后一个数字的下标
count, copyIdx = 0, r
while i >= l and j >= m + 1:
# 复制的时候统计两个子数组之间的逆序对数
if data[i] > data[j]:
copy[copyIdx] = data[i]
count += j - m # 逆序对的数目等于j之前的元素个数(包括j指向的元素)
i -= 1
else:
copy[copyIdx] = data[j]
j -= 1
copyIdx -= 1
# 将剩下复制到辅助数组里
while i >= l:
copy[copyIdx] = data[i]
i -= 1
copyIdx -= 1
while j >= m + 1:
copy[copyIdx] = data[j]
j -= 1
copyIdx -= 1
return left + right + count # 总逆序对个数 = 左区域 + 右区域 + 合并
if not data: return 0
return merge(data, data[:], 0, len(data) - 1)
两个链表的第一个公共结点
题目描述
输入两个单向无环链表，找出它们的第一个公共结点。
最优题解
时间复杂度 O(m + n)，空间复杂度 O(1)
两个链表指针 p1，p2 从头开始一起遍历，但是 p1 来到末尾时指向另一个链表的头结点（不是指向原链表的头结点），p2 也一样
这样第一次遍历时，短的链表指针（假如为 p1）来到长链表（假如为 l2）的头结点，此时 p2 还在 l2 上，且 p2 距离末尾（l2 - l1）
p2 来到 l1 头结点时，p1 在 l2 上距离末尾（l2 - (l2 - l1)）此时 p1 的位置正好就是长指针先出发来到二者长度差的位置，下面一起遍历一定能够相遇
即使没有公共结点，也会在 None 处一起返回（相当于相遇）
整个过程最坏情况下 p1、p2 各遍历两个链表一次，所以时间复杂度 O(m + n)，空间复杂度 O(1)
代码
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
p1, p2 = pHead1, pHead2
while p1 is not p2:
p1 = p1.next if p1 else pHead2
p2 = p2.next if p2 else pHead1
return p1
数字在排序数组中出现的次数
题目描述
统计一个数字在排序数组中出现的次数
最优题解
既然是排好序的，那么自然想到二分法了
总体思路是找到第一个 k 的位置，再找到最后一个 k 的位置，相减加一
以查找第一个 k 的位置为例 ：
如果中间的数字比 k 大，那么 k 只可能出现在数组的前半段，下一轮就只在数组的前半段查找就可以了
如果中间的数字比 k 小，那么 k 只可能出现在数组的后半段，下一轮就只在数组的后半段查找就可以了
关键是如果中间的数字等于 k 呢？我们先判断该数字是不是第一个 k
如果中间数字前面不是 k，则该中间数字刚好就是第一个 k
如果中间数字前面也是 k，则第一个 k 肯定在数组前半段，下一轮我们仍然需要在数组前半段查找
代码
class Solution:
def GetNumberOfK(self, data, k):
def firstK():
l , r = 0 , len(data) - 1
while l <= r:
m = l + ((r - l) >> 1)
if data[m] < k:
l = m + 1
elif data[m] > k:
r = m - 1
else:
if m == 0 or data[m - 1] < k:
return m
else:
r = m - 1
return -1
def lastK():
l , r = 0 , len(data) - 1
while l <= r:
m = l + ((r - l) >> 1)
if data[m] < k:
l = m + 1
elif data[m] > k:
r = m - 1
else:
if m == len(data) - 1 or data[m + 1] > k:
return m
else:
l = m + 1
return -1
if not data: return 0
first, last = firstK(), lastK()
return last - first + 1 if first != -1 else 0
举一反三
二叉树的深度
题目描述
输入一棵二叉树，求该树的深度。
从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
最优题解
递归实现，树的深度 = max(左子树深度，右子树深度) + 1
代码
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def TreeDepth(self, pRoot):
if not pRoot: return 0
return max(self.TreeDepth1(pRoot.left), self.TreeDepth1(pRoot.right)) + 1
判断平衡二叉树
题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
注：平衡二叉树任意结点的左右子树深度相差不超过 1，空树算平衡二叉树
最优题解
根据后序遍历的特点，当遍历到某一结点时该结点的左右子树已经遍历结束
因此在遍历每个结点的时候记录以它为根节点的树的深度，这样在遍历到某个结点时
既知道了左右子树的深度，也知道左右子树是否为平衡二叉树(递归)，即一边计算深度一边判断是否平衡
书上用变量 left 和 right 来单独表示左右子树的深度，函数返回的是 true 或者 false
其实不用这两个变量，我们直接把树的深度返回即可，这样根节点可直接拿到左右子树的深度
因为我们注意到深度总是大于等于 0 的，所以我们只需定义当子树不平衡时返回 -1 即可
这样根节点也就可以通过左右子树返回的深度是否大于等于 0 来间接判断左右子树是否平衡
代码
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def IsBalanced_Solution(self, pRoot):
def isBalanced(root):
if root is None: return 0
left = isBalanced(root.left)
if left == -1: return -1 # 提前返回，不用遍历右子树了
right = isBalanced(root.right)
if right == -1 or abs(left - right) > 1: return -1
return max(left, right) + 1
return isBalanced(pRoot) >= 0
数组中只出现一次的两个数字
题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
最优题解
时间复杂度 O(n)，空间复杂度 O(1)
既然其他的数字都出现了两次，那么可以把数组中所有数异或，则两次的相互抵消，一次的相互异或
即最终的异或结果相当于两个出现一次的数相异或。如果只有一个数字是出现一次的
那么异或结果就是那个数了，但这里有两个，于是我们想着把它俩给分开，使得各自在一个数组里
且每个数组除了那个出现一次的数以外其他数都是出现两次，这样两个数组分别异或就可以找出这两个数了
关键是如何把它俩分开且数组里其他数都是成双成对？我们仍然把整个数组相异或
得到的结果一定不为 0（因为这两个数一定不一样），那么二进制中一定有一个位置为 1
那么我们可以以最右边的 1 为标准，把整个数组中该位为 1 的数划分为一组，为0的划分为一组
这样做一举两得：
一来把那两个出现一次的数分开了
二来把成对的数放在了同一个数组里了（因为相同的数其二进制位一致）
我们其实还可以再优化一下：在第二次循环时，只需把标准位是 1 的数异或起来就可以了
那么最终结果就是那两个数字中的一个，此时把该数与第一次循环的异或结果再次异或就可以得到另一个数了
代码
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
xor_sum = a = 0
for i in array:
xor_sum ^= i
last1 = xor_sum & -xor_sum # 取出最右边的1
for i in array:
if i & last1:
a ^= i
return [a, a ^ xor_sum]
举一反三
和为s的两个数字
题目描述
输入一个递增排序的数组和一个数字 S，在数组中查找两个数，使得他们的和正好是S
如果有多对数字的和等于 S，输出乘积最小的两个数
对应每个测试案例，输出两个数，小的先输出
最优题解
双指针，左右夹逼
设置两个指针分别指向第一个和最后一个数，如果它们的和等于 s，我们就找到了这两个数
如果小于 s，由于数组已经排好序，所以只需让较小数的指针往后移
如果大于 s，则让较大数的指针往前移。最终找到的第一对就是乘积最大的
代码
class Solution:
def FindNumbersWithSum3(self, array, sum):
if array:
l , r = 0, len(array) - 1
while l < r: # 当 l==r 时，指向同一个数，则不再是不同位置的两个数，结束循环
if array[l] + array[r] < tsum:
l += 1
elif array[l] + array[r] > tsum:
r -= 1
else:
return [array[l], array[r]]
return []
和为s的连续正整数序列
题目描述
找出所有和为 S 的连续正整数序列(至少含有两个数)
序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
最优题解
双指针问题
用两个数 small 和 big 分别表示序列的最小值和最大值。首先把 small 初始化为 1，big 初始化为 2
如果从 small 到 big 的序列的和大于 s，可以从序列中去掉较小值，也就是增大 small 的值
如果从 small 到 big 的序列的和小于 s，可以增大 big，让序列包含更多的数字
因为序列至少要有两个连续的数字，所以 small 的上限是 (s -1 ) / 2，big 的上限是(s - 1) / 2 + 1
代码
class Solution:
def FindContinuousSequence(self, sum):
if sum < 3: return []
l, r, curSum = 1, 2, 3
lTop = (sum - 1) // 2
rTop = lTop + 1
res = []
while r <= rTop:
while l <= lTop and curSum > sum:
curSum -= l # 先减再右移
l += 1
if curSum == sum:
res.append(list(range(l, r + 1)))
r += 1 # 如果curSum < sum，那么r后移；如果找到了一个序列，那么r也后移继续寻找下一个序列
curSum += r # 先右移再加
return res
翻转单词顺序
题目描述
输入一个英文句子, 翻转句子中单词的顺序,但单词内字符的顺序不变
为简单起见, 标点符号和前面的单词属于同一个单词
最优题解
两次翻转，第一次整体翻转，第二次每个单词再翻转（也可以先每个单词翻转然后整体翻转）
代码
class Solution:
def ReverseSentence(self, s):
return ' '.join(w[::-1] for w in s[::-1].split(' '))
左旋转字符串
题目描述
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果
对于一个给定的字符序列 S，请你把其循环左移 K 位后的序列输出
例如，字符序列 S = ”abcXYZdef”, 要求输出循环左移3位后的结果，即 “XYZdefabc”
最优题解
先分片后拼接
代码
class Solution:
def LeftRotateString(self, s, n):
if not s: return ''
return s[n%len(s):] + s[:n%len(s)] # 考虑重复左移，所以n % len(s)
n个骰子的点数
题目描述
把 n 个骰子扔在地上, 所有骰子朝上一面的点数和为 s
输入 n, 打印出 s 的所有可能的值出现的次数（原题要求输出概率，为了方便这里只需输出次数）
最优题解
设 n 个骰子投掷点数和为s的出现次数是 F(n, s)
则 F(n, s) 等于 (n - 1) 个骰子投掷的点数和为 s - 1、s - 2、s - 3、s - 4、s - 5、s - 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)
所有的和出现次数总和为 6 ^ n，概率为 F(n, s) / 6 ^ n。(n <= s <= 6n)
代码
class Solution:
def DicesProbability(self, n):
if not n or n < 1:
return
maxVal = 6
count = [[0] * (maxVal * n + 1), []] # 构造两个数组来存放每一个和出现的次数，下标表示和，里面的值代表次数
flag = 0 # 用flag来反复利用这两个数组
for i in range(1, maxVal + 1): # 一开始只有一个骰子，当然次数都为1
count[flag][i] = 1
for i in range(2, n + 1): # 逐渐加入其他骰子
# 一开始另一个数组要初始化为0，因为每加入一个骰子就会使前面的和次数成为0
# 比如，先是1个骰子时和为1的次数为1，当加入第二个骰子时，和为1是不可能出现的
# 换句话说，就是和的范围是动态变化的，且一直往右移
count[1 - flag] = [0] * (maxVal * n + 1)
for j in range(i, maxVal * i + 1): # i <= s <= 6*i
k = 1
while k <= j and k <= maxVal:
# 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)
count[1 - flag][j] += count[flag][j - k]
k += 1
flag = 1 - flag # 将flag更新，flag永远指向求和好的数组
return [(i, count[flag][i]) for i in range(n, maxVal * n + 1)]
扑克牌的顺子
题目描述
从扑克牌中随机抽取5张牌，判断是不是顺子，即这5张牌是不是连续的。2~10为数字本身，A为 1，J~K 为 11~13
而大小王可以看成任意数字。为方便起见这里把大小王看成 0，且规定含有对子时不为顺子
注意：这里大小王的个数不限，且输入参数的 AJQK 和大小王已经转换成相应数字
最优题解
时间O(n)，空间n(1)
- 除 0 外没有重复的数(用位图来记录每个出现过的数字)
- max - min < 5 （由于max 和 min 动态变化，但最终 max - min = 4）
代码
class Solution:
def IsContinuous1(self, numbers):
if not numbers or len(numbers) != 5:
return False
# 把A、J、Q、K转化一下
# transDict = {'A': 1, 'J': 11, 'Q': 12, 'K': 13}
# for i in range(len(numbers)):
# if numbers[i] in transDict.keys():
# numbers[i] = transDict[numbers[i]]
min = 14
max = -1
flag = 0 # 用位图来记录每个出现过的数字
for i in range(len(numbers)):
number = numbers[i]
if number < 0 or number > 13: return False
if number == 0: continue
if ((flag >> number) & 1) == 1: return False # 如果出现过，那么再次出现就是对子了
flag |= (1 << number) # 记录出现过的数字
if number > max: max = number
if number < min: min = number
if max - min >= 5: return False
return True
圆圈中最后剩下的数字（约瑟夫环问题）
题目描述
0, 1, 2, n - 1这 n 个数字排成一个圆环, 从数字 0 开始每次从这个圆圈里删除第 m 个数字
求这个圆圈中最后剩下的一个数字。
最优题解
时间O(n)，空间O(1)
推导递归公式。定义 f(n, m) 表示每次在 n 个数字 0，1，…，n - 1 中删除第 m 个数字最后剩下的数字
则有递归公式：
f(n, m) = [f(n - 1, m) + m] % n if n > 1；0 if n=1
具体推导过程直接看书 P230 ~ 231
公式不好记，更多情况下我们可以直接暴力模拟，这里使用循环队列模拟整个过程
虽然空间复杂度为 O(n)，但是代码可读性大大增加
代码
class Solution:
# 循环实现
def LastRemaining1(self, n, m):
if not n or not m: return -1
last = 0
for i in range(2, n + 1):
last = (last + m) % i
return last
def LastRemaining1(self, n, m):
if not n or not m: return -1
last, circle = 0, list(range(n))
while len(circle) > 1:
last = (last + m + 1) % len(circle)
circle.pop(last)
return circle[0]
求前n项和（各种限制）
题目描述
求 1 + 2 + 3 + … + n
要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句（A ? B : C）
最优题解
利用 and 运算的短路原则退出递归
代码
class Solution:
def Sum(self, n):
return n and (n + self.Sum(n - 1))
不用加减乘除做加法
题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用 +、-、 * 、/ 四则运算符号
最优题解
位运算
1.两个数异或：相当于每一位相加，而不考虑进位；
2.两个数相与，并左移一位：相当于求得进位；
3.将上述两步的结果相加：相当于重复执行上述两步，直到不产生进位
由于 Python 的整型是无限位数的，所以有可能导致不断进位，所以需要截取后 32 位，即 & 0xffffffff
但这样就会导致和为负数时由于截取使得结果为正数，所以需要检查一下如果结果的最高位为 1
说明结果为负数，需要将最高位左边所有的 0 变为 1，这样就可以变为负数，然后按照补码转换成正确的数值
也就是说需要保持右边 32 位不变而左边所有位取反
所以可以先把右边 32 位局部取反，然后整体取反。局部取反可以 ^ 0xffffffff，而整体取反直接 ~
代码
class Solution:
def Add(self, num1, num2):
mask = 0xffffffff
while num2:
num1, num2 = (num1 ^ num2) & mask, ((num1 & num2) << 1) & mask
return num1 if num1 >> 31 == 0 else ~(num1 ^ mask)
把字符串转换成整数
题目描述
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数
数值为 0 或者字符串不是一个合法的数值则返回 0
最优题解
考虑这么几点：
有无正负号
只有正负号
多个正负号开头
空串或 None
非法字符
- 由于 Python 整型无限长，所以不考虑正负溢出（一般对于32位整型来讲，最大正整数是 0x7fffffff，最小负整数是 0x80000000）
代码
class Solution:
def StrToInt(self, s):
if not s:
return 0
start = 0 # 标记开始转换的位置
minus = False # 标记正负
if s[0] == '-':
start = 1
minus = True
elif s[0] == '+':
start = 1
sum = 0
for i in range(start, len(s)):
if s[i] < '0' or s[i] > '9': # 含有非法字符返回0
return 0
sum = sum * 10 + ord(s[i]) - ord('0')
return -1 * sum if minus else sum
二叉树的最低公共祖先
题目描述
找出二叉树中两个结点的最低公共祖先（没有指向父节点的指针）
最优题解
结束递归：
如果遇到了目标节点就返回那个目标节点，表示找到了该结点
如果是 None 就返回 None，表示没有找到
继续递归：
既不是 None 也不是目标节点，说明要接着递归往下左右子树遍历
收集下面传上来的有关子树中出现目标节点的信息
处理递归返回的信息：
如果左子树、右子树都有找到，说明自己就是最小公共祖先了，返回本身
只有一边找到，则说明自己不是最小公共祖先，而是在最小公共祖先的上面
且间接说明这个传上来的结点就是最小公共祖先，把这个传上来的结点继续往上传
两边都没有找到则直接返回 None，表示没有找到
代码
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def findParent(self, root, pNode1, pNode2):
if root in {None, pNode1, pNode2}: return root
left = self.findParent(root.left, pNode1, pNode2)
right = self.findParent(root.right, pNode1, pNode2)
return root if left and right else left or right
举一反三
数组中重复的数字
题目描述
在一个长度为 n 的数组里的所有数字都在 0 到 n - 1 的范围内
数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次
请找出数组中重复的数字，没有则返回 -1
例如，如果输入长度为 7 的数组 [2, 3, 1, 0, 2, 5, 3]，那么对应的输出是重复的数字 2 或者 3
最优题解
时间 O(n)，空间 O(1)
由于长度为 n 的数组里的所有数字都在 0 到 n - 1 的范围内，所以如果没有重复数字的话
那么从小到大排序后的数组每个数和它的下标应该是相等的
所以我们只需从头遍历数组，看每个数字和它下标是否相等，相等就遍历下一个
不相等就和它应该在的位置上（下标和它相等）的数字交换
交换前先检查一下如果那个数字和它相等那么就找到了重复数字了，并且没有必要交换，遍历下一个
代码
class Solution:
# 返回重复数字的列表
def duplicate(self, nums):
if not nums: return -1
i, res = 0, set()
while i < len(nums):
idx = nums[i]
if i == idx:
i += 1
elif nums[i] == nums[idx]:
res.add(nums[i])
i += 1
else: # 只是交换，i 不移动，因为交换过来的数还未检测
nums[i], nums[idx] = nums[idx], nums[i]
return list(res) if res else -1
构建乘积数组
题目描述
给定一个数组 A[0 ,1 , …, n - 1]，请构建一个数组 B[0, 1, …, n - 1]
使得 B 中的元素 B[i] = A[0] * A1 * … * A[i - 1] * A[i + 1] * … * A[n - 1]，不能使用除法
最优题解
时间 O(n)，空间 O(1)
把 B[i] 拆成前 i 项和后 (n - i) 项，分别求乘积，再相乘
即 B[i] = C[i] * D[i] = (A[0] * A1 * … * A[i - 1]) * (A[i + 1] * … * A[n - 1])
而 C[i] = C[i - 1] * A[i - 1], D[i] = D[i + 1] * A[i + 1]
同时利用数组B的空间来节省数组 C 和 D 的空间
代码
class Solution:
def multiply(self, A):
if not A or len(A) == 1:
return
length = len(A)
B = [1]
for i in range(1, length):
B.append(B[i - 1] * A[i - 1]) # 自上而下计算上三角
tmp = 1
for i in range(length - 2, -1, -1):
tmp *= A[i + 1] # 自下而上计算下三角
B[i] *= tmp # B[i]=C[i]*D[i]
return B
正则表达式匹配
题目描述
请实现一个函数用来匹配包括’.’和’*‘的正则表达式
模式中的字符’.’表示任意一个字符，而’ * ‘表示它前面的字符可以出现任意次（包含0次）
在本题中，匹配是指字符串的所有字符匹配整个模式
例如，字符串”aaa”与模式”a.a”和”ab*ac*a”匹配，但是与”aa.a”和”ab*a”均不匹配
最优题解
当模式中的第二个字符是“*”时：
如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，字符串不变，继续匹配；
如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式：
1、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；
2、模式后移2字符，字符串不变，相当于x*被忽略；
3、字符串后移1字符，模式后移2字符；
其中第三种情况可以由前两种组合，所以可以省略
而当模式中的第二个字符不是“*”时：
1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，接着匹配剩余的。
2、如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
代码
class Solution:
def match(self, s, pattern):
if s == None or pattern == None:
return False
if s == '' and pattern == '':
return True
if s != '' and pattern == '':
return False
if len(pattern) > 1 and pattern[1] == '*':
if s != '' and (pattern[0] == s[0] or pattern[0] == '.'):
return self.match1(s[1:], pattern) \
or self.match1(s, pattern[2:]) \
# or self.match(s[1:], pattern[2:]) # 该情况可以由前两种情况组合，所以可以省略
else:
return self.match1(s, pattern[2:])
if s != '' and (s[0] == pattern[0] or pattern[0] == '.'):
return self.match1(s[1:], pattern[1:])
return False
表示数值的字符串
题目描述
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）
例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值
但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是
最优题解
数字的格式可以用A[.[B]][e|EC]或者.B[e|EC]表示，其中A和C都是整数（可以有正负号，也可以没有）
而B是一个无符号整数。考虑这么几种情况：
对于小数点’.’，前后A和B的出现形成或的关系：
- 小数可以没有整数部分，例如.123等于0.123；
- 小数点后面可以没有数字，例如233.等于233.0；
- 当然小数点前面和后面可以有数字，例如233.666
- 但不能单独出现小数点’.’
对于指数符号e或E，前后形成与的关系：
当e或E前面没有数字时，整个字符串不能表示数字，例如.e1、e1；
当e或E后面没有整数时，整个字符串不能表示数字，例如12e、12e+5.4
代码
class Solution:
def isNumeric1(self, s):
import re # 使用内置的re标准库快速匹配
if s:
return True if re.match(r'^[+-]?(\d+|(\.\d+)|(\d+\.)|(\d+\.\d+))([eE][+-]?\d+)?$', s) else False
return False
def isNumeric2(self, s): # 自己造轮子
def scanUnsignedInteger(s):
beforeLength = len(s)
while s and s[0] >= '0' and s[0] <= '9':
s.pop(0)
return len(s) < beforeLength
def scanInteger(s):
if s and (s[0] == '+' or s[0] == '-'):
s.pop(0)
return scanUnsignedInteger(s)
if not s:
return False
s = list(s)
numeric = scanInteger(s)
if s and s[0] == '.':
s.pop(0)
numeric = scanUnsignedInteger(s) or numeric
if s and (s[0] == 'e' or s[0] == 'E'):
s.pop(0)
numeric = scanInteger(s) and numeric
return numeric and s == []
字符流中第一个不重复的字符
题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符
例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”
当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”
如果当前字符流没有存在出现一次的字符，返回#字符
最优题解
哈希表值表示该字符在字符流中首次出现的位置，另外用 index 来记录目前读取的字符流的位置
读取字符时在相应的哈希表位置上看一下是否 >= 0 (哈希表初始化为 -1)，
如果是说明该字符之前出现过，则把值更新为 -2，表示该字符重复出现；
否则说明是第一次出现，把值更新为该字符的出现的位置 index
找出当前第一个出现一次的字符时只需扫描整个哈希表，找出最小的大于等于 0 的值（在字符流中首次出现的位置）对应字符返回即可
代码
class Solution:
def __init__(self):
self.hashList = [-1] * 256
self.index = 0
def Insert(self, char):
asc = ord(char)
if self.hashList[asc] == -1:
self.hashList[asc] = self.index
elif self.hashList[asc] >= 0:
self.hashList[asc] = -2
self.index += 1
def FirstAppearingOnce(self):
ch = '#'
minIndex = float("inf")
for i in range(256):
if 0 <= self.hashList[i] < minIndex:
ch = chr(i)
minIndex = self.hashList[i]
return ch
链表中环的入口结点
题目描述
一个链表中包含环，请找出该链表的环的入口结点。
最优题解
先判断是否含环，可以用快慢指针实现
慢指针一次走一步，快指针一次走两步，当两个指针相遇时说明链表含环
然后把两个指针中的一个指向链表头结点，另一个保持在相遇点
接着两个指针以相同的速度（一次一步）遍历，直到二者再次相遇，该相遇点就是环的入口，理论证明见：
代码
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def EntryNodeOfLoop(self, head):
fast = slow = head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
if fast is slow: # 二者相遇，说明链表含环
fast = head # fast 指向头结点
while fast is not slow: # 二者还没相遇之前一直走下去
fast, slow = fast.next, slow.next # 这里fast和slow的速度一样
return fast
删除链表中重复的结点
题目描述
在一个排序的链表中，存在重复的结点
请删除该链表中重复的结点，重复的结点不保留，返回链表头指针
例如，链表 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 处理后为 1 -> 2 -> 5
最优题解
双指针
pre 和 cur，cur 负责在前面‘探路’，遇到重复结点就一直往后删除
确认是唯一结点就让 pr e后移，这样 pre 其实一直指向唯一结点的尾部
注意头结点可能和后面的结点重复，所以头结点可能被删除
为了减少代码的理解复杂度，引入伪结点 dummy
代码
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def deleteDuplication(self, pHead):
if not pHead: return
pre = dummy = ListNode(0) # 使用伪结点
dummy.next = cur = pHead
while cur:
if cur.next and cur.next.val == cur.val: # 遇到相等的结点
val = cur.val
while cur and cur.val == val: # 连续删除重复结点
pre.next = cur = cur.next # 连续赋值，先算出最右边的值，然后从左到右赋值
# 因此这里 pre.next = cur = cur.next 也是正确的
else:
pre, cur = pre.next, cur.next
return dummy.next # 伪结点的下一个结点就是链表头结点
二叉树的下一个结点（中序）
题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回
注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
最优题解
该结点若有右子树就找到右子树的最左结点
没有右子树则向上找到第一个当前结点是其父结点左孩子的结点的父结点
退到了根节点仍没找到则返回 None
代码
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
self.next = None
class Solution:
def GetNext(self, pNode):
if pNode is None: return
if pNode.right: # 若有右子树就找到右子树的最左结点
cur = pNode.right
while cur.left:
cur = cur.left
return cur
cur = pNode # 没有右子树则向上找到第一个当前结点是其父结点左孩子的结点
while cur.next and cur.next.left is not cur:
cur = cur.next
return cur.next # 注意返回的是该结点的父结点，若node退到了根结点则返回的是None
举一反三
对称的二叉树
题目描述
请实现一个函数，用来判断一颗二叉树是不是对称的
注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的
最优题解
前序遍历，把当前结点的左右子树看成俩棵树
只有当左树的左子树和右树的右子树相同，并且左树的右子树和右树的左子树相同才对称
代码
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def isSymmetrical(self, pRoot):
def sym(root1, root2):
if root1 and root2 and root1.val == root2.val:
return sym(root1.left, root2.right) and sym(root1.right, root2.left)
return not(root1 or root2) # 两个都为None时返回True，一个为None另一个非None时返回False
return sym(pRoot, pRoot)
把二叉树打印成多行
题目描述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
最优题解
层次遍历，队列实现
代码
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回二维列表[[1,2],[4,5]]
def Print(self, pRoot):
if pRoot is None: return []
level, res = [pRoot], []
while level:
next_level = []
res.append([])
for node in level:
res[-1].append(node.val)
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
level = next_level
return res
按之字型顺序打印二叉树
题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印
第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
最优题解
两个栈实现。奇数层打印时先保存左孩子再保存右孩子到另一个栈里
这样在打印偶数层时就会先打印右孩子再打印左孩子
同理，偶数层在打印时反过来先右后左保存子结点到奇数层
代码
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def Print(self, pRoot):
if not pRoot: return []
cur, res = 0, [] # 0表示当前正在打印奇数层， 1表示当前正在打印偶数层
stack = [[pRoot], []] # 奇偶栈
while any(stack):
res.append([])
while stack[cur]:
node = stack[cur].pop()
res[-1].append(node.val)
if cur == 0: # 如果当前正在打印奇数层
if node.left:
stack[~cur].append(node.left) # 保存子结点于偶数层
if node.right:
stack[~cur].append(node.right)
else: # 如果当前正在打印偶数层
if node.right:
stack[~cur].append(node.right) # 保存子结点于奇数层
if node.left:
stack[~cur].append(node.left)
cur = ~cur # 反转奇偶层
return res
二叉树的序列化和反序列化
题目描述
请实现两个函数，分别用来序列化和反序列化二叉树。这里没有规定序列化的方式
最优题解
序列化可以采用多种遍历方式，本来可以仿照第6题序列化成 前序 + 中序 或 后序 + 中序
但这要求结点值不能重复，所以不能使用双遍历的方式。采用单遍历就允许结点值重复
可是单次遍历是无法确定一个二叉树的，所以可以在遍历到 None 时也加入遍历序列中
这里的序列化字符串用 ‘#’ 表示 None，为了防止 12，3 以及 1，23 产生歧义而分不清
故使用逗号将每个结点的值分开
代码
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def Serialize(self, root):
def serialize(root):
level, res = [root], []
while level:
next_level = []
for node in level:
res.append(str(node.val) if node else '#')
if node: next_level += node.left, node.right
level = next_level
return ','.join(res)
def deserialize(s):
s = s.split(',')
if s[0] == '#': return
root = TreeNode(int(s[0]))
queue = [root]
for i in range(1, len(s), 2): # s的长度一定为奇数
node = queue.pop(0)
if s[i] != '#': # 连接左孩子
left = TreeNode(int(s[i]))
node.left = left
queue.append(left)
if s[i + 1] != '#': # 连接右孩子
right = TreeNode(int(s[i + 1]))
node.right = right
queue.append(right)
return root
二叉搜索树中的第k个结点
题目描述
给定一棵二叉搜索树，请找出其中的第k大的结点。例如，
按结点数值大小顺序第三个结点的值为4。
最优题解
二叉搜索树的中序遍历序列是递增排序的，所以中序遍历二叉树，递归实现，找到就返回
代码
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回对应节点TreeNode
def __init__(self):
self.k = 0
def KthNode(self, pRoot, k):
def inOrder(root):
if root is None: return
node = inOrder(root.left)
if node: return node # 找到就直接返回
self.k -= 1 # 没找到就继续在中间找
if self.k == 0: return root # 找到就直接返回
return inOrder(root.right) # 没找到就继续在右边找
self.k = k
return inOrder(pRoot)
数据流的中位数
题目描述
如何得到一个数据流中的中位数？
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值
如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值
最优题解
构建大根堆和小根堆，则插入 O(logn)，取中位数 O(1)
如果用一个数组存储所有到来数据，然后在取中位数时排序返回，则插入 O(1)，取中位数 O(nlogn)
由此可见，动态构建大根堆和小根堆相当于把排序时间平分到每次插入操作中，这样在获取中位数时可以 O(1)
有两个条件要满足：
保证数据平均分配到两个堆中，即两个堆中数据的数目之差不能超过1
保证大根堆里所有数据都要小于小根堆中的数据
当数据总数为奇数时，新加入的元素，应当进入大根堆
注意不是直接进入大根堆，而是经小根堆筛选后取小根堆中最大元素进入大根堆
当数据总数为偶数时，新加入的元素，应当进入小根堆
注意不是直接进入小根堆，而是经大根堆筛选后取大根堆中最大元素进入小根堆
取数时若总数个数为奇数则直接取大堆堆顶，偶数时取两堆堆顶平均值
这里构建堆用 heapq，其默认构建的都是小根堆（优先队列），所以为了构建大根堆需要在存数取数时加上负号
代码
from heapq import heappush, heappushpop
class Solution:
def __init__(self):
self.count = 0
self.maxheap = []
self.minheap = []
def Insert(self, num):
self.count += 1
if self.count & 1: # 奇数时，新加入的元素应当进入大根堆
heappush(self.maxheap, -heappushpop(self.minheap, num))
else: # 偶数时，新加入的元素应当进入小根堆
heappush(self.minheap, -heappushpop(self.maxheap, -num))
def GetMedian(self):
return -self.maxheap[0] if self.count & 1 else (-self.maxheap[0] + self.minheap[0]) / 2.0
滑动窗口的最大值
题目描述
给定一个数组和滑动窗口的大小 k，找出所有滑动窗口里数值的最大值
例如，如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口
他们的最大值分别为 {4, 4, 6, 6, 6, 5}
针对数组 {2, 3, 4, 2, 6, 2, 5, 1} 的滑动窗口有以下 6 个：
{[2, 3, 4], 2, 6, 2, 5, 1}， {2, [3, 4, 2], 6, 2, 5, 1}， {2, 3, [4, 2, 6], 2, 5, 1}，
{2, 3, 4, [2, 6, 2], 5, 1}， {2, 3, 4, 2, [6, 2, 5], 1}， {2, 3, 4, 2, 6, [2, 5, 1]}
最优题解
时间复杂度O（n），空间复杂度O（n）
用一个双端队列，其中保存当前可能为最大值的数的下标，每当窗口滑动一次：
新增加的值从队尾开始比较，把前面所有小于等于它的值从队尾取出，直到遇到比它大的数就停止
因为这些数已经不再可能成为后面滑动窗口的最大值了，有种‘长江后浪推前浪’的感觉
注意等于的数也要淘汰，因为后来的数已经与前面的数同窗口，肯定比前面等于它的数要被晚淘汰
新来的数会淘汰掉前面小于等于它的数，而如果前面的数比它大则自己没有资格淘汰前面的数，更别说更前面的数
但该数还是有‘潜质’成为最大数的，因为可能由于前面的数被滑动窗口的移动而强行淘汰使得自己成为最大数，所以会进入队尾等待‘考核’。
判断当前最大值是否过期，过期则从队首取出：
当一个数字的下标与当前正在处理的数字的下标之差大于等于滑动窗口大小时
该最大值过期，即已经从窗口中滑出，需要从队首删除。滑动窗口总是要往右移的
再大的数也会被淘汰
每次通过以上两步操作使得队列第一个位置为当前窗口的最大值
代码
from collections import deque
class Solution:
def maxInWindows(self, num, size):
if not num or not size: return []
queue, res = deque(), []
for i in range(len(num)):
# 新增加的值从队尾开始比较，把前面所有小于等于它的值从队尾取出，直到遇到比它大的数就停止
while queue and num[queue[-1]] <= num[i]:
queue.pop()
queue.append(i) # 进入队列的是数的下标
# 判断当前最大值是否过期，过期则从队首取出
if i - queue[0] + 1 > size:
queue.popleft()
# 当处理数据下标（从0开始）等于size-1时开始写入窗口最大值，
# 因为此时刚好来到第一个窗口的尾部，产生第一个最大值，之后窗口开始移动
if i >= size - 1:
# 每次通过以上两步操作使得队列第一个位置为当前窗口的最大值
res.append(num[queue[0]])
return res
举一反三
矩阵中的路径
题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子
如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子
例如
[[a b c e],
[s f c s],
[a d e e]]
矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径
因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子
最优题解
回溯法，用一个状态数组保存之前访问过的字符位置，然后再分别按上，下，左，右分别递归
代码
class Solution:
def hasPath(self, matrix, rows, cols, path):
def find(i, j, length):
if length == len(path): return True # 来到末尾，成功找到路径
has_path = False
if 0 <= i < rows
and 0 <= j < cols
and not visited[i][j]
and path[length] == matrix[i * cols + j]:
length += 1
visited[i][j] = 1
has_path = find(i - 1, j, length)
or find(i + 1, j, length)
or find(i, j - 1, length)
or find(i, j + 1, length)
if not has_path: # 上下左右都没找到路径，则回退
visited[i][j] = 0
return has_path
visited = [[False] * cols for _ in range(rows)] # 状态数组保存访问过的字符位置
for i in range(rows):
for j in range(cols): # 遍历以每个格子作为开头的路径
if find(i, j, 0):
return True
return False
机器人的运动范围
题目描述
地上有一个 m 行和 n 列的方格。一个机器人从坐标 (0, 0) 的格子开始移动
每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 k 的格子
例如，当 k 为 18 时，机器人能够进入方格（35, 37），因为 3 + 5 + 3 + 7 = 18
但是，它不能进入方格（35, 38），因为 3 + 5 + 3 + 8 = 19。请问该机器人能够达到多少个格子？
最优题解
经典 DFS 问题：
注意，这里不是寻找路径，而是类似于扫雷
走过的地方发现满足条件就算作能够到达，走不下去了也不必回退
注意这里若去遍历所有位置看是否满足条件是不行的，因为有可能出现‘孤岛’
即这些位置虽然满足条件，但四周并不满足条件，这样机器人是无法到达这些位置的
除了使用 visited 数组标记访问过的位置，还可以进行剪枝：
由于我们从 (0, 0) 出发，因此整体的遍历方向是向右和向下的，不必向左向上遍历
代码
class Solution:
def movingCount(self, threshold, rows, cols):
def can_reach(i, j):
sum = 0
while i or j:
sum += i % 10 + j % 10
i //= 10
j //= 10
return sum <= threshold
def search(i, j):
if 0 <= i < rows and 0 <= j < cols and not visited[i][j] and can_reach(i, j):
# 注意这里and判断条件的顺序，必须先判断 i, j 的有效性
# 否则直接访问 visited 数组有可能越界，而且把 can_reach 放最后判断，减少重复计算
visited[i][j] = True
# search(i - 1, j) # 剪枝
search(i + 1, j)
# search(i, j - 1) # 剪枝
search(i, j + 1)
visited = [[False] * cols for _ in range(rows)]
search(0, 0)
return sum(sum(row) for row in visited)
补充_剪绳子
题目描述
给你一根长度为 n 的绳子，请把绳子剪成 m 段，记每段绳子长度为 k[0], k[1 ]… k[m - 1]
求 k[0]k1…k[m - 1] 的最大值
已知绳子长度 n 为整数，n > 1 且 m > 1(至少要剪一刀，不能不剪)，k[0], k1 … k[m - 1]均要求为整数
例如，绳子长度为 8 时，把它剪成 3 - 3 - 2，得到最大乘积 18;
绳子长度为 3 时，把它剪成 2 - 1，得到最大乘积 2
主要思路
思路1：动态规划（时间 O(n ^ 2)，空间 O(n)）
定义函数 f(n) 为把长度为n的绳子剪成若干段后各段长度乘积的最大值
则状态转移方程为：
f(n) = max(f(i) * f(n - i))，其中 0 < i < n。考虑边界情况：当 n = 2 时，f(2) = 1; 当 n = 3 时，f(3) = 2。递归实现会发生重复计算，所以这里自下而上计算
（从上往下分析问题，从下往上求解问题，用一维或二维数组作备忘录）
思路2： 贪心（时间 O(1)，空间 O(1)）
当 n >= 5 时，尽可能多地剪长度为 3 的绳子；当剩下的绳子长度为 4 时，把绳子剪成两段长度为 2 的绳子
（需要数学证明该贪心策略可以取到最优解，不具有通用性，具体证明见第二版书 P98）
代码
class Solution:
def cuttingRope1(self, length):
if length is None: return
if length < 2: return 0
if length == 2: return 1
if length == 3: return 2
dp = [0] * (length + 1)
dp[1], dp[2], dp[3] = 1, 2, 3 # 注意边界值的填写
for i in range(4, length + 1):
max_val = 0
for j in range(1, (i >> 1) + 1):
dp[i] = max_val = max(max_val, dp[j] * dp[i - j])
return dp[length]
def cuttingRope2(self, length):
if not length: return
if length < 2: return 0
if length == 2: return 1
if length == 3: return 2
numOf3 = length // 3
if length - numOf3 * 3 == 1:
numOf3 -= 1
numOf2 = (length - numOf3 * 3) >> 1
return (3 ** numOf3) * (2 ** numOf2)
补充_数字序列中某一位的数字
题目描述
数字按照 0123456789101112131415161718192021… 的顺序排列
第 5 位（从 0 开始计数）为 5，第 13 位为 1，第 19 位为 4…… 求任意第 n 位对应的数字
最优题解
找出规律跳过若干数字。例如：序列前十位是 0 ~ 9
接下来 180 位数字是 90 个 10 ~ 99 的两位数
接下来的 2700 位是 900 个 100 ~ 999 的三位数。即分组寻找，锁定范围
代码
class Solution:
def digitAtIndex(self, index):
if index is None or index < 0: return
digits = 1 # 表示位数
while True:
numbers = 10 if digits == 1 else 9 * (10 ** (digits - 1)) # digits位数字总共有多少个
if index < numbers * digits: # 在范围内
number = (0 if digits == 1 else 10 ** (digits - 1)) + index // digits # 求出落在哪个数上
for i in range(digits - index % digits - 1): # 右移
number //= 10
return number % 10
index -= digits * numbers # 还没在范围内则继续往后找
digits += 1
补充_把数字翻译成字符串
题目描述
给定一个数字，按照如下规则翻译成字符串：0 翻译成 “a”，1 翻译成 “b”…，25 翻译成 “z”
一个数字有多种翻译可能，例如 12258 一共有 5 种，分别是 bccfi，bwfi，bczi，mcfi，mzi
实现一个函数，用来计算一个数字有多少种不同的翻译方法
最优题解
动态规划（时间 O(n),空间 O(n)）。定义函数 f(i) 表示从第 i 位数字开始的不同翻译的数目，则状态转移方程为
f(i) = f(i + 1) + g(i, i + 1)f(i + 2)
当第 i 位和第 i + 1 位两位数字拼接起来的数字在 10 ~ 25 的范围内时 g(i, i + 1)的值为 1，否则为0
自底向上，在这里为从右向左翻译
注：f(n) = 1，f(n - 1) = f(n) + g(n - 1, n)f(n + 1)，若 g(n - 1,n) 为 1，则易知 f(n - 1) = 2，因此推出 f(n + 1) = 1
该方程类似于青蛙跳台阶，只不过多了 g(i, i + 1) 的限制
代码
class Solution:
def TranslationCount(self, number):
numberStr = str(number)
length = len(numberStr)
if length == 1: return 1
dp = [1] * (length + 1) # 多一个辅助数，相当于 f(n + 1) = 1
for i in range(length - 2, -1, -1):
dp[i] = dp[i + 1] + (dp[i + 2] if (10 <= int(numberStr[i:i + 2]) <= 25) else 0)
return dp[0]
补充_礼物的最大值
题目描述
在一个 m * n 的棋盘的每一个格都放有一个礼物，每个礼物都有一定价值（大于 0）
从左上角开始拿礼物，每次向右或向下移动一格，直到右下角结束
给定一个棋盘，求拿到礼物的最大价值。例如，对于如下棋盘：
1 10 3 8
12 2 9 6
5 7 4 11
3 7 16 5
礼物的最大价值为 1 + 12 + 5 + 7 + 7 + 16 + 5 = 53
最优题解
动态规划（时间 O(m * n),空间 O(n)）
定义函数 f(i, j) 表示到达坐标为 (i, j) 的格子时能拿到的礼物总和的最大值
根据题目要求，有两种可能的途径到达坐标为 (i, j )的格子：通过格子 (i, j - 1) 或 (i - 1, j)
即来自左边格子或上边格子。故状态转移方程为：f(i, j) = max(f(i - 1, j), f(i, j - 1)) + gift[i, j]
gift[i, j] 表示坐标为 (i, j) 的格子里礼物的价值
优化：由于礼物的最大价值只依赖坐标为 (i - 1, j) 和 (i, j - 1) 的两个格子
因此第 i - 1 行及更上面的格子礼物的最大价值实际上不必保存下来。所以可以用一个一维数组作备忘
有两种遍历方式：行优先遍历，即自左向右，自上而下；列优先遍历，自上而下，自左向右
这两种方式都保证了在求 f(i, j) 时已经求出了 f(i -1, j) 和 f(i, j - 1)
注意边界情况：第一行没有来自上边的格子，第一列没有来自左边的格子
代码
class Solution:
def getMaxValue(self, values):
if not values: return 0
cols = len(values[0])
dp = [0] * cols
for i in range(len(values)):
for j in range(cols):
dp[j] = max(dp[j], dp[j - 1] if j > 0 else 0) + values[i][j]
return dp[-1]
补充_最长不含重复字符的字符串长度
题目描述
输入一个字符串（只包含 a ~ z 的字符），求其最长不含重复字符的子字符串的长度
例如对于 arabcacfr，最长不含重复字符的子字符串为 acfr，长度为 4
最优题解
时间 O（n），空间 O（1）（字母种类有限，所以空间为常数）
用两个指针始终记录不重复字符串的头 start 和尾 tail，tail 一直往右边扫描
每当遇到重复的字符（需要一个哈希表记录每个字符曾经出现过的最右的索引）
设该重复字符之前出现的位置为 i，如果 start <= i < tail
则只需把头指针移到 i + 1 的位置即可，否则（i < start）接着往右扫描
当然循环每一步都要更新当前字符出现的最新位置，并且更新最大长度
这里可以稍微优化一下：当出现重复字符并且 start <= i < tail 时
我们令 start = i + 1，则字符串长度一定减小了，可以不用更新字符串长度
换句话说，只有 start 不往右移时我们才去更新最大长度
代码
class Solution:
def LSWD(self, s):
maxLen = start = 0
last = {} # 记录每个字母最近出现的位置
for i, v in enumerate(s): # i一直往右遍历
if v in last and start <= last[v]: # 之前出现过该字母并且最近出现的位置在start到i之间
start = last[v] + 1 # 将start移到上次出现位置的右边
else: # 如果start被右移了就没必要更新maxLen了，因为肯定比原来的小
maxLen = max(maxLen, i - start + 1)
last[v] = i # 新增或更新每个字母最近出现的位置
return maxLen
补充_股票的最大利润
题目描述
假设把某股票的价格按照时间先后顺序存储在数组中
请问买卖交易该股票可能获得的最大利润是多少？
例如一只股票在某些时间节点的价格为 {9, 11, 8, 5, 7, 12, 16, 14}
如果我们能在价格为 5 的时候买入并在价格为 16 时卖出，则能收获最大的利润 11
最优题解
时间 O(n), 空间 O(1)
首先明确一点：买入股票后才能卖出，因此直接用最大值减最小值是不行的，因为最大值可能出现在最小值前面
如果把股票的买入价和卖出价两个数字组成数字对，那么利润就是这个数字对的差值（卖出-买入）
因此，最大利润就是数组中所有数字对的最大差值，显然，在卖出价固定时，买入价越低获得的利润越大
也就是说，如果在遍历到数组中第 i 个数时，只要能够记录下之前的 i - 1 个数字的最小值
就能算出当前价位卖出时可能得到的最大利润，因此算法由左至右遍历，总是获取当前的最小价格（包括当前值）
算出当前价格与当前最小价格的差价（利润）并保存最大利润，注意：当亏损时不买不卖，利润为 0
代码
class Solution:
def maxProfit(self, prices):
# 设置两个变量分别记录最小价格和最大利润
maxProfit, minPrice = 0, float('inf') # 设maxProfit为0可以保证出现负利润时返回0
for price in prices:
minPrice = min(minPrice, price) # 看一下目前有没有更低的价格来买入
profit = price - minPrice # 假如现在卖出能赚多少钱
maxProfit = max(maxProfit, profit) # 记录下最大利润，以便后面作参考比较
return maxProfit