文章目录
- 回溯法
- 67 机器人的运动范围
- 66 矩阵中的路径
- 栈和队列
- 65 滑动窗口的最大值
- 21 包含min函数的栈
- 22 栈的压入和弹出序列
- 二叉树
- 58 二叉树的下一个结点
- 59 对称二叉树
- 60 二叉树打印多行
- 61 之字形打印二叉树
- 62 序列化二叉树
- 63 二叉搜索树的第K个结点
- 50 二叉树的最低公共祖先
- 39 二叉树的深度
- 判断是不是平衡二叉树
- 19 二叉树的镜像
- 23 从上往下打印二叉树
- 24 二叉搜索树的后续遍历
- 25 二叉树中和为某一值的路径
- 27 二叉搜索树与双向链表
- 18 树的子结构
- 6 重建二叉树
- 链表
- 56 链表中环的入口结点
- 57 删除链表中重复的结点
- 45 圆圈中最后剩下的数字
- 37 两个链表的第一个公共结点
- 17 合并两个排序的链表
- 数组
- 51 数组中重复的数字
- 52 构建乘积数组
- 38 数字在排序数组中出现的次数
- 40 数组中出现一次的数字
- 41 和为s的两个数
- 43 骰子点数出现的概率
- 29 数组中出现超过一半的数字
- 30 最小的k个数
- 31 连续子数组的最大和
- 36 数组中的逆序对
- 14 调整奇偶数 奇数位于偶数前边
- 20 顺时针打印矩阵
- 8 旋转数组的最小值
- 字符串
- 53 正则表达式的匹配
- 54 表示数值的字符串
- 49 字符串转换为整数
- 42 翻转单词顺序
- 左旋转字符串
- 32 1到n整数中1出现的次数
- 33 把数排成最小的数
- 34 丑数
- 35 第一个只出现一次的字符
- 28 字符串的全排列
- 数值
- 11 数值的整数次方
回溯法
67 机器人的运动范围
题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
解题思路
- 设置visited矩阵记录每一个格子的访问状态。访问过设置为1，为访问过设置0.
- 递归实现回溯。依次访问当前位置的上下左右的格子。
# -*- coding:utf-8 -*-
import
sys
class
Solution
:
def
movingCount
(
self
,
threshold
,
rows
,
cols
)
:
# write code here
# 记录每个格子的状态
if
rows
<
0
and
cols
<
0
:
return
False
visited
=
[
0
]
*
(
rows
*
cols
)
count
=
self
.
calCount
(
threshold
,
rows
,
cols
,
0
,
0
,
visited
)
return
count
def
calCount
(
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
.
calCount
(
threshold
,
rows
,
cols
,
row
-
1
,
col
,
visited
)
\
+
self
.
calCount
(
threshold
,
rows
,
cols
,
row
+
1
,
col
,
visited
)
\
+
self
.
calCount
(
threshold
,
rows
,
cols
,
row
,
col
+
1
,
visited
)
\
+
self
.
calCount
(
threshold
,
rows
,
cols
,
row
,
col
-
1
,
visited
)
return
count
def
check
(
self
,
threshold
,
rows
,
cols
,
row
,
col
,
visited
)
:
if
0
<=
row
<
rows
and
0
<=
col
<
cols
and
visited
[
row
*
cols
+
col
]
==
0
\
and
self
.
getSum
(
row
)
+
self
.
getSum
(
col
)
<=
threshold
:
return
True
return
False
def
getSum
(
self
,
digit
)
:
res
=
0
while
digit
>
0
:
res
+=
digit
%
10
digit
//=
10
return
res
if
__name__
==
'__main__'
:
arr
=
sys
.
stdin
.
readline
(
)
.
strip
(
)
.
split
(
' '
)
threshold
,
rows
,
cols
=
[
int
(
x
)
for
x
in
arr
]
count
=
Solution
(
)
.
movingCount
(
threshold
,
rows
,
cols
)
print
(
count
)
66 矩阵中的路径
题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
解题思路
- 设置visited矩阵记录每一个格子的访问状态。访问过设置为1，为访问过设置0.
- index 记录path的元素， 回溯法寻找匹配的元素。如果当前元素符合，寻找当前元素的四周元素。
- 如果没有找到， index-1回溯到前一个位置。
# -*- coding:utf-8 -*-
class
Solution
:
def
hasPath
(
self
,
matrix
,
rows
,
cols
,
path
)
:
# write code here
if
matrix
is
None
and
rows
<=
0
and
cols
<=
0
:
return
False
visited
=
[
0
]
*
(
rows
*
cols
)
pathindex
=
0
for
row
in
range
(
rows
)
:
for
col
in
range
(
cols
)
:
if
self
.
hasPathCore
(
matrix
,
rows
,
cols
,
row
,
col
,
path
,
pathindex
,
visited
)
:
return
True
return
False
def
hasPathCore
(
self
,
matrix
,
rows
,
cols
,
row
,
col
,
path
,
pathindex
,
visited
)
:
haspath
=
False
length
=
len
(
path
)
if
pathindex
==
length
:
return
True
if
rows
>
row
>=
0
and
cols
>
col
>=
0
and
visited
[
row
*
cols
+
col
]
==
0
\
and
matrix
[
row
*
cols
+
col
]
==
path
[
pathindex
]
:
pathindex
+=
1
visited
[
row
*
cols
+
col
]
=
1
haspath
=
self
.
hasPathCore
(
matrix
,
rows
,
cols
,
row
-
1
,
col
,
path
,
pathindex
,
visited
)
or
\
self
.
hasPathCore
(
matrix
,
rows
,
cols
,
row
+
1
,
col
,
path
,
pathindex
,
visited
)
or
\
self
.
hasPathCore
(
matrix
,
rows
,
cols
,
row
,
col
-
1
,
path
,
pathindex
,
visited
)
or
\
self
.
hasPathCore
(
matrix
,
rows
,
cols
,
row
,
col
+
1
,
path
,
pathindex
,
visited
)
if
not
haspath
:
pathindex
-=
1
visited
[
row
*
cols
+
col
]
=
0
return
haspath
栈和队列
65 滑动窗口的最大值
题目描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。
解题思路
- 设置一个两头都能进出的数据结构，python里边的list符合。
- 存储元素的下标而非元素值，目的是好判断是否在窗口中。与当前元素下标差值大于size的都应该滑出窗口。
- 判断当前元素和栈内元素的大小，大于栈尾部元素，尾部元素出栈。
class
Solution
:
def
maxInWindows
(
self
,
num
,
size
)
:
# write code here
if
num
is
None
or
size
<=
0
:
return
[
]
dequeen
=
[
]
windows
=
[
]
for
idx
,
val
in
enumerate
(
num
)
:
if
dequeen
is
[
]
:
dequeen
.
append
(
idx
)
if
idx
-
dequeen
[
0
]
>=
size
:
dequeen
.
pop
(
0
)
while
dequeen
is
not
[
]
and
val
>=
num
[
dequeen
[
-
1
]
]
:
dequeen
.
pop
(
)
dequeen
.
append
(
idx
)
if
idx
>=
size
-
1
:
windows
.
append
(
num
[
dequeen
[
0
]
]
)
return
windows
21 包含min函数的栈
#########################################################################
# 21 包含min函数的栈
#########################################################################
# 另外用一个辅助栈存储最小的元素
# 注意判断栈是否为空
# -*- coding:utf-8 -*-
class
Solution
:
def
__init__
(
self
)
:
self
.
stack
=
[
]
self
.
min_stack
=
[
]
def
push
(
self
,
node
)
:
self
.
stack
.
append
(
node
)
if
self
.
min_stack
==
[
]
:
self
.
min_stack
.
append
(
node
)
else
:
self
.
min_stack
.
append
(
min
(
node
,
self
.
min_stack
[
-
1
]
)
)
def
pop
(
self
)
:
if
self
.
stack
!=
[
]
and
self
.
min_stack
!=
[
]
:
self
.
min_stack
.
pop
(
)
return
self
.
stack
.
pop
(
)
def
top
(
self
)
:
if
self
.
stack
!=
[
]
:
return
self
.
stack
[
-
1
]
def
min
(
self
)
:
if
self
.
min_stack
!=
[
]
:
return
self
.
min_stack
[
-
1
]
22 栈的压入和弹出序列
#########################################################################
# 22 栈的压入和弹出序列
#########################################################################
# 利用辅助栈，判断辅助栈最后能否全部弹出
# -*- coding:utf-8 -*-
class
Solution
:
def
IsPopOrder
(
self
,
pushV
,
popV
)
:
# write code here
if
pushV
==
None
and
popV
==
None
:
return
True
if
pushV
==
None
or
popV
==
None
:
return
False
stack
=
[
]
for
val
in
pushV
:
stack
.
append
(
val
)
while
stack
!=
[
]
and
stack
[
-
1
]
==
popV
[
0
]
:
stack
.
pop
(
)
popV
.
pop
(
0
)
return
True
if
stack
==
[
]
else
False
二叉树
58 二叉树的下一个结点
题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
解题思路
- 中序遍历是左根右。
- 如果这个结点有右子树，下一个结点就是右子树的最左结点。
- 如果这个结点没有右子树，父节点存在，是父节点的左子结点，那么下一个结点就是此父节点，
- 如果不是父节点的左子节点，向上遍历找到一个结点是它父节点的左子节点，此节点的父节点就是下一个结点。
class
Solution
:
def
GetNext
(
self
,
pNode
)
:
# write code here
if
pNode
==
None
:
return
None
if
pNode
.
right
:
right
=
pNode
.
right
while
right
.
left
!=
None
:
right
=
right
.
left
return
right
elif
pNode
.
next
!=
None
:
parent
=
pNode
.
next
if
pNode
==
parent
.
left
:
return
parent
else
:
curNode
=
pNode
while
parent
!=
None
and
curNode
==
parent
.
right
:
curNode
=
parent
parent
=
parent
.
next
return
parent
return
None
59 对称二叉树
题目描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
解题思路
前序遍历： 根左右
自定义反前序遍历： 根右左
只要两个遍历结果一样，就是对称二叉树。也就是两个树，根节点相等，root1的左子树与oot2 的右子树对称，root1的右子树与oot2 的左子树对称，结果就是True
class
Solution
:
def
isSymmetrical
(
self
,
pRoot
)
:
# write code here
return
self
.
isSymmetricalCore
(
pRoot
,
pRoot
)
def
isSymmetricalCore
(
self
,
root1
,
root2
)
:
if
root1
==
None
and
root2
==
None
:
return
True
if
root1
==
None
or
root2
==
None
:
return
False
if
root1
.
val
!=
root2
.
val
:
return
False
return
self
.
isSymmetricalCore
(
root1
.
left
,
root2
.
right
)
and
\
self
.
isSymmetricalCore
(
root1
.
right
,
root2
.
left
)
60 二叉树打印多行
题目描述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
解题思路
层次遍历，另开一个存储空间存储每一层的数值。
# -*- 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
==
None
:
return
[
]
res
=
[
]
queen
=
[
pRoot
]
while
queen
:
cur
=
[
]
size
=
len
(
queen
)
for
_
in
range
(
size
)
:
root
=
queen
.
pop
(
0
)
cur
.
append
(
root
.
val
)
if
root
.
left
:
queen
.
append
(
root
.
left
)
if
root
.
right
:
queen
.
append
(
root
.
right
)
res
.
append
(
cur
)
return
res
61 之字形打印二叉树
题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
解题思路
定义两个栈，当前位置是奇数层时，先存储当前结点的左结点在存右结点到另一个栈中。偶数层时相反。
class
Solution
:
def
Print
(
self
,
pRoot
)
:
# write code here
if
pRoot
==
None
:
return
[
]
stack_odd
=
[
]
stack_even
=
[
]
res
=
[
]
stack_odd
.
append
(
pRoot
)
while
stack_odd
or
stack_even
:
cur
=
[
]
while
stack_odd
:
root
=
stack_odd
.
pop
(
)
cur
.
append
(
root
.
val
)
if
root
.
left
:
stack_even
.
append
(
root
.
left
)
if
root
.
right
:
stack_even
.
append
(
root
.
right
)
if
cur
:
res
.
append
(
cur
)
cur
=
[
]
while
stack_even
:
root
=
stack_even
.
pop
(
)
cur
.
append
(
root
.
val
)
if
root
.
right
:
stack_odd
.
append
(
root
.
right
)
if
root
.
left
:
stack_odd
.
append
(
root
.
left
)
if
cur
:
res
.
append
(
cur
)
return
res
62 序列化二叉树
题目描述
请实现两个函数，分别用来序列化和反序列化二叉树
解题思路
前序遍历序列化，将空值记录成特殊的符号。
class
Solution
:
def
Serialize
(
self
,
root
)
:
# write code here
if
root
==
None
:
return
"#"
return
str
(
root
.
val
)
+
','
+
self
.
Serialize
(
root
.
left
)
+
','
+
self
.
Serialize
(
root
.
right
)
def
Deserialize
(
self
,
s
)
:
# write code here
lis
=
s
.
split
(
','
)
return
self
.
DeserializeTree
(
lis
)
def
DeserializeTree
(
self
,
lis
)
:
if
lis
==
[
]
:
return
None
val
=
lis
.
pop
(
0
)
root
=
None
if
val
!=
'#'
:
root
=
TreeNode
(
int
(
val
)
)
root
.
left
=
self
.
DeserializeTree
(
lis
)
root
.
right
=
self
.
DeserializeTree
(
lis
)
return
root
63 二叉搜索树的第K个结点
#########################################################################
# 63 二叉搜索树的第K个结点
#########################################################################
# 中序遍历 返回第K个
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class
Solution
:
# 返回对应节点TreeNode
def
KthNode
(
self
,
pRoot
,
k
)
:
# write code here
if
pRoot
==
None
:
return
None
stack
=
[
]
res
=
[
]
cur
=
pRoot
while
stack
or
cur
:
while
cur
:
stack
.
append
(
cur
)
cur
=
cur
.
left
cur
=
stack
.
pop
(
)
res
.
append
(
cur
)
cur
=
cur
.
right
print
(
len
(
res
)
)
if
len
(
res
)
==
k
:
return
res
[
k
-
1
]
if
k
>
len
(
res
)
:
return
None
50 二叉树的最低公共祖先
#########################################################################
# 50 二叉树的最低公共祖先
#########################################################################
# （1）二叉搜索树的最低公共祖先
# 判断结点是与根结点的大小关系，都小于根就递归搜索左子树， 找到返回。
# 如果都大于根就递归右子树， 找到返回结点
# 如果不满足上述两个条件，返回根节点
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class
Solution
(
object
)
:
def
lowestCommonAncestor
(
self
,
root
,
p
,
q
)
:
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if
root
==
None
:
return
None
if
root
!=
None
and
root
==
p
or
root
==
q
:
return
root
if
root
.
val
>
p
.
val
and
root
.
val
>
q
.
val
:
left
=
self
.
lowestCommonAncestor
(
root
.
left
,
p
,
q
)
if
left
:
return
left
elif
root
.
val
<
p
.
val
and
root
.
val
<
q
.
val
:
right
=
self
.
lowestCommonAncestor
(
root
.
right
,
p
,
q
)
if
right
:
return
right
else
:
return
root
# （2） 有父节点的最低公共祖先
# 有父节点的二叉树相当于一个双向链表，等价于寻找两个链表的第一个公共结点
class
Solution
(
object
)
:
def
lowestCommonAncestor
(
self
,
root
,
p
,
q
)
:
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if
root
==
None
:
return
None
if
not
p
or
not
q
:
return
None
if
p
==
q
:
return
p
depth
=
lambda
node
:
depth
(
node
.
parent
)
+
1
if
node
else
0
depth_p
=
depth
(
p
)
depth_q
=
depth
(
q
)
minDepth
=
min
(
depth_p
,
depth_q
)
for
i
in
range
(
depth_p
-
minDepth
)
:
p
=
p
.
parent
for
i
in
range
(
depth_q
-
minDepth
)
:
q
=
q
.
parent
while
p
and
q
:
if
p
==
q
:
return
p
else
:
p
=
p
.
parent
q
=
q
.
parent
return
None
# （3） 普通二叉树的最低公共祖先
# 分为三种情况，一是都在左边，二是都在右边，三是左右都有
class
Solution
(
object
)
:
def
lowestCommonAncestor
(
self
,
root
,
p
,
q
)
:
if
root
==
None
:
return
None
if
root
!=
None
and
root
==
p
or
root
==
q
:
return
root
left
=
self
.
lowestCommonAncestor
(
root
.
left
,
p
,
q
)
right
=
self
.
lowestCommonAncestor
(
root
.
right
,
p
,
q
)
if
left
and
right
:
return
root
elif
left
!=
None
:
return
left
elif
right
!=
None
:
return
right
39 二叉树的深度
#########################################################################
# 39 二叉树的深度
#########################################################################
# 递归求解左右子树的深度，二者中较大的加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 here
if
pRoot
==
None
:
return
0
left
=
self
.
TreeDepth
(
pRoot
.
left
)
right
=
self
.
TreeDepth
(
pRoot
.
right
)
return
max
(
left
,
right
)
+
1
判断是不是平衡二叉树
# 判断是不是平衡二叉树
# 方法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 here
if
pRoot
==
None
:
return
0
left
=
self
.
TreeDepth
(
pRoot
.
left
)
right
=
self
.
TreeDepth
(
pRoot
.
right
)
return
max
(
left
,
right
)
+
1
def
IsBalanced_Solution
(
self
,
pRoot
)
:
# write code here
if
pRoot
==
None
:
return
None
left
=
self
.
TreeDepth
(
pRoot
.
left
)
right
=
self
.
TreeDepth
(
pRoot
.
right
)
if
abs
(
left
-
right
)
<=
1
:
return
True
return
False
# 方法2：采用深度优先搜索的后序遍历，先看左右子树是否平衡，这样不用重复遍历左右结点。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class
Solution
:
def
DFS
(
self
,
root
)
:
if
root
==
None
:
return
0
left
=
self
.
DFS
(
root
.
lef
)
if
left
==
-
1
:
return
-
1
right
=
self
.
DFS
(
root
.
right
)
if
right
==
-
1
:
return
-
1
if
abs
(
left
-
right
)
>
1
:
return
-
1
return
max
(
left
,
right
)
+
1
def
IsBalanced_Solution
(
self
,
pRoot
)
:
# write code here
return
self
.
DFS
(
pRoot
)
!=
-
1
19 二叉树的镜像
#########################################################################
# 19 二叉树的镜像
#########################################################################
# 前序遍历 交换左右结点
# -*- 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
==
None
:
return
None
tmp
=
root
.
left
root
.
left
=
root
.
right
root
.
right
=
tmp
if
root
.
left
!=
None
:
self
.
Mirror
(
root
.
left
)
if
root
.
right
!=
None
:
self
.
Mirror
(
root
.
right
)
23 从上往下打印二叉树
#########################################################################
# 23 从上往下打印二叉树
#########################################################################
# -*- 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
)
:
if
root
==
None
:
return
[
]
queen
=
[
root
]
res
=
[
]
while
queen
!=
None
:
root
=
queen
.
pop
(
0
)
res
.
append
(
root
.
val
)
if
root
.
left
!=
None
:
queen
.
append
(
root
.
left
)
if
root
.
right
!=
None
:
queen
.
append
(
root
.
right
)
return
res
24 二叉搜索树的后续遍历
#########################################################################
# 24 二叉搜索树的后续遍历
#########################################################################
# -*- coding:utf-8 -*-
class
Solution
:
def
VerifySquenceOfBST
(
self
,
sequence
)
:
# write code here
if
sequence
==
[
]
:
return
False
if
len
(
sequence
)
==
1
:
return
True
length
=
len
(
sequence
)
root
=
sequence
[
-
1
]
i
=
0
while
sequence
[
i
]
<
root
:
i
+=
1
for
j
in
range
(
i
,
length
-
1
)
:
if
sequence
[
j
]
<
root
:
return
False
left
=
True
right
=
True
if
i
>
0
:
left
=
self
.
VerifySquenceOfBST
(
sequence
[
:
i
]
)
if
length
-
i
-
1
>
0
:
right
=
self
.
VerifySquenceOfBST
(
sequence
[
i
:
length
-
1
]
)
return
left
and
right
25 二叉树中和为某一值的路径
#########################################################################
# 25 二叉树中和为某一值的路径
#########################################################################
# 递归算法
# -*- 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
==
None
:
return
[
]
res
=
[
]
path
=
[
]
self
.
FindPathCore
(
root
,
expectNumber
,
res
,
path
)
return
res
def
FindPathCore
(
self
,
root
,
target
,
res
,
path
)
:
if
root
==
None
:
return
path
.
append
(
root
.
val
)
if
root
.
val
==
target
and
root
.
left
==
None
and
root
.
right
==
None
:
res
.
append
(
path
[
:
]
)
if
root
.
left
!=
None
:
self
.
FindPathCore
(
root
.
left
,
target
-
root
.
val
,
res
,
path
)
if
root
.
right
!=
None
:
self
.
FindPathCore
(
root
.
right
,
target
-
root
.
val
,
res
,
path
)
path
.
pop
(
)
27 二叉搜索树与双向链表
#########################################################################
# 27 二叉搜索树与双向链表
#########################################################################
# 利用中序遍历 左根右
# 左子树的最右节点 --根节点 -- 右子树的最左结点 相连接
# -*- 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
==
None
:
return
None
self
.
Convert
(
pRootOfTree
.
left
)
if
pRootOfTree
.
left
!=
None
:
left
=
pRootOfTree
.
left
while
left
.
right
:
left
=
left
.
right
left
.
right
,
pRootOfTree
.
left
=
pRootOfTree
,
left
self
.
Convert
(
pRootOfTree
.
right
)
if
pRootOfTree
.
right
!=
None
:
right
=
pRootOfTree
.
right
while
right
.
left
:
right
=
right
.
left
right
.
left
,
pRootOfTree
.
right
=
pRootOfTree
,
right
while
pRootOfTree
.
left
:
pRootOfTree
=
pRootOfTree
.
left
return
pRootOfTree
18 树的子结构
#########################################################################
# 18 树的子结构
#########################################################################
# -*- 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
==
None
or
pRoot2
==
None
:
return
False
result
=
False
if
pRoot1
.
val
==
pRoot2
.
val
:
result
=
self
.
helper
(
pRoot1
,
pRoot2
)
or
\
self
.
HasSubtree
(
pRoot1
.
left
,
pRoot2
)
or
\
self
.
HasSubtree
(
pRoot1
.
right
,
pRoot2
)
return
result
def
helper
(
self
,
root1
,
root2
)
:
if
root2
==
None
:
return
True
if
root1
==
None
:
return
False
if
root1
.
val
!=
root2
.
val
:
return
False
return
self
.
helper
(
root1
.
left
,
root2
.
left
)
and
self
.
helper
(
root1
.
right
,
root2
.
right
)
6 重建二叉树
#########################################################################
# 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
pre
==
None
or
tin
==
None
:
return
None
root
=
None
if
pre
:
rootVal
=
pre
[
0
]
rootIndex
=
tin
.
index
(
rootVal
)
root
=
TreeNode
(
rootVal
)
root
.
left
=
self
.
reConstructBinaryTree
(
pre
[
1
:
rootIndex
+
1
]
,
tin
[
:
rootIndex
]
)
root
.
right
=
self
.
reConstructBinaryTree
(
pre
[
rootIndex
+
1
:
]
,
tin
[
rootIndex
+
1
:
]
)
return
root
链表
56 链表中环的入口结点
#########################################################################
# 56 链表中环的入口结点
#########################################################################
# 快慢指针先找到环 然后找到环的结点
# -*- 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
==
None
or
pHead
.
next
==
None
or
pHead
.
next
.
next
==
None
:
return
None
fast
=
pHead
slow
=
pHead
while
fast
.
next
and
fast
.
next
.
next
and
slow
!=
fast
:
fast
=
fast
.
next
.
next
slow
=
slow
.
next
if
slow
==
fast
:
slow
=
pHead
while
fast
!=
slow
:
slow
=
slow
.
next
fast
=
fast
.
next
return
slow
return
None
57 删除链表中重复的结点
#########################################################################
# 57 删除链表中重复的结点
#########################################################################
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class
Solution
:
def
deleteDuplication
(
self
,
pHead
)
:
# write code here
if
pHead
==
None
or
pHead
.
next
==
None
:
return
pHead
pre
=
ListNode
(
0
)
pre
.
next
=
pHead
post
=
pre
cur
=
pHead
while
cur
and
cur
.
next
:
if
cur
.
next
.
val
!=
cur
.
val
:
cur
=
cur
.
next
post
=
post
.
next
else
:
val
=
cur
.
val
while
cur
and
cur
.
val
==
val
:
cur
=
cur
.
next
post
.
next
=
cur
return
pre
.
next
45 圆圈中最后剩下的数字
#########################################################################
# 45 圆圈中最后剩下的数字
#########################################################################
# -*- coding:utf-8 -*-
class
ListNode
:
def
__init__
(
self
,
val
)
:
self
.
val
=
val
self
.
next
=
None
class
Solution
:
def
LastRemaining_Solution
(
self
,
n
,
m
)
:
if
n
==
0
or
m
==
0
:
return
-
1
head
=
self
.
build_circle
(
n
)
step
=
0
while
head
:
step
+=
1
if
step
==
m
:
if
head
.
next
!=
head
:
head
.
val
=
head
.
next
.
val
head
.
next
=
head
.
next
.
next
else
:
return
head
.
val
step
=
0
else
:
head
=
head
.
next
# write code here
def
build_circle
(
self
,
n
)
:
tmp
=
None
head
=
None
for
x
in
range
(
n
)
:
if
tmp
==
None
:
tmp
=
ListNode
(
x
)
head
=
tmp
else
:
tmp
.
next
=
ListNode
(
x
)
tmp
=
tmp
.
next
tmp
.
next
=
head
return
head
# 约瑟夫环
# f(n,m ) = 0 n = 1
# f(n-1, m) + m % n n > 1
class
Solution
:
def
LastRemaining_Solution
(
self
,
n
,
m
)
:
if
n
==
0
or
m
==
0
:
return
-
1
if
n
==
1
:
return
0
res
=
0
for
i
in
range
(
1
,
n
+
1
)
:
res
=
(
res
+
m
)
%
i
return
res
37 两个链表的第一个公共结点
#########################################################################
# 37 两个链表的第一个公共结点
#########################################################################
# 计算两个链表的长度，长链表先走diff步然后两个链表一起走，相交点就是第一个公共结点
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class
Solution
:
def
FindFirstCommonNode
(
self
,
pHead1
,
pHead2
)
:
# write code here
if
pHead1
==
None
or
pHead2
==
None
:
return
None
length1
=
self
.
getLength
(
pHead1
)
length2
=
self
.
getLength
(
pHead2
)
diff
=
length1
-
length2
headlong
=
pHead1
headshort
=
pHead2
if
length2
>
length1
:
diff
=
length2
-
length1
headlong
=
pHead2
headshort
=
pHead1
while
diff
>
0
:
headlong
=
headlong
.
next
diff
-=
1
while
headlong
!=
None
and
headshort
!=
None
and
headlong
!=
headshort
:
headlong
=
headlong
.
next
headshort
=
headshort
.
next
return
headlong
def
getLength
(
self
,
head
)
:
length
=
0
while
head
:
length
+=
1
head
=
head
.
next
return
length
# 更为简单的方法是P1和P2同时向后移动，如果到了链表的最后结点，就接到另一个链表的头部
# 直到两者相遇就是公共结点
class
Solution
:
def
FindFirstCommonNode
(
self
,
pHead1
,
pHead2
)
:
if
pHead1
==
None
or
pHead2
==
None
:
return
None
p1
=
pHead1
p2
=
pHead2
while
p1
!=
p2
:
p1
=
p1
.
next
if
p1
!=
None
else
pHead2
p2
=
p2
.
next
if
p2
!=
None
else
pHead1
return
p1
17 合并两个排序的链表
#########################################################################
# 17 合并两个排序的链表
#########################################################################
# 初始化一个头结点ret与mergehead指向同一个位置。
# 比较两个链表的大小，next指向小的链表，然后merge移动到next 直到遍历完一个链表
# 最后拼接起来不为空的链表
# -*- 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
==
None
:
return
pHead2
if
pHead2
==
None
:
return
pHead1
mergeHead
=
ListNode
(
-
1
)
ret
=
mergeHead
while
pHead1
and
pHead2
:
if
pHead1
.
val
<=
pHead2
.
val
:
mergeHead
.
next
=
pHead1
pHead1
=
pHead1
.
next
else
:
mergeHead
.
next
=
pHead2
pHead2
=
pHead2
.
next
mergeHead
=
mergeHead
.
next
if
pHead1
!=
None
:
mergeHead
.
next
=
pHead1
if
pHead2
!=
None
:
mergeHead
.
next
=
pHead2
return
ret
.
next
数组
51 数组中重复的数字
#########################################################################
# 51 数组中重复的数字
#########################################################################
# -*- coding:utf-8 -*-
class
Solution
:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def
duplicate
(
self
,
numbers
,
duplication
)
:
# write code here
if
numbers
==
[
]
:
return
False
for
i
in
range
(
len
(
numbers
)
)
:
while
numbers
[
i
]
!=
i
:
if
numbers
[
i
]
==
numbers
[
numbers
[
i
]
]
:
duplication
[
0
]
=
numbers
[
i
]
return
True
#numbers[numbers[i]], numbers[i] = numbers[i], numbers[numbers[i]]
tmp
=
numbers
[
i
]
numbers
[
i
]
=
numbers
[
tmp
]
numbers
[
tmp
]
=
tmp
return
False
52 构建乘积数组
#########################################################################
# 52 构建乘积数组
#########################################################################
# 将数组B 分成两段，C = A[0]* ... A[i-1] D = A[i+1:] *...A[n]
# 所以 C[i] = C[i-1] * A[i-1]; D[i] = D[i+1]*A[i+1]
# -*- coding:utf-8 -*-
class
Solution
:
def
multiply
(
self
,
A
)
:
# write code here
if
A
==
[
]
:
return
[
]
B
=
[
1
]
*
len
(
A
)
c
=
1
for
i
in
range
(
len
(
A
)
)
:
d
=
1
c
*=
A
[
i
-
1
]
if
i
>
0
else
c
for
j
in
(
A
[
i
+
1
:
]
)
:
d
*=
j
B
[
i
]
=
c
*
d
return
B
38 数字在排序数组中出现的次数
#########################################################################
# 38 数字在排序数组中出现的次数
#########################################################################
# 排序数组用二分查找的变体
# 分别找到数字的开始和结束位置。
# 1. 找到开始位置。 二分查找的中间值 如果小于k，查找后半段 low=mid+1;
# 如果大于或者等于k,都查找前半段 high=mid
# 终点位置同理
# -*- coding:utf-8 -*-
class
Solution
:
def
GetNumberOfK
(
self
,
data
,
k
)
:
if
data
==
[
]
:
return
0
# write code here
low
=
0
high
=
len
(
data
)
-
1
while
high
>
low
:
mid
=
(
low
+
high
)
//
2
if
data
[
mid
]
<
k
:
low
=
mid
+
1
# 如果当前值大于或者等于k都直接向前半段搜索，知道找到第一个K
else
:
high
=
mid
if
data
[
low
]
!=
k
:
return
0
first
=
low
high
=
len
(
data
)
-
1
while
high
>
low
:
mid
=
(
low
+
high
)
//
2
+
1
if
data
[
mid
]
>
k
:
high
=
mid
-
1
else
:
low
=
mid
end
=
high
return
end
-
first
+
1
40 数组中出现一次的数字
#########################################################################
# 40 数组中出现一次的数字
#########################################################################
# 所有数字异或后肯定有一位是1，按照这一位是1划分数组，然后在每一组中在分别找只出现一次的数字
# -*- coding:utf-8 -*-
class
Solution
:
# 返回[a,b] 其中ab是出现一次的两个数字
def
FindNumsAppearOnce
(
self
,
array
)
:
# write code here
if
array
==
[
]
:
return
[
]
res
=
array
[
0
]
for
num
in
array
[
1
:
]
:
res
^
=
num
mask
=
1
while
res
&
mask
!=
1
:
mask
<<
=
1
num1
=
0
num2
=
0
for
x
in
array
:
# 这一位是0 相与为0， 划分为两组
if
x
&
mask
==
0
:
num1
^
=
x
else
:
num2
^
=
x
return
[
num1
,
num2
]
41 和为s的两个数
#########################################################################
# 41 和为s的两个数
#########################################################################
# 递增序列中寻找和为sde的两个数字，用两个指针前后搜索O(n)
# -*- coding:utf-8 -*-
class
Solution
:
def
FindNumbersWithSum
(
self
,
array
,
tsum
)
:
# write code here
if
array
==
[
]
:
return
[
]
left
=
0
right
=
len
(
array
)
-
1
while
left
<
right
:
if
array
[
left
]
+
array
[
right
]
==
tsum
:
return
[
array
[
left
]
,
array
[
right
]
]
elif
array
[
left
]
+
array
[
right
]
>
tsum
:
right
-=
1
else
:
left
+=
1
return
[
]
# 和为s的连续正数序列
# -*- coding:utf-8 -*-
class
Solution
:
def
FindContinuousSequence
(
self
,
tsum
)
:
# write code here
if
tsum
<=
1
:
return
[
]
small
=
1
big
=
2
ret
=
[
]
cur_sum
=
small
+
big
while
small
<=
(
tsum
+
1
)
//
2
:
# 如果此时相等，记录结果并且big继续加大， 寻找下一组结果
if
cur_sum
==
tsum
:
res
=
list
(
range
(
small
,
big
+
1
)
)
ret
.
append
(
res
)
big
+=
1
cur_sum
+=
big
# 如果大于tsum，加大small的值
elif
cur_sum
>
tsum
:
cur_sum
-=
small
small
+=
1
# 如果小于tsum 加大big
else
:
big
+=
1
cur_sum
+=
big
return
ret
43 骰子点数出现的概率
#########################################################################
# 43 骰子点数出现的概率
#########################################################################
# 骰子出现的点数的概率，用动态规划的思想
# 设dp为n * 6n的二维数组，n代表n个骰子，6n代表最大和为6n
# 递推公式为f(n, sum) = f(n-1, sum-1)+ f(n-1, sum-2) +f(n-1, sum-3)+f(n-1, sum-4)+f(n-1, sum-5)+f(n-1, sum-6)
# 这个四舍五入的真是太费劲了！！！！
from
decimal
import
*
class
Solution
:
def
dicesSum
(
self
,
n
)
:
g_maxvalue
=
6
dp
=
[
[
0
]
*
(
6
*
n
)
for
_
in
range
(
n
)
]
# 初始化n=1时的情况
for
i
in
range
(
g_maxvalue
)
:
dp
[
0
]
[
i
]
=
1
# n=2 开始
for
i
in
range
(
1
,
n
)
:
# i个骰子至少得到i个点（都是1），至多6*i个点（都是6）
for
j
in
range
(
i
,
6
*
(
i
+
1
)
)
:
# 上一个骰子可能出现的点数为1-6
for
k
in
range
(
1
,
6
+
1
)
:
if
j
>=
k
:
dp
[
i
]
[
j
]
+=
dp
[
i
-
1
]
[
j
-
k
]
total
=
6.0
**
n
res
=
[
(
dp
[
n
-
1
]
[
i
]
/
total
)
for
i
in
range
(
6
*
n
)
]
ret
=
[
]
for
i
in
range
(
n
-
1
,
6
*
n
)
:
ret
.
append
(
[
i
+
1
,
float
(
Decimal
(
str
(
res
[
i
]
)
)
.
quantize
(
Decimal
(
'0.00'
)
,
rounding
=
ROUND_HALF_UP
)
)
]
)
return
ret
29 数组中出现超过一半的数字
#########################################################################
# 29 数组中出现超过一半的数字
#########################################################################
# 方法1：从头遍历一遍，选定一个数字，如果相同count+1.不同减去1；如果count为0了，重新选择一个数字。
# 最后的结果就是最后一次把结果设置为1的数字。
# -*- coding:utf-8 -*-
class
Solution
:
def
MoreThanHalfNum_Solution
(
self
,
numbers
)
:
# write code here
if
numbers
==
0
:
return
0
count
=
1
res
=
numbers
[
0
]
for
i
in
range
(
1
,
len
(
numbers
)
)
:
if
count
==
0
:
res
=
numbers
[
i
]
if
numbers
[
i
]
==
res
:
count
+=
1
else
:
count
-=
1
count
=
0
for
x
in
numbers
:
if
x
==
res
:
count
+=
1
if
count
>
len
(
numbers
)
//
2
:
return
res
else
:
return
0
# 方法2 利用Partition函数排序，如果存在，中间位置的数字就是结果
class
Solution
:
def
MoreThanHalfNum_Solution
(
self
,
numbers
)
:
if
numbers
==
[
]
:
return
0
middle
=
(
len
(
numbers
)
)
//
2
left
=
0
right
=
len
(
numbers
)
-
1
index
=
self
.
Partition
(
numbers
,
left
,
right
)
while
index
!=
middle
:
if
index
>
middle
:
right
=
index
-
1
index
=
self
.
Partition
(
numbers
,
left
,
right
)
elif
index
<
middle
:
left
=
index
+
1
index
=
self
.
Partition
(
numbers
,
left
,
right
)
count
=
0
for
x
in
numbers
:
if
x
==
numbers
[
middle
]
:
count
+=
1
if
count
>
middle
:
return
numbers
[
index
]
else
:
return
0
def
Partition
(
self
,
nums
,
begin
,
end
)
:
left
=
begin
+
1
right
=
end
index
=
begin
while
left
<=
right
:
if
nums
[
left
]
>
nums
[
index
]
and
nums
[
right
]
<
nums
[
index
]
:
nums
[
left
]
,
nums
[
right
]
=
nums
[
right
]
,
nums
[
left
]
if
nums
[
left
]
<=
nums
[
index
]
:
left
+=
1
if
nums
[
right
]
>=
nums
[
index
]
:
right
-=
1
nums
[
index
]
,
nums
[
right
]
=
nums
[
right
]
,
nums
[
index
]
return
right
30 最小的k个数
#########################################################################
# 30 最小的k个数
#########################################################################
# 方法1： Partition函数
# -*- coding:utf-8 -*-
class
Solution
:
def
GetLeastNumbers_Solution
(
self
,
tinput
,
k
)
:
# write code here
if
tinput
==
[
]
:
return
[
]
if
k
<=
0
or
k
>
len
(
tinput
)
:
return
[
]
if
k
==
len
(
tinput
)
:
return
self
.
quicksort
(
tinput
,
0
,
k
-
1
)
begin
=
0
end
=
len
(
tinput
)
-
1
index
=
self
.
Partition
(
tinput
,
begin
,
end
)
while
index
!=
k
:
if
index
>
k
:
end
=
index
-
1
index
=
self
.
Partition
(
tinput
,
begin
,
end
)
elif
index
<
k
:
begin
=
index
+
1
index
=
self
.
Partition
(
tinput
,
begin
,
end
)
res
=
tinput
[
:
index
]
return
self
.
quicksort
(
res
,
0
,
len
(
res
)
-
1
)
def
Partition
(
self
,
nums
,
begin
,
end
)
:
index
=
begin
left
=
begin
+
1
right
=
end
while
left
<=
right
:
if
nums
[
left
]
>
nums
[
index
]
and
nums
[
right
]
<
nums
[
index
]
:
nums
[
left
]
,
nums
[
right
]
=
nums
[
right
]
,
nums
[
left
]
if
nums
[
left
]
<=
nums
[
index
]
:
left
+=
1
if
nums
[
right
]
>=
nums
[
index
]
:
right
-=
1
nums
[
index
]
,
nums
[
right
]
=
nums
[
right
]
,
nums
[
index
]
return
right
def
quicksort
(
self
,
nums
,
left
,
right
)
:
if
left
<
right
:
index
=
self
.
Partition
(
nums
,
left
,
right
)
self
.
quicksort
(
nums
,
left
,
index
-
1
)
self
.
quicksort
(
nums
,
index
+
1
,
right
)
return
nums
import
heapq
class
Solution
:
def
GetLeastNumbers_Solution
(
self
,
tinput
,
k
)
:
if
tinput
==
[
]
:
return
[
]
if
k
<=
0
or
k
>
len
(
tinput
)
:
return
[
]
if
k
==
len
(
tinput
)
:
res
=
sorted
(
tinput
)
return
res
res
=
[
]
# 取x的相反数建立最小堆，res的第一个值是最小的，也就是-res[0]是最大的
for
x
in
tinput
:
if
len
(
res
)
<
k
:
res
.
append
(
-
x
)
heapq
.
heapify
(
res
)
for
x
in
tinput
[
k
:
]
:
max_val
=
-
res
[
0
]
if
x
<
max_val
:
heapq
.
heappop
(
res
)
heapq
.
heappush
(
res
,
-
x
)
return
sorted
(
[
-
x
for
x
in
res
]
)
31 连续子数组的最大和
#########################################################################
# 31 连续子数组的最大和
#########################################################################
# -*- coding:utf-8 -*-
class
Solution
:
def
FindGreatestSumOfSubArray
(
self
,
array
)
:
# write code here
if
array
==
[
]
:
return
None
if
len
(
array
)
==
1
:
return
array
[
0
]
dp
=
[
-
float
(
'inf'
)
]
*
len
(
array
)
for
i
in
range
(
len
(
array
)
)
:
if
i
==
0
:
dp
[
i
]
=
array
[
0
]
if
dp
[
i
-
1
]
<=
0
:
dp
[
i
]
=
array
[
i
]
else
:
dp
[
i
]
=
dp
[
i
-
1
]
+
array
[
i
]
return
max
(
dp
)
36 数组中的逆序对
#########################################################################
# 36 数组中的逆序对
#########################################################################
# 采用归并的方法
# 循环将数组一分为二， 直到数组为两个长度为1的数组，在进行合并和排序
# 比如 7564 ——> 75 64 ——>7 5 和 6 4
# 合并相邻数组7 5 存在一个逆序对记录count+1 并且排序为5 7 避免之后重复统计
# -*- coding:utf-8 -*-
from
copy
import
deepcopy
class
Solution
:
def
InversePairs
(
self
,
data
)
:
# write code here;
if
data
==
[
]
:
return
0
start
=
0
end
=
len
(
data
)
-
1
copy
=
deepcopy
(
data
)
count
=
self
.
InverseaPairsCore
(
data
,
copy
,
start
,
end
)
return
count
%
1000000007
def
InverseaPairsCore
(
self
,
data
,
copy
,
start
,
end
)
:
if
start
==
end
:
copy
[
start
]
=
data
[
start
]
return
0
length
=
(
end
-
start
)
//
2
left
=
self
.
InverseaPairsCore
(
data
,
copy
,
start
,
start
+
length
)
right
=
self
.
InverseaPairsCore
(
data
,
copy
,
start
+
length
+
1
,
end
)
i
=
start
+
length
j
=
end
count
=
0
copyindex
=
end
while
i
>=
start
and
j
>
start
+
length
:
if
data
[
i
]
>
data
[
j
]
:
copy
[
copyindex
]
=
data
[
i
]
copyindex
-=
1
i
-=
1
count
+=
j
-
(
start
+
length
)
else
:
copy
[
copyindex
]
=
data
[
j
]
copyindex
-=
1
j
-=
1
while
i
>=
start
:
copy
[
copyindex
]
=
data
[
i
]
copyindex
-=
1
i
-=
1
while
j
>=
start
+
length
+
1
:
copy
[
copyindex
]
=
data
[
j
]
copyindex
-=
1
j
-=
1
s
=
start
while
s
<=
end
:
data
[
s
]
=
copy
[
s
]
s
+=
1
return
left
+
right
+
count
14 调整奇偶数 奇数位于偶数前边
#########################################################################
# 14 调整奇偶数 奇数位于偶数前边
#########################################################################
# -*- coding:utf-8 -*-
class
Solution
:
def
reOrderArray
(
self
,
array
)
:
# write code here
if
array
==
None
:
return
[
]
left
=
0
right
=
len
(
array
)
-
1
while
left
<=
right
:
# 左边是偶数 右边是奇数 交换
if
self
.
isEven
(
array
[
left
]
)
and
not
self
.
isEven
(
array
[
right
]
)
:
array
[
left
]
,
array
[
right
]
=
array
[
right
]
,
array
[
left
]
if
not
self
.
isEven
(
array
[
left
]
)
:
left
+=
1
if
self
.
isEven
(
array
[
right
]
)
:
right
-=
1
return
array
def
isEven
(
self
,
num
)
:
if
num
&
0x1
==
0
:
return
True
return
False
# 采用插入排序的算法
# 插入排序 从小到大排序
# 依次遍历数组中的每个元素，当插入到第 i 个位置时，前边的所有元素V[0] V[1]··· V[i-1]都已经排序完毕。
# 此时将V[i] 与前边的所有元素比较，找到插入位置，插入V[i] ,原来位置上的元素向后顺移。
def
InsertSort
(
nums
)
:
length
=
len
(
nums
)
for
i
in
range
(
length
)
:
key
=
nums
[
i
]
for
j
in
range
(
i
-
1
,
-
1
,
-
1
)
:
if
nums
[
j
]
>
key
:
nums
[
j
+
1
]
=
nums
[
j
]
nums
[
j
]
=
key
return
nums
# 调整奇偶数 奇数位于偶数前边 且不改变数字的前后位置
# 判断当前位置是不是奇数 如果是 遍历前边数字 如果是偶数与当前位置交换
class
Solution
:
def
reOrderArray
(
self
,
array
)
:
length
=
len
(
array
)
for
i
in
range
(
length
)
:
if
self
.
isOdd
(
array
[
i
]
)
:
key
=
array
[
i
]
for
j
in
range
(
i
-
1
,
-
1
,
-
1
)
:
if
not
self
.
isOdd
(
array
[
j
]
)
:
array
[
j
+
1
]
=
array
[
j
]
array
[
j
]
=
key
return
array
def
isOdd
(
self
,
num
)
:
if
num
&
0x1
==
1
:
return
True
return
False
20 顺时针打印矩阵
#########################################################################
# 20 顺时针打印矩阵
#########################################################################
# -*- coding:utf-8 -*-
class
Solution
:
# matrix类型为二维列表，需要返回列表
def
printMatrix
(
self
,
matrix
)
:
# write code here
if
matrix
==
None
:
return
None
def
helper
(
r1
,
r2
,
c1
,
c2
)
:
for
c
in
range
(
c1
,
c2
+
1
)
:
yield
r1
,
c
for
r
in
range
(
r1
+
1
,
r2
+
1
)
:
yield
r
,
c2
if
r1
<
r2
and
c1
<
c2
:
for
c
in
range
(
c2
-
1
,
c1
,
-
1
)
:
yield
r2
,
c
for
r
in
range
(
r2
,
r1
,
-
1
)
:
yield
r
,
c1
r1
,
r2
=
0
,
len
(
matrix
)
-
1
c1
,
c2
=
0
,
len
(
matrix
[
0
]
)
-
1
res
=
[
]
while
r1
<=
r2
and
c1
<=
c2
:
for
r
,
c
in
helper
(
r1
,
r2
,
c1
,
c2
)
:
res
.
append
(
matrix
[
r
]
[
c
]
)
r1
+=
1
r2
-=
1
c1
+=
1
c2
-=
1
return
res
8 旋转数组的最小值
#########################################################################
# 8 旋转数组的最小值
#########################################################################
# -*- coding:utf-8 -*-
class
Solution
:
def
minNumberInRotateArray
(
self
,
rotateArray
)
:
# write code here
if
rotateArray
==
None
:
return
None
left
=
0
right
=
len
(
rotateArray
)
-
1
mid
=
left
while
rotateArray
[
left
]
>=
rotateArray
[
right
]
:
if
right
-
left
==
1
:
mid
=
right
break
mid
=
(
left
+
right
)
//
2
if
rotateArray
[
mid
]
>=
rotateArray
[
left
]
:
left
=
mid
elif
rotateArray
[
mid
]
<=
rotateArray
[
right
]
:
right
=
mid
if
rotateArray
[
mid
]
==
rotateArray
[
left
]
and
rotateArray
[
mid
]
==
rotateArray
[
right
]
:
return
self
.
Inorder
(
rotateArray
,
left
,
right
)
return
rotateArray
[
mid
]
def
Inorder
(
self
,
nums
,
left
,
right
)
:
res
=
nums
[
left
]
for
i
in
range
(
left
,
right
+
1
)
:
if
nums
[
i
]
<
res
:
res
=
nums
[
i
]
return
res
字符串
53 正则表达式的匹配
#########################################################################
# 53 正则表达式匹配
#########################################################################
# 分情况讨论 1. 如果第二个正则不是*， 那么只看第一个字符即可。
# 如果S[0] == P[0] or P[0] == '.', 那么第一个匹配，S和P 同时向后移动一位
# 2. 如果第二个正则是P，情况分为三种。
# 方法2 动态规划
# dp[i][j] 分别表示s[i] 与p[j]的匹配情况
# -*- coding:utf-8 -*-
class
Solution
:
# s, pattern都是字符串
def
match
(
self
,
s
,
pattern
)
:
# write code here
memo
=
{
}
def
dp
(
i
,
j
)
:
if
(
i
,
j
)
not
in
memo
:
# 匹配结束，如果此时遍历完s，表示匹配成功
if
j
==
len
(
pattern
)
:
res
=
i
==
len
(
s
)
else
:
firstmatch
=
len
(
s
)
>
i
and
pattern
[
j
]
in
{
s
[
i
]
,
'.'
}
if
len
(
pattern
)
>
j
+
1
and
pattern
[
j
+
1
]
==
'*'
:
# 如果第二个是*， 匹配0个： dp(i, j+2)
# 或者匹配多个 (第一个匹配且第二个为*) firstmatch and dp(s+1, j)
res
=
dp
(
i
,
j
+
2
)
or
firstmatch
and
dp
(
i
+
1
,
j
)
else
:
# 如果第二个不是*， 如果第一个匹配，那么s,p 同时向前一个
res
=
firstmatch
and
dp
(
i
+
1
,
j
+
1
)
memo
[
i
,
j
]
=
res
return
memo
[
i
,
j
]
return
dp
(
0
,
0
)
class
Solution
:
# s, pattern都是字符串
# 递归方法
def
match
(
self
,
s
,
pattern
)
:
if
len
(
s
)
==
0
and
len
(
pattern
)
==
0
:
return
True
if
len
(
s
)
!=
0
and
len
(
pattern
)
==
0
:
return
False
if
len
(
pattern
)
>
1
and
pattern
[
1
]
==
'*'
:
if
len
(
s
)
>
0
and
(
s
[
0
]
==
pattern
[
0
]
or
pattern
[
0
]
==
'.'
)
:
# 匹配0个 or 匹配1个 or 匹配多个
return
self
.
match
(
s
,
pattern
[
2
:
]
)
\
or
self
.
match
(
s
[
1
:
]
,
pattern
[
2
:
]
)
\
or
self
.
match
(
s
[
1
:
]
,
pattern
)
else
:
# 如果第一个不匹配
return
self
.
match
(
s
,
pattern
[
2
:
]
)
else
:
if
len
(
s
)
>
0
and
(
s
[
0
]
==
pattern
[
0
]
or
pattern
[
0
]
==
'.'
)
:
return
self
.
match
(
s
[
1
:
]
,
pattern
[
1
:
]
)
return
False
54 表示数值的字符串
#########################################################################
# 54 表示数值的字符串
#########################################################################
# -*- coding:utf-8 -*-
class
Solution
:
# s字符串
def
__init__
(
self
)
:
self
.
idx
=
0
self
.
expo
=
{
'e'
,
'E'
}
self
.
sign
=
{
'+'
,
'-'
}
def
isNumeric
(
self
,
s
)
:
# write code here
if
s
==
''
:
return
False
if
s
[
self
.
idx
]
in
self
.
sign
:
self
.
idx
+=
1
if
self
.
idx
==
len
(
s
)
:
return
False
res
=
True
self
.
scanString
(
s
)
print
(
self
.
idx
)
if
self
.
idx
<
len
(
s
)
:
if
s
[
self
.
idx
]
==
'.'
:
self
.
idx
+=
1
self
.
scanString
(
s
)
if
self
.
idx
<
len
(
s
)
and
s
[
self
.
idx
]
in
self
.
expo
:
res
=
self
.
isExpo
(
s
)
elif
s
[
self
.
idx
]
in
self
.
expo
:
res
=
self
.
isExpo
(
s
)
else
:
res
=
False
return
res
and
self
.
idx
==
len
(
s
)
def
scanString
(
self
,
s
)
:
while
self
.
idx
<
len
(
s
)
and
s
[
self
.
idx
]
>=
'0'
and
s
[
self
.
idx
]
<=
'9'
:
self
.
idx
+=
1
def
isExpo
(
self
,
s
)
:
if
s
[
self
.
idx
]
not
in
self
.
expo
:
return
False
self
.
idx
+=
1
if
self
.
idx
<
len
(
s
)
and
s
[
self
.
idx
]
in
self
.
sign
:
self
.
idx
+=
1
if
self
.
idx
==
len
(
s
)
:
return
False
self
.
scanString
(
s
)
return
True
if
self
.
idx
==
len
(
s
)
else
False
49 字符串转换为整数
#########################################################################
# 49 字符串转换为整数
#########################################################################
# -*- coding:utf-8 -*-
class
Solution
:
def
StrToInt
(
self
,
s
)
:
# write code here
s
=
s
.
strip
(
)
if
len
(
s
)
==
0
:
return
0
if
s
[
0
]
==
'-'
:
sign
=
-
1
else
:
sign
=
1
if
s
[
0
]
in
{
'+'
,
'-'
}
:
s
=
s
[
1
:
]
if
len
(
s
)
==
0
:
return
0
res
=
0
if
not
s
[
0
]
.
isdigit
(
)
:
return
0
for
x
in
s
:
if
x
.
isdigit
(
)
:
res
=
10
*
res
+
ord
(
x
)
-
ord
(
'0'
)
else
:
break
return
0
return
max
(
-
2
**
(
31
)
,
min
(
2
**
31
-
1
,
sign
*
res
)
)
42 翻转单词顺序
#########################################################################
# 42 翻转单词顺序
#########################################################################
# 先翻转整个句子， 然后翻转每个单词
class
Solution
:
def
ReverseSentence
(
self
,
s
)
:
# write code here
begin
=
0
end
=
len
(
s
)
-
1
s
=
self
.
ReverseWord
(
list
(
s
)
[
begin
:
end
+
1
]
)
begin
=
0
end
=
0
res
=
''
while
end
<
len
(
s
)
:
if
s
[
end
]
==
' '
:
reverse_word
=
self
.
ReverseWord
(
list
(
s
)
[
begin
:
end
]
)
res
+=
reverse_word
res
+=
s
[
end
]
begin
=
end
+
1
elif
end
==
len
(
s
)
-
1
:
reverse_word
=
self
.
ReverseWord
(
list
(
s
)
[
begin
:
end
+
1
]
)
res
+=
reverse_word
end
+=
1
return
res
def
ReverseWord
(
self
,
s
)
:
if
s
==
''
:
return
''
begin
=
0
end
=
len
(
s
)
-
1
while
begin
<=
end
:
s
[
begin
]
,
s
[
end
]
=
s
[
end
]
,
s
[
begin
]
begin
+=
1
end
-=
1
return
''
.
join
(
s
)
左旋转字符串
class
Solution
:
def
LeftRotateString
(
self
,
s
,
n
)
:
if
s
==
''
:
return
''
if
n
>
len
(
s
)
:
return
None
left
=
self
.
ReverseWord
(
list
(
s
[
:
n
]
)
)
right
=
self
.
ReverseWord
(
list
(
s
[
n
:
]
)
)
res
=
self
.
ReverseWord
(
list
(
left
+
right
)
)
return
res
def
ReverseWord
(
self
,
s
)
:
begin
=
0
end
=
len
(
s
)
-
1
while
begin
<=
end
:
s
[
begin
]
,
s
[
end
]
=
s
[
end
]
,
s
[
begin
]
begin
+=
1
end
-=
1
return
''
.
join
(
s
)
32 1到n整数中1出现的次数
#########################################################################
# 32 1到n整数中1出现的次数
#########################################################################
# 找数字规律求解 比如21345这个数，分为1-1345和1346-21345两个阶段。
# 1346-21345 最高位的1为10000个也就是10^(n-1)个；如果最高位是1，比如12345 最高位则是2345+1=2346个1
# 剩下的四位数可以分为两段 1346-11345和11345-21345，两段中都可以选择一位为1，其余三位的选择分别有0-9 10 个数字，
# 也就是2*4*10^3
# 1-1345可以递归求解
# -*- coding:utf-8 -*-
class
Solution
:
def
NumberOf1Between1AndN_Solution
(
self
,
n
)
:
# write code here
length
=
len
(
str
(
n
)
)
first
=
int
(
str
(
n
)
[
0
]
)
if
length
==
0
:
return
None
if
length
==
1
and
first
==
0
:
return
0
if
length
==
1
and
first
>
0
:
return
1
# 求得最高位的1
if
first
>
1
:
numberFirst_1
=
10
**
(
length
-
1
)
else
:
numberFirst_1
=
int
(
str
(
n
)
[
1
:
]
)
+
1
# 求得剩下的几位数中的1
numberOther_1
=
first
*
(
length
-
1
)
*
10
**
(
length
-
2
)
numberRecursive
=
self
.
NumberOf1Between1AndN_Solution
(
int
(
str
(
n
)
[
1
:
]
)
)
return
numberFirst_1
+
numberOther_1
+
numberRecursive
33 把数排成最小的数
#########################################################################
# 33 把数排成最小的数
#########################################################################
# 自定义比较规则为 如果mn < nm,则定义m
# -*- coding:utf-8 -*-
import
functools
class
Solution
:
def
PrintMinNumber
(
self
,
numbers
)
:
# write code here
if
numbers
==
[
]
:
return
''
if
len
(
numbers
)
==
1
:
return
str
(
numbers
[
0
]
)
def
mycmp
(
num1
,
num2
)
:
return
cmp
(
num1
+
num2
,
num2
+
num1
)
nums
=
[
str
(
n
)
for
n
in
numbers
]
res
=
sorted
(
nums
,
mycmp
)
return
''
.
join
(
res
)
34 丑数
#########################################################################
# 34 丑数
#########################################################################
# 空间换时间。每一个丑数都是前一个丑数乘以2 3 5 得到的。
# 所以最小的丑数= min(现在最小的乘以2,3,4后的结果)
# 而且对于现有的每一个丑数乘以2之后，肯定存在一个数T2， 在他之前的都小于现有的，在他之后的都会大于现有的最小丑数
# 对于3 和 5 的同理。只需要找到T2 T3 T5 即可。
# -*- coding:utf-8 -*-
class
Solution
:
def
GetUglyNumber_Solution
(
self
,
index
)
:
# write code here
if
index
<=
0
:
return
0
if
index
==
1
:
return
1
uglynum
=
[
0
]
*
index
nextidx
=
1
uglynum
[
0
]
=
1
p2
,
p3
,
p5
=
0
,
0
,
0
while
nextidx
<
index
:
min_ugly
=
min
(
uglynum
[
p2
]
*
2
,
uglynum
[
p3
]
*
3
,
uglynum
[
p5
]
*
5
)
uglynum
[
nextidx
]
=
min_ugly
while
uglynum
[
p2
]
*
2
<=
min_ugly
:
p2
+=
1
while
uglynum
[
p3
]
*
3
<=
min_ugly
:
p3
+=
1
while
uglynum
[
p5
]
*
5
<=
min_ugly
:
p5
+=
1
nextidx
+=
1
return
uglynum
[
index
-
1
]
35 第一个只出现一次的字符
#########################################################################
# 35 第一个只出现一次的字符
#########################################################################
# hash表存储字符和次数，因为python里边的dict不会按照顺序存储，所以单独用一个list存储顺序
# -*- coding:utf-8 -*-
class
Solution
:
def
FirstNotRepeatingChar
(
self
,
s
)
:
# write code here
if
s
==
''
:
return
-
1
dic
=
{
}
once
=
[
]
for
i
in
range
(
len
(
s
)
)
:
if
s
[
i
]
not
in
once
:
once
.
append
(
i
)
if
s
[
i
]
not
in
dic
:
dic
[
s
[
i
]
]
=
1
else
:
dic
[
s
[
i
]
]
+=
1
for
i
in
once
:
if
dic
[
s
[
i
]
]
==
1
:
return
i
return
None
28 字符串的全排列
#########################################################################
# 28 字符串的全排列
#########################################################################
# 全排列方法 字符串的全排列 八皇后问题 正方体问题
# -*- coding:utf-8 -*-
class
Solution
:
def
Permutation
(
self
,
ss
)
:
if
ss
==
''
:
return
[
]
res
=
[
]
path
=
''
self
.
PermutationCore
(
ss
,
res
,
path
)
res
=
set
(
res
)
return
sorted
(
list
(
res
)
)
def
PermutationCore
(
self
,
s
,
res
,
path
)
:
if
s
==
''
:
res
.
append
(
path
)
else
:
for
i
in
range
(
len
(
s
)
)
:
self
.
PermutationCore
(
s
[
:
i
]
+
s
[
i
+
1
:
]
,
res
,
path
+
s
[
i
]
)
# 八皇后问题
# 设置一个一维数组，num[i] = j 表示第i行皇后的位置是第j列
# i 从0-n全排列 判断是否符合要求 不同行不同列不同一对角线
# 一维数组能够保证不同行不同列 对角线是y=x+b，y1-y2 = x1-x2 代表是同一对角线
# 所以 不在同一对角线要保证 abs(nums[i] - nums[n]) ！= n-i and nums[i] != nums[n]
class
Solution
(
object
)
:
def
solveNQueens
(
self
,
n
)
:
"""
:type n: int
:rtype: List[List[str]]
"""
if
n
<=
0
:
return
''
num
=
[
-
1
]
*
n
res
=
[
]
path
=
[
]
self
.
Permutation
(
num
,
0
,
res
,
path
)
return
res
def
Permutation
(
self
,
num
,
index
,
res
,
path
)
:
if
index
==
len
(
num
)
:
res
.
append
(
path
)
return
else
:
for
i
in
range
(
len
(
num
)
)
:
num
[
index
]
=
i
if
self
.
CheckValid
(
num
,
index
)
:
tmp
=
'.'
*
len
(
num
)
self
.
Permutation
(
num
,
index
+
1
,
res
,
path
+
[
tmp
[
:
i
]
+
'Q'
+
tmp
[
i
+
1
:
]
]
)
def
CheckValid
(
self
,
num
,
index
)
:
for
i
in
range
(
index
)
:
if
abs
(
num
[
i
]
-
num
[
index
]
)
==
index
-
i
or
num
[
i
]
==
num
[
index
]
:
return
False
return
True
数值
11 数值的整数次方
#########################################################################
# 11 数值的整数次方
################################### ######################################
# a^n = a ^(n/2) * a(n/2) 偶数
a
*
(
n
-
1
/
2
)
*
a
(
n
-
1
/
2
)
奇数
# -*- coding:utf-8 -*-
class
Solution
:
def
Power
(
self
,
base
,
exponent
)
:
# write code here
if
base
==
1
or
exponent
==
0
:
return
1
if
exponent
==
1
:
return
base
if
exponent
<
0
:
return
1.0
/
self
.
Power
(
base
,
abs
(
exponent
)
)
result
=
self
.
Power
(
base
,
exponent
>>
1
)
result
*=
result
if
exponent
&
0x1
==
1
:
result
*=
base
return
result
