《剑指offer》 刷题记录（Python）

本博客同时发布于个人主页：www.doctorsrn.cn

《剑指offer》 刷题记录

最近使用Python把《剑指offer》刷了一遍，自己能第一时间有想法的题目就直接写，没有思路的题目就看懂书上的思路和参考其他开源的实现后再自己写一遍。主要以牛客网《剑指offer》作为在线评测网站，有些题目牛客网没有的再找其他网站进行在线评测，主要使用的其他网站有：

• AcWing
• LintCode

刷题过程主要参考的开源实现有：

• https://github.com/Lazy-Pig/CodingInterviewChinese2
• https://github.com/apachecn/Interview/tree/master/docs/Algorithm/剑指offer/Python

本博客对应的代码仓库在此。

今年企业缩招，找工作的行情不容乐观，秋招路漫漫啊。

3.数组中重复数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

## 方法一：排序，然后查找
## 时间复杂度：O(nlog n)  空间复杂度：*
# -*- coding:utf-8 -*-
class Solution:# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]# 函数返回True/Falsedef duplicate(self, numbers, duplication):# write code hereif not numbers or len(numbers) <= 1:return Falsefor i in numbers:if i<0 or i > len(numbers)-1:return Falsenumbers_sorted = self.quickSort(numbers)for i,j in zip(numbers_sorted[:-1],numbers_sorted[1:]):if i == j:duplication[0] = ireturn Truereturn Falsedef quickSort(self, arr):if len(arr) <= 1:return arrlength = len(arr)pivot = arr[length // 2]left = [x for x in arr if x > pivot]right = [x for x in arr if x < pivot]mid = [x for x in arr if x == pivot]# 升序排列可以通过，降序排列无法通过全部测试样例return self.quickSort(right) + mid + self.quickSort(left)#return self.quickSort(left) + mid + self.quickSort(right)

## 方法二：引入hash表（字典）
## 时间复杂度：O(n)  空间复杂度：O(n)
# -*- coding:utf-8 -*-
class Solution:# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]# 函数返回True/Falsedef duplicate(self, numbers, duplication):# write code hereif not numbers or len(numbers) <= 1:return Falsefor i in numbers:if i < 0 or i > len(numbers) - 1:return Falsedic = {}for i in numbers:if dic.has_key(i):duplication[0] = ireturn Trueelse:dic[i]=1return False

## 方法三：利用数字自身下标和值的key-value特性
## 时间复杂度：O(n)  空间复杂度：O(1)
# -*- coding:utf-8 -*-
class Solution:# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]# 函数返回True/Falsedef duplicate(self, numbers, duplication):# write code hereif not numbers or len(numbers) <= 1:return Falsefor i in numbers:if i < 0 or i > len(numbers) - 1:return Falsei = 0while i < len(numbers):if i == numbers[i]:i += 1elif numbers[i] == numbers[numbers[i]]:duplication[0] = numbers[i]return Trueelse:tmp = numbers[i]numbers[i] = numbers[tmp]numbers[tmp] = tmpreturn False

4.二维数组的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数

# 方法一：暴力遍历法
# 时间复杂度：O（n^2）
# -*- coding:utf-8 -*-
class Solution:# array 二维列表def Find(self, target, array):# write code hereif len(array) < 1:return Falsefor i in array:for j in i:if target == j:return Truereturn False

# 方法二：反向剔除不满足元素法：从右上角进行查找
# -*- coding:utf-8 -*-
class Solution:# array 二维列表def Find(self, target, array):# write code hereif len(array) < 1 or len(array[0]) < 1:return Falser_l = len(array)c_l = len(array[0])# 从右上角开始搜索i, j = 0, c_l-1while target != array[i][j]:if target > array[i][j]:if i < r_l - 1:i += 1else:return Falseelse:if j > 0:j -= 1else:return Falsereturn True

5.替换空格

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

# 方法一：遍历判断然后替换法，时间复杂度O（n）
# -*- coding:utf-8 -*-
class Solution:# s 源字符串def replaceSpace(self, s):# write code hereif not isinstance(s, str) or len(s) < 1 or s == None:return stmp = []for i in s:if i != ' ':tmp.append(i)else:tmp.append("%20")res = ''.join(tmp)return res

# 方法二：从后向前遍历替换法，时间复杂度O（n）
# -*- coding:utf-8 -*-
class Solution:# s 源字符串def replaceSpace(self, s):# write code hereif not isinstance(s, str) or len(s) < 1 or s == None:return ''spaceN = 0 for i in s:if i == ' ':spaceN += 1total = len(s) + 2 * spaceNnewStr = [None] * totalindexO, indexN = len(s)-1, total-1while indexO >= 0:if s[indexO] == ' ':newStr[indexN]='0'newStr[indexN-1]='2'newStr[indexN-2]='%'indexN -= 3indexO -= 1else:newStr[indexN] = s[indexO]indexN -= 1indexO -= 1return ''.join(newStr)

6.从尾到头打印链表

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

# 方法一： 使用栈
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:# 返回从尾部到头部的列表值序列，例如[1,2,3]def printListFromTailToHead(self, listNode):# write code hereif listNode == None:return []if listNode.next == None:return listNode.valstack = []nextNode = listNodewhile nextNode.next != None:stack.append(nextNode.val)nextNode = nextNode.nextstack.append(nextNode.val)return stack[::-1]

# 方法二：递归的方法# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:# 返回从尾部到头部的列表值序列，例如[1,2,3]def printListFromTailToHead(self, listNode):# write code hereif not listNode:return []if listNode.next == None:res = []res.append(listNode.val)return resre = self.printListFromTailToHead(listNode.next)re.append(listNode.val)return reL=[]
l=ListNode(1)
t = l
for i in range(4):t.next = ListNode(i)t = t.next# while l.next != None:
#     print(l.val)
#     l = l.next
# print(l.val)
s = Solution()
s.printListFromTailToHead(l)

7.重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

# 递归法
# 按照前序遍历和中序遍历的特点进行递归重建
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:# 返回构造的TreeNode根节点def reConstructBinaryTree(self, pre, tin):# write code here# 有效性判断if set(pre) != set(tin):return None# 递归终止条件if len(pre) < 1  or len(tin) < 1:return Noneif len(pre) == 1 or len(tin) == 1:return TreeNode(pre[0])root = pre[0]root_index = tin.index(root)L_tin, R_tin = tin[:root_index], tin[root_index+1:]L_pre, R_pre = pre[1:1+len(L_tin)], pre[1+len(L_tin):]# 构建左树L_child = self.reConstructBinaryTree(L_pre, L_tin)# 构建右树R_child = self.reConstructBinaryTree(R_pre, R_tin)node = TreeNode(root)node.left, node.right = L_child, R_childreturn node

8.二叉树的下一个节点

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

# -*- coding:utf-8 -*-
class TreeLinkNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneself.next = None
# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:def GetNext(self, pNode):# write code hereif not pNode:return pNode# 如果存在右子节点，则下一个节点是右子节点中的最左节点if pNode.right:pNode = pNode.rightwhile pNode.left:pNode = pNode.leftreturn pNode# 如果不存在右子节点，则反向根据父节点和子节点的关系确定else:pC = pNode  # 记录当前节点# 当父节点不为根节点时，如果当前节点是父左子节点，返回当前节点while pNode.next: pN = pNode.nextif pN.left and pN.left == pNode:return pNelse:pC = pNodepNode = pN# 当父节点是根节点时，如果当前节点是根节点的左子节点，则返回根节点if pNode.left and pNode.left == pC:return pNodeelse:return Nonea = TreeLinkNode('a')
b = TreeLinkNode('b')
c = TreeLinkNode('c')
d = TreeLinkNode('d')
e = TreeLinkNode('e')
f = TreeLinkNode('f')
g = TreeLinkNode('g')
h = TreeLinkNode('h')
i = TreeLinkNode('i')
a.left, a.right = b, c
b.left, b.right, b.next = d, e, a
c.left, c.right, c.next = f, g, a
d.next = b
e.left, e.right, e.next = h, i, b
h.next = e
i.next = e
f.next, g.next = c, cs = Solution()
print(s.GetNext(i).val)

9.用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

# -*- coding:utf-8 -*-
class Solution:def __init__(self):self.stack1 = [] # 用于pushself.stack2 = [] # 用于popdef push(self, node):# write code hereself.stack1.append(node)def pop(self):if len(self.stack1) == 0 and len(self.stack2) == 0:return None# stack2不为空时，弹出栈顶元素即为队列头部元素elif len(self.stack2) > 0:  res = self.stack2.pop()return reselse:# stack2为空时，将stack1元素弹出后压入stack2，则stack2栈顶元素即为队列头部元素while len(self.stack1) > 0: i = self.stack1.pop()self.stack2.append(i)res = self.stack2.pop()return res

10. 斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

f ( n ) = { 0 n = 0 1 n = 1 f ( n − 1 ) + f ( n − 2 ) n > 1 f(n) = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ f(n-1)+f(n-2) & n > 1 \end{cases} f(n)=⎩⎪⎨⎪⎧​01f(n−1)+f(n−2)​n=0n=1n>1​

# 方法一：循环法实现
# 时间复杂度为：O（n）
# 自下而上的求解
# -*- coding:utf-8 -*-
class Solution:def Fibonacci(self, n):# write code hereif not isinstance(n,int) or n < 0 or n > 39:return Noneif n == 0:return 0if n == 1:return 1fn1, fn2 = 1, 0for i in range(2,n+1):fn = fn1 + fn2fn2 = fn1fn1 = fnreturn fn

# 方法二：递归法实现----运行超时
# 时间复杂度为n的指数级
# 自上而下的求解
# -*- coding:utf-8 -*-
class Solution:def Fibonacci(self, n):# write code hereif not isinstance(n, int) or n < 0 or n > 39:return 0if n == 0:return 0if n == 1:return 1return self.Fibonacci(n-1) + self.Fibonacci(n-2)

方法三：时间复杂度为$O(logn)$的不实用解法

可证明存在如下公式：
[ f ( n ) f ( n − 1 ) f ( n − 1 ) f ( n − 2 ) ] = [ 1 1 1 0 ] n − 1 \begin{bmatrix} f(n)& f(n-1)\\ f(n-1)& f(n-2) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1} [f(n)f(n−1)​f(n−1)f(n−2)​]=[11​10​]n−1
利用上述公式可以根据 [ 1 1 1 0 ] n − 1 \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1} [11​10​]n−1求得$f(n)$

# 方法一：更简洁的循环实现# -*- coding:utf-8 -*-
class Solution:def Fibonacci(self, n):# write code heretempArray = [0,1]if n >= 2:for i in range(2, n+1):tempArray[i%2] = tempArray[0] + tempArray[1]return tempArray[n%2]

10.2 跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

**分析：**设跳法是台阶数n的函数f(n), n>2时第一次跳有两种跳法，跳一个台阶则共f(n-1)种，跳两个台阶则共f(n-2)种，所以总共f(n)=f(n-1)+f(n-2)

# -*- coding:utf-8 -*-
class Solution:def jumpFloor(self, number):# write code hereif number < 1:return 0if number == 1:return 1if number == 2:return 2fn1 = 2fn2 = 1for i in range(3, number+1):fn = fn1 + fn2fn2 = fn1fn1 = fnreturn fn

10.3 变态跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

**解析：**类比普通跳台阶问题，设跳法是台阶数n的函数f(n), 则有：
$$f(n)=f(n-1)+f(n-2)+...+f(1)+1$$
递推可得：$$f(n-1)=f(n-2)+f(n-3)+...+f(1)+1$$
两式相减可得：$$f(n)-f(n-1)=f(n-1)$$
即$f(n)=2f(n-1)$,即$f(n)$是公比为2的等比级数： f ( n ) = 2 n − 1 f(n)=2^{n-1} f(n)=2n−1

# -*- coding:utf-8 -*-
class Solution:def jumpFloorII(self, number):# write code hereif number < 1:return 0fn = 1if number == 1:return fnfor _ in range(2,number+1):fn *= 2return fn

10.4 矩形覆盖问题

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

# -*- coding:utf-8 -*-
class Solution:def rectCover(self, number):# write code hereif number < 1 or not isinstance(number, int):return 0if number == 1:return 1if number == 2:return 2fn1 = 2fn2 = 1for i in range(3, number+1):fn = fn1 + fn2fn2 = fn1fn1 = fnreturn fn

11.旋转数组中的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

# 方法一：暴力遍历法--不推荐
# 时间复杂度为：O(n)
# -*- coding:utf-8 -*-
class Solution:def minNumberInRotateArray(self, rotateArray):# write code hereif len(rotateArray) < 1:return 0small = rotateArray[0]for i in rotateArray:if small > i:small = ireturn smallreturn small

