文章目录
回溯法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.递归实现回溯。依次访问当前位置的上下左右的格子。
import sys
class Solution:
def movingCount(self
, threshold
, rows
, cols
):
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回溯到前一个位置。
class Solution:
def hasPath(self
, matrix
, rows
, cols
, path
):
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
):
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函数的栈
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 栈的压入和弹出序列
class Solution:
def IsPopOrder(self
, pushV
, popV
):
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
):
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
):
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 二叉树打印多行
题目描述 从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。 解题思路 层次遍历，另开一个存储空间存储每一层的数值。
class Solution:
def Print(self
, pRoot
):
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
):
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
):
if root
== None:
return "#"
return str(root
.val
) + ',' + self
.Serialize
(root
.left
) + ',' + self
.Serialize
(root
.right
)
def Deserialize(self
, s
):
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个结点
class Solution:
def KthNode(self
, pRoot
, k
):
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 二叉树的最低公共祖先
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
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
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 二叉树的深度
class Solution:
def TreeDepth(self
, pRoot
):
if pRoot
== None:
return 0
left
= self
.TreeDepth
(pRoot
.left
)
right
= self
.TreeDepth
(pRoot
.right
)
return max(left
, right
) +1
判断是不是平衡二叉树
class Solution:
def TreeDepth(self
, pRoot
):
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
):
if pRoot
== None:
return None
left
= self
.TreeDepth
(pRoot
.left
)
right
= self
.TreeDepth
(pRoot
.right
)
if abs(left
- right
) <= 1:
return True
return False
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
):
return self
.DFS
(pRoot
) != -1
19 二叉树的镜像
class Solution:
def Mirror(self
, root
):
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 从上往下打印二叉树
class Solution:
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 二叉搜索树的后续遍历
class Solution:
def VerifySquenceOfBST(self
, sequence
):
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 二叉树中和为某一值的路径
class Solution:
def FindPath(self
, root
, expectNumber
):
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 二叉搜索树与双向链表
class Solution:
def Convert(self
, pRootOfTree
):
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 树的子结构
class Solution:
def HasSubtree(self
, pRoot1
, pRoot2
):
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 重建二叉树
class Solution:
def reConstructBinaryTree(self
, pre
, tin
):
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 链表中环的入口结点
class Solution:
def EntryNodeOfLoop(self
, pHead
):
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 删除链表中重复的结点
class Solution:
def deleteDuplication(self
, pHead
):
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 圆圈中最后剩下的数字
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
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
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 两个链表的第一个公共结点
class Solution:
def FindFirstCommonNode(self
, pHead1
, pHead2
):
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
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 合并两个排序的链表
class Solution:
def Merge(self
, pHead1
, pHead2
):
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 数组中重复的数字
class Solution:
def duplicate(self
, numbers
, duplication
):
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
tmp
= numbers
[i
]
numbers
[i
] = numbers
[tmp
]
numbers
[tmp
] = tmp
return False
52 构建乘积数组
class Solution:
def multiply(self
, A
):
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 数字在排序数组中出现的次数
class Solution:
def GetNumberOfK(self
, data
, k
):
if data
== []:
return 0
low
= 0
high
= len(data
) - 1
while high
> low
:
mid
= (low
+ high
) // 2
if data
[mid
] < k
:
low
= mid
+ 1
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 数组中出现一次的数字
class Solution:
def FindNumsAppearOnce(self
, array
):
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
:
if x
& mask
== 0:
num1
^= x
else:
num2
^= x
return [num1
, num2
]
41 和为s的两个数
class Solution:
def FindNumbersWithSum(self
, array
, tsum
):
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 []
class Solution:
def FindContinuousSequence(self
, tsum
):
if tsum
<= 1:
return []
small
= 1
big
= 2
ret
= []
cur_sum
= small
+ big
while small
<= (tsum
+ 1) // 2:
if cur_sum
== tsum
:
res
= list(range(small
, big
+1))
ret
.append
(res
)
big
+= 1
cur_sum
+= big
elif cur_sum
> tsum
:
cur_sum
-= small
small
+= 1
else:
big
+= 1
cur_sum
+= big
return ret
43 骰子点数出现的概率
from decimal
import *
class Solution:
def dicesSum(self
, n
):
g_maxvalue
= 6
dp
= [[0] * (6 * n
) for _
in range(n
)]
for i
in range(g_maxvalue
):
dp
[0][i
] = 1
for i
in range(1, n
):
for j
in range(i
, 6 * (i
+ 1)):
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 数组中出现超过一半的数字
class Solution:
def MoreThanHalfNum_Solution(self
, numbers
):
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
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个数
class Solution:
def GetLeastNumbers_Solution(self
, tinput
, k
):
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
= []
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 连续子数组的最大和
class Solution:
def FindGreatestSumOfSubArray(self
, array
):
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 数组中的逆序对
from copy
import deepcopy
class Solution:
def InversePairs(self
, data
):
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 调整奇偶数 奇数位于偶数前边
class Solution:
def reOrderArray(self
, array
):
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
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 顺时针打印矩阵
class Solution:
def printMatrix(self
, matrix
):
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 旋转数组的最小值
class Solution:
def minNumberInRotateArray(self
, rotateArray
):
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 正则表达式的匹配
class Solution:
def match(self
, s
, pattern
):
memo
= {}
def dp(i
, j
):
if (i
, j
) not in memo
:
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] == '*':
res
= dp
(i
, j
+ 2) or firstmatch
and dp
(i
+ 1, j
)
else:
res
= firstmatch
and dp
(i
+ 1, j
+ 1)
memo
[i
, j
] = res
return memo
[i
, j
]
return dp
(0, 0)
class Solution:
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] == '.'):
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 表示数值的字符串
class Solution:
def __init__(self
):
self
.idx
= 0
self
.expo
= {'e', 'E'}
self
.sign
= {'+', '-'}
def isNumeric(self
, s
):
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 字符串转换为整数
class Solution:
def StrToInt(self
, s
):
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 翻转单词顺序
class Solution:
def ReverseSentence(self
, s
):
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出现的次数
class Solution:
def NumberOf1Between1AndN_Solution(self
, n
):
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
if first
> 1:
numberFirst_1
= 10 ** (length
- 1)
else:
numberFirst_1
= int(str(n
)[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 把数排成最小的数
import functools
class Solution:
def PrintMinNumber(self
, numbers
):
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 丑数
class Solution:
def GetUglyNumber_Solution(self
, index
):
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 第一个只出现一次的字符
class Solution:
def FirstNotRepeatingChar(self
, s
):
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 字符串的全排列
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
])
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 数值的整数次方
a
* (n
-1/2) * a
(n
-1/2) 奇数
class Solution:
def Power(self
, base
, exponent
):
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
