本博客同时发布于个人主页：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/False
def
duplicate
(
self
,
numbers
,
duplication
)
:
# write code here
if
not
numbers
or
len
(
numbers
)
<=
1
:
return
False
for
i
in
numbers
:
if
i
<
0
or
i
>
len
(
numbers
)
-
1
:
return
False
numbers_sorted
=
self
.
quickSort
(
numbers
)
for
i
,
j
in
zip
(
numbers_sorted
[
:
-
1
]
,
numbers_sorted
[
1
:
]
)
:
if
i
==
j
:
duplication
[
0
]
=
i
return
True
return
False
def
quickSort
(
self
,
arr
)
:
if
len
(
arr
)
<=
1
:
return
arr
length
=
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/False
def
duplicate
(
self
,
numbers
,
duplication
)
:
# write code here
if
not
numbers
or
len
(
numbers
)
<=
1
:
return
False
for
i
in
numbers
:
if
i
<
0
or
i
>
len
(
numbers
)
-
1
:
return
False
dic
=
{
}
for
i
in
numbers
:
if
dic
.
has_key
(
i
)
:
duplication
[
0
]
=
i
return
True
else
:
dic
[
i
]
=
1
return
False
## 方法三：利用数字自身下标和值的key-value特性
## 时间复杂度：O(n) 空间复杂度：O(1)
# -*- coding:utf-8 -*-
class
Solution
:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def
duplicate
(
self
,
numbers
,
duplication
)
:
# write code here
if
not
numbers
or
len
(
numbers
)
<=
1
:
return
False
for
i
in
numbers
:
if
i
<
0
or
i
>
len
(
numbers
)
-
1
:
return
False
i
=
0
while
i
<
len
(
numbers
)
:
if
i
==
numbers
[
i
]
:
i
+=
1
elif
numbers
[
i
]
==
numbers
[
numbers
[
i
]
]
:
duplication
[
0
]
=
numbers
[
i
]
return
True
else
:
tmp
=
numbers
[
i
]
numbers
[
i
]
=
numbers
[
tmp
]
numbers
[
tmp
]
=
tmp
return
False
4.二维数组的查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
# 方法一：暴力遍历法
# 时间复杂度：O（n^2）
# -*- coding:utf-8 -*-
class
Solution
:
# array 二维列表
def
Find
(
self
,
target
,
array
)
:
# write code here
if
len
(
array
)
<
1
:
return
False
for
i
in
array
:
for
j
in
i
:
if
target
==
j
:
return
True
return
False
# 方法二：反向剔除不满足元素法：从右上角进行查找
# -*- coding:utf-8 -*-
class
Solution
:
# array 二维列表
def
Find
(
self
,
target
,
array
)
:
# write code here
if
len
(
array
)
<
1
or
len
(
array
[
0
]
)
<
1
:
return
False
r_l
=
len
(
array
)
c_l
=
len
(
array
[
0
]
)
# 从右上角开始搜索
i
,
j
=
0
,
c_l
-
1
while
target
!=
array
[
i
]
[
j
]
:
if
target
>
array
[
i
]
[
j
]
:
if
i
<
r_l
-
1
:
i
+=
1
else
:
return
False
else
:
if
j
>
0
:
j
-=
1
else
:
return
False
return
True
5.替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
# 方法一：遍历判断然后替换法，时间复杂度O（n）
# -*- coding:utf-8 -*-
class
Solution
:
# s 源字符串
def
replaceSpace
(
self
,
s
)
:
# write code here
if
not
isinstance
(
s
,
str
)
or
len
(
s
)
<
1
or
s
==
None
:
return
s
tmp
=
[
]
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 here
if
not
isinstance
(
s
,
str
)
or
len
(
s
)
<
1
or
s
==
None
:
return
''
spaceN
=
0
for
i
in
s
:
if
i
==
' '
:
spaceN
+=
1
total
=
len
(
s
)
+
2
*
spaceN
newStr
=
[
None
]
*
total
indexO
,
indexN
=
len
(
s
)
-
1
,
total
-
1
while
indexO
>=
0
:
if
s
[
indexO
]
==
' '
:
newStr
[
indexN
]
=
'0'
newStr
[
indexN
-
1
]
=
'2'
newStr
[
indexN
-
2
]
=
'%'
indexN
-=
3
indexO
-=
1
else
:
newStr
[
indexN
]
=
s
[
indexO
]
indexN
-=
1
indexO
-=
1
return
''
.
join
(
newStr
)
6.从尾到头打印链表
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
# 方法一： 使用栈
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class
Solution
:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
def
printListFromTailToHead
(
self
,
listNode
)
:
# write code here
if
listNode
==
None
:
return
[
]
if
listNode
.
next
==
None
:
return
listNode
.
val
stack
=
[
]
nextNode
=
listNode
while
nextNode
.
next
!=
None
:
stack
.
append
(
nextNode
.
val
)
nextNode
=
nextNode
.
next
stack
.
append
(
nextNode
.
val
)
return
stack
[
:
:
-
1
]
# 方法二：递归的方法
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class
Solution
:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
def
printListFromTailToHead
(
self
,
listNode
)
:
# write code here
if
not
listNode
:
return
[
]
if
listNode
.
next
==
None
:
res
=
[
]
res
.
append
(
listNode
.
val
)
return
res
re
=
self
.
printListFromTailToHead
(
listNode
.
next
)
re
.
append
(
listNode
.
val
)
return
re
L
=
[
]
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
None
if
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_child
return
node
8.二叉树的下一个节点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
# -*- coding:utf-8 -*-
class
TreeLinkNode
:
def
__init__
(
self
,
x
)
:
self
.
val
=
x
self
.
left
=
None
self
.
right
=
None
self
.
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 here
if
not
pNode
:
return
pNode
# 如果存在右子节点，则下一个节点是右子节点中的最左节点
if
pNode
.
right
:
pNode
=
pNode
.
right
while
pNode
.
left
:
pNode
=
pNode
.
left
return
pNode
# 如果不存在右子节点，则反向根据父节点和子节点的关系确定
else
:
pC
=
pNode
# 记录当前节点
# 当父节点不为根节点时，如果当前节点是父左子节点，返回当前节点
while
pNode
.
next
:
pN
=
pNode
.
next
if
pN
.
left
and
pN
.
left
==
pNode
:
return
pN
else
:
pC
=
pNode
pNode
=
pN
# 当父节点是根节点时，如果当前节点是根节点的左子节点，则返回根节点
if
pNode
.
left
and
pNode
.
left
==
pC
:
return
pNode
else
:
return
None
a
=
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
,
c
s
=
Solution
(
)
print
(
s
.
GetNext
(
i
)
.
val
)
9.用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
# -*- coding:utf-8 -*-
class
Solution
:
def
__init__
(
self
)
:
self
.
stack1
=
[
]
# 用于push
self
.
stack2
=
[
]
# 用于pop
def
push
(
self
,
node
)
:
# write code here
self
.
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
res
else
:
# 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 ) = ⎩ ⎪ ⎨ ⎪ ⎧ 0 1 f ( n − 1 ) + f ( n − 2 ) n = 0 n = 1 n > 1
# 方法一：循环法实现
# 时间复杂度为：O（n）
# 自下而上的求解
# -*- coding:utf-8 -*-
class
Solution
:
def
Fibonacci
(
self
,
n
)
:
# write code here
if
not
isinstance
(
n
,
int
)
or
n
<
0
or
n
>
39
:
return
None
if
n
==
0
:
return
0
if
n
==
1
:
return
1
fn1
,
fn2
=
1
,
0
for
i
in
range
(
2
,
n
+
1
)
:
fn
=
fn1
+
fn2
fn2
=
fn1
fn1
=
fn
return
fn
# 方法二：递归法实现----运行超时
# 时间复杂度为n的指数级
# 自上而下的求解
# -*- coding:utf-8 -*-
class
Solution
:
def
Fibonacci
(
self
,
n
)
:
# write code here
if
not
isinstance
(
n
,
int
)
or
n
<
0
or
n
>
39
:
return
0
if
n
==
0
:
return
0
if
n
==
1
:
return
1
return
self
.
Fibonacci
(
n
-
1
)
+
self
.
Fibonacci
(
n
-
2
)
方法三：时间复杂度为 O ( l o g   n ) O(log \, n) O ( l o g n ) 的不实用解法
可证明存在如下公式：
[ 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
)
]
=
[
1
1
1
0
]
n
−
1
利用上述公式可以根据
[ 1 1 1 0 ] n − 1 \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1}
[
1
1
1
0
]
n
−
1
求得
f ( n ) f(n)
f
(
n
)
# 方法一：更简洁的循环实现
# -*- coding:utf-8 -*-
class
Solution
:
def
Fibonacci
(
self
,
n
)
:
# write code here
tempArray
=
[
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 here
if
number
<
1
:
return
0
if
number
==
1
:
return
1
if
number
==
2
:
return
2
fn1
=
2
fn2
=
1
for
i
in
range
(
3
,
number
+
1
)
:
fn
=
fn1
+
fn2
fn2
=
fn1
fn1
=
fn
return
fn
10.3 变态跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
**解析：**类比普通跳台阶问题，设跳法是台阶数n的函数f(n), 则有：
f ( n ) = f ( n − 1 ) + f ( n − 2 ) + . . . + f ( 1 ) + 1 f(n)=f(n-1)+f(n-2)+...+f(1)+1
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-1)=f(n-2)+f(n-3)+...+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)-f(n-1)=f(n-1)
f
(
n
)
−
f
(
n
−
1
)
=
f
(
n
−
1
)
即
f ( n ) = 2 f ( n − 1 ) f(n)=2f(n-1)
f
(
n
)
=
2
f
(
n
−
1
)
,即
f ( n ) f(n)
f
(
n
)
是公比为2的等比级数：
f ( n ) = 2 n − 1 f(n)=2^{n-1}
f
(
n
)
=
2
n
−
1
# -*- coding:utf-8 -*-
class
Solution
:
def
jumpFloorII
(
self
,
number
)
:
# write code here
if
number
<
1
:
return
0
fn
=
1
if
number
==
1
:
return
fn
for
_
in
range
(
2
,
number
+
1
)
:
fn
*=
2
return
fn
10.4 矩形覆盖问题
我们可以用2 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
# -*- coding:utf-8 -*-
class
Solution
:
def
rectCover
(
self
,
number
)
:
# write code here
if
number
<
1
or
not
isinstance
(
number
,
int
)
:
return
0
if
number
==
1
:
return
1
if
number
==
2
:
return
2
fn1
=
2
fn2
=
1
for
i
in
range
(
3
,
number
+
1
)
:
fn
=
fn1
+
fn2
fn2
=
fn1
fn1
=
fn
return
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 here
if
len
(
rotateArray
)
<
1
:
return
0
small
=
rotateArray
[
0
]
for
i
in
rotateArray
:
if
small
>
i
:
small
=
i
return
small
return
small
# 方法二：二分法
# -*- coding:utf-8 -*-
class
Solution
:
def
minNumberInRotateArray
(
self
,
rotateArray
)
:
# write code here
if
len
(
rotateArray
)
<
1
:
return
0
if
len
(
rotateArray
)
==
1
:
return
rotateArray
[
0
]
index
=
len
(
rotateArray
)
//
2
# index >= 1
base
=
len
(
rotateArray
)
//
2
while
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
//
2
else
:
base
-=
index
//
2
index
//=
2
return
rotateArray
[
base
]
## 这个方法存在问题，当针对[1,1,1,1,1,0,1]时无法正常判断，所以应该修改为当base与左右值相等时采用顺序查找的方法搜索最小值
class
Solution
:
def
minNumberInRotateArray
(
self
,
rotateArray
)
:
# write code here
if
len
(
rotateArray
)
<
1
:
return
0
if
len
(
rotateArray
)
==
1
:
return
rotateArray
[
0
]
index
=
len
(
rotateArray
)
//
2
# index >= 1
base
=
len
(
rotateArray
)
//
2
while
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
//
2
elif
rotateArray
[
base
]
<
rotateArray
[
0
]
:
base
-=
index
//
2
else
:
# 顺序查找
minNum
=
self
.
minSearch
(
rotateArray
)
return
minNum
index
//=
2
return
rotateArray
[
base
]
def
minSearch
(
self
,
rotateArray
)
:
small
=
rotateArray
[
0
]
for
i
in
rotateArray
:
if
small
>
i
:
small
=
i
return
small
return
small
# 方法三：二分法示例代码
# -*- coding:utf-8 -*-
class
Solution
:
def
minNumberInRotateArray
(
self
,
rotateArray
)
:
# write code here
if
len
(
rotateArray
)
<
1
:
return
0
if
len
(
rotateArray
)
==
1
:
return
rotateArray
[
0
]
# 双指针
first
=
0
end
=
len
(
rotateArray
)
-
1
while
end
-
first
!=
1
:
mid
=
(
first
+
end
)
//
2
if
rotateArray
[
first
]
==
rotateArray
[
mid
]
==
rotateArray
[
end
]
:
# 特殊情况，使用顺序查找
minN
=
rotateArray
[
0
]
for
i
in
rotateArray
[
1
:
]
:
if
i
<
minN
:
minN
=
i
return
minN
elif
rotateArray
[
first
]
<
rotateArray
[
end
]
:
# 特殊情况，整个数组是升序，没有进行旋转
return
rotateArray
[
first
]
elif
rotateArray
[
mid
]
>=
rotateArray
[
first
]
:
first
=
mid
else
:
end
=
mid
return
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} ⎣ ⎡ a s a b f d c c e e s e ⎦ ⎤ 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
# 回溯法--使用递归实现
# -*- coding:utf-8 -*-
class
Solution
:
def
hasPath
(
self
,
matrix
,
rows
,
cols
,
path
)
:
# write code here
if
len
(
matrix
)
<
1
or
rows
<
1
or
cols
<
1
or
len
(
path
)
<
1
:
return
False
visited
=
[
0
]
*
(
rows
*
cols
)
pathL
=
0
for
row
in
range
(
rows
)
:
for
col
in
range
(
cols
)
:
if
self
.
if_has_path
(
matrix
,
rows
,
cols
,
path
,
row
,
col
,
visited
,
pathL
)
:
return
True
return
False
def
if_has_path
(
self
,
matrix
,
rows
,
cols
,
path
,
row
,
col
,
visited
,
pathL
)
:
# 递归终止条件
if
pathL
==
len
(
path
)
:
return
True
hasPath
=
False
if
0
<=
row
<
rows
and
0
<=
col
<
cols
and
\
matrix
[
row
*
cols
+
col
]
==
path
[
pathL
]
and
\
not
visited
[
row
*
cols
+
col
]
:
pathL
+=
1
visited
[
row
*
cols
+
col
]
=
1
hasPath
=
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
-=
1
visited
[
row
*
cols
+
col
]
=
0
return
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 here
if
threshold
<
1
or
rows
<
1
or
cols
<
1
:
return
0
visited
=
[
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
=
0
while
row
!=
0
:
res
+=
row
%
10
row
//=
10
while
col
!=
0
:
res
+=
col
%
10
col
//=
10
if
res
<=
threshold
:
return
True
else
:
return
False
def
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
]
=
1
visited
[
row
*
cols
+
col
]
=
1
self
.
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] = 0
return
# 回溯法--示例代码
# -*- 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
count
def
movingCountCore
(
self
,
threshold
,
rows
,
cols
,
row
,
col
,
visited
)
:
count
=
0
if
self
.
check
(
threshold
,
rows
,
cols
,
row
,
col
,
visited
)
:
visited
[
row
*
cols
+
col
]
=
True
count
=
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
count
def
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
True
return
False
def
getDigitSum
(
self
,
number
)
:
sum
=
0
while
number
>
0
:
sum
+=
(
number
%
10
)
number
=
number
//
10
return
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
0
if
n
==
2
:
return
1
if
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
=
0
for
j
in
range
(
1
,
i
//
2
+
1
)
:
max_product
=
max
(
max_product
,
mem
[
j
]
*
mem
[
i
-
j
]
)
mem
[
i
]
=
max_product
return
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
0
if
n
==
2
:
return
1
if
n
==
3
:
return
2
p
=
(
n
//
3
)
r
=
(
n
%
3
)
if
r
==
0
:
return
pow
(
3
,
p
)
elif
r
==
1
:
return
pow
(
3
,
p
-
1
)
*
4
elif
r
==
2
:
return
pow
(
3
,
p
)
*
2
15.二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
解析：
- 使用位运算的效率高于除法
- 负数的右移运算会在高位进行补1，如果没考虑这一点，可能导致程序陷入死循环
- 可以使用与运算实现1的个数统计
# 方法一：常规不会陷入死循环的方法
# -*- coding:utf-8 -*-
class
Solution
:
def
NumberOf1
(
self
,
n
)
:
# write code here
if
n
==
0
:
return
0
# 设置循环终止条件
MAX_INT
=
(
1
<<
(
32
-
1
)
)
flag
=
1
count
=
0
while
n
and
flag
<=
MAX_INT
:
if
n
&
flag
:
count
+=
1
n
-=
flag
flag
=
flag
<<
1
return
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 here
if
n
==
0
:
return
0
count
=
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
+=
1
n
=
n
&
(
n
-
1
)
return
count
16.数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
# 方法一：普通方法
# 注意边界条件的控制、功能的测试、
# -*- coding:utf-8 -*-
class
Solution
:
def
Power
(
self
,
base
,
exponent
)
:
# write code here
if
base
==
0
:
return
0
res
=
1
if
exponent
==
0
:
return
res
elif
exponent
>
0
:
for
_
in
range
(
exponent
)
:
res
*=
base
return
res
else
:
for
_
in
range
(
abs
(
exponent
)
)
:
res
*=
base
if
res
!=
0
:
return
1
/
res
else
:
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}
a
n
=
{
a
n
/
2
⋅
a
n
/
2
a
(
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
0
if
exponent
==
0
:
return
1
if
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
base
if
(
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'
]
*
n
while
True
:
# 确定进位的位置
i
=
len
(
str_num
)
-
1
while
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
=
0
for
i
in
range
(
len
(
str_num
)
)
:
if
str_num
[
i
]
!=
'0'
:
index
=
i
break
print
(
''
.
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'
]
*
n
for
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
)
return
for
i
in
range
(
10
)
:
str_num
[
index
+
1
]
=
str
(
i
)
self
.
recursivePrint1ToMaxofNDigits
(
str_num
,
length
,
index
+
1
)
def
Print
(
self
,
str_num
)
:
index
=
-
1
for
i
in
range
(
len
(
str_num
)
)
:
if
str_num
[
i
]
!=
'0'
:
index
=
i
break
if
index
!=
-
1
:
print
(
''
.
join
(
str_num
[
index
:
]
)
)
s
=
Solution
(
)
s
.
Print1ToMaxofNDigits
(
2
)
18.删除链表节点
题目一：在 O ( 1 ) O(1) O ( 1 ) 时间内删除链表节点
给定单向链表的头指针和一个节点指针，定义一个函数在 O ( 1 ) 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 = val
self.next = next
"""
class
Solution
:
"""
@param: node: the node in the list should be deleted
@return: nothing
"""
def
deleteNode
(
self
,
node
)
:
# write your code here
if
not
node
or
not
node
.
next
:
node
=
None
return
node
.
val
=
node
.
next
.
val
node
.
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 here
if
pHead
is
None
or
pHead
.
next
is
None
:
return
pHead
first
=
ListNode
(
-
1
)
first
.
next
=
pHead
last
=
first
# 记录上一个有效节点
# 遍历不重复节点，更新last自身和last指向的节点
while
pHead
and
pHead
.
next
:
if
pHead
.
val
==
pHead
.
next
.
val
:
# 遍历得到与当前值不相等的节点，并将last指向该节点
val
=
pHead
.
val
while
pHead
and
val
==
pHead
.
val
:
pHead
=
pHead
.
next
last
.
next
=
pHead
else
:
# 如果当前节点有效，则更新last节点
last
=
pHead
pHead
=
pHead
.
next
return
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前两位当成空
-
首位相等，则有三种情况：
- pattern后移2位，s不变；相当于把pattern前两位当成空，匹配后面的
- pattern后移2位，s后移1位；相当于pattern前两位与s[0]匹配
- 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 False
return
self
.
match_recursion
(
s
,
pattern
)
def
match_recursion
(
self
,
s
,
pattern
)
:
# 递归终止条件
if
len
(
s
)
==
0
and
len
(
pattern
)
==
0
:
return
True
elif
len
(
s
)
!=
0
and
len
(
pattern
)
==
0
:
return
False
elif
len
(
s
)
==
0
and
len
(
pattern
)
!=
0
:
if
len
(
pattern
)
>
1
and
pattern
[
1
]
is
"*"
:
return
self
.
match_recursion
(
s
,
pattern
[
2
:
]
)
else
:
return
False
else
:
# 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 here
if
len
(
s
)
<
1
:
return
False
dot_index
=
-
1
e_index
=
-
1
for
i
in
range
(
len
(
s
)
)
:
if
s
[
i
]
is
'.'
:
dot_index
=
i
if
s
[
i
]
is
'e'
or
s
[
i
]
is
'E'
:
e_index
=
i
break
res
=
True
if
dot_index
>
0
:
# 小数点不在首位
res
=
res
and
self
.
isInt
(
s
[
:
dot_index
]
,
1
)
if
e_index
>
0
:
# 存在e或者E
res
=
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或者E
res
=
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 -+E
if
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
:
# 不存在小数点和E
res
=
res
and
self
.
isInt
(
s
[
dot_index
+
1
:
]
,
0
)
return
res
def
isInt
(
self
,
s
,
case
)
:
# 是否是整形数字，即“-+”在首位的0--9数字
# case = 1：表示要判断的部分在数字的开头，此时可以仅有“-+”，而没有数字
if
len
(
s
)
<
1
:
return
False
if
s
[
0
]
==
'+'
or
s
[
0
]
==
'-'
:
if
len
(
s
)
==
1
and
case
:
return
True
else
:
return
self
.
scanInt
(
s
[
1
:
]
)
else
:
return
self
.
scanInt
(
s
[
0
:
]
)
def
scanInt
(
self
,
s
)
:
# 必须在0--9之间
if
len
(
s
)
<
1
:
return
False
a
=
[
str
(
x
)
for
x
in
range
(
10
)
]
for
i
in
s
:
if
not
i
in
a
:
return
False
return
True
21.调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
# -*- coding:utf-8 -*-
class
Solution
:
def
reOrderArray
(
self
,
array
)
:
if
len
(
array
)
<
1
:
return
array
# write code here
odd_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 = None
class
Solution
:
def
FindKthToTail
(
self
,
head
,
k
)
:
# write code here
if
head
is
None
or
k
==
0
:
return
None
count
=
1
temp
=
head
while
temp
.
next
!=
None
:
count
+=
1
temp
=
temp
.
next
if
count
<
k
:
return
None
else
:
k
=
count
-
k
count
=
0
while
count
!=
k
:
count
+=
1
head
=
head
.
next
return
head
# 方法二：双指针法，使用两个间隔为k-1的指针
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class
Solution
:
def
FindKthToTail
(
self
,
head
,
k
)
:
# write code here
if
head
is
None
or
k
==
0
:
return
None
fP
=
head
sP
=
head
count
=
0
while
count
<
k
:
# 注意对fP是否为空的判断
if
fP
is
None
:
return
None
fP
=
fP
.
next
count
+=
1
while
fP
!=
None
:
fP
=
fP
.
next
sP
=
sP
.
next
return
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 here
if
pHead
is
None
:
return
None
node_num
=
self
.
hasCircle
(
pHead
)
if
node_num
==
0
:
return
None
else
:
# 存在环，环中节点数为node_num,查找环的入口节点
fP
=
pHead
# first point
sP
=
pHead
# second point
count
=
0
while
count
<
node_num
:
fP
=
fP
.
next
count
+=
1
while
fP
!=
sP
:
fP
=
fP
.
next
sP
=
sP
.
next
return
sP
def
hasCircle
(
self
,
pHead
)
:
# 判断是否存在circle，返回0表示不存在，返回正整数表示环中节点个数
fast
=
pHead
slow
=
pHead
while
fast
!=
None
:
# fast 移动两步，slow移动一步
fast
=
fast
.
next
if
fast
==
None
:
break
fast
=
fast
.
next
slow
=
slow
.
next
if
fast
==
slow
:
# 存在环，统计环中节点的个数
num
=
1
fast
=
fast
.
next
while
fast
!=
slow
:
num
+=
1
fast
=
fast
.
next
return
num
return
0
24.反转链表
输入一个链表，反转链表后，输出新链表的表头。
# 借助三个指针，一边遍历链表一边修改当前节点的指向，直到遍历完整个链表
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class
Solution
:
# 返回ListNode
def
ReverseList
(
self
,
pHead
)
:
# write code here
if
pHead
is
None
:
return
None
previous_p
=
pHead
current_p
=
pHead
.
next
if
current_p
is
None
:
# 只有一个节点
return
pHead
next_p
=
current_p
.
next
if
next_p
is
None
:
# 只有两个节点
previous_p
.
next
=
None
current_p
.
next
=
previous_p
return
current_p
#节点数大于等于3,借助三个指针一边遍历一边修改指向
previous_p
.
next
=
None
while
next_p
!=
None
:
current_p
.
next
=
previous_p
# 更新各个指针指向。向前移动
previous_p
=
current_p
current_p
=
next_p
next_p
=
next_p
.
next
current_p
.
next
=
previous_p
return
current_p
# 方法二：递归法实现，从尾部开始修改指向
# -*- coding:utf-8 -*-
class
ListNode
:
def
__init__
(
self
,
x
)
:
self
.
val
=
x
self
.
next
=
None
class
Solution
:
# 返回ListNode
def
ReverseList
(
self
,
pHead
)
:
# write code here
if
pHead
is
None
:
return
None
previous_p
=
pHead
current_p
=
pHead
.
next
if
current_p
is
None
:
# 只有一个节点
return
pHead
#节点数大于等于2,递归实现反转
previous_p
.
next
=
None
return
self
.
Rev_recursion
(
previous_p
,
current_p
)
def
Rev_recursion
(
self
,
pre
,
cur
)
:
# 递归终止条件：遍历至尾节点
if
cur
.
next
is
None
:
cur
.
next
=
pre
return
cur
next_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
.
next
print
(
pHead
.
val
)
# test
a
=
ListNode
(
1
)
b
=
ListNode
(
2
)
c
=
ListNode
(
3
)
d
=
ListNode
(
4
)
a
.
next
=
b
b
.
next
=
c
c
.
next
=
d
s
=
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
=
x
self
.
next
=
None
class
Solution
:
# 返回合并后列表
def
Merge
(
self
,
pHead1
,
pHead2
)
:
# write code here
if
pHead1
is
None
:
return
pHead2
elif
pHead2
is
None
:
return
pHead1
# 确定头结点
if
pHead1
.
val
>
pHead2
.
val
:
head
=
self
.
insertMerge
(
pHead2
,
pHead1
)
else
:
head
=
self
.
insertMerge
(
pHead1
,
pHead2
)
return
head
def
insertMerge
(
self
,
head
,
insertL
)
:
# head指头节点所在的链表，insertL链表中的元素将被插入head指向的链表
pHead
=
head
insert_h
=
insertL
while
pHead
.
next
!=
None
:
pre1
=
pHead
cur1
=
pHead
.
next
insert_p
=
insert_h
if
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.next
pHead
=
pHead
.
next
insert_h
=
insert_h
.
next
pre1
.
next
=
insert_p
insert_p
.
next
=
cur1
else
:
# 不满足插入条件，移动head所在链表，insertL链表不动
pHead
=
pHead
.
next
if
insert_h
!=
None
:
pHead
.
next
=
insert_h
return
head
def
PrintList
(
self
,
pHead
)
:
while
pHead
.
next
!=
None
:
print
(
pHead
.
val
)
pHead
=
pHead
.
next
print
(
pHead
.
val
)
a
=
ListNode
(
1
)
b
=
ListNode
(
3
)
c
=
ListNode
(
5
)
d
=
ListNode
(
7
)
a
.
next
=
b
b
.
next
=
c
c
.
next
=
d
e
=
ListNode
(
2
)
f
=
ListNode
(
4
)
g
=
ListNode
(
6
)
h
=
ListNode
(
8
)
e
.
next
=
f
f
.
next
=
g
g
.
next
=
h
s
=
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
pHead2
elif
pHead2
is
None
:
return
pHead1
if
pHead1
.
val
<
pHead2
.
val
:
pHead1
.
next
=
self
.
Merge
(
pHead1
.
next
,
pHead2
)
return
pHead1
else
:
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
False
res
=
False
if
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
res
def
isEqual
(
self
,
pRoot1
,
pRoot2
)
:
# 递归终止条件
if
pRoot2
is
None
:
return
True
if
pRoot1
is
None
:
return
False
if
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
:
return
if
root
.
left
!=
None
and
root
.
right
!=
None
:
root
.
left
,
root
.
right
=
root
.
right
,
root
.
left
self
.
Mirror
(
root
.
left
)
self
.
Mirror
(
root
.
right
)
elif
root
.
left
!=
None
and
root
.
right
is
None
:
root
.
left
,
root
.
right
=
None
,
root
.
left
self
.
Mirror
(
root
.
right
)
elif
root
.
left
is
None
and
root
.
right
!=
None
:
root
.
left
,
root
.
right
=
root
.
right
,
None
self
.
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
:
return
root
.
left
,
root
.
right
=
root
.
right
,
root
.
left
self
.
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
True
return
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
=
False
if
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 here
return
self
.
selfIsSym
(
pRoot
,
pRoot
)
def
selfIsSym
(
self
,
root1
,
root2
)
:
if
root1
==
root2
and
root2
==
None
:
return
True
if
root1
==
None
or
root2
==
None
:
return
False
if
root1
.
val
!=
root2
.
val
:
return
False
return
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 here
if
len
(
matrix
)
<
1
:
return
None
if
len
(
matrix
[
0
]
)
<=
1
:
m
=
[
x
[
0
]
for
x
in
matrix
]
return
m
row_len
=
len
(
matrix
)
# 行
col_len
=
len
(
matrix
[
0
]
)
# 列
# 四个数确定打印的边界
a
,
b
,
c
,
d
=
0
,
row_len
-
1
,
0
,
col_len
-
1
m
=
[
]
while
a
<=
b
and
c
<=
d
:
# 在当前边界条件下打印一次
m
=
m
+
self
.
Print
(
matrix
,
a
,
b
,
c
,
d
)
# 更新边界
a
+=
1
b
-=
1
c
+=
1
d
-=
1
return
m
def
Print
(
self
,
matrix
,
a
,
b
,
c
,
d
)
:
m
=
[
]
# 打印过程为：先横向右移，再纵向下移，再横向左移，最后纵向上移
m
=
matrix
[
a
]
[
c
:
d
+
1
]
# 横向右移打印
# 如果a=b，则只需要横向打印一次即完成打印
if
a
==
b
:
return
m
m
=
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
m
s
=
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.py
class
Solution
:
# matrix类型为二维列表，需要返回列表
def
printMatrix
(
self
,
matrix
)
:
if
not
matrix
:
return
[
]
rows
=
len
(
matrix
)
columns
=
len
(
matrix
[
0
]
)
start
=
0
result
=
[
]
while
rows
>
start
*
2
and
columns
>
start
*
2
:
self
.
PrintMatrixInCircle
(
matrix
,
columns
,
rows
,
start
,
result
)
start
+=
1
return
result
def
PrintMatrixInCircle
(
self
,
matrix
,
columns
,
rows
,
start
,
result
)
:
endX
=
columns
-
1
-
start
endY
=
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 here
self
.
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 here
if
len
(
self
.
stack
)
<
1
:
return
None
else
:
self
.
assist_stack
.
pop
(
)
return
self
.
stack
.
pop
(
)
def
top
(
self
)
:
# write code here
return
self
.
stack
[
-
1
]
def
min
(
self
)
:
# write code here
return
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 here
if
len
(
pushV
)
!=
len
(
popV
)
:
return
False
elif
len
(
pushV
)
<
1
:
return
True
stack
=
[
]
for
i
in
popV
:
# 辅助栈为空时，根据情况向辅助栈压入一个元素
if
len
(
stack
)
<
1
:
if
len
(
pushV
)
<
1
:
return
False
else
:
stack
.
append
(
pushV
.
pop
(
0
)
)
while
i
!=
stack
[
-
1
]
:
# 判断辅助栈栈顶元素是否和当前弹出元素相等，不相等则将压入序列中元素不断压入辅助栈，直到发现相等元素
if
len
(
pushV
)
<
1
:
# 如果压入序列为空，则没有元素可以匹配，所以不满足弹出顺序
return
False
else
:
stack
.
append
(
pushV
.
pop
(
0
)
)
# 如果弹出序列和辅助栈栈顶元素相等则，将辅助栈栈顶元素弹出
stack
.
pop
(
)
return
True
# 参考实现
# -*- coding:utf-8 -*-
class
Solution
:
def
IsPopOrder
(
self
,
pushV
,
popV
)
:
# write code here
if
pushV
==
[
]
or
popV
==
[
]
:
return
False
stack
=
[
]
for
i
in
pushV
:
stack
.
append
(
i
)
while
len
(
stack
)
and
stack
[
-
1
]
==
popV
[
0
]
:
stack
.
pop
(
)
popV
.
pop
(
0
)
if
len
(
stack
)
:
return
False
else
:
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 here
if
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 here
if
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 here
if
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
+=
1
return
res
33.二叉搜索树的后续遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
# -*- coding:utf-8 -*-
class
Solution
:
def
VerifySquenceOfBST
(
self
,
sequence
)
:
# write code here
if
len
(
sequence
)
==
0
:
return
False
return
self
.
recursion_verify
(
sequence
)
def
recursion_verify
(
self
,
sequence
)
:
if
len
(
sequence
)
<=
1
:
return
True
root
=
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 here
if
root
is
None
:
return
[
]
stack
=
[
]
# 辅助栈，存储路径节点
path
=
[
]
# 存储路径
sums
=
root
.
val
# 和值
stack
.
append
(
root
)
res
=
self
.
recursion_find
(
root
,
expectNumber
,
stack
,
sums
,
path
)
return
res
def
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
path
else
:
return
path
else
:
#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
.
val
if
root
.
right
!=
None
:
# 递归右节点
stack
.
append
(
root
.
right
)
sums
+=
root
.
right
.
val
self
.
recursion_find
(
root
.
right
,
expectNumber
,
stack
,
sums
,
path
)
stack
.
pop
(
)
# 一次递归结束后弹出当前节点，并恢复原来的和值
sums
-=
root
.
right
.
val
return
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 here
if
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
.
val
left
=
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
:
# 返回 RandomListNode
def
Clone
(
self
,
pHead
)
:
# write code here
if
pHead
is
None
:
return
None
pH_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_node
next_node
=
next_node
.
next
pH_new
=
copy_next_node
# 复制特殊指针
pH_new
=
pH_new_c
# 临时变量，用于遍历
next_node
=
pHead
rand_node
=
pHead
.
random
while
next_node
!=
None
:
rand_node
=
next_node
.
random
if
rand_node
==
None
:
pH_new
.
random
=
None
else
:
temp
=
pHead
# 原始头结点
copy_random
=
pH_new_c
# 复制链表的头结点
# 同时遍历原始链表和复制链表，寻找复制链表中特殊指针指向的节点
while
temp
!=
None
:
if
temp
.
label
==
rand_node
.
label
:
# 找到特殊指针指向的节点
break
else
:
temp
=
temp
.
next
copy_random
=
copy_random
.
next
pH_new
.
random
=
copy_random
# 给复制链表当前节点的特殊指针赋值
# 进行下个节点特殊指针的赋值
next_node
=
next_node
.
next
pH_new
=
pH_new
.
next
return
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
:
# 返回 RandomListNode
def
Clone
(
self
,
pHead
)
:
# write code here
if
pHead
is
None
:
return
None
pH_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_node
N_Nc
[
next_node
.
label
]
=
copy_next_node
# 存储赋值前--赋值后节点对
next_node
=
next_node
.
next
pH_new
=
copy_next_node
# 复制特殊指针
pH_new
=
pH_new_c
# 临时变量，用于遍历
next_node
=
pHead
rand_node
=
pHead
.
random
while
next_node
!=
None
:
rand_node
=
next_node
.
random
if
rand_node
==
None
:
pH_new
.
random
=
None
else
:
# 借助哈希表存储的赋值前--赋值后节点对，给复制链表当前节点的特殊指针赋值
pH_new
.
random
=
N_Nc
[
rand_node
.
label
]
# 进行下个节点特殊指针的赋值
next_node
=
next_node
.
next
pH_new
=
pH_new
.
next
return
pH_new_c
# 解法三：不使用辅助空间，在原始链表上添加复制链表成为一个长链表，然后拆分出复制链表
# -*- coding:utf-8 -*-
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class
Solution
:
# 返回 RandomListNode
def
Clone
(
self
,
pHead
)
:
# write code here
if
pHead
is
None
:
return
None
node
=
pHead
# 定义临时变量，用于遍历
# 先顺序复制，将复制的节点接在原始节点后面，得到一个长链表
while
node
!=
None
:
next_node
=
node
.
next
copy_next_node
=
RandomListNode
(
node
.
label
)
copy_next_node
.
next
=
next_node
node
.
next
=
copy_next_node
node
=
next_node
node
=
pHead
while
node
!=
None
:
next_node
=
node
.
next
if
node
.
random
!=
None
:
next_node
.
random
=
node
.
random
.
next
node
=
next_node
.
next
node
=
pHead
pH_new
=
pH_new_c
=
node
.
next
# 复制链表的头节点
node
.
next
=
pH_new
.
next
# 需要借助node.next进行节点的赋值
node
=
node
.
next
while
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 here
if
pRootOfTree
is
None
:
return
None
return
self
.
recursion_modify
(
pRootOfTree
)
def
recursion_modify
(
self
,
pRoot
)
:
if
pRoot
is
None
:
return
None
if
pRoot
.
left
is
None
and
pRoot
.
right
is
None
:
return
pRoot
self
.
recursion_modify
(
pRoot
.
left
)
left
=
pRoot
.
left
if
left
!=
None
:
while
left
.
right
!=
None
:
left
=
left
.
right
pRoot
.
left
=
left
left
.
right
=
pRoot
self
.
recursion_modify
(
pRoot
.
right
)
right
=
pRoot
.
right
if
right
!=
None
:
while
right
.
left
!=
None
:
right
=
right
.
left
pRoot
.
right
=
right
right
.
left
=
pRoot
while
pRoot
.
left
!=
None
:
pRoot
=
pRoot
.
left
return
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 here
if
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
# 原始二叉树为空时，序列化得到的是"$,"，此时直接返回None
elif
len
(
s
)
==
2
and
s
[
0
]
==
'$'
:
return
None
s_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
root
def
recursion_deserialize
(
self
,
s
)
:
if
len
(
s
)
<
1
:
return
None
if
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 here
if
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
]
:
# 重复字符排列过就不用再重排
continue
temp
=
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 here
if
numbers
is
None
:
return
0
count
=
{
}
length
=
len
(
numbers
)
//
2
for
i
in
numbers
:
if
i
in
count
:
count
[
i
]
+=
1
else
:
count
[
i
]
=
1
for
key
in
count
:
if
count
[
key
]
>
length
:
return
key
return
0
# 方法二：根据数组特点寻找，次数超过一半
# 使用两个变量记录当前数字和数字出现的次数，出现与当前数字相同的数时次数加1，否则减1，若减为0，则将之前的数改为当前的数字
# 最后存储的数字在进行是否频次大于长度一半的验证即可
# -*- coding:utf-8 -*-
class
Solution
:
def
MoreThanHalfNum_Solution
(
self
,
numbers
)
:
# write code here
if
numbers
is
None
:
return
0
count
=
1
num
=
numbers
[
0
]
for
i
in
numbers
[
1
:
]
:
if
i
==
num
:
count
+=
1
else
:
if
count
>
0
:
count
-=
1
else
:
count
+=
1
num
=
i
# 验证num是否次数大于长度一半
count
=
0
for
i
in
numbers
:
if
i
==
num
:
count
+=
1
if
count
>
len
(
numbers
)
//
2
:
return
num
else
:
return
0
# 方法三：利用快速排序得到排序后的数组，判断排序后的数组中位数是否出现频次大于数组长度一半
# 时间复杂度：O(nlogn)
# -*- coding:utf-8 -*-
class
Solution
:
def
MoreThanHalfNum_Solution
(
self
,
numbers
)
:
# write code here
if
numbers
is
None
:
return
0
nums
=
self
.
quickSort
(
numbers
)
# 排序
num
=
nums
[
len
(
nums
)
//
2
]
# 取中位数
# 验证num是否次数大于长度一半
count
=
0
for
i
in
numbers
:
if
i
==
num
:
count
+=
1
if
count
>
len
(
numbers
)
//
2
:
return
num
else
:
return
0
# 快排
def
quickSort
(
self
,
numbers
)
:
if
len
(
numbers
)
<=
1
:
return
numbers
pivot
=
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 here
if
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
arr
pivot
=
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 here
if
tinput
is
None
or
len
(
tinput
)
<
k
or
k
==
0
:
return
[
]
tinput
=
self
.
countingSort
(
tinput
,
k
)
return
tinput
def
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
]
+=
1
res
=
[
]
count
=
0
for
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 here
if
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 here
if
len
(
self
.
num
)
<
1
:
return
None
length
=
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 here
length
=
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.0
def
adjustMax
(
self
)
:
# 大顶堆调整，返回堆顶元素
length
=
len
(
self
.
max_heap
)
if
length
<
1
:
return
if
length
==
1
:
return
self
.
max_heap
[
0
]
i
=
length
//
2
-
1
while
i
>=
0
:
left
=
2
*
i
+
1
right
=
2
*
i
+
2
if
right
<
length
and
self
.
max_heap
[
left
]
<
self
.
max_heap
[
right
]
:
left
=
right
if
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
=
left
continue
i
-=
1
return
self
.
max_heap
[
0
]
def
adjustMin
(
self
)
:
# 小顶堆调整，返回堆顶元素
length
=
len
(
self
.
min_heap
)
if
length
<
1
:
return
if
length
==
1
:
return
self
.
min_heap
[
0
]
i
=
length
//
2
-
1
while
i
>=
0
:
left
=
2
*
i
+
1
right
=
2
*
i
+
2
if
right
<
length
and
self
.
min_heap
[
left
]
>
self
.
min_heap
[
right
]
:
left
=
right
if
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
=
left
continue
i
-=
1
return
self
.
min_heap
[
0
]
42.连续子数组的最大和
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)要求时间复杂度为 O ( n ) O(n) O ( n )
# 方法一：根据数组和的规律进行查找
# -*- coding:utf-8 -*-
class
Solution
:
def
FindGreatestSumOfSubArray
(
self
,
array
)
:
# write code here
if
array
is
None
or
len
(
array
)
==
0
:
return
if
len
(
array
)
==
1
:
return
array
[
0
]
max_sum
=
0
final_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_sum
return
final_max
# 方法二：动态规划法
# 设f(i)表示第i个数结尾的的子数组的最大和，则要求的最大和为max(f(i))
# -*- coding:utf-8 -*-
class
Solution
:
def
FindGreatestSumOfSubArray
(
self
,
array
)
:
# write code here
if
array
is
None
or
len
(
array
)
==
0
:
return
if
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
=
i
else
:
max_sum
+=
i
if
final_max
<
max_sum
:
final_max
=
max_sum
return
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 here
if
n
is
None
:
return
count
=
0
for
i
in
range
(
1
,
n
+
1
)
:
count
+=
self
.
countNum
(
i
)
return
count
def
countNum
(
self
,
n
)
:
count
=
0
while
n
>
0
:
if
n
%
10
==
1
:
count
+=
1
n
=
n
//
10
return
count
s
=
Solution
(
)
s
.
NumberOf1Between1AndN_Solution
(
10000
)
4001
# 方法二：递归法，根据数字的规律进行递归求解
# 时间复杂度：O(logn)
# -*- coding:utf-8 -*-
class
Solution
:
def
NumberOf1Between1AndN_Solution
(
self
,
n
)
:
# write code here
if
n
is
None
or
n
<
1
:
return
0
return
self
.
recursion_count
(
n
)
def
recursion_count
(
self
,
n
)
:
if
n
==
0
:
return
0
if
n
<
10
:
return
1
count
=
0
high_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
count
def
getHigh
(
self
,
n
)
:
# 获取高位数字和总的位数
if
n
==
0
:
return
0
time
=
0
while
n
>
0
:
time
+=
1
if
n
<
10
:
return
n
,
time
n
=
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
+=
1
rest
=
n
//
i
# 相对当前位数数字所处的位置
inte
=
n
%
i
# 相对当前数字的位置
return
self
.
get_number
(
i
,
rest
,
inte
)
def
count_of_integers
(
self
,
n
)
:
# 计算不同位数数字的个数
if
n
==
1
:
return
10
else
:
return
(
pow
(
10
,
n
)
-
pow
(
10
,
n
-
1
)
)
*
n
def
get_number
(
self
,
i
,
rest
,
inte
)
:
# 根据数字位数i，相对i位数起始第rest个数字，得到第rest个数字的第inte位的数字
if
i
==
1
:
num
=
0
+
rest
else
:
num
=
pow
(
10
,
i
-
1
)
+
rest
inte
=
i
-
inte
-
1
while
inte
!=
0
:
num
=
num
//
10
inte
-=
1
return
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 here
if
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
-
1
else
:
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 ) ∗ f ( i + 2 ) f(i)=f(i+1)+g(i,i+1)*f(i+2)
f
(
i
)
=
f
(
i
+
1
)
+
g
(
i
,
i
+
1
)
∗
f
(
i
+
2
)
其中 f ( i ) f(i) f ( i ) 表示从第i位数字开始的翻译数目， g ( i , i + 1 ) g(i,i+1) 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
1
count
=
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
+=
1
return
count
方法二：递归法，自下而上使用循环实现
自下而上实现（即从字符串右至左循环）效率更高。递归公式相同： f ( i ) = f ( i + 1 ) + g ( i , i + 1 ) ∗ f ( i + 2 ) f(i)=f(i+1)+g(i,i+1)*f(i+2) f ( i ) = f ( i + 1 ) + g ( i , i + 1 ) ∗ 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
1
count
=
0
length
=
len
(
s
)
# 递推公式fi = fi_1 + g(i,i+1)*fi_2
# 初始赋值，i从len(s)-1开始，此时赋值如下
fi_2
,
fi_1
,
fi
=
0
,
0
,
1
for
i
in
range
(
length
-
2
,
-
1
,
-
1
)
:
if
i
+
2
>
length
:
fi_2
=
0
# 更新
fi_2
,
fi_1
=
fi_1
,
fi
if
10
<=
int
(
s
[
i
]
+
s
[
i
+
1
]
)
<=
25
:
fi
=
fi_1
+
fi_2
else
:
fi
+
fi_1
return
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
0
m
,
n
=
len
(
grid
)
,
len
(
grid
[