# 方法二：二分法
# -*- coding:utf-8 -*-
class Solution:def minNumberInRotateArray(self, rotateArray):# write code hereif len(rotateArray) < 1:return 0if len(rotateArray) == 1:return rotateArray[0]index = len(rotateArray) // 2  # index >= 1base = len(rotateArray) // 2while 0<= base < len(rotateArray):if rotateArray[base-1] > rotateArray[base]:  # 如果前一个大于当前数，则当前数为最小return rotateArray[base]elif base + 1 < len(rotateArray) and rotateArray[base] > rotateArray[base+1]: # 如果后一个数存在且小于当前数，则后一个数为最小return rotateArray[base+1]else:# 否则重新搜索，以数组第一个数为基准移动索引if rotateArray[base] > rotateArray[0]:base += index // 2else:base -= index // 2index //= 2return rotateArray[base]## 这个方法存在问题，当针对[1,1,1,1,1,0,1]时无法正常判断，所以应该修改为当base与左右值相等时采用顺序查找的方法搜索最小值
class Solution:def minNumberInRotateArray(self, rotateArray):# write code hereif len(rotateArray) < 1:return 0if len(rotateArray) == 1:return rotateArray[0]index = len(rotateArray) // 2  # index >= 1base = len(rotateArray) // 2while 0<= base < len(rotateArray):if rotateArray[base-1] > rotateArray[base]:  # 如果前一个大于当前数，则当前数为最小return rotateArray[base]elif base + 1 < len(rotateArray) and rotateArray[base] > rotateArray[base+1]: # 如果后一个数存在且小于当前数，则后一个数为最小return rotateArray[base+1]else:# 否则重新搜索，以数组第一个数为基准移动索引if rotateArray[base] > rotateArray[0]:base += index // 2elif rotateArray[base] < rotateArray[0]:base -= index // 2else:  # 顺序查找minNum = self.minSearch(rotateArray)return minNumindex //= 2return rotateArray[base]def minSearch(self, rotateArray):small = rotateArray[0]for i in rotateArray:if small > i:small = ireturn smallreturn small

# 方法三：二分法示例代码
# -*- coding:utf-8 -*-
class Solution:def minNumberInRotateArray(self, rotateArray):# write code hereif len(rotateArray) < 1:return 0if len(rotateArray) == 1:return rotateArray[0]# 双指针first = 0end = len(rotateArray)-1while end - first != 1:mid = (first + end) // 2if rotateArray[first] == rotateArray[mid] == rotateArray[end]: # 特殊情况，使用顺序查找minN = rotateArray[0]for i in rotateArray[1:]:if i < minN:minN = ireturn minNelif rotateArray[first] < rotateArray[end]:  # 特殊情况，整个数组是升序，没有进行旋转return rotateArray[first]elif rotateArray[mid] >= rotateArray[first]:first = midelse:end = midreturn rotateArray[end]

12.矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 [ a b c e s f c s a d e e ] \begin{bmatrix} a & b & c & e \\ s & f & c & s \\ a & d & e & e \end{bmatrix} ⎣⎡​asa​bfd​cce​ese​⎦⎤​ 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

# 回溯法--使用递归实现
# -*- coding:utf-8 -*-
class Solution:def hasPath(self, matrix, rows, cols, path):# write code hereif len(matrix) < 1 or rows < 1 or cols < 1 or len(path) < 1:return Falsevisited = [0] * (rows * cols)pathL = 0for row in range(rows):for col in range(cols):if self.if_has_path(matrix, rows, cols, path, row, col, visited, pathL):return Truereturn Falsedef if_has_path(self, matrix, rows, cols, path, row, col, visited, pathL):# 递归终止条件if pathL == len(path):return TruehasPath = Falseif 0 <= row < rows and 0 <= col < cols and \matrix[row * cols + col] == path[pathL] and \not visited[row * cols + col]:pathL += 1visited[row * cols + col] = 1hasPath = self.if_has_path(matrix, rows, cols, path, row-1, col, visited, pathL) or \self.if_has_path(matrix, rows, cols, path, row+1, col, visited, pathL) or \self.if_has_path(matrix, rows, cols, path, row, col-1, visited, pathL) or \self.if_has_path(matrix, rows, cols, path, row, col+1, visited, pathL)if not hasPath:pathL -= 1visited[row * cols + col] = 0return hasPath

13.机器人的运动范围

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

# 回溯法
# -*- coding:utf-8 -*-
class Solution:def movingCount(self, threshold, rows, cols):# write code hereif threshold < 1 or rows < 1 or cols < 1:return 0visited = [0] * (rows * cols)    # 记录当前位置是否访问过available = [0] * (rows * cols)  # 记录当前位置是否可达self.ifAvailable(threshold, rows, cols, 0, 0, visited, available)return sum(available)def ifTrue(self, row, col, threshold):res = 0while row != 0:res += row % 10row //= 10while col != 0:res += col % 10col //= 10if res <= threshold:return Trueelse:return Falsedef ifAvailable(self, threshold, rows, cols, row, col, visited, available):if 0 <= row < rows and 0 <= col < cols and self.ifTrue(row, col, threshold) and \not visited[row * cols + col]:available[row * cols + col] = 1visited[row * cols + col] = 1self.ifAvailable(threshold, rows, cols, row-1, col, visited, available)self.ifAvailable(threshold, rows, cols, row+1, col, visited, available)self.ifAvailable(threshold, rows, cols, row, col-1, visited, available)self.ifAvailable(threshold, rows, cols, row, col+1, visited, available)else:# visited[row * cols + col] = 0return

# 回溯法--示例代码
# -*- coding:utf-8 -*-
class Solution:def movingCount(self, threshold, rows, cols):visited = [False] * (rows * cols)count = self.movingCountCore(threshold, rows, cols, 0, 0, visited)return countdef movingCountCore(self, threshold, rows, cols, row, col, visited):count = 0if self.check(threshold, rows, cols, row, col, visited):visited[row * cols + col] = Truecount = 1 + self.movingCountCore(threshold, rows, cols, row-1, col, visited) + \self.movingCountCore(threshold, rows, cols, row+1, col, visited) + \self.movingCountCore(threshold, rows, cols, row, col-1, visited) + \self.movingCountCore(threshold, rows, cols, row, col+1, visited)return countdef check(self, threshold, rows, cols, row, col, visited):if row >= 0 and row < rows and col >= 0 and col < cols and self.getDigitSum(row) + self.getDigitSum(col) <= threshold and not visited[row * cols + col]:return Truereturn Falsedef getDigitSum(self, number):sum = 0while number > 0:sum += (number % 10)number = number // 10return sum

14.剪绳子

与leetcode 343题一样，中文版：
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

注意：存储最优解的数组的前三个值是剪开后或者不剪情况下绳子的最大值，而不仅仅是剪开后乘积的最大值
参考题解：https://blog.csdn.net/weixin_41796401/article/details/84899457

# 方法一：动态规划法
# 时间复杂度为O（n^2）,空间复杂度为O（n）
class Solution(object):def integerBreak(self, n):""":type n: int:rtype: int"""if n < 2:return 0if n == 2:return 1if n == 3:return 2# mem[0] not used# ！！！ mem中存储的是剪开后或者不剪情况下绳子的最大值，而不仅仅是剪开后乘积的最大值mem = [0] * (n+1)  mem[1], mem[2], mem[3] = 1, 2, 3  for i in range(4, n+1):max_product = 0for j in range(1, i//2+1):max_product = max(max_product, mem[j] * mem[i-j])mem[i] = max_productreturn mem[n]

