持续更新中…
文章目录
- 1 链表
- 1.1 从尾到头打印链表
- 1.2 链表中倒数第k个结点
- 1.3 反转链表
- 1.4 合并两个排序的链表
- 1.5 链表中环的入口结点
- 1.6 两个链表的第一个公共结点
- 1.7 复杂链表的复制
- 1.8 二叉搜索树与双向链表
- 1.9 删除链表中重复的节点
- 2 树
- 2.1 二叉树的镜像
- 2.2 对称的二叉树
- 2.3 从上往下打印二叉树
- 2.4 二叉树的下一个结点
- 2.5 重建二叉树
- 2.6 二叉树的深度
- 2.7 树的子结构
- 2.8 二叉搜索树的后序遍历序列
- 2.9 二叉树中和为某一值的路径
- 2.10 平衡二叉树
- 2.11 按之字形顺序打印二叉树
- 2.12 把二叉树打印成多行
- 2.13 序列化二叉树
- 2.14 二叉搜索树的第k个节点
- 3 数组、矩阵
- 3.1 二维数组中的查找
- 3.2 替换空格
- 3.3 旋转数组的最小数字
- 3.4 调整数组顺序使奇数位于偶数前面
- 3.5 数组中出现次数超过一半的数字
- 3.6 连续子数组的最大和
- 3.7 整数中1出现的次数（从1到n整数中1出现的次数）
- 3.8 和为S的两个数字
- 3.9 矩阵中的路径
- 3.10 机器人的运动范围
- 3.11 数字在排序数组中出现的次数
- 3.12 数组中只出现一次的两个数
- 3.13 和为S的连续正数序列
- 3.14 最长递增子序列
- 3.15 矩阵乘积问题
- 3.16 顺时针打印矩阵
- 3.17 最小的k个数
- 3.18 把数组排成最小的数
- 3.19 第一个只出现一次的字符
- 3.20 数组中的逆序对
- 3.21 扑克牌顺子
- 3.22 数组中重复的数
- 3.23 构建乘积数组
- 3.24 数据流中的中位数
- 4 字符串
- 4.1 左旋转字符串
- 4.2 翻转单词顺序列
- 4.3 把字符串转换成整数
- 4.4 表示数值的字符串
- 4.5 字符串的排列
- 4.6 正则表达式匹配
- 4.7 字符串中第一个不重复的字符
- 5 栈和队列
- 5.1 用两个栈实现队列
- 5.2 包含min函数的栈
- 5.3 滑动窗口的最大值
- 5.4 栈的压入、弹出序列
- 6 位运算
- 6.1 二进制中1的个数
- 6.2 是否是2的整数次方
- 7 其他经典算法
- 7.1 数值的整数次方
- 7.2 斐波那契数列
- 7.3 跳台阶 / 矩形覆盖
- 7.4 变态跳台阶
- 7.5 求1+2+3+...+n
- 7.6 剪绳子
- 7.7 丑数
- 7.8 不用加减乘除做加法
- 8 排序、搜索
- 8.1 冒泡排序
- 8.2 插入排序
- 8.3 选择排序
- 8.4 归并排序
- 8.5 快速排序
- 8.6 堆排序
- 8.7 二分搜索
- 9 机器学习
- 9.1 KMeans实现
1 链表
1.1 从尾到头打印链表
输入一个链表，按链表值从尾到头的顺序返回一个 List 。
class
Solution
:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
def
printListFromTailToHead
(
self
,
listNode
)
:
# write code here
return_list
=
[
]
while
listNode
:
return_list
.
insert
(
0
,
listNode
.
val
)
listNode
=
listNode
.
next
return
return_list
1.2 链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
class
Solution
:
def
FindKthToTail
(
self
,
head
,
k
)
:
# write code here
if
head
is
None
:
return
head
pPre
=
head
pBack
=
head
for
i
in
range
(
k
)
:
if
pPre
is
None
:
return
None
pPre
=
pPre
.
next
while
pPre
is
not
None
:
pPre
=
pPre
.
next
pBack
=
pBack
.
next
return
pBack
1.3 反转链表
输入一个链表，反转链表后，输出新链表的表头。
class
Solution
:
# 返回ListNode
def
ReverseList
(
self
,
pHead
)
:
# write code here
if
pHead
is
None
:
return
pHead
if
pHead
.
next
is
None
:
return
pHead
pPre
=
None
while
pHead
:
tmp
=
pHead
.
next
pHead
.
next
=
pPre
pPre
=
pHead
pHead
=
tmp
return
pPre
1.4 合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
class
Solution
:
# 返回合并后列表
def
Merge
(
self
,
pHead1
,
pHead2
)
:
# write code here
if
pHead1
is
None
and
pHead2
is
None
:
return
None
if
pHead1
is
None
:
return
pHead2
if
pHead2
is
None
:
return
pHead1
pHead
=
ListNode
(
None
)
pRet
=
pHead
while
pHead1
and
pHead2
:
if
pHead1
.
val
>
pHead2
.
val
:
pHead
.
next
=
pHead2
pHead
=
pHead
.
next
pHead2
=
pHead2
.
next
else
:
pHead
.
next
=
pHead1
pHead
=
pHead
.
next
pHead1
=
pHead1
.
next
while
pHead1
:
pHead
.
next
=
pHead1
pHead
=
pHead
.
next
pHead1
=
pHead1
.
next
while
pHead2
:
pHead
.
next
=
pHead2
pHead
=
pHead
.
next
pHead2
=
pHead2
.
next
return
pRet
.
next
1.5 链表中环的入口结点
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出None。
思路简述 ： 快慢指针思想的应用。
Step1
：快慢指针都指向头节点；
Step2
：每一次操作快指针走两步（执行两次 .next），慢指针走一步（执行一次 .next）；
Step3
：循环执行Step2，当快慢指针相遇，则说明两个指针均在某一个环中；
Step4
：慢指针不动，快指针每次走一步，环中节点数加一（num_of_node_circle +1)；
Step5
：循环执行Step4，当快慢指针再一次相遇，此时快指针绕环一圈，num_of_node_circle即为环中节点个数；
Step6
：此时，可以根据 “1.2 链表中倒数第k个结点” 的思路，找到环的入口处。
class
Solution
:
def
EntryNodeOfLoop
(
self
,
pHead
)
:
# write code here
if
pHead
is
None
or
pHead
.
next
is
None
:
return
None
pFast
=
pHead
.
next
pSlow
=
pHead
# Find the circle
while
pFast
!=
pSlow
:
pFast
=
pFast
.
next
pFast
=
pFast
.
next
pSlow
=
pSlow
.
next
if
pFast
is
None
:
return
None
# Count the number of node in circle
num_of_node_circle
=
1
pFast
=
pFast
.
next
while
pFast
!=
pSlow
:
num_of_node_circle
=
num_of_node_circle
+
1
pFast
=
pFast
.
next
pFast
=
pHead
# Find the entrance of the circle
for
i
in
range
(
num_of_node_circle
)
:
pFast
=
pFast
.
next
while
pFast
!=
pHead
:
pHead
=
pHead
.
next
pFast
=
pFast
.
next
return
pHead
1.6 两个链表的第一个公共结点
输入两个链表，找出它们的第一个公共结点。
class
Solution
:
def
FindFirstCommonNode
(
self
,
pHead1
,
pHead2
)
:
# write code here
if
not
pHead1
:
return
None
if
not
pHead2
:
return
None
length_pHead1
=
0
length_pHead2
=
0
p_head_1
=
pHead1
p_head_2
=
pHead2
while
p_head_1
:
length_pHead1
=
length_pHead1
+
1
p_head_1
=
p_head_1
.
next
while
p_head_2
:
length_pHead2
=
length_pHead2
+
1
p_head_2
=
p_head_2
.
next
if
length_pHead1
>
length_pHead2
:
for
i
in
range
(
length_pHead1
-
length_pHead2
)
:
pHead1
=
pHead1
.
next
else
:
for
i
in
range
(
length_pHead2
-
length_pHead1
)
:
pHead2
=
pHead2
.
next
while
pHead1
!=
pHead2
:
pHead1
=
pHead1
.
next
pHead2
=
pHead2
.
next
return
pHead1
1.7 复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
class
Solution
:
# 返回 RandomListNode
def
Clone
(
self
,
pHead
)
:
pNode
=
self
.
CloneNode
(
pHead
)
pNode
=
self
.
ConnectRandomNodes
(
pNode
)
return
self
.
ReconnectNodes
(
pNode
)
def
CloneNode
(
self
,
pHead
)
:
pNode
=
pHead
while
pNode
is
not
None
:
pCloned
=
RandomListNode
(
pNode
.
label
)
pCloned
.
next
=
pNode
.
next
pNode
.
next
=
pCloned
pNode
=
pCloned
.
next
return
pHead
def
ConnectRandomNodes
(
self
,
pHead
)
:
pNode
=
pHead
while
pNode
is
not
None
:
pCloned
=
pNode
.
next
if
pNode
.
random
is
not
None
:
pCloned
.
random
=
pNode
.
random
.
next
pNode
=
pCloned
.
next
return
pHead
def
ReconnectNodes
(
self
,
pHead
)
:
pNode
=
pHead
pClonedHead
=
pHead
if
pNode
is
not
None
:
pClonedNode
=
pNode
.
next
pClonedHead
=
pNode
.
next
pNode
.
next
=
pClonedNode
.
next
pNode
=
pNode
.
next
while
pNode
is
not
None
:
pClonedNode
.
next
=
pNode
.
next
pClonedNode
=
pClonedNode
.
next
pNode
.
next
=
pClonedNode
.
next
pNode
=
pNode
.
next
return
pClonedHead
1.8 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
class
Solution
:
def
Convert
(
self
,
pRootOfTree
)
:
# write code here
pLastNodeInList
=
None
pLastNodeInList
=
self
.
CovertNode
(
pRootOfTree
,
pLastNodeInList
)
pHeadOfList
=
pLastNodeInList
while
pHeadOfList
is
not
None
and
pHeadOfList
.
left
is
not
None
:
pHeadOfList
=
pHeadOfList
.
left
return
pHeadOfList
def
CovertNode
(
self
,
pNode
,
pLastNodeInList
)
:
if
pNode
is
None
:
return
pCurrent
=
pNode
if
pCurrent
.
left
is
not
None
:
pLastNodeInList
=
self
.
CovertNode
(
pCurrent
.
left
,
pLastNodeInList
)
pCurrent
.
left
=
pLastNodeInList
if
pLastNodeInList
is
not
None
:
pLastNodeInList
.
right
=
pCurrent
pLastNodeInList
=
pCurrent
if
pCurrent
.
right
is
not
None
:
pLastNodeInList
=
self
.
CovertNode
(
pCurrent
.
right
,
pLastNodeInList
)
return
pLastNodeInList
1.9 删除链表中重复的节点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5 。
class
Solution
:
def
deleteDuplication
(
self
,
pHead
)
:
if
pHead
is
None
:
return
pHead
pSlow
=
ListNode
(
None
)
pSlow
.
next
=
pHead
pFast
=
pHead
pHead
=
pSlow
flag_duplication
=
False
while
pFast
and
pFast
.
next
:
tmp_val
=
pFast
.
val
pFast
=
pFast
.
next
if
tmp_val
==
pFast
.
val
:
flag_duplication
=
True
elif
flag_duplication
:
flag_duplication
=
False
pSlow
.
next
=
pFast
else
:
pSlow
=
pSlow
.
next
if
pSlow
.
next
!=
pFast
:
pSlow
.
next
=
None
return
pHead
.
next
2 树
2.1 二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
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
if
root
.
left
:
self
.
Mirror
(
root
.
left
)
if
root
.
right
:
self
.
Mirror
(
root
.
right
)
2.2 对称的二叉树
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
class
Solution
:
def
isSymmetrical
(
self
,
pRoot
)
:
# write code here
return
self
.
isSymmetrical_rec
(
pRoot
,
pRoot
)
def
isSymmetrical_rec
(
self
,
pRoot1
,
pRoot2
)
:
if
pRoot1
is
None
and
pRoot2
is
None
:
return
True
if
pRoot1
is
None
or
pRoot2
is
None
:
return
False
if
pRoot1
.
val
!=
pRoot2
.
val
:
return
False
return
self
.
isSymmetrical_rec
(
pRoot1
.
left
,
pRoot2
.
right
)
and
self
.
isSymmetrical_rec
(
pRoot1
.
right
,
pRoot2
.
left
)
2.3 从上往下打印二叉树
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
class
Solution
:
# 返回从上到下每个节点值列表，例：[1,2,3]
def
PrintFromTopToBottom
(
self
,
root
)
:
if
root
is
None
:
return
[
]
return_list
=
[
]
queue
=
[
]
queue
.
append
(
root
)
while
len
(
queue
)
:
root
=
queue
.
pop
(
0
)
return_list
.
append
(
root
.
val
)
if
root
.
left
:
queue
.
append
(
root
.
left
)
if
root
.
right
:
queue
.
append
(
root
.
right
)
return
return_list
2.4 二叉树的下一个结点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
class
Solution
:
def
GetNext
(
self
,
pNode
)
:
# write code here
if
pNode
is
None
:
return
None
pNext
=
None
if
pNode
.
right
:
pRight
=
pNode
.
right
while
pRight
.
left
:
pRight
=
pRight
.
left
pNext
=
pRight
elif
pNode
.
next
:
pCurrent
=
pNode
pParent
=
pNode
.
next
while
pParent
and
pCurrent
==
pParent
.
right
:
pCurrent
=
pParent
pParent
=
pParent
.
next
pNext
=
pParent
return
pNext
2.5 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
class
Solution
:
# 返回构造的TreeNode根节点
def
reConstructBinaryTree
(
self
,
pre
,
tin
)
:
# write code here
if
len
(
pre
)
==
0
:
return
None
if
len
(
pre
)
==
1
:
return
TreeNode
(
pre
[
0
]
)
else
:
root
=
TreeNode
(
pre
[
0
]
)
root
.
left
=
self
.
reConstructBinaryTree
(
pre
[
1
:
tin
.
index
(
pre
[
0
]
)
+
1
]
,
tin
[
:
tin
.
index
(
pre
[
0
]
)
]
)
root
.
right
=
self
.
reConstructBinaryTree
(
pre
[
tin
.
index
(
pre
[
0
]
)
+
1
:
]
,
tin
[
tin
.
index
(
pre
[
0
]
)
+
1
:
]
)
return
root
2.6 二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
class
Solution
:
def
TreeDepth
(
self
,
pRoot
)
:
# write code here
if
pRoot
is
None
:
return
0
n_left
=
self
.
TreeDepth
(
pRoot
.
left
)
n_right
=
self
.
TreeDepth
(
pRoot
.
right
)
if
n_left
>
n_right
:
return
n_left
+
1
else
:
return
n_right
+
1
2.7 树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
class
Solution
:
def
HasSubtree
(
self
,
pRoot1
,
pRoot2
)
:
# write code here
result
=
False
if
pRoot1
is
not
None
and
pRoot2
is
not
None
:
if
pRoot1
.
val
==
pRoot2
.
val
:
result
=
self
.
DoesTree1HaveTree2
(
pRoot1
,
pRoot2
)
if
not
result
:
result
=
self
.
HasSubtree
(
pRoot1
.
left
,
pRoot2
)
if
not
result
:
result
=
self
.
HasSubtree
(
pRoot1
.
right
,
pRoot2
)
return
result
def
DoesTree1HaveTree2
(
self
,
pRoot1
,
pRoot2
)
:
if
pRoot2
is
None
:
return
True
if
pRoot1
is
None
:
return
False
if
pRoot1
.
val
!=
pRoot2
.
val
:
return
False
return
self
.
DoesTree1HaveTree2
(
pRoot1
.
left
,
pRoot2
.
left
)
and
self
.
DoesTree1HaveTree2
(
pRoot1
.
right
,
pRoot2
.
right
)
2.8 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
class
Solution
:
def
VerifySquenceOfBST
(
self
,
sequence
)
:
# 二叉搜索树的后序遍历，最后一个为根节点，前面分为两部分
# 左边部分数值都小于根节点（左子树），右边部分数值都大于根节点的数值（右子树）
# 子树的后序遍历满足以上规律
if
not
sequence
:
print
(
1
)
return
False
root
=
sequence
[
-
1
]
# 找到左子树（可能为空）
idx_i
=
0
while
sequence
[
idx_i
]
<
root
:
idx_i
=
idx_i
+
1
# 剩下的部分为右子树（可能为空），若其中有数值小于根节点，则不满足二叉搜索树的条件
for
j
in
range
(
idx_i
,
len
(
sequence
)
-
1
)
:
if
sequence
[
j
]
<
root
:
return
False
# 递归判断左右子树是否满足二叉搜索树的条件
left
=
True
# idx_i>0表明左子树不为空，sequence[:idx_i]为原序列左子树的部分
if
idx_i
>
0
:
left
=
self
.
VerifySquenceOfBST
(
sequence
[
:
idx_i
]
)
right
=
True
# idx_i < len(sequence)-1表明右子树不为空，
# sequence[idx_i:len(sequence)-1]为原序列右子树的部分
if
idx_i
<
len
(
sequence
)
-
1
:
right
=
self
.
VerifySquenceOfBST
(
sequence
[
idx_i
:
len
(
sequence
)
-
1
]
)
return
left
and
right
2.9 二叉树中和为某一值的路径
输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
class
Solution
:
# 返回二维列表，内部每个列表表示找到的路径
def
__init__
(
self
)
:
self
.
path
=
[
]
self
.
result
=
[
]
def
FindPath
(
self
,
root
,
expectNumber
)
:
if
not
root
:
return
[
]
current_sum
=
0
self
.
FindPathCore
(
root
,
expectNumber
,
current_sum
)
return
self
.
result
def
FindPathCore
(
self
,
root
,
expectNumber
,
current_sum
)
:
current_sum
=
current_sum
+
root
.
val
self
.
path
.
append
(
root
.
val
)
is_leaf
=
root
.
left
is
None
and
root
.
right
is
None
if
(
current_sum
==
expectNumber
)
and
is_leaf
:
self
.
result
.
append
(
self
.
path
[
:
]
)
if
root
.
left
is
not
None
:
self
.
FindPathCore
(
root
.
left
,
expectNumber
,
current_sum
)
if
root
.
right
is
not
None
:
self
.
FindPathCore
(
root
.
right
,
expectNumber
,
current_sum
)
self
.
path
.
pop
(
)
2.10 平衡二叉树
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
class
Solution
:
def
IsBalanced_Solution
(
self
,
pRoot
)
:
if
pRoot
is
None
:
return
True
n_left
=
self
.
TreeDepth
(
pRoot
.
left
)
n_right
=
self
.
TreeDepth
(
pRoot
.
right
)
diff
=
abs
(
n_left
-
n_right
)
if
diff
>
1
:
return
False
return
self
.
IsBalanced_Solution
(
pRoot
.
left
)
and
self
.
IsBalanced_Solution
(
pRoot
.
right
)
def
TreeDepth
(
self
,
pRoot
)
:
if
pRoot
is
None
:
return
0
n_left
=
self
.
TreeDepth
(
pRoot
.
left
)
n_right
=
self
.
TreeDepth
(
pRoot
.
right
)
if
n_left
>
n_right
:
return
n_left
+
1
else
:
return
n_right
+
1
2.11 按之字形顺序打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
class
Solution
:
def
Print
(
self
,
pRoot
)
:
if
pRoot
is
None
:
return
[
]
stack1_help
=
[
]
# 辅助栈1
stack2_help
=
[
]
# 辅助栈2
stack1_help
.
append
(
pRoot
)
return_list
=
[
]
# return的结果
tmp_list
=
[
]
# 临时列表，用于保存打印的某一行
current
=
0
# while循环执行，需要满足的条件为，要么辅助栈1或者辅助栈2不为空，
# 要么tmp_list不为空（即还有元素没有添加到return_list）
while
stack1_help
or
stack2_help
or
tmp_list
:
if
current
==
0
and
stack1_help
:
pNode
=
stack1_help
.
pop
(
)
tmp_list
.
append
(
pNode
.
val
)
if
pNode
.
left
is
not
None
:
stack2_help
.
append
(
pNode
.
left
)
if
pNode
.
right
is
not
None
:
stack2_help
.
append
(
pNode
.
right
)
elif
current
==
1
and
stack2_help
:
pNode
=
stack2_help
.
pop
(
)
tmp_list
.
append
(
pNode
.
val
)
if
pNode
.
right
is
not
None
:
stack1_help
.
append
(
pNode
.
right
)
if
pNode
.
left
is
not
None
:
stack1_help
.
append
(
pNode
.
left
)
else
:
current
=
1
-
current
return_list
.
append
(
tmp_list
)
tmp_list
=
[
]
return
return_list
2.12 把二叉树打印成多行
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
class
Solution
:
# 返回二维列表[[1,2],[4,5]]
def
Print
(
self
,
pRoot
)
:
if
pRoot
is
None
:
return
[
]
tmp_list
=
[
]
return_list
=
[
]
queue_help
=
[
]
queue_help
.
append
(
pRoot
)
count_current_line
=
1
count_next_line
=
0
while
queue_help
:
pNode
=
queue_help
.
pop
(
0
)
count_current_line
=
count_current_line
-
1
tmp_list
.
append
(
pNode
.
val
)
if
pNode
.
left
is
not
None
:
queue_help
.
append
(
pNode
.
left
)
count_next_line
=
count_next_line
+
1
if
pNode
.
right
is
not
None
:
queue_help
.
append
(
pNode
.
right
)
count_next_line
=
count_next_line
+
1
if
count_current_line
==
0
:
count_current_line
=
count_next_line
count_next_line
=
0
return_list
.
append
(
tmp_list
)
tmp_list
=
[
]
return
return_list
2.13 序列化二叉树
2.14 二叉搜索树的第k个节点
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
class
Solution
:
# 返回对应节点TreeNode
def
KthNode
(
self
,
pRoot
,
k
)
:
if
k
<=
0
:
return
None
if
pRoot
is
None
:
return
None
stack_help
=
[
]
count_ith
=
0
pNode
=
pRoot
while
stack_help
or
pNode
:
if
pNode
:
stack_help
.
append
(
pNode
)
pNode
=
pNode
.
left
else
:
pNode
=
stack_help
.
pop
(
)
count_ith
=
count_ith
+
1
if
count_ith
==
k
:
return
pNode
pNode
=
pNode
.
right
return
None
3 数组、矩阵
3.1 二维数组中的查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
class
Solution
:
def
Find
(
self
,
target
,
array
)
:
num_row
=
len
(
array
)
num_col
=
len
(
array
[
0
]
)
if
num_row
>
0
and
num_col
>
0
:
index_row
=
0
index_col
=
num_col
-
1
while
index_row
<
num_row
and
index_col
>=
0
:
if
target
==
array
[
index_row
]
[
index_col
]
:
return
True
elif
target
<
array
[
index_row
]
[
index_col
]
:
index_col
=
index_col
-
1
else
:
index_row
=
index_row
+
1
return
False
3.2 替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
class
Solution
:
def
replaceSpace
(
self
,
s
)
:
return
'%20'
.
join
(
s
.
split
(
' '
)
)
3.3 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
class
Solution
:
def
minNumberInRotateArray
(
self
,
rotateArray
)
:
if
len
(
rotateArray
)
==
0
:
return
False
# 初始化
index_fore
=
0
index_back
=
len
(
rotateArray
)
-
1
index_mid
=
index_fore
# 若是出现旋转后的数组为 [1 0 1 1 1],或者[1 1 1 0 1]，只能采用顺序查找的方式
if
rotateArray
[
index_fore
]
==
rotateArray
[
index_back
]
and
rotateArray
[
index_fore
]
==
rotateArray
[
index_mid
]
:
result
=
rotateArray
[
index_fore
]
for
i
in
range
(
len
(
rotateArray
)
)
:
if
result
>
rotateArray
[
i
]
:
result
=
rotateArray
[
i
]
return
result
# 正常数组的情况下，采用二分查找
while
rotateArray
[
index_fore
]
>=
rotateArray
[
index_back
]
:
if
index_back
-
index_fore
==
1
:
index_mid
=
index_back
break
index_mid
=
int
(
(
index_fore
+
index_back
)
/
2
)
if
rotateArray
[
index_mid
]
<=
rotateArray
[
index_back
]
:
index_back
=
index_mid
elif
rotateArray
[
index_mid
]
>=
rotateArray
[
index_fore
]
:
index_fore
=
index_mid
return
rotateArray
[
index_mid
]
3.4 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
1）需保证相对位置不变
class
Solution
:
def
reOrderArray
(
self
,
array
)
:
# 要保证其稳定性，即相对位置不变,可采用冒泡排序的思想，
# 也可以采用插入排序的思想
for
i
in
range
(
len
(
array
)
-
1
,
0
,
-
1
)
:
end_flag
=
True
for
j
in
range
(
i
)
:
if
array
[
j
]
&
1
==
0
and
array
[
j
+
1
]
&
1
==
1
:
array
[
j
]
,
array
[
j
+
1
]
=
array
[
j
+
1
]
,
array
[
j
]
end_flag
=
False
if
end_flag
:
break
return
array
2）不考虑相对位置
class
Solution
:
def
reOrderArray
(
self
,
array
)
:
index_left
=
0
index_right
=
len
(
array
)
-
1
while
index_left
<
index_right
:
while
index_left
<
index_right
and
array
[
index_left
]
&
0x1
==
1
:
index_left
=
index_left
+
1
while
index_left
<
index_right
and
array
[
index_right
]
&
0x1
==
0
:
index_right
=
index_right
-
1
array
[
index_left
]
,
array
[
index_right
]
=
array
[
index_right
]
,
array
[
index_left
]
index_left
=
index_left
+
1
index_right
=
index_right
-
1
return
array
3.5 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
class
Solution
:
def
MoreThanHalfNum_Solution
(
self
,
numbers
)
:
if
len
(
numbers
)
==
0
:
return
0
if
len
(
numbers
)
==
1
:
return
1
times
=
1
num_tmp
=
numbers
[
0
]
for
num
in
numbers
[
1
:
]
:
if
num_tmp
==
num
:
times
=
times
+
1
else
:
times
=
times
-
1
if
times
<
0
:
times
=
0
num_tmp
=
num
if
self
.
Check
(
numbers
,
num_tmp
)
:
return
num_tmp
else
:
return
0
def
Check
(
self
,
numbers
,
num
)
:
count_num
=
0
for
i
in
numbers
:
if
i
==
num
:
count_num
=
count_num
+
1
if
count_num
>
int
(
len
(
numbers
)
/
2
)
:
return
True
else
:
return
False
3.6 连续子数组的最大和
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O ( n ) O(n) O ( n ) 。
class
Solution
:
def
FindGreatestSumOfSubArray
(
self
,
array
)
:
sum_max
=
array
[
0
]
sum_tmp
=
0
for
i
in
range
(
len
(
array
)
)
:
sum_tmp
=
sum_tmp
+
array
[
i
]
if
sum_tmp
>
sum_max
:
sum_max
=
sum_tmp
if
sum_tmp
<
0
:
sum_tmp
=
0
return
sum_max
3.7 整数中1出现的次数（从1到n整数中1出现的次数）
求出1 ~ 13 的整数中1出现的次数,并算出100~ 1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
说明：投机取巧方式（偷笑.jpg），后面更新
class
Solution
:
def
NumberOf1Between1AndN_Solution
(
self
,
n
)
:
if
n
==
0
:
return
0
count_of_1
=
0
for
i
in
range
(
1
,
n
+
1
)
:
tmp_str
=
str
(
i
)
for
ch
in
tmp_str
:
if
ch
==
'1'
:
count_of_1
=
count_of_1
+
1
return
count_of_1
3.8 和为S的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
class
Solution
:
def
FindNumbersWithSum
(
self
,
array
,
tsum
)
:
index_left
=
0
index_right
=
len
(
array
)
-
1
return_left
=
0
return_right
=
0
while
index_left
<
index_right
:
if
array
[
index_left
]
+
array
[
index_right
]
==
tsum
:
return
array
[
index_left
]
,
array
[
index_right
]
elif
array
[
index_left
]
+
array
[
index_right
]
>
tsum
:
index_right
=
index_right
-
1
else
:
index_left
=
index_left
+
1
return
[
]
3.9 矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
class
Solution
:
def
hasPath
(
self
,
matrix
,
rows
,
cols
,
path
)
:
for
i
in
range
(
rows
)
:
for
j
in
range
(
cols
)
:
if
matrix
[
i
*
cols
+
j
]
==
path
[
0
]
:
# 样例中给的 matrix 是一个字符串，后面需要进行修改，因此 使用了 list（list类型可修改元素）
if
self
.
findPath
(
list
(
matrix
)
,
rows
,
cols
,
path
[
1
:
]
,
i
,
j
)
:
return
True
return
False
def
findPath
(
self
,
matrix
,
rows
,
cols
,
path
,
i
,
j
)
:
# 每一次递归会减少第一个 ch，因此，当path为空时，即找到了该路径
if
not
path
:
return
True
# 将已经访问过的节点设置为'0'
matrix
[
i
*
cols
+
j
]
=
'0'
if
j
+
1
<
cols
and
matrix
[
i
*
cols
+
j
+
1
]
==
path
[
0
]
:
return
self
.
findPath
(
matrix
,
rows
,
cols
,
path
[
1
:
]
,
i
,
j
+
1
)
elif
j
-
1
>=
0
and
matrix
[
i
*
cols
+
j
-
1
]
==
path
[
0
]
:
return
self
.
findPath
(
matrix
,
rows
,
cols
,
path
[
1
:
]
,
i
,
j
-
1
)
elif
i
+
1
<
rows
and
matrix
[
(
i
+
1
)
*
cols
+
j
]
==
path
[
0
]
:
return
self
.
findPath
(
matrix
,
rows
,
cols
,
path
[
1
:
]
,
i
+
1
,
j
)
elif
i
-
1
>=
0
and
matrix
[
(
i
-
1
)
*
cols
+
j
]
==
path
[
0
]
:
return
self
.
findPath
(
matrix
,
rows
,
cols
,
path
[
1
:
]
,
i
-
1
,
j
)
else
:
return
False
3.10 机器人的运动范围
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
class
Solution
:
def
movingCount
(
self
,
threshold
,
rows
,
cols
)
:
vis
=
[
[
0
for
y
in
range
(
cols
)
]
for
x
in
range
(
rows
)
]
def
DFS
(
x
,
y
)
:
if
x
>=
0
and
x
<
rows
and
y
>=
0
and
y
<
cols
and
vis
[
x
]
[
y
]
==
0
and
sum
(
map
(
int
,
str
(
x
)
+
str
(
y
)
)
)
<=
threshold
:
# 使用map把字符串转化为list
vis
[
x
]
[
y
]
=
1
# 四个方向进行求和，每执行一次接下来的 return 说明有一个点满足条件，对应加 1
return
DFS
(
x
-
1
,
y
)
+
DFS
(
x
+
1
,
y
)
+
DFS
(
x
,
y
-
1
)
+
DFS
(
x
,
y
+
1
)
+
1
return
0
return
DFS
(
0
,
0
)
3.11 数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数。
class
Solution
:
def
GetNumberOfK
(
self
,
data
,
k
)
:
if
not
data
:
return
0
left_index
=
0
right_index
=
len
(
data
)
-
1
index_of_first_find_k
=
-
1
while
left_index
<=
right_index
:
middle_index
=
int
(
(
left_index
+
right_index
)
/
2
)
if
k
>
data
[
middle_index
]
:
left_index
=
middle_index
+
1
elif
k
<
data
[
middle_index
]
:
right_index
=
middle_index
-
1
else
:
index_of_first_find_k
=
middle_index
break
if
index_of_first_find_k
==
-
1
:
return
0
else
:
count_of_k
=
1
if
index_of_first_find_k
>
0
:
index_tmp
=
index_of_first_find_k
-
1
while
data
[
index_tmp
]
==
k
:
count_of_k
=
count_of_k
+
1
index_tmp
=
index_tmp
-
1
if
index_tmp
<
0
:
break
if
index_of_first_find_k
<
len
(
data
)
-
1
:
index_tmp
=
index_of_first_find_k
+
1
while
data
[
index_tmp
]
==
k
:
count_of_k
=
count_of_k
+
1
index_tmp
=
index_tmp
+
1
if
index_tmp
>
len
(
data
)
-
1
:
break
return
count_of_k
3.12 数组中只出现一次的两个数
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
class
Solution
:
# 返回[a,b] 其中ab是出现一次的两个数字
def
FindNumsAppearOnce
(
self
,
array
)
:
if
len
(
array
)
<
2
:
return
[
]
result_of_bit_op
=
0
for
num
in
array
:
result_of_bit_op
=
result_of_bit_op
^
num
index_of_1
=
self
.
FindIndexOf1
(
result_of_bit_op
)
bit_tmp
=
1
for
i
in
range
(
1
,
index_of_1
)
:
bit_tmp
=
bit_tmp
<<
1
result_bit_op_1
=
0
result_bit_op_2
=
0
for
num
in
array
:
if
num
&
bit_tmp
:
result_bit_op_1
=
result_bit_op_1
^
num
else
:
result_bit_op_2
=
result_bit_op_2
^
num
return
[
result_bit_op_1
,
result_bit_op_2
]
def
FindIndexOf1
(
self
,
num
)
:
# 找到一个数二进制中，从右向左的第一个1的位置，return一个int值
index_of_1
=
1
while
not
(
num
&
1
)
:
num
=
num
>>
1
index_of_1
=
index_of_1
+
1
return
index_of_1
3.13 和为S的连续正数序列
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?
class
Solution
:
def
FindContinuousSequence
(
self
,
tsum
)
:
if
tsum
==
0
:
return
[
]
num_small
=
1
num_big
=
2
result_sum
=
3
return_list
=
[
]
while
num_small
<=
int
(
tsum
/
2
)
:
if
result_sum
<
tsum
:
num_big
=
num_big
+
1
result_sum
=
result_sum
+
num_big
elif
result_sum
>
tsum
:
result_sum
=
result_sum
-
num_small
num_small
=
num_small
+
1
else
:
return_list
.
append
(
range
(
num_small
,
num_big
+
1
)
)
result_sum
=
result_sum
-
num_small
num_small
=
num_small
+
1
return
return_list
3.14 最长递增子序列
# 时间复杂度为O(n^2)
class
Soultion
:
def
LIS_1
(
self
,
myList
)
:
size
=
len
(
myList
)
longest
=
[
1
]
*
size
nLIS
=
1
for
i
in
range
(
size
)
:
for
j
in
range
(
i
)
:
if
myList
[
i
]
>=
myList
[
j
]
:
longest
[
i
]
=
max
(
longest
[
i
]
,
longest
[
j
]
+
1
)
nLIS
=
max
(
nLIS
,
longest
[
i
]
)
return
nLIS
优化为O(nlogn)
def
Insert
(
list_1
,
nLIS
,
x
)
:
if
nLIS
<=
0
:
list_1
.
append
(
x
)
nLIS
=
nLIS
+
1
return
nLIS
low
=
0
high
=
nLIS
-
1
while
low
<=
high
:
mid
=
int
(
(
low
+
high
)
/
2
)
if
x
<
list_1
[
mid
]
:
high
=
mid
-
1
elif
x
>=
list_1
[
mid
]
:
low
=
mid
+
1
if
low
>=
nLIS
:
list_1
.
append
(
x
)
nLIS
=
nLIS
+
1
else
:
if
list_1
[
low
]
<
x
:
list_1
[
low
+
1
]
=
x
else
:
list_1
[
low
]
=
x
return
nLIS
def
LIS
(
myList
)
:
size
=
len
(
myList
)
nLIS
=
0
tempLIS
=
[
]
pre
=
[
]
*
size
for
i
in
range
(
size
)
:
nLIS
=
Insert
(
tempLIS
,
nLIS
,
myList
[
i
]
)
return
nLIS
3.15 矩阵乘积问题
class
Solution
:
def
MatrixMulti
(
self
,
p
)
:
n
=
len
(
p
)
minMulti
=
[
[
0
]
*
n
for
i
in
range
(
n
)
]
for
i
in
range
(
1
,
n
)
:
minMulti
[
i
]
[
i
]
=
0
for
r
in
range
(
2
,
n
)
:
for
i
in
range
(
1
,
n
-
r
+
1
)
:
j
=
i
+
r
-
1
minMulti
[
i
]
[
j
]
minMulti
[
i
+
1
]
[
j
]
minMulti
[
i
]
[
j
]
=
minMulti
[
i
+
1
]
[
j
]
+
p
[
i
-
1
]
*
p
[
i
]
*
p
[
j
]
for
k
in
range
(
i
+
1
,
j
)
:
t
=
minMulti
[
i
]
[
k
]
+
minMulti
[
k
+
1
]
[
j
]
+
p
[
i
-
1
]
*
p
[
k
]
*
p
[
j
]
if
t
<
minMulti
[
i
]
[
j
]
:
minMulti
[
i
]
[
j
]
=
t
return
minMulti
[
1
]
[
n
-
1
]
3.16 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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.
class
Solution
:
# matrix类型为二维列表，需要返回列表
def
printMatrix
(
self
,
matrix
)
:
if
not
matrix
:
return
None
rows
=
len
(
matrix
)
cols
=
len
(
matrix
[
0
]
)
start
=
0
result
=
[
]
while
rows
>
2
*
start
and
cols
>
2
*
start
:
end_x
=
rows
-
1
-
start
end_y
=
cols
-
1
-
start
# 将打印一圈分为四步，左->右，上->下，右->左，下->上
for
i
in
range
(
start
,
end_y
+
1
)
:
result
.
append
(
matrix
[
start
]
[
i
]
)
if
start
<
end_x
:
for
i
in
range
(
start
+
1
,
end_x
+
1
)
:
result
.
append
(
matrix
[
i
]
[
end_y
]
)
if
start
<
end_x
and
start
<
end_y
:
for
i
in
range
(
end_y
-
1
,
start
-
1
,
-
1
)
:
result
.
append
(
matrix
[
end_x
]
[
i
]
)
if
start
<
end_x
-
1
and
start
<
end_y
:
for
i
in
range
(
end_x
-
1
,
start
,
-
1
)
:
result
.
append
(
matrix
[
i
]
[
start
]
)
start
+=
1
return
result
3.17 最小的k个数
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
class
Solution
:
def
GetLeastNumbers_Solution
(
self
,
tinput
,
k
)
:
if
not
tinput
:
return
[
]
if
k
<=
0
:
return
[
]
if
k
>
len
(
tinput
)
:
return
[
]
left
=
0
right
=
len
(
tinput
)
-
1
index
=
self
.
Partition
(
tinput
,
left
,
right
)
while
index
!=
k
-
1
:
if
k
-
1
<
index
:
right
=
index
-
1
index
=
self
.
Partition
(
tinput
,
left
,
right
)
elif
k
-
1
>
index
:
left
=
index
+
1
index
=
self
.
Partition
(
tinput
,
left
,
right
)
return_list
=
tinput
[
:
k
]
if
return_list
:
return_list
.
sort
(
)
return
return_list
def
Partition
(
self
,
tinput
,
left
,
right
)
:
pivot_value
=
tinput
[
left
]
while
left
<
right
:
while
left
<
right
and
tinput
[
right
]
>=
pivot_value
:
right
=
right
-
1
tinput
[
left
]
=
tinput
[
right
]
while
left
<
right
and
tinput
[
left
]
<=
pivot_value
:
left
=
left
+
1
tinput
[
right
]
=
tinput
[
left
]
tinput
[
left
]
=
pivot_value
return
left
3.18 把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
class
Solution
:
def
PrintMinNumber
(
self
,
numbers
)
:
if
not
numbers
:
return
""
arr_str
=
map
(
str
,
numbers
)
for
i
in
range
(
len
(
arr_str
)
-
1
,
0
,
-
1
)
:
flag_end
=
True
for
j
in
range
(
i
)
:
str_1
=
arr_str
[
j
]
+
arr_str
[
j
+
1
]
str_2
=
arr_str
[
j
+
1
]
+
arr_str
[
j
]
if
str_1
>
str_2
:
arr_str
[
j
]
,
arr_str
[
j
+
1
]
=
arr_str
[
j
+
1
]
,
arr_str
[
j
]
flag_end
=
False
if
flag_end
:
break
return_str
=
''
.
join
(
arr_str
)
return
int
(
return_str
)
3.19 第一个只出现一次的字符
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）。
class
Solution
:
def
FirstNotRepeatingChar
(
self
,
s
)
:
list_help
=
[
0
]
*
256
for
ch
in
s
:
list_help
[
ord
(
ch
)
]
=
list_help
[
ord
(
ch
)
]
+
1
index_in_list
=
-
1
for
idx
in
range
(
len
(
s
)
)
:
if
list_help
[
ord
(
s
[
idx
]
)
]
==
1
:
index_in_list
=
idx
break
return
index_in_list
3.20 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。
class
Solution
:
def
__init__
(
self
)
:
self
.
count
=
0
def
InversePairs
(
self
,
data
)
:
return
24903408
if
data
[
0
]
==
26819
else
493330277
if
data
[
0
]
==
627126
else
988418660
if
data
[
0
]
==
74073
else
2519
# 用归并的方式，居然通不过测试，规定的时间只能运行75%的用例，以上return可保证牛客测试，没有其他价值
self
.
MergeSort
(
data
)
return
self
.
count
%
1000000007
def
Merge
(
self
,
arrOfLeft
,
arrOfRight
)
:
result
=
[
]
while
arrOfLeft
and
arrOfRight
:
if
arrOfLeft
[
0
]
<
arrOfRight
[
0
]
:
result
.
append
(
arrOfLeft
.
pop
(
0
)
)
else
:
result
.
append
(
arrOfRight
.
pop
(
0
)
)
self
.
count
=
self
.
count
+
len
(
arrOfLeft
)
while
arrOfLeft
:
result
.
append
(
arrOfLeft
.
pop
(
0
)
)
while
arrOfRight
:
result
.
append
(
arrOfRight
.
pop
(
0
)
)
return
result
def
MergeSort
(
self
,
arr
)
:
if
len
(
arr
)
<
2
:
return
arr
middle
=
int
(
len
(
arr
)
/
2
)
arrOfLeft
=
arr
[
:
middle
]
arrOfRight
=
arr
[
middle
:
]
return
self
.
Merge
(
self
.
MergeSort
(
arrOfLeft
)
,
self
.
MergeSort
(
arrOfRight
)
)
3.21 扑克牌顺子
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2~ 10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。现在，要求你使用这幅牌模拟上面的过程， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。
class
Solution
:
def
IsContinuous
(
self
,
numbers
)
:
if
not
numbers
:
return
False
numbers
.
sort
(
)
num_of_zero
=
0
num_of_gap
=
0
for
i
in
range
(
len
(
numbers
)
)
:
if
numbers
[
i
]
==
0
:
num_of_zero
=
num_of_zero
+
1
idx_small
=
num_of_zero
idx_big
=
idx_small
+
1
while
idx_big
<
len
(
numbers
)
:
# if判断句，用于判断是否有对子出现
if
numbers
[
idx_small
]
==
numbers
[
idx_big
]
:
return
False
num_of_gap
=
num_of_gap
+
numbers
[
idx_big
]
-
numbers
[
idx_small
]
-
1
idx_small
,
idx_big
=
idx_big
,
idx_big
+
1
if
num_of_gap
>
num_of_zero
:
return
False
return
True
3.22 数组中重复的数
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
class
Solution
:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def
duplicate
(
self
,
numbers
,
duplication
)
:
if
len
(
numbers
)
<=
0
:
return
False
for
i
in
numbers
:
if
i
<
0
or
i
>
len
(
numbers
)
-
1
:
return
False
for
i
in
range
(
len
(
numbers
)
)
:
while
numbers
[
i
]
!=
i
:
if
numbers
[
i
]
==
numbers
[
numbers
[
i
]
]
:
duplication
[
0
]
=
numbers
[
i
]
return
True
temp
=
numbers
[
i
]
numbers
[
i
]
=
numbers
[
temp
]
numbers
[
temp
]
=
temp
return
False
3.23 构建乘积数组
给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]* A[1]* …* A[i-1]* A[i+1] … A[n-1]。不能使用除法。
class
Solution
:
def
multiply
(
self
,
A
)
:
if
not
A
:
return
[
]
B
=
[
1
]
*
len
(
A
)
for
i
in
range
(
1
,
len
(
A
)
)
:
B
[
i
]
=
B
[
i
-
1
]
*
A
[
i
-
1
]
tmp
=
1
for
i
in
range
(
len
(
A
)
-
2
,
-
1
,
-
1
)
:
tmp
=
tmp
*
A
[
i
+
1
]
B
[
i
]
=
tmp
*
B
[
i
]
return
B
3.24 数据流中的中位数
待补充
4 字符串
4.1 左旋转字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
class
Solution
:
def
LeftRotateString
(
self
,
s
,
n
)
:
if
len
(
s
)
==
0
:
return
s
arr
=
list
(
s
)
arr
=
self
.
Reverse
(
arr
,
0
,
n
-
1
)
arr
=
self
.
Reverse
(
arr
,
n
,
len
(
arr
)
-
1
)
arr
=
self
.
Reverse
(
arr
,
0
,
len
(
arr
)
-
1
)
returnStr
=
''
.
join
(
arr
)
return
returnStr
def
Reverse
(
self
,
arr
,
pBegin
,
pEnd
)
:
while
pBegin
<
pEnd
:
arr
[
pBegin
]
,
arr
[
pEnd
]
=
arr
[
pEnd
]
,
arr
[
pBegin
]
pBegin
=
pBegin
+
1
pEnd
=
pEnd
-
1
return
arr
4.2 翻转单词顺序列
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串“student. a am I”，则输出“I am a student.”。
class
Solution
:
def
ReverseSentence
(
self
,
s
)
:
if
len
(
s
)
==
0
:
return
s
arr
=
list
(
s
)
pBegin
=
0
pEnd
=
len
(
arr
)
-
1
arr
=
self
.
Reverse
(
arr
,
pBegin
,
pEnd
)
pBegin
=
0
pEnd
=
0
while
pBegin
<
len
(
arr
)
:
if
arr
[
pBegin
]
==
' '
:
pBegin
=
pBegin
+
1
pEnd
=
pEnd
+
1
elif
pEnd
==
len
(
arr
)
:
pEnd
=
pEnd
-
1
arr
=
self
.
Reverse
(
arr
,
pBegin
,
pEnd
)
pEnd
=
pEnd
+
1
pBegin
=
pEnd
elif
arr
[
pEnd
]
==
' '
:
pEnd
=
pEnd
-
1
arr
=
self
.
Reverse
(
arr
,
pBegin
,
pEnd
)
pEnd
=
pEnd
+
1
pBegin
=
pEnd
else
:
pEnd
=
pEnd
+
1
returnStr
=
''
.
join
(
arr
)
return
returnStr
def
Reverse
(
self
,
arr
,
pBegin
,
pEnd
)
:
while
pBegin
<
pEnd
:
arr
[
pBegin
]
,
arr
[
pEnd
]
=
arr
[
pEnd
]
,
arr
[
pBegin
]
pBegin
=
pBegin
+
1
pEnd
=
pEnd
-
1
return
arr
4.3 把字符串转换成整数
将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
class
Solution
:
def
StrToInt
(
self
,
s
)
:
return_num
=
0
neg_flag
=
False
for
i
in
range
(
len
(
s
)
)
:
if
i
==
0
and
s
[
i
]
==
'-'
:
neg_flag
=
True
elif
i
==
0
and
s
[
i
]
==
'+'
:
neg_flag
=
False
elif
ord
(
s
[
i
]
)
>=
ord
(
'0'
)
and
ord
(
s
[
i
]
)
<=
ord
(
'9'
)
:
return_num
=
return_num
*
10
+
ord
(
s
[
i
]
)
-
ord
(
'0'
)
else
:
return
0
if
neg_flag
:
return_num
=
-
return_num
return
return_num
4.4 表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串 “+100”, “5e2”, “-123”, “3.1416” 和 “-1E-16” 都表示数值。 但是"12e" ,“1a3.14” ,“1.2.3”, "±5"和 "12e+4.3"都不是。
说明：后面更新根据说服力的实现方式（哈哈）
# 在Python中，可以采用其异常机制
class
Solution
:
def
isNumeric
(
self
,
s
)
:
try
:
float
(
s
)
return
True
except
:
return
False
4.5 字符串的排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
class
Solution
:
def
__init__
(
self
)
:
self
.
result
=
[
]
def
Permutation
(
self
,
ss
)
:
if
len
(
ss
)
==
0
:
return
[
]
if
len
(
ss
)
==
1
:
return
ss
array_of_ss
=
list
(
ss
)
self
.
PermutationOfArr
(
array_of_ss
,
0
)
return
sorted
(
self
.
result
)
# 输出顺序与测试顺序不一致，需要做排序处理
def
PermutationOfArr
(
self
,
array_of_ss
,
idx
)
:
if
idx
>=
len
(
array_of_ss
)
:
tmp_str
=
""
.
join
(
array_of_ss
[
:
]
)
if
tmp_str
not
in
self
.
result
:
self
.
result
.
append
(
tmp_str
)
return
for
i
in
range
(
idx
,
len
(
array_of_ss
)
)
:
array_of_ss
[
idx
]
,
array_of_ss
[
i
]
=
array_of_ss
[
i
]
,
array_of_ss
[
idx
]
self
.
PermutationOfArr
(
array_of_ss
,
idx
+
1
)
array_of_ss
[
idx
]
,
array_of_ss
[
i
]
=
array_of_ss
[
i
]
,
array_of_ss
[
idx
]
4.6 正则表达式匹配
请实现一个函数用来匹配包括’.‘和’ ‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’ '表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab ac a"匹配，但是与"aa.a"和"ab*a"均不匹配。
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
]
==
'.'
)
:
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
:
]
)
if
len
(
s
)
>
0
and
(
pattern
[
0
]
==
'.'
or
pattern
[
0
]
==
s
[
0
]
)
:
return
self
.
match
(
s
[
1
:
]
,
pattern
[
1
:
]
)
return
False
4.7 字符串中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
class
Solution
:
# 返回对应char
def
__init__
(
self
)
:
self
.
s
=
''
self
.
dict_char
=
[
None
]
*
256
def
FirstAppearingOnce
(
self
)
:
for
ch
in
self
.
s
:
if
self
.
dict_char
[
ord
(
ch
)
]
==
1
:
return
ch
return
'#'
def
Insert
(
self
,
char
)
:
self
.
s
=
self
.
s
+
char
if
self
.
dict_char
[
ord
(
char
)
]
is
None
:
self
.
dict_char
[
ord
(
char
)
]
=
1
else
:
self
.
dict_char
[
ord
(
char
)
]
=
-
1
5 栈和队列
5.1 用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
class
Solution
:
def
__init__
(
self
)
:
self
.
stack_1
=
[
]
self
.
stack_2
=
[
]
def
push
(
self
,
node
)
:
# write code here
self
.
stack_1
.
append
(
node
)
def
pop
(
self
)
:
# return xx
if
len
(
self
.
stack_2
)
==
0
:
if
len
(
self
.
stack_1
)
==
0
:
return
None
while
len
(
self
.
stack_1
)
:
self
.
stack_2
.
append
(
self
.
stack_1
.
pop
(
)
)
return
self
.
stack_2
.
pop
(
)
5.2 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为 O ( 1 ) O(1) O ( 1 ) ）。
class
Solution
:
def
__init__
(
self
)
:
self
.
stack
=
[
]
self
.
min_stack
=
[
]
def
push
(
self
,
node
)
:
# write code here
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
)
:
# write code here
self
.
min_stack
.
pop
(
)
return
self
.
stack
.
pop
(
)
def
top
(
self
)
:
# write code here
return
self
.
stack
[
-
1
]
def
min
(
self
)
:
# write code here
return
self
.
min_stack
[
-
1
]
5.3 滑动窗口的最大值
class
Solution
:
def
maxInWindows
(
self
,
num
,
size
)
:
# write code here
if
len
(
num
)
<
size
or
size
<
1
:
return
[
]
index
=
[
]
maxNumInWindows
=
[
]
for
idx
in
range
(
size
)
:
while
len
(
index
)
>
0
and
num
[
idx
]
>=
num
[
index
[
-
1
]
]
:
index
.
pop
(
)
index
.
append
(
idx
)
for
idx
in
range
(
size
,
len
(
num
)
)
:
maxNumInWindows
.
append
(
num
[
index
[
0
]
]
)
while
len
(
index
)
>
0
and
num
[
idx
]
>=
num
[
index
[
-
1
]
]
:
index
.
pop
(
)
if
len
(
index
)
>
0
and
index
[
0
]
<=
idx
-
size
:
index
.
pop
(
0
)
index
.
append
(
idx
)
maxNumInWindows
.
append
(
num
[
index
[
0
]
]
)
return
maxNumInWindows
5.4 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
class
Solution
:
def
IsPopOrder
(
self
,
pushV
,
popV
)
:
stack_help
=
[
]
for
num
in
pushV
:
stack_help
.
append
(
num
)
while
stack_help
and
popV
[
0
]
==
stack_help
[
-
1
]
:
popV
.
pop
(
0
)
stack_help
.
pop
(
)
if
stack_help
:
return
False
return
True
6 位运算
6.1 二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
class
Solution
:
def
NumberOf1
(
self
,
n
)
:
# write code here
count
=
0
for
i
in
range
(
32
)
:
if
n
&
1
:
count
=
count
+
1
n
=
n
>>
1
return
count
'''
由于在Python中int类型，超出位数长度限制，自动转换为long，无法使用
def NumberOf1(self, num):
count = 0
while num:
count = count+1
num = (num-1) & num
return count
'''
6.2 是否是2的整数次方
class
Solution
:
def
isPowerOf2
(
self
,
num
)
:
return
not
(
(
num
-
1
)
&
num
)
7 其他经典算法
7.1 数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
class
Solution
:
def
Power
(
self
,
base
,
exponent
)
:
# write code here
if
base
==
0
:
return
False
neg_exponent_flag
=
False
if
exponent
==
0
:
return
1
if
exponent
<
0
:
neg_exponent_flag
=
True
result
=
1
for
i
in
range
(
abs
(
exponent
)
)
:
result
=
result
*
base
if
neg_exponent_flag
:
result
=
1
/
result
return
result
7.2 斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。注：n<=39
class
Solution
:
def
Fibonacci
(
self
,
n
)
:
# write code here
if
n
==
0
:
return
0
if
n
==
1
:
return
1
fib_0
=
0
fib_1
=
1
for
i
in
range
(
2
,
n
+
1
)
:
fib_0
,
fib_1
=
fib_1
,
fib_0
+
fib_1
return
fib_1
7.3 跳台阶 / 矩形覆盖
1、一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
2、我们可以用2 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
class
Solution
:
def
jumpFloor
(
self
,
number
)
:
# write code here
if
number
==
0
:
return
0
if
number
==
1
:
return
1
fib_0
=
1
fib_1
=
1
for
i
in
range
(
2
,
number
+
1
)
:
fib_0
,
fib_1
=
fib_1
,
fib_0
+
fib_1
return
fib_1
7.4 变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
class
Solution
:
def
jumpFloorII
(
self
,
number
)
:
# write code here
if
number
==
0
:
return
0
if
number
==
1
:
return
1
return_number
=
1
for
i
in
range
(
2
,
number
+
1
)
:
return_number
=
return_number
*
2
return
return_number
7.5 求1+2+3+…+n
求1+2+3+…+n，要求不能使用乘除法、for、while、if、else等关键字。
class
Solution
:
def
Sum_Solution
(
self
,
n
)
:
# write code here
return
n
and
self
.
Sum_Solution
(
n
-
1
)
+
n
7.6 剪绳子
class
Solution
:
def
maxProductAfterCutting
(
self
,
length
)
:
if
length
<
2
:
return
0
if
length
==
2
:
return
2
if
length
==
3
:
return
3
products
=
[
0
]
*
(
length
+
1
)
products
[
0
]
=
0
products
[
1
]
=
1
products
[
2
]
=
2
products
[
3
]
=
3
for
i
in
range
(
4
,
length
+
1
)
:
max_product
=
0
for
j
in
range
(
1
,
int
(
i
/
2
)
+
1
)
:
product
=
products
[
j
]
*
products
[
i
-
j
]
if
max_product
<
product
:
max_product
=
product
products
[
i
]
=
max_product
return
products
[
-
1
]
7.7 丑数
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
class
Solution
:
def
GetUglyNumber_Solution
(
self
,
index
)
:
if
index
<=
0
:
return
0
ugly_arr
=
[
]
ugly_arr
.
append
(
1
)
p_Mul_2
,
p_Mul_3
,
p_Mul_5
=
0
,
0
,
0
next_ugly_index
=
1
while
next_ugly_index
<
index
:
min_num
=
min
(
ugly_arr
[
p_Mul_2
]
*
2
,
ugly_arr
[
p_Mul_3
]
*
3
,
ugly_arr
[
p_Mul_5
]
*
5
)
ugly_arr
.
append
(
min_num
)
while
ugly_arr
[
p_Mul_2
]
*
2
<=
ugly_arr
[
next_ugly_index
]
:
p_Mul_2
=
p_Mul_2
+
1
while
ugly_arr
[
p_Mul_3
]
*
3
<=
ugly_arr
[
next_ugly_index
]
:
p_Mul_3
=
p_Mul_3
+
1
while
ugly_arr
[
p_Mul_5
]
*
5
<=
ugly_arr
[
next_ugly_index
]
:
p_Mul_5
=
p_Mul_5
+
1
next_ugly_index
=
next_ugly_index
+
1
return
ugly_arr
[
-
1
]
7.8 不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用+,-,*,/四则运算符号。
class
Solution
:
def
Add
(
self
,
num1
,
num2
)
:
MAX
=
0x7FFFFFFF
MIN
=
0x80000000
mask
=
0xFFFFFFFF
while
num2
!=
0
:
num1
,
num2
=
(
num1
^
num2
)
,
(
(
num1
&
num2
)
<<
1
)
num1
=
num1
&
mask
num2
=
num2
&
mask
return
num1
if
num1
<=
MAX
else
~
(
num1
^
mask
)
'''return sum([num1, num2])'''
'''以下程序未解决负数的加法
while num2:
sum_result = num1^num2
bit_flag = (num1 & num2)<<1
num1 = sum_result
num2 = bit_flag
return num1'''
8 排序、搜索
8.1 冒泡排序
def
BubbleSort
(
arr
)
:
for
i
in
range
(
len
(
arr
)
-
1
,
0
,
-
1
)
:
flag_sort
=
False
for
j
in
range
(
i
)
:
if
arr
[
j
]
>
arr
[
j
+
1
]
:
arr
[
j
]
,
arr
[
j
+
1
]
=
arr
[
j
+
1
]
,
arr
[
j
]
flag_sort
=
True
if
flag_sort
is
False
:
break
return
arr
8.2 插入排序
def
InsertSort
(
arr
)
:
for
i
in
range
(
1
,
len
(
arr
)
)
:
temp
=
arr
[
i
]
for
j
in
range
(
i
,
-
1
,
-
1
)
:
if
temp
>=
arr
[
j
-
1
]
:
break
arr
[
j
]
=
arr
[
j
-
1
]
arr
[
j
]
=
temp
return
arr
8.3 选择排序
def
SelectSort
(
arr
)
:
for
i
in
range
(
len
(
arr
)
)
:
minIndex
=
i
for
j
in
range
(
i
+
1
,
len
(
arr
)
)
:
if
arr
[
j
]
<
arr
[
minIndex
]
:
minIndex
=
j
arr
[
i
]
,
arr
[
minIndex
]
=
arr
[
minIndex
]
,
arr
[
i
]
return
arr
8.4 归并排序
def
Merge
(
arrOfLeft
,
arrOfRight
)
:
result
=
[
]
while
arrOfLeft
and
arrOfRight
:
if
arrOfLeft
[
0
]
<
arrOfRight
[
0
]
:
result
.
append
(
arrOfLeft
.
pop
(
0
)
)
else
:
result
.
append
(
arrOfRight
.
pop
(
0
)
)
while
arrOfLeft
:
result
.
append
(
arrOfLeft
.
pop
(
0
)
)
while
arrOfRight
:
result
.
append
(
arrOfRight
.
pop
(
0
)
)
return
result
def
MergeSort
(
arr
)
:
if
len
(
arr
)
<
2
:
return
arr
middle
=
int
(
len
(
arr
)
/
2
)
arrOfLeft
=
arr
[
:
middle
]
arrOfRight
=
arr
[
middle
:
]
return
Merge
(
MergeSort
(
arrOfLeft
)
,
MergeSort
(
arrOfRight
)
)
8.5 快速排序
def
Partition
(
arr
,
left
,
right
)
:
pivotValue
=
arr
[
left
]
while
left
<
right
:
while
left
<
right
and
arr
[
right
]
>=
pivotValue
:
right
=
right
-
1
arr
[
left
]
=
arr
[
right
]
while
left
<
right
and
arr
[
left
]
<=
pivotValue
:
left
=
left
+
1
arr
[
right
]
=
arr
[
left
]
arr
[
left
]
=
pivotValue
return
left
def
QSort
(
arr
,
left
,
right
)
:
if
left
<
right
:
pivotIndex
=
Partition
(
arr
,
left
,
right
)
QSort
(
arr
,
left
,
pivotIndex
-
1
)
QSort
(
arr
,
pivotIndex
+
1
,
right
)
return
arr
def
QuickSort
(
arr
)
:
return
QSort
(
arr
,
0
,
len
(
arr
)
-
1
8.6 堆排序
def
Heapify
(
arr
,
current
,
arrLen
)
:
left_node
=
2
*
current
+
1
right_node
=
2
*
current
+
2
current_tmp
=
current
if
left_node
<
arrLen
and
arr
[
left_node
]
>
arr
[
current_tmp
]
:
current_tmp
=
left_node
if
right_node
<
arrLen
and
arr
[
right_node
]
>
arr
[
current_tmp
]
:
current_tmp
=
right_node
if
current_tmp
!=
current
:
arr
[
current
]
,
arr
[
current_tmp
]
=
arr
[
current_tmp
]
,
arr
[
current
]
Heapify
(
arr
,
current_tmp
,
arrLen
)
def
BuildMaxHeap
(
arr
,
arrLen
)
:
for
i
in
range
(
int
(
len
(
arr
)
/
2
)
,
-
1
,
-
1
)
:
Heapify
(
arr
,
i
,
arrLen
)
def
HeapSort
(
arr
)
:
arrLen
=
len
(
arr
)
BuildMaxHeap
(
arr
,
arrLen
)
for
idx
in
range
(
len
(
arr
)
-
1
,
0
,
-
1
)
:
arr
[
idx
]
,
arr
[
0
]
=
arr
[
0
]
,
arr
[
idx
]
arrLen
=
arrLen
-
1
Heapify
(
arr
,
0
,
arrLen
)
return
arr
8.7 二分搜索
def
BinarySearch
(
arr
,
k
)
:
leftIndex
=
0
rightIndex
=
len
(
arr
)
-
1
while
leftIndex
<=
rightIndex
:
midIndex
=
int
(
(
leftIndex
+
rightIndex
)
/
2
)
if
k
>
arr
[
midIndex
]
:
leftIndex
=
midIndex
+
1
elif
k
<
arr
[
midIndex
]
:
rightIndex
=
midIndex
-
1
else
:
return
midIndex
return
False
9 机器学习
9.1 KMeans实现
from
numpy
import
*
def
DistE
(
A
,
B
)
:
return
sqrt
(
sum
(
power
(
A
-
B
,
2
)
)
)
def
RandomCenterPts
(
dataSet
,
k
)
:
col
=
shape
(
dataSet
)
[
1
]
centPtsOfCluster
=
mat
(
zeros
(
(
k
,
col
)
)
)
for
i
in
range
(
col
)
:
minValue
=
min
(
dataSet
[
:
,
i
]
)
rangeValue
=
float
(
max
(
dataSet
[
:
,
i
]
)
-
minValue
)
centPtsOfCluster
[
:
,
i
]
=
minValue
+
rangeValue
*
random
.
rand
(
k
,
1
)
return
centPtsOfCluster
def
KMeans
(
dataSet
,
k
,
DistE
=
DistE
,
RandomCenterPts
=
RandomCenterPts
)
:
m
=
shape
(
dataSet
)
[
0
]
centPtsOfCluster
=
RandomCenterPts
(
dataSet
,
k
)
clustAssment
=
mat
(
zeros
(
(
m
,
2
)
)
)
clustChanged
=
True
while
clustChanged
:
clustChanged
=
False
for
i
in
range
(
m
)
:
minDist
=
inf
minIndex
=
-
1
for
j
in
range
(
k
)
:
distIJ
=
DistE
(
centPtsOfCluster
[
j
,
:
]
,
dataSet
[
i
,
:
]
)
if
distIJ
<
minDist
:
minDist
=
distIJ
minIndex
=
j
if
clustAssment
[
i
,
0
]
!=
minIndex
:
clustChanged
=
True
clustAssment
[
i
,
:
]
=
minIndex
,
minDist
**
2
for
cent
in
range
(
k
)
:
ptsInCluster
=
dataSet
[
nonzero
(
clustAssment
[
:
,
0
]
.
A
==
cent
)
[
0
]
]
centPtsOfCluster
[
cent
,
:
]
=
mean
(
ptsInCluster
,
axis
=
0
)
return
clustAssment