# 方法二：贪婪法
# 证明：n > 4时，3(n-3) >= 2(n-2) > n
# 尽可能多的将数分解成3，当余下是4时，分解成2*2
class Solution(object):def integerBreak(self, n):""":type n: int:rtype: int"""if n < 2:return 0if n == 2:return 1if n == 3:return 2p = (n // 3)r = (n % 3)if r == 0:return pow(3, p)elif r == 1:return pow(3, p-1)*4elif r == 2:return pow(3, p) *2

15.二进制中1的个数

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

解析：

• 使用位运算的效率高于除法
• 负数的右移运算会在高位进行补1，如果没考虑这一点，可能导致程序陷入死循环
• 可以使用与运算实现1的个数统计

# 方法一：常规不会陷入死循环的方法
# -*- coding:utf-8 -*-
class Solution:def NumberOf1(self, n):# write code hereif n == 0:return 0# 设置循环终止条件MAX_INT = (1 << (32-1)) flag = 1count = 0while n and flag <= MAX_INT :if n & flag:count += 1n -= flagflag = flag << 1return count

# 方法二：技巧性方法：正数减去1，再和原来的数做与运算，会把正数最右边的1变成0
# 参考：https://www.cnblogs.com/klchang/p/8017627.html
# 或者根据负数补码的特点，使用模将负数转化：n = n & 0xffffffff，然后再进行减1做与运算
# -*- coding:utf-8 -*-
class Solution:def NumberOf1(self, n):# write code hereif n == 0:return 0count = 0# 假设系统的整数是四字节，由于python自身整数是8字节，所以手动设置整数的界限# 例如-1在8字节情况下的补码是：1111.......1111(64个)，在4字节下1111.......1111(32个)MAX_INT = 1 << (32-1)while n != 0:if -MAX_INT > n or n > MAX_INT:  # 主要是针对负数，当n为负数时，随着n = n & (n-1)，n将越界break                        # 如果不添加该终止循环的条件，程序将陷入死循环count += 1n = n & (n-1)return count

16.数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

# 方法一：普通方法
# 注意边界条件的控制、功能的测试、
# -*- coding:utf-8 -*-
class Solution:def Power(self, base, exponent):# write code hereif base == 0:return 0res = 1if exponent == 0:return reselif exponent > 0:for _ in range(exponent):res *= basereturn reselse:for _ in range(abs(exponent)):res *= baseif res != 0:return 1/reselse:return 

方法二：高效法

利用如下的递推公式：
a n = { a n / 2 ⋅ a n / 2 n 为 偶 数 a ( n − 1 ) / 2 ⋅ a ( n − 1 ) / 2 ⋅ a n 为 奇 数 a^n = \begin{cases} a^{n/2}\cdot a^{n/2} & n 为偶数 \\ a^{(n-1)/2}\cdot a^{(n-1)/2}\cdot a & n 为奇数 \end{cases} an={an/2⋅an/2a(n−1)/2⋅a(n−1)/2⋅a​n为偶数n为奇数​

# -*- coding:utf-8 -*-
class Solution:def Power(self, base, exponent):# write code here# 要考虑base=0而exponent为负数这种异常情况的处理if base == 0 and exponent < 0:raise Exception('Error: base is zero ')if base == 0:return 0if exponent == 0:return 1if exponent > 0:return self.power_re(base, exponent)else:return 1/self.power_re(base, abs(exponent))# 递归求解def power_re(self, base, exponent):if exponent == 1:return baseif (exponent & 0x1) == 0:return self.power_re(base, (exponent >> 1))*self.Power(base, (exponent >> 1))else:return self.power_re(base, ((exponent-1) >> 1)) * self.Power(base, ((exponent-1) >> 1))*base

17. 打印1到最大的n位数

解析：主要需要解决大数问题

# 方法一：使用字符串数组解决大数问题，实现进位功能
class Solution:def Print1ToMaxofNDigits(self, n):if n < 1:raise Exception('invalid input n')str_num = ['0'] * nwhile True:# 确定进位的位置i = len(str_num) - 1while str_num[i] == '9' and i > 0:i -= 1# 打印结束终止条件if str_num[0] == '9' and i == 0:break# 不需要进位if i == len(str_num)-1:str_num[i] = str(int(str_num[i])+1)self.Print(str_num)# 需要进位else:str_num[i] = str(int(str_num[i])+1)for j in range(i+1,len(str_num)):str_num[j] = '0'self.Print(str_num)def Print(self, str_num):index = 0for i in range(len(str_num)):if str_num[i] != '0': index = ibreakprint(''.join(str_num[index:]))s = Solution()
s.Print1ToMaxofNDigits(3)   

# 方法二：使用数字排列的方法实现
# 使用递归实现数字排列：从上到下分析，从下到上实现。。
# 从上到下分析：从最高位开始排列，高位排列完后排列低一位，直到排列完最低位
class Solution:def Print1ToMaxofNDigits(self, n):if n < 1:raise Exception('invalid input n')str_num = ['0'] * nfor i in range(10):str_num[0] = str(i)self.recursivePrint1ToMaxofNDigits(str_num, len(str_num), index=0)def recursivePrint1ToMaxofNDigits(self, str_num, length, index):# 递归终止条件if index == length - 1:self.Print(str_num)returnfor i in range(10):str_num[index + 1] = str(i)self.recursivePrint1ToMaxofNDigits(str_num, length, index + 1)def Print(self, str_num):index = -1for i in range(len(str_num)):if str_num[i] != '0': index = ibreakif index != -1:print(''.join(str_num[index:]))        s = Solution()
s.Print1ToMaxofNDigits(2) 

18.删除链表节点

题目一：在$O(1)$时间内删除链表节点

给定单向链表的头指针和一个节点指针，定义一个函数在$O(1)$时间内删除该节点。

lintcode: https://www.lintcode.com/problem/delete-node-in-a-linked-list/description

# 解题思路：将要删除节点的下一个节点复制到当前节点即可
"""
Definition of ListNode
class ListNode(object):def __init__(self, val, next=None):self.val = valself.next = next
"""class Solution:"""@param: node: the node in the list should be deleted@return: nothing"""def deleteNode(self, node):# write your code hereif not node or not node.next:node = Nonereturnnode.val = node.next.valnode.next = node.next.next

题目二：删除链表中的重复节点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

# 标准解答：https://github.com/apachecn/awesome-algorithm/blob/master/docs/%E5%89%91%E6%8C%87offer/Python/56-%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E4%B8%AD%E9%87%8D%E5%A4%8D%E7%9A%84%E7%BB%93%E7%82%B9.py
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:def deleteDuplication(self, pHead):# write code hereif pHead is None or pHead.next is None:return pHeadfirst = ListNode(-1)first.next = pHeadlast = first  # 记录上一个有效节点# 遍历不重复节点，更新last自身和last指向的节点while pHead and pHead.next:if pHead.val == pHead.next.val:# 遍历得到与当前值不相等的节点，并将last指向该节点val = pHead.valwhile pHead and val == pHead.val:pHead = pHead.nextlast.next = pHeadelse:# 如果当前节点有效，则更新last节点last = pHeadpHead = pHead.nextreturn first.next

19. 正则表达式的匹配

请实现一个函数用来匹配包括’.‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配

题解参考:递归求解，根据s和pattern长度不同进行分情况讨论：

• 递归终止条件的确定：s和pattern长度均为0，或s不为0而pattern为0
• s长度为0，pattern长度不为0
• s和pattern长度都不为0，此时根据pattern第二位是否为"*"进行分情况讨论
  • pattern第二位不为"*"，s和pattern比较后各后移一位
  • pattern第二位为"*"，根据首位是否相等讨论：
    • 首位不相等，则s不变，pattern向后移动2位，相当于pattern前两位当成空
    • 首位相等，则有三种情况：
      1. pattern后移2位，s不变；相当于把pattern前两位当成空，匹配后面的
      2. pattern后移2位，s后移1位；相当于pattern前两位与s[0]匹配
      3. pattern不变，s后移1位；相当于pattern前两位与s中的多位进行匹配

另外可以使用动态规划来优化递归，参考题解。

# -*- coding:utf-8 -*-
class Solution:# s, pattern都是字符串def match(self, s, pattern):# write code here#if not s and not pattern:#    return Falsereturn self.match_recursion(s, pattern)def match_recursion(self, s, pattern):# 递归终止条件if len(s) == 0 and len(pattern) == 0:return Trueelif len(s) != 0 and len(pattern) == 0:return Falseelif len(s) == 0 and len(pattern) != 0:if len(pattern) > 1 and pattern[1] is "*":return self.match_recursion(s, pattern[2:])else:return Falseelse:# s和pattern都不为空if len(pattern) > 1 and pattern[1] is "*":# s和pattern第一个元素不相同,则s不变，pattern向后移动2位，相当于pattern前两位当成空if s[0] != pattern[0] and pattern[0]  != ".":return self.match_recursion(s, pattern[2:])else:# 如果s[0]和pattern[0]相同，此时有三种情况# 1.pattern后移2位，s不变；相当于把pattern前两位当成空，匹配后面的# 2.pattern后移2位，s后移1位；相当于pattern前两位与s[0]匹配# 3.pattern不变，s后移1位；相当于pattern前两位与s中的多位进行匹配return self.match_recursion(s,pattern[2:]) or self.match_recursion(s[1:], pattern[2:]) or self.match_recursion(s[1:], pattern)else:if s[0] == pattern[0] or pattern[0] is ".":return self.match_recursion(s[1:], pattern[1:])else:return False

20.表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示数值。 但是"12e",“1a3.14”,“1.2.3”,"±5"和"12e+4.3"都不是。

# -*- coding:utf-8 -*-
class Solution:# s字符串def isNumeric(self, s):# write code hereif len(s) < 1:return Falsedot_index = -1e_index = -1for i in range(len(s)):if s[i] is '.':dot_index = iif s[i] is 'e' or s[i] is 'E':e_index = ibreakres = Trueif dot_index > 0:# 小数点不在首位res = res and self.isInt(s[:dot_index], 1)if e_index > 0:# 存在e或者Eres = res and self.scanInt(s[dot_index+1:e_index])res = res and self.isInt(s[e_index+1:], 0)else:res = res and self.scanInt(s[dot_index+1:])elif dot_index == 0:# 小数点在首位if e_index > 0:# 存在e或者Eres = res and self.scanInt(s[dot_index+1:e_index])res = res and self.isInt(s[e_index+1:], 0)else:res = res and self.scanInt(s[dot_index+1:])else:# 不存在小数点if e_index > 0:# 存在e或者E  -+Eif s[dot_index+1] == '-' or s[dot_index+1] == '+':res = res and self.scanInt(s[dot_index+2:e_index])else:res = res and self.scanInt(s[dot_index+1:e_index])res = res and self.isInt(s[e_index+1:], 0)else:# 不存在小数点和Eres = res and self.isInt(s[dot_index+1:], 0)return resdef isInt(self, s, case):# 是否是整形数字，即“-+”在首位的0--9数字# case = 1：表示要判断的部分在数字的开头，此时可以仅有“-+”，而没有数字if len(s) < 1:return Falseif s[0] == '+' or s[0] == '-':if len(s) == 1 and case:return Trueelse:return self.scanInt(s[1:])else:return self.scanInt(s[0:])def scanInt(self, s):# 必须在0--9之间if len(s) < 1:return Falsea = [str(x) for x in range(10)] for i in s:if not i in a:return Falsereturn True

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

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

# -*- coding:utf-8 -*-
class Solution:def reOrderArray(self, array):if len(array) < 1:return array# write code hereodd_number = []even_number = []for i in array:if i%2 == 1:odd_number.append(i)else:even_number.append(i)return odd_number+even_number

22.链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个结点

# 方法1：先计数，在输出
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def FindKthToTail(self, head, k):# write code hereif head is None or k == 0:return Nonecount = 1temp = headwhile temp.next != None:count += 1temp = temp.nextif count < k:return Noneelse:k = count - kcount = 0while count != k:count += 1head = head.nextreturn head

# 方法二：双指针法，使用两个间隔为k-1的指针
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def FindKthToTail(self, head, k):# write code hereif head is None or k == 0:return NonefP = headsP = headcount = 0while count < k:# 注意对fP是否为空的判断if fP is None:return NonefP = fP.nextcount += 1while fP != None:fP = fP.nextsP = sP.nextreturn sP

23.链表中环的入口节点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:def EntryNodeOfLoop(self, pHead):# write code hereif pHead is None:return Nonenode_num = self.hasCircle(pHead)if node_num == 0:return Noneelse:# 存在环，环中节点数为node_num,查找环的入口节点fP = pHead # first pointsP = pHead # second pointcount = 0while count < node_num:fP = fP.nextcount += 1while fP != sP:fP = fP.nextsP = sP.nextreturn sPdef hasCircle(self, pHead):# 判断是否存在circle，返回0表示不存在，返回正整数表示环中节点个数fast = pHeadslow = pHeadwhile fast != None:# fast 移动两步，slow移动一步fast = fast.nextif fast == None:breakfast = fast.nextslow = slow.nextif fast == slow:# 存在环，统计环中节点的个数num = 1fast = fast.nextwhile fast != slow:num += 1fast = fast.nextreturn numreturn 0

24.反转链表

输入一个链表，反转链表后，输出新链表的表头。

# 借助三个指针，一边遍历链表一边修改当前节点的指向，直到遍历完整个链表
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:# 返回ListNodedef ReverseList(self, pHead):# write code hereif pHead is None:return Noneprevious_p = pHeadcurrent_p = pHead.nextif current_p is None:# 只有一个节点return pHeadnext_p = current_p.nextif next_p is None:# 只有两个节点previous_p.next = Nonecurrent_p.next = previous_preturn current_p#节点数大于等于3,借助三个指针一边遍历一边修改指向previous_p.next = Nonewhile next_p != None:current_p.next = previous_p# 更新各个指针指向。向前移动previous_p = current_pcurrent_p = next_pnext_p = next_p.nextcurrent_p.next = previous_preturn current_p

# 方法二：递归法实现，从尾部开始修改指向
# -*- coding:utf-8 -*-
class ListNode:def __init__(self, x):self.val = xself.next = None
class Solution:# 返回ListNodedef ReverseList(self, pHead):# write code hereif pHead is None:return Noneprevious_p = pHeadcurrent_p = pHead.nextif current_p is None:# 只有一个节点return pHead#节点数大于等于2,递归实现反转previous_p.next = Nonereturn self.Rev_recursion(previous_p, current_p)def Rev_recursion(self, pre, cur):# 递归终止条件：遍历至尾节点if cur.next is None:cur.next = prereturn curnext_node = cur.next  # 保存当前节点下一节点的指向cur.next = pre  # 修改当前节点指向上一节点return self.Rev_recursion(cur, next_node)def PrintList(self, pHead):while pHead.next != None:print(pHead.val)pHead =pHead.nextprint(pHead.val)# test
a = ListNode(1)
b = ListNode(2)
c = ListNode(3)
d = ListNode(4)
a.next = b
b.next = c
c.next = ds=Solution()
h = s.ReverseList(a)
s.PrintList(h)

4
3
2
1

25.合并两个排序链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

Tips：python对象如果是结构体或类，则把对象的引用值修改，那么原始对象的值也会被改变。

# 方法1:确定头节点后，将另一个链表插入头节点所在的链表
# -*- coding:utf-8 -*-
class ListNode:def __init__(self, x):self.val = xself.next = None
class Solution:# 返回合并后列表def Merge(self, pHead1, pHead2):# write code hereif pHead1 is None:return pHead2elif pHead2 is None:return pHead1# 确定头结点if pHead1.val > pHead2.val:head = self.insertMerge(pHead2, pHead1)else:head = self.insertMerge(pHead1, pHead2)return headdef insertMerge(self, head, insertL):# head指头节点所在的链表，insertL链表中的元素将被插入head指向的链表pHead = headinsert_h = insertLwhile pHead.next != None:pre1 = pHeadcur1 = pHead.nextinsert_p = insert_hif insert_p.val <= cur1.val:# 介于两个节点之间，满足插入条件，插入后移动head所在链表和insertL链表# ！！！！必须先更新，在重新连接节点，否则变量的值已经被改变# 如果按照注释中的顺序执行，则变量pHead和insert_h的值就会收到前面赋值的影响# 此处insert_h值的更新必须要在insert_p.next的赋值之前，因为结构体内部值的改变会间接改变原始变量的值
#                 pre1.next = insert_p
#                 insert_p.next = cur1
#                 pHead = pHead.next
#                 insert_h = insert_h.nextpHead = pHead.nextinsert_h = insert_h.nextpre1.next = insert_pinsert_p.next = cur1else:# 不满足插入条件，移动head所在链表，insertL链表不动pHead = pHead.nextif insert_h != None:pHead.next = insert_hreturn headdef PrintList(self, pHead):while pHead.next != None:print(pHead.val)pHead =pHead.nextprint(pHead.val)a = ListNode(1)
b = ListNode(3)
c = ListNode(5)
d = ListNode(7)
a.next = b
b.next = c
c.next = de = ListNode(2)
f = ListNode(4)
g = ListNode(6)
h = ListNode(8) 
e.next = f
f.next = g
g.next = hs = Solution()
h = s.Merge(a, e)
# s.PrintList(h)

# 方法二：递归法
# 只对两个链表的头节点进行重排，直到其中一个链表排至尾部时终止
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:# 返回合并后列表def Merge(self, pHead1, pHead2):# write code here# 递归终止条件if pHead1 is None:return pHead2elif pHead2 is None:return pHead1if pHead1.val < pHead2.val:pHead1.next = self.Merge(pHead1.next, pHead2)return pHead1else:pHead2.next = self.Merge(pHead1, pHead2.next)return pHead2

26.树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:def HasSubtree(self, pRoot1, pRoot2):# write code here# 特殊边界情况判断if pRoot1 is None or pRoot2 is None:return Falseres = Falseif pRoot1.val == pRoot2.val:res = self.isEqual(pRoot1, pRoot2)if not res:# 当前节点不相等则继续递归遍历树if pRoot1.left != None:res = self.HasSubtree(pRoot1.left, pRoot2)if not res and pRoot1.right != None:res = self.HasSubtree(pRoot1.right, pRoot2)return resdef isEqual(self, pRoot1, pRoot2):# 递归终止条件if pRoot2 is None :return Trueif pRoot1 is None:return Falseif pRoot2.val == pRoot1.val:res = self.isEqual(pRoot1.left, pRoot2.left)else:return False# 递归res = res and self.isEqual(pRoot1.left, pRoot2.left) and self.isEqual(pRoot1.right, pRoot2.right)return res

27.二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：
源二叉树

    	    8/  \6   10/ \  / \5  7 9 11

镜像二叉树

    	    8/  \10   6/ \  / \11 9 7  5

非递归实现：

• 借助于栈，先交换两棵子树，再求完一棵子树的镜像后在求还有一棵子树的镜像（纵向，深度优先）
• 借助于队列以用广度优先的顺序遍历一遍实现逐层镜像（横向，广度优先）

# 递归法
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:# 返回镜像树的根节点def Mirror(self, root):# write code here# 异常情况判断if root is None:return# 递归终止条件：遍历至非叶子节点if root.left is None and root.right is None:returnif root.left != None and root.right != None:root.left, root.right = root.right, root.leftself.Mirror(root.left)self.Mirror(root.right)elif root.left != None and root.right is None:root.left, root.right = None, root.leftself.Mirror(root.right)elif root.left is None and root.right != None:root.left, root.right = root.right, Noneself.Mirror(root.left)return 

# 更简洁的递归实现
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:# 返回镜像树的根节点def Mirror(self, root):# write code here# 异常情况判断if root is None:return# 递归终止条件：遍历至非叶子节点if root.left is None and root.right is None:returnroot.left, root.right = root.right, root.leftself.Mirror(root.left)self.Mirror(root.right)return 

28.对称的二叉树

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:def isSymmetrical(self, pRoot):# write code here# 空树对称if pRoot is None:return Truereturn self.issymm_recursion(pRoot.left, pRoot.right)def issymm_recursion(self, left, right):# 如果左右节点均为None，则遍历结束，且满足对称if left is None and right is None:return True# 反之仅有一个节点为空则不满足对称if left is None or right is None:return False# 当两个节点均不为空时，对其值进行判断res = Falseif left.val == right.val: # 两个节点的值相等时，对其子节点进行递归判断# 对称前序遍历递归实现res = self.issymm_recursion(left.left, right.right)res = res and self.issymm_recursion(left.right, right.left)return res

# 更简洁的参考实现：
# https://github.com/apachecn/awesome-algorithm/blob/master/docs/%E5%89%91%E6%8C%87offer/Python/58-%E5%AF%B9%E7%A7%B0%E7%9A%84%E4%BA%8C%E5%8F%89%E6%A0%91.py
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:def isSymmetrical(self, pRoot):# write code herereturn self.selfIsSym(pRoot,pRoot)def selfIsSym(self,root1,root2):if root1 == root2 and root2 == None:return Trueif root1 == None or root2 == None:return Falseif root1.val != root2.val:return Falsereturn self.selfIsSym(root1.left, root2.right) and self.selfIsSym(root1.right,root2.left)

29.顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 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.

# 方法一：借助四个数指定打印范围
# -*- coding:utf-8 -*-
class Solution:# matrix类型为二维列表，需要返回列表def printMatrix(self, matrix):# write code hereif len(matrix) < 1:return Noneif len(matrix[0]) <= 1:m = [x[0] for x in matrix]return mrow_len = len(matrix) # 行col_len = len(matrix[0]) # 列# 四个数确定打印的边界a, b, c, d = 0, row_len-1, 0, col_len-1m = []while a <= b and c <= d:# 在当前边界条件下打印一次m = m + self.Print(matrix, a, b, c, d)# 更新边界a += 1b -= 1c += 1d -= 1return mdef Print(self, matrix, a, b, c, d):m = []# 打印过程为：先横向右移，再纵向下移，再横向左移，最后纵向上移m = matrix[a][c:d+1] # 横向右移打印# 如果a=b，则只需要横向打印一次即完成打印if a == b:return mm = m + [x[d] for x in matrix[a+1:b+1]] # 纵向下移打印if c == 0: #横向左移打印m = m + (matrix[b][d-1::-1])else:m = m + (matrix[b][d-1:c-1:-1])m = m + ([x[c] for x in matrix[b-1:a:-1]]) # 纵向上移打印return ms = Solution()
a = [[1,2],[3,4]]
s.printMatrix(a)

[1, 2, 4, 3]

# 方法二：根据规律左上角的坐标中行标和列标总是相等的
# 参考代码
# https://github.com/apachecn/awesome-algorithm/blob/master/docs/%E5%89%91%E6%8C%87offer/Python/19-%E9%A1%BA%E6%97%B6%E9%92%88%E6%89%93%E5%8D%B0%E7%9F%A9%E9%98%B5.pyclass Solution:# matrix类型为二维列表，需要返回列表def printMatrix(self, matrix):if not matrix:return []rows = len(matrix)columns = len(matrix[0])start = 0result = []while rows > start * 2 and columns > start * 2:self.PrintMatrixInCircle(matrix, columns, rows, start,result)start += 1return result    def PrintMatrixInCircle(self, matrix, columns, rows,start,result):endX = columns - 1 - startendY = rows - 1 - start# 从左到右打印一行for i in range(start, endX+1):#number = matrix[start][i]result.append(matrix[start][i])# 从上到下打印一行if start < endY:for i in range(start+1, endY+1):#number = matrix[i][endX]result.append(matrix[i][endX])# 从右到左打印一行if start < endX and start < endY:for i in range(endX-1, start-1, -1):#number = matrix[endY][i]result.append(matrix[endY][i])# 从下到上打印一行if start < endX and start < endY-1:for i in range(endY-1, start, -1):#number = matrix[i][start]result.append(matrix[i][start])

30.包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

# 借助辅助栈实现
# -*- coding:utf-8 -*-
class Solution:def __init__(self):self.stack = []self.assist_stack = []def push(self, node):# write code hereself.stack.append(node)if len(self.assist_stack) < 1:self.assist_stack.append(node)elif node < self.assist_stack[-1]:self.assist_stack.append(node)else:self.assist_stack.append(self.assist_stack[-1])def pop(self):# write code hereif len(self.stack) < 1:return Noneelse:self.assist_stack.pop()return self.stack.pop()def top(self):# write code herereturn self.stack[-1]def min(self):# write code herereturn self.assist_stack[-1]

31.栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

# 方法：借助辅助栈实现
# -*- coding:utf-8 -*-
class Solution:def IsPopOrder(self, pushV, popV):# write code hereif len(pushV) != len(popV):return Falseelif len(pushV) < 1:return Truestack = []for i in popV:# 辅助栈为空时，根据情况向辅助栈压入一个元素if len(stack) < 1:if len(pushV) < 1:return Falseelse:stack.append(pushV.pop(0))while i != stack[-1]:# 判断辅助栈栈顶元素是否和当前弹出元素相等，不相等则将压入序列中元素不断压入辅助栈，直到发现相等元素if len(pushV) < 1:# 如果压入序列为空，则没有元素可以匹配，所以不满足弹出顺序return Falseelse:stack.append(pushV.pop(0))# 如果弹出序列和辅助栈栈顶元素相等则，将辅助栈栈顶元素弹出stack.pop()return True

# 参考实现# -*- coding:utf-8 -*-
class Solution:def IsPopOrder(self, pushV, popV):# write code hereif pushV == [] or popV == []:return Falsestack = []for i in pushV:stack.append(i)while len(stack) and stack[-1] == popV[0]:stack.pop()popV.pop(0)if len(stack): return Falseelse:return True

32.从上到下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

# 方法：借助辅助队列实现
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:# 返回从上到下每个节点值列表，例：[1,2,3]def PrintFromTopToBottom(self, root):# write code hereif root is None:return []que = []res = []que.append(root)while len(que) >= 1:node = que.pop(0)res.append(node.val)if node.left != None:que.append(node.left)if node.right != None:que.append(node.right)return res

32.2 把二叉树打印成多行

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

# -*- coding:utf-8 -*-
# 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):# write code hereif pRoot is None:return []que1 = []  # 存储每行元素构成的队列，que1是二维数组que2 = []  # 将一行元素作为队列存储que2.append(pRoot)que1.append(que2)res = [] # 存储最终结果，是二维数组res1 = [] # 存储每一行打印的结果while len(que1) >= 1:# 打印所有行nodes = que1.pop(0)que2 = []for node in nodes:# 打印一行res1.append(node.val)if node.left != None:que2.append(node.left)if node.right != None:que2.append(node.right)if len(que2) >= 1:que1.append(que2)# 存储当前行打印的结果res.append(res1)res1 = []return res

32.3 之字形打印二叉树

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:def Print(self, pRoot):# write code hereif pRoot is None:return []count = 1  # 打印层数记录res, res1 = [], []nodes = [pRoot]while nodes:que = []if count % 2 == 1:for node in nodes:res1.append(node.val)# 节点存储顺序由左至右，然后翻转if node.left != None:que.append(node.left)if node.right != None:que.append(node.right)else:for node in nodes:res1.append(node.val)# 节点存储顺序由右至左，然后翻转if node.right != None:que.append(node.right)if node.left != None:que.append(node.left)nodes = que[::-1]res.append(res1)res1 = []count += 1return res

33.二叉搜索树的后续遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

# -*- coding:utf-8 -*-
class Solution:def VerifySquenceOfBST(self, sequence):# write code hereif len(sequence) == 0:return Falsereturn self.recursion_verify(sequence) def recursion_verify(self, sequence):if len(sequence) <= 1:return Trueroot = sequence[-1]for i in range(len(sequence)-1):if sequence[i] > root:break# 如果只有左子树，仅对左子树递归判断if i == len(sequence)-2:return self.recursion_verify(sequence[0:i])for j in sequence[i:-1]:if j < root:return False# 左右子树都有节点，则对左右子树递归判断return self.recursion_verify(sequence[0:i]) and self.recursion_verify(sequence[i:-1])s=Solution()
# a = [4,8,6,12,16,14,10]
a = [5,4,3,2,1]
print(s.VerifySquenceOfBST(a))

True

34.二叉树中和为某一值的函数

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

# 方法：递归法
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:# 返回二维列表，内部每个列表表示找到的路径def FindPath(self, root, expectNumber):# write code hereif root is None:return []stack = []  # 辅助栈，存储路径节点path = []  # 存储路径sums = root.val # 和值stack.append(root)res = self.recursion_find(root, expectNumber, stack, sums, path)return resdef recursion_find(self, root, expectNumber, stack, sums, path):# 递归终止条件：递归至叶节点# 或只有根节点的情况if root.left is None and root.right is None:if sums == expectNumber:res = [x.val for x in stack]  # 将路径节点转换为值列表path.append(res)return pathelse:return pathelse:  #VLR前序递归if root.left != None:  # 递归左节点stack.append(root.left)sums += root.left.val self.recursion_find(root.left, expectNumber, stack, sums, path)stack.pop() # 一次递归结束后弹出当前节点，并恢复原来的和值sums -= root.left.valif root.right != None:  # 递归右节点stack.append(root.right)sums += root.right.valself.recursion_find(root.right, expectNumber, stack, sums, path)stack.pop() # 一次递归结束后弹出当前节点，并恢复原来的和值sums -= root.right.valreturn sorted(path, key=lambda x: -len(x))  # 降序排列

# 参考解法
# https://github.com/apachecn/awesome-algorithm/blob/master/docs/%E5%89%91%E6%8C%87offer/Python/24-%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E5%92%8C%E4%B8%BA%E6%9F%90%E4%B8%80%E5%80%BC%E7%9A%84%E8%B7%AF%E5%BE%84.py
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:# 返回二维列表，内部每个列表表示找到的路径def FindPath(self, root, expectNumber):# write code hereif not root or root.val > expectNumber:  # 没有找到路径，递归终止return []if not root.left and not root.right and root.val == expectNumber:  # 找到路径return [[root.val]]else:expectNumber -= root.valleft = self.FindPath(root.left,expectNumber)right = self.FindPath(root.right,expectNumber)result = [[root.val]+i for i in left]for i in right:result.append([root.val]+i)return sorted(result, key=lambda x:-len(x))

35.复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

# 解法一： 分两步：第一步：顺序复制链表，第二步：复制特殊指针，每次从原始链表头部开始遍历查找特殊指针的位置
# 时间复杂度：O(n^2)
# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:# 返回 RandomListNodedef Clone(self, pHead):# write code hereif pHead is None:return NonepH_new_c = RandomListNode(pHead.label) # 复制链表的头结点pH_new = pH_new_c # 定义临时变量，用于遍历next_node = pHead.next # 定义临时变量，用于遍历# 先顺序复制while next_node != None:copy_next_node = RandomListNode(next_node.label)pH_new.next = copy_next_nodenext_node = next_node.nextpH_new = copy_next_node# 复制特殊指针pH_new = pH_new_c # 临时变量，用于遍历next_node = pHeadrand_node = pHead.randomwhile next_node != None:rand_node = next_node.randomif rand_node == None:pH_new.random = Noneelse:temp = pHead  # 原始头结点copy_random = pH_new_c # 复制链表的头结点# 同时遍历原始链表和复制链表，寻找复制链表中特殊指针指向的节点while temp != None:if temp.label == rand_node.label:  # 找到特殊指针指向的节点breakelse:temp = temp.nextcopy_random = copy_random.nextpH_new.random = copy_random # 给复制链表当前节点的特殊指针赋值# 进行下个节点特殊指针的赋值next_node = next_node.nextpH_new = pH_new.nextreturn pH_new_c

# 解法二：时间换空间法，借助哈希表存储当前节点和特殊指针之间的对应关系
# 时间和空间复杂度均为：O(n)
# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:# 返回 RandomListNodedef Clone(self, pHead):# write code hereif pHead is None:return NonepH_new_c = RandomListNode(pHead.label) # 复制链表的头结点pH_new = pH_new_c # 定义临时变量，用于遍历next_node = pHead.next # 定义临时变量，用于遍历N_Nc = {} # 定义字典，存储赋值前--赋值后节点对N_Nc[pHead.label] = pH_new# 先顺序复制while next_node != None:copy_next_node = RandomListNode(next_node.label)pH_new.next = copy_next_nodeN_Nc[next_node.label] = copy_next_node # 存储赋值前--赋值后节点对next_node = next_node.nextpH_new = copy_next_node# 复制特殊指针pH_new = pH_new_c # 临时变量，用于遍历next_node = pHeadrand_node = pHead.randomwhile next_node != None:rand_node = next_node.randomif rand_node == None:pH_new.random = Noneelse:# 借助哈希表存储的赋值前--赋值后节点对，给复制链表当前节点的特殊指针赋值pH_new.random = N_Nc[rand_node.label] # 进行下个节点特殊指针的赋值next_node = next_node.nextpH_new = pH_new.nextreturn pH_new_c

# 解法三：不使用辅助空间，在原始链表上添加复制链表成为一个长链表，然后拆分出复制链表
# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:# 返回 RandomListNodedef Clone(self, pHead):# write code hereif pHead is None:return Nonenode = pHead # 定义临时变量，用于遍历# 先顺序复制，将复制的节点接在原始节点后面，得到一个长链表while node != None:next_node = node.nextcopy_next_node = RandomListNode(node.label)copy_next_node.next = next_nodenode.next = copy_next_nodenode = next_nodenode = pHeadwhile node != None:next_node = node.nextif node.random != None:next_node.random = node.random.nextnode = next_node.nextnode = pHeadpH_new = pH_new_c = node.next  # 复制链表的头节点node.next = pH_new.next # 需要借助node.next进行节点的赋值node = node.nextwhile node != None:pH_new_c.next = node.next # 复制节点pH_new_c = pH_new_c.next # 复制节点node.next = pH_new_c.next # 原始节点，需要借助node.next进行节点的赋值node = node.next #原始节点return pH_new

36.二叉搜索树与双向链表

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

# 方法：将二叉搜索树的左右节点分别重置为双向链表的向前、向后指针
# 使用LVR递归遍历实现
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:def Convert(self, pRootOfTree):# write code hereif pRootOfTree is None:return Nonereturn self.recursion_modify(pRootOfTree)def recursion_modify(self, pRoot):if pRoot is None:return Noneif pRoot.left is None and pRoot.right is None:return pRootself.recursion_modify(pRoot.left)left = pRoot.leftif left != None:while left.right != None:left = left.rightpRoot.left = leftleft.right = pRootself.recursion_modify(pRoot.right)right = pRoot.rightif right != None:while right.left != None:right = right.leftpRoot.right = rightright.left = pRootwhile pRoot.left != None:pRoot = pRoot.leftreturn pRoot

37.序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树

# 使用前序遍历实现序列化和反序列化
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:def Serialize(self, root):# write code hereif root is None:return '$,'return str(root.val) + ',' + self.Serialize(root.left) + self.Serialize(root.right)def Deserialize(self, s):# write code here# 特殊情况处理if len(s) < 1:return None# 原始二叉树为空时，序列化得到的是"$,"，此时直接返回Noneelif len(s) == 2 and s[0] == '$':return Nones_list = s.split(',')root = TreeNode(int(s_list[0])) # 设置头节点s_list.pop(0) # 将用过的节点弹出# 递归重构二叉树root.left = self.recursion_deserialize(s_list)root.right = self.recursion_deserialize(s_list)return rootdef recursion_deserialize(self, s):if len(s) < 1:return Noneif s[0] == '$':s.pop(0)return None# 递归重构二叉树val = s.pop(0)node = TreeNode(int(val))node.left = self.recursion_deserialize(s)node.right = self.recursion_deserialize(s)return node

38.字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

# 递归法：将字符串分为头部+头部之外两部分
# -*- coding:utf-8 -*-
class Solution:def Permutation(self, ss):# write code hereif ss is None:return []if len(ss) == 1:return list(ss)s = list(ss)s.sort()  # 得到升序排列的字符数组res = []for i in range(len(s)):if i > 0 and s[i] == s[i-1]: # 重复字符排列过就不用再重排continuetemp = self.Permutation(''.join(s[:i])+''.join(s[i+1:]))for j in temp:res.append(s[i] + j)return res

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

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

# 方法一：借助字典实现，统计每个数字出现的频次
# 时间和空间复杂度均为：O(n)
# -*- coding:utf-8 -*-
class Solution:def MoreThanHalfNum_Solution(self, numbers):# write code hereif numbers is None:return 0count = {}length = len(numbers) // 2for i in numbers:if i in count:count[i] += 1else:count[i] = 1for key in count:if count[key] > length:return keyreturn 0

# 方法二：根据数组特点寻找，次数超过一半
# 使用两个变量记录当前数字和数字出现的次数，出现与当前数字相同的数时次数加1，否则减1，若减为0，则将之前的数改为当前的数字
# 最后存储的数字在进行是否频次大于长度一半的验证即可
# -*- coding:utf-8 -*-
class Solution:def MoreThanHalfNum_Solution(self, numbers):# write code hereif numbers is None:return 0count = 1num = numbers[0]for i in numbers[1:]:if i == num:count += 1else:if count > 0:count -= 1else:count += 1num = i# 验证num是否次数大于长度一半count = 0for i in numbers:if i == num:count += 1if count > len(numbers) // 2:return numelse:return 0

# 方法三：利用快速排序得到排序后的数组，判断排序后的数组中位数是否出现频次大于数组长度一半
# 时间复杂度：O(nlogn)
# -*- coding:utf-8 -*-
class Solution:def MoreThanHalfNum_Solution(self, numbers):# write code hereif numbers is None:return 0nums = self.quickSort(numbers) # 排序num = nums[len(nums)//2] # 取中位数# 验证num是否次数大于长度一半count = 0for i in numbers:if i == num:count += 1if count > len(numbers) // 2:return numelse:return 0# 快排def quickSort(self, numbers):if len(numbers) <= 1:return numberspivot = numbers[0]left = [x for x in numbers if x < pivot]mid = [x for x in numbers if x == pivot]right = [x for x in numbers if x > pivot]return self.quickSort(left) + mid + self.quickSort(right)

40.最小的K个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

# 方法一：排序后取前K个
# 时间复杂度由排序算法决定：快排则为O(nlogn)
# -*- coding:utf-8 -*-
class Solution:def GetLeastNumbers_Solution(self, tinput, k):# write code hereif tinput is None or len(tinput) < k:return []tinput = self.quickSort(tinput)return tinput[0:k]def quickSort(self, arr):if len(arr) <= 1:return arrpivot = arr[0]left = [x for x in arr if x < pivot]mid = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return self.quickSort(left) + mid + self.quickSort(right)

# 方法二：类似计数排序法，计数后取出前K个
# 时间复杂度O(n+k)
# -*- coding:utf-8 -*-
class Solution:def GetLeastNumbers_Solution(self, tinput, k):# write code hereif tinput is None or len(tinput) < k or k == 0:return []tinput = self.countingSort(tinput, k)return tinputdef countingSort(self, arr, k):min_num = min(arr)max_num = max(arr)counts = [0] * (max_num-min_num+1)for i in arr:counts[i-min_num] += 1res = []count = 0for i in range(len(counts)):for j in range(counts[i]):res.append(i+min_num)if len(res) == k:return res

41.数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

# 方法一：使用有序数组
# 插入数据和查找中位数的时间复杂度分别为：O(n)，O(1)
# -*- coding:utf-8 -*-
class Solution:def __init__(self):self.num = []def Insert(self, num):# write code hereif num != None:length = len(self.num)for i in range(length):if num <= self.num[i]:self.num.insert(i, num)break# 如果没有插入，则说明该数最大，所以放置于数组末尾if length == len(self.num):self.num.append(num)def GetMedian(self, x):# write code hereif len(self.num) < 1:return Nonelength = len(self.num)if length % 2 == 1:return self.num[length//2]else:return (self.num[length//2]+self.num[length//2-1])/2.0

# 方法二：使用大顶堆和小顶堆存储数据，实现中位数的查找
# -*- coding:utf-8 -*-
class Solution:def __init__(self):self.min_heap = [] # 小顶堆self.max_heap = [] # 大顶堆def Insert(self, num):# write code here# 根据数据总个数插入，当数据总数为奇数时插入大顶堆，否则插入小顶堆length = len(self.min_heap) + len(self.max_heap)if length % 2 == 1: # 总数为奇数，将元素插入大顶堆self.min_heap.append(num)min_num = self.adjustMin()self.min_heap.pop(0)  # 将小顶堆最小元素弹出后放入大顶堆self.adjustMin() # 弹出后再次调整堆结构self.max_heap.append(min_num)self.adjustMax()else: # 总数为偶数，将元素插入小顶堆self.max_heap.append(num)max_num = self.adjustMax()self.max_heap.pop(0)  # 将小顶堆最小元素弹出后放入大顶堆self.adjustMax()  # 弹出后再次调整堆结构self.min_heap.append(max_num)self.adjustMin()def GetMedian(self, x):# x 为无效参数# write code herelength = len(self.min_heap) + len(self.max_heap)if length == 0:return []if length % 2 == 1:return self.min_heap[0]else:return (self.max_heap[0]+self.min_heap[0])/2.0def adjustMax(self):# 大顶堆调整，返回堆顶元素length = len(self.max_heap)if length < 1:returnif length == 1:return self.max_heap[0]i = length // 2 - 1while i >= 0:left = 2*i + 1right = 2*i + 2if right < length and self.max_heap[left] < self.max_heap[right]:left = rightif self.max_heap[left] > self.max_heap[i]:self.max_heap[i], self.max_heap[left] = self.max_heap[left], self.max_heap[i]if left <= length // 2 - 1:i = leftcontinuei -= 1return self.max_heap[0]def adjustMin(self):# 小顶堆调整，返回堆顶元素length = len(self.min_heap)if length < 1:returnif length == 1:return self.min_heap[0]i = length // 2 - 1while i >= 0:left = 2*i + 1right = 2*i + 2if right < length and self.min_heap[left] > self.min_heap[right]:left = rightif self.min_heap[left] < self.min_heap[i]:self.min_heap[i], self.min_heap[left] = self.min_heap[left], self.min_heap[i]if left <= length // 2 - 1:i = leftcontinuei -= 1return self.min_heap[0]

42.连续子数组的最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)要求时间复杂度为$O(n)$

# 方法一：根据数组和的规律进行查找
# -*- coding:utf-8 -*-
class Solution:def FindGreatestSumOfSubArray(self, array):# write code hereif array is None or len(array) == 0:returnif len(array) == 1:return array[0]max_sum = 0final_max = array[0]  # 存储最大和for i in range(len(array)):max_sum += array[i]print(max_sum)print(array[i])if max_sum < array[i]:max_sum = array[i]if final_max < max_sum:final_max = max_sumreturn final_max

# 方法二：动态规划法
# 设f(i)表示第i个数结尾的的子数组的最大和，则要求的最大和为max(f(i))
# -*- coding:utf-8 -*-
class Solution:def FindGreatestSumOfSubArray(self, array):# write code hereif array is None or len(array) == 0:returnif len(array) == 1:return array[0]max_sum = 0  # f(i)final_max = array[0]  # 存储最大和 max(f(i))for i in array:# 循环实现动态规划if max_sum <= 0:max_sum = ielse:max_sum += iif final_max < max_sum:final_max = max_sumreturn final_max

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

求出1_{13的整数中1出现的次数,并算出100}1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

# 方法一：暴力遍历法，时间复杂度为O(nlogn)
# -*- coding:utf-8 -*-
class Solution:def NumberOf1Between1AndN_Solution(self, n):# write code hereif n is None:returncount = 0for i in range(1,n+1):count += self.countNum(i)return countdef countNum(self, n):count = 0while n > 0:if n % 10 == 1:count += 1n = n // 10return counts = Solution()
s.NumberOf1Between1AndN_Solution(10000)

4001

# 方法二：递归法，根据数字的规律进行递归求解
# 时间复杂度：O(logn)
# -*- coding:utf-8 -*-
class Solution:def NumberOf1Between1AndN_Solution(self, n):# write code hereif n is None or n < 1:return 0return self.recursion_count(n)def recursion_count(self, n):if n == 0:return 0if n < 10:return 1count = 0high_num, time = self.getHigh(n)# 1在最高位时if high_num > 1:count = pow(10, time-1)else:count = n - pow(10, time-1) + 1# 1在除最高位之外的位置时count += high_num * (time - 1) * pow(10, time - 2) # 排列组合# 递归count += self.recursion_count(n - high_num*pow(10, time-1))return countdef getHigh(self, n):# 获取高位数字和总的位数if n == 0:return 0time = 0while n > 0:time += 1if n < 10:return n, timen = n // 10

44.数字序列中每一位的数字

数字以01234567891011121314…的格式排列。在这个序列中，第5位（从0开始计）是5，第13位是1，第19位是4。求任意第n为对应的数字。

**PS:**此题牛客网没有对应的在线评测，可以在acwing第57题进行在线评测。

# 方法：根据数字不同位数所占个数的规律进行求解
class Solution(object):def digitAtIndex(self, n):""":type n: int:rtype: int"""i = 1 # 数字位数while n - self.count_of_integers(i) >= 0:n = n - self.count_of_integers(i)i += 1rest = n // i # 相对当前位数数字所处的位置inte = n % i # 相对当前数字的位置return self.get_number(i, rest, inte)def count_of_integers(self, n):# 计算不同位数数字的个数if n == 1:return 10else:return (pow(10, n) - pow(10, n-1)) * ndef get_number(self, i, rest, inte):# 根据数字位数i，相对i位数起始第rest个数字，得到第rest个数字的第inte位的数字if i == 1:num = 0 + restelse:num = pow(10, i-1) + restinte = i - inte - 1while inte != 0:num = num // 10inte -= 1return num % 10

45.把数组排成最小的数

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

# 方法：重新定义比较大小函数，根据字符串m+n与n+m的比较结果进行排序
# python3中利用functools模块，实现自定义排序
# -*- coding:utf-8 -*-
import functools
class Solution:def PrintMinNumber(self, numbers):# write code hereif numbers is None or len(numbers) == 0:return ''numbers = [str(x) for x in numbers]numbers.sort(key=functools.cmp_to_key(self.comp))return "".join(numbers)def comp(self, x, y):if (str(x)+str(y)) < (str(y)+str(x)):return -1else:return 1
s = Solution()
num = [3,5,1,4,2]
#num = [3, 32, 321]
s.PrintMinNumber(num)

'12345'

46.把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：

0翻译成”a”，1翻译成”b”，……，11翻译成”l”，……，25翻译成”z”。

一个数字可能有多个翻译。例如12258有5种不同的翻译，它们分别是”bccfi”、”bwfi”、”bczi”、”mcfi”和”mzi”。

请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

PS: 此题牛客网没有对应的在线评测，可以在acwing第55题进行评测。

方法一：递归法，自上而下的实现

自上而下的实现（即从字符串左至右递归），存在很多重复计算的问题。
递归公式：$$f(i)=f(i+1)+g(i,i+1)\ast f(i+2)$$

其中$f(i)$表示从第i位数字开始的翻译数目，$g(i,i+1)$表示第i位和第i+1为组合的数字如果在10–25范围则为1，否则为0

class Solution:def getTranslationCount(self, s):""":type s: str:rtype: int"""if int(s) < 0 or s is None:return 0# 将数字拆分s = [x for x in s]return self.recursion_count(s)def recursion_count(self, s):# 递归终止条件if len(s) < 2:return 1count = 0# 将s拆分为1个元素和其余元素count += self.recursion_count(s[1:])# 将s拆分为前两个元素和其余元素if 10 <= int(s[0]+s[1]) <= 25:if len(s) >= 3:count += self.recursion_count(s[2:])else:count += 1return count

方法二：递归法，自下而上使用循环实现

自下而上实现（即从字符串右至左循环）效率更高。递归公式相同：$$f(i)=f(i+1)+g(i,i+1)\ast f(i+2)$$

从i=len(s)开始循环计算。

class Solution:def getTranslationCount(self, s):""":type s: str:rtype: int"""if int(s) < 0 or s is None:return 0# 将数字拆分s = [x for x in s]return self.curlce_count(s)def curlce_count(self, s):# 递归终止条件if len(s) < 2:return 1count = 0length = len(s)# 递推公式fi = fi_1 + g(i,i+1)*fi_2# 初始赋值，i从len(s)-1开始，此时赋值如下fi_2,fi_1,fi = 0, 0, 1for i in range(length-2, -1, -1):if i+2 > length:fi_2 = 0# 更新fi_2, fi_1 = fi_1, fiif 10 <= int(s[i]+s[i+1]) <= 25:fi = fi_1 + fi_2else:fi + fi_1return fi

47.礼物的最大价值

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

**PS:**此题牛客网没有对应的在线评测，可以在acwing第60题进行评测。

# 方法一：动态规划
# 递推公式：f(i,j) = max(f(i, j-1), f(i-1, j)) + gift[i, j]
class Solution(object):def getMaxValue(self, grid):""":type grid: List[List[int]]:rtype: int"""if grid is None or len(grid) < 1 or len(grid[0]) < 1:return 0m, n = len(grid), len(grid[0])assist_list = [[0 for _ in range(n)] for _ in range(m)] # 辅助二维数组# 递推公式为：f(i,j) = max(f(i, j-1), f(i-1, j)) + gift[i, j]for i in range(m):for j in range(n):if i == 0 and j == 0:assist_list[0][0] = grid[0][0]elif i == 0:assist_list[0][j] = assist_list[0][j-1] + grid[0][j]elif j == 0:assist_list[i][0] = assist_list[i-1][0] + grid[i][0]else:assist_list[i][j] = max(assist_list[i-1][j], assist_list[i][j-1]) + grid[i][j]return assist_list[-1][-1]# 方法二： 在动态规划的基础上，可以进一步优化空间使用，只使用一维数组进行辅助

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

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

这个题没有包含在牛客网《剑指offer》题库里，可以在以下网址进行在线评测：

• 牛客网面试题
• acwing第61题
• leetcode 第三题

长度为n的字符串，其子字符串的个数为$n\ast (n+1)/2+1$，所以从长度为n的字符串中生成子串的时间复杂度为 O ( n 2 ) O(n^2) O(n2).

则暴力法的时间复杂度为： O ( n 3 ) O(n^3) O(n3)

# 方法一：双指针法
class Solution:def longestSubstringWithoutDuplication(self, s):""":type s: str:rtype: int"""if s is None:return 0s = [x for x in s]length = len(s)assist_list = [-1]*26  # 辅助数组，记录字符出现的位置left, right = 0, 0 # 左右双指针扫描max_l, count = 0, 0for left in range(length):right = leftwhile right < length and assist_list[ord(s[right])-ord('a')] == -1: # 当右指针未到末尾且当前字符未出现过时继续扫描count += 1assist_list[ord(s[right])-ord('a')] = rightright += 1if max_l < count:max_l = count# 从left下一位置重新扫描计数 count = 0assist_list = [-1]*26return max_l 

方法二：动态规划法

递推公式：$f(i)=f(i-1)+1$， f(i)表示以第i个字符结尾的不重复子串的最长长度

分情况讨论：

• 当前字符之前未出现过：$f(i)=f(i-1)+1$
• 当前字符之前出现过，设重复字符之间相距d：
  • $d<=f(i)$: $f(i)=d$
  • $d>f(i)$ : $f(i)=f(i-1)+1$

class Solution:def longestSubstringWithoutDuplication(self, s):""":type s: str:rtype: int"""if s is None:return 0s = [x for x in s]length = len(s)assist_list = [-1]*26fi_1, fi, d = 0, 0, 0max_l = 0for i in range(length):if assist_list[ord(s[i])-ord('a')] == -1:fi = fi + 1else:d = i - assist_list[ord(s[i])-ord('a')]if d <= fi:fi = delse:fi = fi + 1# 更新字符位置   assist_list[ord(s[i])-ord('a')] = i# 记录最大值if max_l < fi:max_l = fireturn max_l 

49.丑数

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

# 方法一：暴力遍历法，时间复杂度过大，不可取
# -*- coding:utf-8 -*-
class Solution:def GetUglyNumber_Solution(self, index):# write code hereif index < 1:return 0i, n = 1, 1while i < index:n += 1if self.ifUgly(n):i += 1return ndef ifUgly(self, number):while number % 2 == 0:number = number // 2while number % 3 == 0:number = number // 3while number % 5 == 0:number = number // 5return number == 1

# 方法二：根据丑数生成的规律，使用辅助数组进行丑数生成和查找
# -*- coding:utf-8 -*-
class Solution:def GetUglyNumber_Solution(self, index):# write code hereif index < 1:return 0i, n = 1, 1ugly_number_list = [1] # 辅助数组，存储所有的丑数Max = ugly_number_list[0] # 当前最大的丑数T2, T3, T5 = 0, 0, 0  # 记录上一次大于最大丑数的位置M2, M3, M5 = 0, 0, 0  # 记录当前大于最大丑数的第一个数while i < index:for j in range(T2, len(ugly_number_list)):if ugly_number_list[j] * 2 > Max:M2  = ugly_number_list[j] * 2T2 = jbreakfor j in range(T3, len(ugly_number_list)):if ugly_number_list[j] * 3 > Max:M3  = ugly_number_list[j] * 3T3 = jbreakfor j in range(T5, len(ugly_number_list)):if ugly_number_list[j] * 5 > Max:M5  = ugly_number_list[j] * 5T5 = jbreakugly_number_list.append(min(M2,M3,M5)) # 按顺序添加丑数Max = ugly_number_list[-1] # 更新当前的最大丑数i += 1return ugly_number_list[-1]

50.第一个只出现一次的字符

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）

# 方法：借助字典统计字符出现次数，确定第一个出现一次的字符，时间复杂度O(n)
# -*- coding:utf-8 -*-
class Solution:def FirstNotRepeatingChar(self, s):# write code hereif s is None or len(s) < 1:return -1count_dict = {}# 使用字典统计字符出现次数for i in s:if count_dict.has_key(i):count_dict[i] += 1else:count_dict[i] = 1# 再次遍历，确定第一个只出现一次的字符for p, i in enumerate(s):if count_dict[i] == 1:return preturn -1

50.1 字符流中第一个只出现一次的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。

# 方法：借助字典统计字符出现的位置，当之前出现过时，将位置置为特殊标记，比如-1
# 插入和查找的时间复杂度分别为O(1)、O(n)
# -*- coding:utf-8 -*-
class Solution:# 返回对应chardef __init__(self):self.count_dict = {} # 辅助数组self.counter = 0 # 记录字符个数，即字符出现位置def FirstAppearingOnce(self):# write code herefirstChar, count = None, 1000000 # count表示第一个出现一次字符的位置，初始时赋一个大值for char, count_ in self.count_dict.items():if count_ != -1 and count_ < count:firstChar = charcount = count_if firstChar is not None:return firstCharelse:return '#'def Insert(self, char):# write code hereif char is None:returnself.counter += 1 if self.count_dict.has_key(char):self.count_dict[char] = -1else:self.count_dict[char] = self.counter

51.数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

**PS：**此题牛客网Python实现都超时无法通过，在AcWing65题评测使用Python可以通过。

# 方法一：暴力法，时间复杂度O(n^2),时间复杂度过大，不可取
class Solution:def InversePairs(self, data):# write code hereif data is None or len(data) < 2:return 0P = 0for i in range(len(data)-1):for j in range(i+1, len(data)):if data[i] > data[j]:P += 1return P%1000000007
s = Solution()
data = [1,2,3,4,5,6,7,0]
s.InversePairs(data)

7

# 方法二：基于分治法--归并排序思路进行统计
# 时间复杂度：O(nlogn)，但是在牛客网评测只通过50%，然后超时。在AcWing网站评测可以通过
# 牛客网使用Python 无法AC此题
# -*- coding:utf-8 -*-
class Solution:def __init__(self):self.count = 0def InversePairs(self, data):# write code hereif data is None or len(data) < 2:return 0self.mergeSort(data)return self.count%1000000007def mergeSort(self, data):if len(data) <= 1:return datamid = len(data) // 2# 分left = self.mergeSort(data[:mid])right = self.mergeSort(data[mid:])# 治return self.merge(left, right)def merge(self, left, right):i, j = 0, 0res = []while i < len(left) and j < len(right):if left[i] > right[j]:res.append(left[i])i += 1self.count += len(right[j:])else:res.append(right[j])j += 1if i < len(left):res += left[i:]if j < len(right):res += right[j:]return res

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

输入两个链表，找出它们的第一个公共结点。

方法：
存在公共节点的链表呈Y字形分布，倒叙遍历将分叉。

• 1.暴力遍历法，时间复杂度 O ( n 2 ) O(n^2) O(n2)
• 2.借助两个辅助栈，倒叙遍历至分叉前的节点即为第一个公共节点，时间复杂度$O(n+m)$,空间复杂度$O(n+m)$
• 3.统计链表节点个数，让长链表先遍历若干步，然后同时开始遍历，第一个相等节点即为第一个公共节点,时间复杂度$O(n+m)$

# 方法三：统计链表节点个数，让长链表先遍历若干步，然后同时开始遍历，第一个相等节点即为第一个公共节点
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:def FindFirstCommonNode(self, pHead1, pHead2):# write code hereif pHead1 is None or pHead2 is None:return Nonecount1, count2 = 1, 1# 统计链表节点个数p = pHead1while p.next != None:count1 += 1p = p.nextp = pHead2while p.next != None:count2 += 1p = p.next# 让较长的链表先遍历若干步dis = count1 - count2p1, p2 = pHead1, pHead2if dis > 0:rest_length = count2for _ in range(dis):p1 = p1.nextelse: rest_length = count1dis = abs(dis)for _ in range(dis):p2 = p2.next# 寻找第一个公共节点for _ in range(rest_length):if p1.val == p2.val:return p1else:p1, p2 = p1.next, p2.nextreturn None

53.在排序数组中查找数字

53.1 数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。

# 方法一：遍历统计：O(n)
# -*- coding:utf-8 -*-
class Solution:def GetNumberOfK(self, data, k):# write code hereif data is None:return 0count = 0for i in data:if i == k:count += 1return count

# 方法二：二分查找思路，O(logn)
# -*- coding:utf-8 -*-
class Solution:def GetNumberOfK(self, data, k):# write code hereif data is None or len(data) < 1:return 0# 判断排序数组是升序还是降序up_flag = Falseif data[0] < data[-1]:up_flag = True # 升序# 二分法查找与K相等的值的index left, right = 0, len(data)pivot = (left + right) // 2previous_pivot = pivotwhile data[pivot] != k:if data[pivot] > k:if up_flag:right = pivotpivot = (left + right) // 2else:left = pivotpivot = (left + right) // 2else:if up_flag:left = pivotpivot = (left + right) // 2else:right = pivotpivot = (left + right) // 2if previous_pivot == pivot:# 如果两次的pivot相等，则说明数组里不存在k值，返回0return 0previous_pivot = pivot# 找到k所在位置后，在k左右进行统计count = 1index = pivot - 1while index > -1 and data[index] == k:count += 1index -= 1index = pivot + 1while index < len(data) and data[index] == k:count += 1index += 1return count

53.2 0~n-1缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0到n-1之内。
在范围0到n-1的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

PS: 牛客网没有此题在线评测，可在AcWing第68题进行评测。

# 方法：二分法查找与下标不相等的第一个数
class Solution(object):def getMissingNumber(self, data):""":type nums: List[int]:rtype: int"""if data is None or len(data) < 1:return 0# 特例情况if len(data) >1 and data[0] != 0:return 0# 二分法查找与K相等的值的index left, right = 0, len(data)pivot = (left + right) // 2previous_pivot = pivotwhile True:if data[pivot] > pivot:right = pivotpivot = (left + right) // 2else:left = pivotpivot = (left + right) // 2if previous_pivot == pivot:# 如果两次的pivot相等,则下一个数即为不存在的数return pivot+1previous_pivot = pivot

53.3 数组中数值和下标相等的元素

假设一个单调递增的数组里的每个元素都是整数并且是唯一的。
请编程实现一个函数找出数组中任意一个数值等于其下标的元素。
例如，在数组[-3, -1, 1, 3, 5]中，数字3和它的下标相等。

PS: 牛客网没有此题在线评测，可在AcWing第69题进行评测。

class Solution(object):def getNumberSameAsIndex(self, nums):""":type nums: List[int]:rtype: int"""if nums is None or len(nums) < 1:return -1left, right = 0, len(nums)mid = (left + right) // 2previous_mid = midwhile nums[mid] != mid:if nums[mid] < mid:left = mid else:right = midmid = (left + right) // 2#print(mid)if previous_mid == mid:return -1previous_mid = midreturn mid 

54. 二叉搜索树的第K大节点

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

# 方法：中序遍历得到节点数组，然后取节点数组第k个元素
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:# 返回对应节点TreeNodedef KthNode(self, pRoot, k):# write code hereif pRoot is None or k < 1:return Nonenode_list = self.recursion_LVR(pRoot)if len(node_list) < k:return Noneelse:return node_list[k-1]def recursion_LVR(self, pRoot):# 中序遍历，返回节点数组if pRoot is None:return []return self.recursion_LVR(pRoot.left) + [pRoot] + self.recursion_LVR(pRoot.right)

55.1 二叉树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

# 递归实现计算，选择较长的子节点所在路径长度作为深度
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:def TreeDepth(self, pRoot):# write code hereif pRoot is None:return 0left = self.TreeDepth(pRoot.left)right = self.TreeDepth(pRoot.right)return (left+1) if (left > right) else (right+1)

55.2 平衡二叉树

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

# 方法一：递归得到每个子节点的深度，判断是否满足平衡二叉树条件
# 该方法存在重复遍历过程，效率较低，不可取
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:def IsBalanced_Solution(self, pRoot):# write code hereif pRoot is None:return Trueleft = self.tree_depth(pRoot.left)right = self.tree_depth(pRoot.right)if abs(left-right) > 1:return Falsereturn self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)def tree_depth(self, pRoot):# 递归遍历求子节点的深度if pRoot is None:return 0left = self.tree_depth(pRoot.left)right = self.tree_depth(pRoot.right)return (left+1) if (left > right) else (right + 1)

# 方法二：递归遍历子节点的过程，判断当前子树是否满足平衡条件，不满足则将标志位置为False
# 与方法一相比，少了重复递归的过程
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:def __init__(self):self.flag = Truedef IsBalanced_Solution(self, pRoot):# write code hereif pRoot is None:self.depth = 0return Trueself.tree_depth(pRoot)return self.flagdef tree_depth(self, pRoot):if pRoot is None:return 0left = self.tree_depth(pRoot.left)right = self.tree_depth(pRoot.right)if abs(left - right) > 1:self.flag = Falsereturn (left+1) if (left > right) else (right + 1)

56.数组中数字出现的次数

56.1 数组中只出现一次的两个数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

**方法：**根据异或的性质来解题。当一个数组只存在一个出现一次的数，将数组所有数进行异或，则结果为这个只出现一次的数；当数组存在两个只出现一次的数，将数组所有数进行异或，然后按照异或结果将数组可分为两部分（分类依据是：找出异或结果中第一个非零位，根据该位是否为零可以将数组分为两部分），将这两部分分别进行异或即可得到两个各出现一次的数字。

# -*- coding:utf-8 -*-
class Solution:# 返回[a,b] 其中ab是出现一次的两个数字def FindNumsAppearOnce(self, array):# write code hereif array is None or len(array) < 2:return []bin_xor = array[0]for i in array[1:]:bin_xor = bin_xor ^ iif bin_xor != 0:first1 = self.getFirst1(bin_xor)else:return []a, b = 0, 0for i in array:if self.getFirst1(i) == first1:a ^= ielse:b ^= ireturn [a, b]def getFirst1(self, num):# 自右向左获取第一个非零位置n = 0while num & (1 << n) == 0:n += 1return n

56.2 数组中唯一出现一次的数字

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

此题牛客网没有在线评测，可以在AcWing第74题进行评测。

方法：

• 方法一：基于数字二进制数的特点，统计数组所有数对应二进制数每一位1出线的次数总和，将次数分别对3取余，取余不为零的位则为1，就可得到只出现一次的数的二进制数，时间复杂度$O(n)$
• 数组排序后得到出现一次的数，时间复杂度$O(nlogn)$
• 借助哈希表统计数字出现次数，，空间复杂度$O(n)$

# 基于方法一
class Solution(object):def findNumberAppearingOnce(self, nums):""":type nums: List[int]:rtype: int"""if nums is None or len(nums) < 1:raise('Invalid input')digits_count = [0] * 16 # 定义数组，存储数字二进数数每一位1的总个数# 累加数组中数字二进数每一位1的总个数for i in nums:n = 0while i>>n != 0:digits_count[n] += (i>>n) & 1n += 1 # 根据每一位1的个数是否能被3整除得到只出现一次的数字对应的二进制数flag_index = 0for i in range(len(digits_count)):if digits_count[i] == 0:flag_index = ibreakelse:digits_count[i] %= 3# 将只出现一次的数字从二进制数转化为整数res = 0for i, n in enumerate(digits_count[:flag_index]):res += pow(2, i) * nreturn ress = Solution()
nums = [1,1,1,2,2,2,3,4,4,4]
s.findNumberAppearingOnce(nums)

3

57.和为s的数字

57.1 和为s的两个数字

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

方法：

• 暴力遍历法，时间复杂度 O ( n 2 ) O(n^2) O(n2)
• 双指针向中间遍历法，时间复杂度$O(n)$

# 双指针法
# -*- coding:utf-8 -*-
class Solution:def FindNumbersWithSum(self, array, tsum):# write code hereif array is None or len(array) < 2:return []head, end = 0, len(array) - 1while head < end:s = array[head] + array[end]if s == tsum:return [array[head], array[end]]elif s > tsum:end -= 1else:head += 1return []

57.2 和为s的连续正数数列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

# 双指针法，同时从头开始向后递增，循环条件为head < (tsum+1) // 2
# -*- coding:utf-8 -*-
class Solution:def FindContinuousSequence(self, tsum):# write code hereif tsum < 1:return []res = []head, end = 1, 2while head < (tsum+1) // 2:s = sum(range(head,end))if  s == tsum:res.append(range(head, end))end += 1elif s < tsum:end += 1else:head += 1return res

58.翻转字符串

58.1 翻转单词顺序

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

# 方法一：借助额外的空间记录句子中的单词，然后对单词进行翻转，空间复杂度O(n)
# -*- coding:utf-8 -*-
class Solution:def ReverseSentence(self, s):# write code hereif s is None or len(s) < 1:return ""start, end = 0, 0assist_list = []for i,c in enumerate(s):if c is " ":assist_list.append(s[start:i])start = i+1if i == len(s)-1:assist_list.append(s[start:])assist_list.reverse()return " ".join(assist_list)

# 方法二：两次翻转法，不需要额外的空间消耗
# -*- coding:utf-8 -*-
class Solution:def ReverseSentence(self, s):# write code hereif s is None or len(s) < 1:return ""s = list(s)# 翻转句子s = self.reverse(s)res = []# 翻转单词start, end = 0, 0for i, c in enumerate(s):if c == " ":temp = self.reverse(s[start:i])res.append(''.join(temp))start = i + 1if i == len(s) - 1:temp = self.reverse(s[start:])res.append(''.join(temp))return " ".join(res)def reverse(self, s):# 对整个句子进行翻转head, end = 0, len(s)-1while head < end:s[head], s[end] = s[end], s[head]head += 1end -= 1return s

58.2 左旋转字符串

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

# 方法一：利用python字符串特性直接操作
# -*- coding:utf-8 -*-
class Solution:def LeftRotateString(self, s, n):# write code hereif s is None or len(s) < 1 or n < 0:return ""length = len(s)n = n % lengthreturn s[n:] + s[:n]

# 方法二：从移位点将字符串分割为左右两部分，分别进行翻转，总共进行三次翻转实现左旋
# -*- coding:utf-8 -*-
class Solution:def LeftRotateString(self, s, n):# write code hereif s is None or len(s) < 1 or n < 0:return ""s = list(s)length = len(s)n = n % lengths = self.reverse(s)left = self.reverse(s[:length-n])right = self.reverse(s[length-n:])return "".join(left+right)def reverse(self, s):# 对整个句子进行翻转head, end = 0, len(s)-1while head < end:s[head], s[end] = s[end], s[head]head += 1end -= 1return s

59.队列的最大值

59.1 滑动窗口的最大值

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。

# 方法：利用双端队列存储窗口的最大值在数组中的位置（下标）
# -*- coding:utf-8 -*-
class Solution:def maxInWindows(self, num, size):# write code hereif num is None or len(num) < 1 or size == 0:return []max_deque = []max_val = []for i, n in enumerate(num):# 弹出超出窗口的队首if len(max_deque) > 0 and i >= (max_deque[0]+size):max_deque.pop(0)if len(max_deque) > 0 and i < (max_deque[0]+size) and n >= num[max_deque[0]]:# 更新队首为最大值max_deque = []max_deque.append(i)elif len(max_deque) > 0 and num[max_deque[-1]] <= n:# 更新队尾为较大值while len(max_deque) > 0 and num[max_deque[-1]] <= n:max_deque.pop(-1)max_deque.append(i)else:max_deque.append(i)# 取出各个窗口的最大值if i - size >= -1:max_val.append(num[max_deque[0]])return max_val

59.2 队列的最大值

定义一个队列并实现函数 max 得到队列里的最大值，要求函数 max、push_back 和 pop_front 的时间复杂度都是O(1)。

**PS:**此题没有在网上找到对应的在线评测平台。

方法： 利用双端队列存储队列最大值，实现$O(1)$获取队列最大值

class QueueWithMax:def __init__(self):self.max_q = []self.queue_with_max = []def push_back(self, n):self.queue_with_max.append(n)index = len(self.queue_with_max) - 1 # 当前插入值对应的indexif len(self.max_q) > 0 and n >= self.queue_with_max[self.max_q[0]]:self.max_q = []self.max_q.append(index)elif len(self.max_q) > 0 and self.queue_with_max[self.max_q[-1]] <= n:while len(self.max_q) > 0 and self.queue_with_max[self.max_q[-1]] <= n:self.max_q.pop(-1)self.max_q.append(index)else:self.max_q.append(index)def pop_front(self):if len(self.queue_with_max) > 0:res = self.queue_with_max.pop(0)# 弹出最大值队列队首元素if self.max_q[0]-1 < 0:self.max_q.pop(0)# 将最大值队列所存储的索引前移一位for i in range(len(self.max_q)):self.max_q[i] -= 1 return reselse:return Nonedef max(self):if len(self.max_q) < 1:return Noneelse:return self.queue_with_max[self.max_q[0]]# Test
s = QueueWithMax()
s.push_back(1)
print(s.max())
s.push_back(5)
print(s.max())
s.push_back(3)
print(s.max())
s.push_back(7)
print(s.max())
s.push_back(2)
print(s.max())
print(s.pop_front())
print(s.max())
print(s.pop_front())
print(s.max())
print(s.pop_front())
print(s.max())
print(s.pop_front())
print(s.max())
s.push_back(5)
print(s.max())

1
5
5
7
7
1
7
5
7
3
7
7
2
5

60.n个骰子的点数

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

PS: 此题牛客网没有对应的在线评测，可以在AcWing第80题进行评测。

# 方法一：递归法，递归公式f(n) += f(n-1)，使用辅助数组存储和值出现的次数，数组的索引即为和值
#  这种方法时间效率较低，由于递归存在很多重复计算
class Solution(object):def numberOfDice(self, n):""":type n: int:rtype: List[int]"""if n is None or n < 1:return []return self.recursion_count(n)def recursion_count(self, n):# 递归计算不同和值出线的次数if n == 1:res = [0] * (6*n - n + 1)for i in range(1,7): res[i-1] = 1return resres = [0] * (6*n - n + 1) # 统计n时，和值出现的次数#print(6*n - n + 1)res_pre = self.recursion_count(n-1)#print(res_pre)for i in range(1,7):for j in range(n-1, 6*(n-1)+1):  # n-1时和值的范围为[n-1, 6*(n-1)]#print(i+j - n)res[i+j - n] += res_pre[j-(n-1)] # n-1时和值出现的次数为res_pre[j-(n-1)]return res# 如果求每个和值的概率，则返回如下# sum_count = sum(res)# return [x/sum_count for x in res]

# 方法二：将方法一中的递归使用循环实现，减少重复计算，时间效率O(n^2)
class Solution(object):def numberOfDice(self, n):""":type n: int:rtype: List[int]"""if n is None or n < 1:return []if n == 1:res = [0] * (6*n - n + 1)for i in range(1,7): res[i-1] = 1return resres_pre = [1] * (6*1 - 1 + 1) # 只有一个骰子的情况记录for num in range(2, n+1):res = [0] * (6*num - num + 1)for i in range(1,7):for j in range(num-1, 6*(num-1)+1):  # num-1时和值的范围为[num-1, 6*(num-1)]res[i+j - num] += res_pre[j-(num-1)] # num-1时和值出现的次数为res_pre[j-(num-1)]res_pre = resreturn res# 如果求每个和值的概率，则返回如下# sum_count = sum(res)# return [x/sum_count for x in res]

# 方法三：动态规划法
# 状态转移公式，f(n,k) = f(n-1, k-1) + f(n-1, k-2) + ... + f(n-1, k-6),  n<= k <= 6n
# 初始状态： f(1, 1)= f(1, 2) = ... = f(1, 5) = f(1, 6) = 1
# 其中f(n , k)表示n个骰子点数和为k时出现的次数
# 使用1维数组存储有效的和值次数，比二维数组空间使用率稍高
# 时间复杂度： O(n^2)
class Solution(object):def numberOfDice(self, n):""":type n: int:rtype: List[int]"""if n is None or n < 1:return []f1 = [1] * 6if n == 1:return f1# 动态规划fn_1 = f1 # n-1时有效和值的次数统计for i in range(2, n+1):fn = [0] * (6*i - i + 1) # 和值有效范围[n, 6*n]-->线性映射至(长度为(6*n - n + 1)的一维数组for k in range(len(fn)):#fn[k] = k_sum = k + i # 从数组索引反映射回对应的有效和值# 此处求f(n,k)， f(n,k) = f(n-1, k-1) + f(n-1, k-2) + ... + f(n-1, k-6),for j in range(1, 7):if 6*(i-1) >= k_sum-j >= i-1:fn[k] += fn_1[k_sum- j - (i-1)]fn_1 = fn  return fn

61.扑克牌中的顺子

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

# 根据数字间的差值和王的数量关系判断是否成为顺子，同时如果存在对子则无法成为顺子
# -*- coding:utf-8 -*-
class Solution:def IsContinuous(self, numbers):# write code hereif numbers is None or len(numbers) != 5:return Falsenumbers.sort()zero_num = 0 # 记录零的个数dif = 0 # 统计数字差值for i,j in zip(numbers[:-1], numbers[1:]):if i == 0:zero_num += 1elif i == j:  # 如果存在对子，则无法成为顺子return Falseelse:dif += j - i - 1 # 统计数字之间比1大的差值if dif <= zero_num: # 王的数量是否大于等于数字之间的差值return Trueelse:return False

62.圆圈中最后剩下的数字

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

约瑟夫环问题。

方法一：使用额外空间存储数字，模拟删除过程

时间复杂度$O(nm)，空间复杂度$O(n),这种方法在牛客网超时无法通过，在Acwing第82题可以通过。

# -*- coding:utf-8 -*-
class Solution:def LastRemaining_Solution(self, n, m):# write code hereif n is None or n <= 1 or m < 1:return 0num = [x for x in range(n)]index = 0for _ in range(n-1):count = 0while count < m:if num[index] != -1:count += 1index = (index + 1) % nelse:index = (index + 1) % nnum[index-1] = -1for i in num:if i != -1:return i
s = Solution()
s.LastRemaining_Solution(5, 3)

3

方法二：分析问题，建立递归公式

定义关于$n,m$的函数$f(n,m)$,表示每次在n个数字$0,1,2,\cdots ,n-1$中删除第m个数字后剩下的数字。第一个被删除的是$k=(m-1)$，剩余数字为$0,1,\cdots ,k-1,k+1,\cdots ,n-1$，则新的序列为$k+1,\cdots, n-1, 0,1,\cdots, k-1 $,可记为$f(n-1, m)$，将新的序列可映射至$0n-2$范围，映射函数为$p(x)=(x-k-1)\%n$，逆映射为 p − 1 ( x ) = ( x + k + 1 ) % n p^{-1}(x)=(x+k+1)\%n p−1(x)=(x+k+1)%n。最终可得递推关系：
f ( n , m ) = { 0 n = 1 [ f ( n − 1 , m ) + m ] % n n > 1 f(n,m) = \left\{ \begin{matrix} 0 & n=1 \\ [f(n-1,m)+m]\%n & n > 1 \end{matrix}\right. f(n,m)={0[f(n−1,m)+m]%n​n=1n>1​

# 根据方法二的递推公式使用循环法从1开始递推
# -*- coding:utf-8 -*-
class Solution:def LastRemaining_Solution(self, n, m):# write code hereif n is None or n < 1 or m < 1:return -1last = 0for i in range(2, n+1):last = (last + m)%ireturn last

63. 股票的最大利润

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

**PS：**此题牛客网没有在线评测，可在AcWing第83题进行评测。

class Solution(object):def maxDiff(self, nums):""":type nums: List[int]:rtype: int"""if nums is None or len(nums) <= 1:return 0min_in = nums[0]profit = 0for i in nums[1:]:if i < min_in:min_in = ielif (i - min_in) > profit:profit = i - min_inreturn profit

64. 求1+2+3+…+n

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

# 使用递归实现累加
# -*- coding:utf-8 -*-
class Solution:def Sum_Solution(self, n):# write code hereres = nflag = (n > 0) and self.Sum_Solution(n - 1)res += flagreturn res

# 另一种递归
# -*- coding:utf-8 -*-
class Solution:def Sum_Solution(self, n):# write code herereturn n and self.Sum_Solution(n - 1) + n

65. 不用加减乘除做加法

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

# 方法：使用位运算实现
# -*- coding:utf-8 -*-
class Solution:def Add(self, num1, num2):# write code hereif num1 is None or num2 is None:return -1while num2 != 0:sums = num1 ^ num2num2 = (num1&num2)<<1 # 进位num1 = sums & 0xFFFFFFFF # 考虑负数return num1 if num1 >> 31 == 0 else num1 - 4294967296

66. 构建乘积数组

给定一个数组$A[0,1,...,n-1]$,请构建一个数组$B[0,1,...,n-1]$,其中B中的元素$B[i]=A[0]\ast A[1]\ast ...\ast A[i-1]\ast A[i+1]\ast ...\ast A[n-1]$。不能使用除法。

# 方法一暴力法：O(n^2)# 方法二使用A构造矩阵来构造B
# -*- coding:utf-8 -*-
class Solution:def multiply(self, A):# write code hereif A is None or len(A) <= 1:return []length = len(A)BA = [[1 if i == j else A[j] for j in range(length)] for i in range(length)] # 构建矩阵，对角线元素为1B = [1] * lengthfor i, li in enumerate(BA):mul = 1for j in li:mul *= j B[i] = mulreturn B

67. 把字符串转整数

将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。

# -*- coding:utf-8 -*-
class Solution:def StrToInt(self, s):# write code hereif s is None or len(s) < 1:return 0if len(s) == 1 and (s[0] is "+" or s[0] is "-"):return 0flag = 1head = 0valid_list = "1234567890"if s[0] is "-":flag = -1elif s[0] != "-" and s[0] != "+":if s[0] in valid_list:head = int(s[0])else:return 0length,count = len(s), len(s)res = 0while count > 1:if s[count-1] in valid_list:res += int(s[count-1])*pow(10, length-count)count -= 1else:return 0if head == 0:return flag*reselse:return head*pow(10, length-1)+res

67.& 更复杂的字符串转正数

在AcWing第87题对字符串转整数提出更高的要求。

你的函数应满足下列条件：

• 忽略所有行首空格，找到第一个非空格字符，可以是 ‘+/−’ 表示是正数或者负数，紧随其后找到最长的一串连续数字，将其解析成一个整数；
• 整数后可能有任意非数字字符，请将其忽略；
• 如果整数长度为0，则返回0；
• 如果整数大于INT_MAX(2^31 − 1)，请返回INT_MAX；如果整数小于INT_MIN(−2^31) ，请返回INT_MIN；

class Solution(object):def strToInt(self, str):""":type str: str:rtype: int"""s = strif s is None or len(s) < 1:return 0if len(s) == 1 and (s[0] is "+" or s[0] is "-"):return 0dig_flag = 1head = 0valid_list = "1234567890"# 剔除字符串首的空格，尾的不合法元素count = 0while  s[0] == " ": #!= "+" and s[0] != "-" and s[0] not in valid_list and :count += 1s = s[1:]if len(s) < 1:return 0count = len(s)while  s[-1] not in valid_list:count -= 1s = s[:-1]if len(s) < 1:return 0# 处理字符串第一个元素if s[0] is "-":dig_flag = -1elif s[0] != "-" and s[0] != "+":if s[0] in valid_list:head = int(s[0])else:return 0# 处理其余元素length,count = len(s), len(s)res = 0while count > 1:if s[count-1] in valid_list:res += int(s[count-1])*pow(10, length-count)count -= 1else:return 0INT_MAX = pow(2,31)-1INT_MIN = -pow(2,31)# 合并得到最终值if head == 0:res = dig_flag*reselse:res = head*pow(10, length-1)+res# 判断值的范围if INT_MIN <= res <= INT_MAX:return reselif res > INT_MAX:return INT_MAXelse:return INT_MIN

68.树中两个节点的最低公共祖先

给出一个二叉树，输入两个树节点，求它们的最低公共祖先。
一个树节点的祖先节点包括它本身。

注意：

• 输入的二叉树不为空；
• 输入的两个节点一定不为空，且是二叉树中的节点；

**PS:**此题牛客网没有在线评测，可在AcWing第88题进行评测。

方法：

• 使用链表保存从树根节点到目标节点的路径，然后问题转化为求两个链表的第一个公共节点
• 使用递归进行遍历，终止条件为遍历至树的末页节点或者遍历至目标节点，返回目标节点，当返回的左右子节点均不为空则说明其根节点为最低公共祖先，当左右子节点只有其一为空，则另一个节点必为最低公共祖先

# 递归遍历
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""if root is None:return Noneif root == p or root == q:return rootleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)if left != None and right != None:return rootif left is None:return rightelif right is None:return left

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！