剑指offer

剑指offer

二维数组中的查找

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

思路:思路从右上开始,右上为一行最大,一列最小。target<右上,删一列; target>右上,删一行

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution1:
# array 二维列表
def Find(self, target, array):
# write code here
i = 0
j = len(array[0])-1
while i<len(array) and j>=0:
if array[i][j] == target:
return True
elif array[i][j] > target:
j -= 1
else:
i += 1
return False

替换空格

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

思路:python式。。

其他语言思路:从头到尾遍历数空格数量,然后从后往前遍历,碰到空格后根据之前数好的数量移位

Code

1
2
3
4
5
6
class Solution2:
# s 源字符串
def replaceSpace(self, s):
# write code here
s= s.replace(' ', '%20')
return s

从尾到头打印链表

Q:输入一个链表,从尾到头打印链表每个节点的值

思路:遍历链表每次遍历的val从头插入list

Code

1
2
3
4
5
6
7
8
9
10
class Solution3:
# 返回从尾部到头部的列表值序列,例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
list = []
p = listNode
while p:
list = [p.val] + list
p = p.next
return list

重建二叉树

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

思路:先序第一个为根节点,中序中根节点左边全在左子树,右边全在右子树。据此用递归建树

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 我的解法
# 对len==1的list判定,繁琐
class Solution32:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
root = TreeNode(pre[0])
if len(pre) == 1 and len(tin) == 1:
return root
root_index = tin.index(pre[0])
if root_index != 0:
root.left = self.reConstructBinaryTree(pre[1:root_index+1],tin[:root_index])
if root_index != len(tin)-1:
root.right = self.reConstructBinaryTree(pre[root_index+1:],tin[root_index+1:])
return root

# 精简解法
# 对空list的判定,鲁棒性更强,更精简
def reConstructBinaryTree(self, pre, tin):
# write code here
if not pre or not tin:
return None
root = TreeNode(pre[0])
index = tin.index(root.val)
root.left = self.reConstructBinaryTree(pre[1:index+1], tin[0:index])
root.right = self.reConstructBinaryTree(pre[index+1:], tin[index+1:])
return root

旋转数组的最小数字

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

思路:太简单,不说了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution5:
def minNumberInRotateArray(self, rotateArray):
# write code here
nums = rotateArray
if not nums:
return 0
p = len(nums) - 1
min = nums[0]
while p > 0 and nums[p-1]<= nums[p]:
p -= 1
if nums[p] < min:
min = nums[p]
return min

斐波那契数列

Q:大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。n<=39

思路:分别用while 与 递归实现

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 不用递归,避免重复运算,运行时间短
class Solution6:
def Fibonacci(self, n):
# write code here
if n == 0:
return 0
if n < 3:
return 1
pre = 1
post = 1
count = 3
while count <= n:
temp = post
post = pre + post
pre = temp
count += 1
return post
# 递归,代码简单,运行超时
class Solution62:
def Fibonacci(self, n):
# write code here
if n == 0:
return 0
if n == 1:
return 1
return self.Fibonacci(n-1) + self.Fibonacci(n-2)

跳台阶

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

思路:斐波那契数列问题,斐波那契数列前移一位

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution7:
def jumpFloor(self, number):
# write code here
if number < 2:
return 1
pre = 1
post = 1
count = 2
while count <= number:
temp = post
post = pre + post
pre = temp
count += 1
return post

变态跳台阶

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

思路:

F(n) = F(n-1)+F(n-2)+F(n-3)+….+F(1)

第n项是前n-1项的和,所以第n+1项是第n项的两倍,都是二的指数次方

Code

1
2
3
4
class Solution8:
def jumpFloorII(self, number):
# write code here
return 2 ** (number-1)

矩形覆盖

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

思路:还是个斐波那契问题 n*2 矩形覆盖时候最后一步要不覆盖田,要不覆盖日,因此是斐波那契问题F(n) = F(n-1)+F(n-2)只不过题目规定F(0)=0

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution9:
def rectCover(self, number):
# write code here
if not number:
return 0
if number < 2:
return 1
pre = 1
post = 1
count = 2
while count <= number:
temp = post
post = pre + post
pre = temp
count += 1
return post

二进制中1的个数

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

思路1:一个整数减去1,再和原整数做 与 运算,会把该整数最右边的1变成0(用补码表示的负数也是)。所以一个整数中有多少个1就可以进行多少次这种运算该法用python写超时

Code

1
2
3
4
5
6
7
8
class Solution10:
def NumberOf1(self, n):
# write code here
i = 0
while n:
n = n & (n-1)
i += 1
return i

思路2:因为右移数字n会造成死循环(负数第一位是1),可以先把n和1做与运算,判断n的最低位是不是1,接着把1左移一位得到2,再和n做与运算……反复左移就能判断n的其中一位是不是1

注意:1要是无符号整数(unsigned int)

Code

1
2
3
4
5
6
7
8
9
10
11
12
int NumberOf1(int n)
{
int count = 0;
unsigned int flag = 1;
while(flag)
{
if(n&flag)
count ++
flag = flag << 1
}
return count;
}

数值的整数次方

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

思路:Life is short, you need python

Code

1
2
3
4
class Solution11:
def Power(self, base, exponent):
# write code here
return pow(base, exponent)

调整数组是奇数位于偶数前并保证奇数偶数各自相对位置

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

思路:一个list存奇数一个list存偶数,两个合起来

Code

1
2
3
4
5
6
7
8
9
10
11
class Solution12:
def reOrderArray(self, array):
# write code here
res1 = []
res2 = []
for i in range(len(array)):
if array[i] % 2 == 0 :
res2.append(array[i])
else:
res1.append(array[i])
return res1+res2

链表中倒数第K个节点

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

思路:构造长度为K的滑窗(构造时考虑K过大问题),将滑窗滑至最后即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution13:
def FindKthToTail(self, head, k):
# write code here
if k < 1:
return None
if not head:
return None
post = pre = head
count = k
while k-1 > 0:
if post.next:
post = post.next
k -= 1
else:
return None
while post.next:
post = post.next
pre = pre.next
return pre

翻转链表

Q:输入一个链表,反转链表后,输出链表的所有元素。

思路:比较简单临近双指针遍历至最后,注意最后对边界值的处理

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution14:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
if not pHead or not pHead.next:
return pHead
post = pHead.next
pHead.next = None
while post:
if post.next:
temp = post.next
else:
post.next = pHead
break
post.next = pHead
pHead = post
post = temp
return post

合并两个排序链表

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

思路:每次选出两个链表较小的头结点,然后用剩下的递归链接

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution15:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
if not pHead1 or not pHead2:
return pHead1 or pHead2
if pHead1.val < pHead2.val:
pHead1.next = self.Merge(pHead1.next, pHead2)
return pHead1
else:
pHead2.next = self.Merge(pHead1, pHead2.next)
return pHead2

树的子结构

Q:输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

思路1:递归的查找子结构

注意:

①要全面遍历所有所可能(类似机器人路径中的找出所有起始位置),不能找到一对根节点相等的点,后面不等就return False; 这里体现在相等时候也留一手 or 类似与不等继续进行判断

②因为题中给出空节点不是子结构,而我迭代又要用到对pRoot2是否为空的判断,因此,先对pRoot2判断,再单独写了个函数

③本题求的是子结构而非子树

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution16:
def HasSubtree(self, pRoot1, pRoot2):
# write code here
if not pRoot2:
return False
def Search(pRoot1,pRoot2):
if not pRoot2:
return True
if not pRoot1:
return False
if pRoot1.val ==pRoot2.val:
# 注意or的运用,遍历所有可能的节点
return True and ( (Search(pRoot1.left,pRoot2.left) and Search(pRoot1.right,pRoot2.right))
or Search(pRoot1.left,pRoot2) or Search(pRoot1.right,pRoot2) )
else:
return Search(pRoot1.left,pRoot2) or Search(pRoot1.right,pRoot2)
return Search(pRoot1,pRoot2)

思路2:更精简的分治递归

写一个函数判断两树是同一根节点的情况下pRoot2是否是pRoot1的子结构

在主函数里递归调用这个函数

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
# write code here
if not pRoot1 or not pRoot2:
return False
return self.IsSub(pRoot1,pRoot2) or self.IsSub(pRoot1.left,pRoot2) or self.IsSub(pRoot1.right,pRoot2)
def IsSub(self,p1,p2):
if not p2:
return True
if not p1 or p1.val != p2.val:
return False
return self.IsSub(p1.left,p2.left) and self.IsSub(p1.right,p2.right)

二叉树的镜像

Q:操作给定的二叉树,将其变换为源二叉树的镜像。

思路:递归实现没什么难度

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution17:
# 返回镜像树的根节点
def Mirror(self, root):
# write code here
def Trans(root):
if not root:
return
temp = root.left
root.left = root.right
root.right = temp
Trans(root.left)
Trans(root.right)
Trans(root)
return root

顺时针打印矩阵

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

思路:通过递归函数实现,每次添加最外一圈

注意:对行列为2的判断(里面的if判断),过程中一个不满足就代表添加完毕

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution18:
# matrix类型为二维列表,需要返回列表
def __init__(self):
self.List = []
def printMatrix(self, matrix):
# write code here
row_u = 0
row_d = len(matrix) - 1
col_l = 0
col_r = len(matrix[0]) - 1
def Printnum(matrix,row_u,row_d,col_l,col_r):
if row_u > row_d or col_l > col_r:
return
if row_u <= row_d and col_l <= col_r:
for j in range(col_l,col_r+1):
self.List.append(matrix[row_u][j])
row_u += 1
if row_u <= row_d and col_l <= col_r:
for i in range(row_u,row_d+1):
self.List.append(matrix[i][col_r])
col_r -= 1
if row_u <= row_d and col_l <= col_r:
for j in range(col_r,col_l-1,-1):
self.List.append(matrix[row_d][j])
row_d -= 1
if row_u <= row_d and col_l <= col_r:
for i in range(row_d,row_u-1,-1):
self.List.append(matrix[i][col_l])
col_l += 1
Printnum(matrix,row_u,row_d,col_l,col_r)
Printnum(matrix,row_u,row_d,col_l,col_r)
return self.List

包含Min函数的栈

Q:定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。

思路:python式。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution19:
def __init__(self):
self.stack = []
def push(self, node):
# write code here
self.stack.append(node)
def pop(self):
# write code here
self.stack = self.stack[:-1]
def top(self):
# write code here
return self.stack[-1]
def min(self):
# write code here
return min(self.stack)

栈的压入、弹出序列

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

思路:弹出一个便从压入list中记录index为p,并删除 这个元素。下一个弹出的元素的index只能是p的前一个位置(pre)或者后面位置,弹出后便继续更新p

注意:压入list中删除元素后要更新index。list.remove(val)删除后会更新index,正好符合这道题。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution20:
def IsPopOrder(self, pushV, popV):
# write code here
pre = p = -1
for i in range(len(popV)):
# 判断pushV popV是否一致
if popV[i] not in pushV:
return False
if pushV.index(popV[i]) < pre:
return False
p = pushV.index(popV[i])
pushV.remove(popV[i])
if p == 0:
pre = -1
else:
pre = p - 1
return True

从上往下打印二叉树

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

思路:简单的层序遍历

注意:node=[] res=[] 跟 node=res=[]的区别,前面两个是两个[],后面两个是同一个[]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution21:
# 返回从上到下每个节点值列表,例:[1,2,3]
def PrintFromTopToBottom(self, root):
# write code here
if not root :
return []
node = []
res = []
node.append(root)
while node:
res.append(node[0].val)
if node[0].left:
node.append(node[0].left)
if node[0].right:
node.append(node[0].right)
node = node[1:]
return res

二叉树的后序遍历序列

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

思路:二叉搜索树的中序遍历序列便相当于升序序列,因此将原序列排序便得到中序序列。然后判断能否成树判断能否成树的方法:后序最末位为根节点,通过此节点在中序中的位置(mid_index)分割左右子树节点。

递归判断不能成树的条件是:递归中一旦出现两序列节点组成不一致的情况(最重要的思想!!!想死我了)

注意:其实此题不需要用到二叉搜索树left<root<right,或者说这个条件的全部信息都转化为升序序列为中序序列刚看此题想到中序序列以为此题得到解决,但是拘泥于二叉搜索树的性质写不出递归,其实可完全转化为一个中序一个后序能否成树问题。能否成树又可通过递归过程序列组成是否全程一致来判断。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution22:
def VerifySquenceOfBST(self, sequence):
# write code here
if not sequence:
return False
mid = sorted(sequence)
post = sequence
def Define(mid, post):
if not mid and not post:
return True
# 不能成树的判定
if set(mid)!= set(post):
return False
mid_index = mid.index(post[-1])
return True and Define(mid[:mid_index],post[:mid_index]) and Define(mid[mid_index+1:],post[mid_index:-1])
return Define(mid,post)

二叉树中和为某一值的路径

Q:输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路:定义全局list:self.res,用rest记录剩下路径所需拟合值,PathList记录当前路径。递归遍历节点如果root.val拟合完毕,将PathList并入全局res,并且rest重置为expectNumber,重置PathList=[],从孩子节点从头递归;如果root.val不拟合rest,则将这个节点加入当前PathList,左右孩子传承此PathList继续递归寻找接下来的Path,左右孩子也要不继承PathList把rest重置为expectNumber从头递归

注意:

①root.val拟合或者不拟合都要在左右孩子加一个递归重置rest为expectNumber,重置PathList=[]继续寻找

②左右节点继承当前PathList递归时,PathList要分开指代,要不右节点会继承左节点的PathList

③PathList2=PathList这种方法指代,这俩指针还是指向同一list

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution23:
# 返回二维列表,内部每个列表表示找到的路径
def __init__(self):
self.res = []
def FindPath(self, root, expectNumber):
# write code here
def Path(root, expectNumber, rest, PathList=[] ):
if not root:
return
if root.val == rest:
PathList=PathList+[root.val]
# 不加以下这个if结构是任意子路径,加了代表路径结尾必须是叶子节点。
if not root.left and not root.right:
self.res.append(PathList)
Path(root.left,expectNumber,expectNumber,[])
Path(root.right,expectNumber,expectNumber,[])
return
else:
PathList.append(root.val)
rest -= root.val
# 将此节点填入路径继续递归
# 接下来两个递归会操作同一个PathList,这两个不应该操作统一list
# 直接令PathList2=PathList这俩还是指向同一个
PathList2 = []
PathList2 += PathList
Path(root.left,expectNumber,rest,PathList)
Path(root.right,expectNumber,rest,PathList2)
# 从此节点的子节点开始从头寻找路径
Path(root.left,expectNumber,expectNumber,[])
Path(root.right,expectNumber,expectNumber,[])
return
Path(root,expectNumber,expectNumber,[])
return self.res

复杂链表的复制

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

思路1:难点在给随机指针赋值时候怎样指向已存在的节点,这里的思路是通过next复制节点时,构造原节点与新节点一一对应的字典此方法因为用到哈希,空间复杂度较大

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution24:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
if not pHead:
return None
Node_dic = {}
pre = pHead
clone_head = RandomListNode(pre.label)
p = clone_head
Node_dic[pre] = p
while pre:
pre = pre.next
if pre :
temp = RandomListNode(pre.label)
p.next = temp
p=p.next
# 边复制节点边构造哈希表
Node_dic[pre] = p
pre = pHead
p = clone_head
while pre:
if pre.random:
p.random = Node_dic[pre.random]
pre = pre.next
p = p.next
return clone_head

思路2:省去了空间复杂度,复制链表时一一间隔,将新节点插入原链表

注意:不能用一个while(调整random指针的while)直接将合并的链表拆开

因为如果有random指向前面会出错,因为已经不是一一间隔了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution24_2:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
if not pHead:
return pHead
p = pHead
# 将新节点一一间隔插入原链表
while p:
temp = RandomListNode(p.label)
temp.next = p.next
p.next = temp
p = p.next.next
pre = pHead
post = pre.next
new_head = pre.next
while pre:
if pre.random:
post.random = pre.random.next
pre = post.next
if not pre:
continue
if pre.next:
post = pre.next
pre = pHead
post = pre.next
# 不能直接在上一个while直接将两链表分开,如果有random指向前面会出错,因为已经不是一一间隔了
while pre:
pre.next = post.next
# 考虑到尾节点情况
if post.next:
post.next = post.next.next
pre = pre.next
post = post.next
return new_head

二叉搜索树与双向链表

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

思路:二叉搜索树中序序列便是升序序列,用中序遍历构造链表

注意:需要两个全局变量记录起点指针self.head,还有上一节点的指针self.p

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution25:
def __init__(self):
self.p = None
self.head = None
def Convert(self, pRootOfTree):
# write code here
root = pRootOfTree
def Trans(root):
if not root:
return
#temp保留右指针
temp_left = root.left
temp_right = root.right
self.Convert(temp_left)
if not self.p:
self.p = root
self.head = root
else:
self.p.right = root
root.left = self.p
self.p = root
self.Convert(temp_right)
return
Trans(root)
return self.head

字符串的排列

Q:输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

思路1:先用递归将所有可能的情况列出来,用sorted()解决字典排序问题列出所有情况的方法:分成两个列表s1,s2 ,每次s2中的一个元素加入s1当做下一个s1,其余元素当做下一个s2,进行递归自己的解法:非常不优雅,先将str转为list,在转为str添加进去,还用到了py自带的排序解决字典序问题 如果不用自带排序,则可以参考LeetCode31

注意:因为python中的字符串不可以更改,所以,先将str转为list,在转为str添加进去

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution26_1:
def __init__(self):
self.res = []
def Permutation(self, ss):
# write code here
if not ss:
return []
def allkinds(s1,s2):
if len(s2) == 1:
s = ''.join(s1+s2)
self.res.append(s)
return
for i in range(len(s2)):
# 将选中元素替换到s2第一位
temp = s2[i]
s2[i]=s2[0]
s2[0]=temp
allkinds(s1+[s2[0]],s2[1:])
return
s = sorted(ss)
allkinds([],s)
self.res = list(set(self.res))
return sorted(self.res)

思路2:itertools.permutations用来返回所有排列(元组形式)的list’’.join() 将list、元组内的字符结合成字符串map函数将f应用于右边可迭代的每一个对象

Code

1
2
3
4
5
6
7
8
import itertools
class Solution26_2:
def Permutation(self, ss):
# write code here
if not ss :
return []
else:
return sorted(list(set(map(''.join,itertools.permutations(ss)))))

最小的k个数

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

思路1:python式

Code

1
2
3
4
5
6
class Solution28_1:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if k>len(tinput):
return []
return sorted(tinput)[:k]

思路2:partition函数法(快排):如果下标刚好是k(k-1)则左边(k-1则包含本身)便是所求,如果下标>k则递归左边,下标<k递归右边

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution28_2:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if k > len(tinput):
return []

def Partition(nums, k):
i = 0
j = len(nums) - 1
temp = nums[0]
while i < j:
while nums[j] > temp:
j -= 1
nums[i] = nums[j]
i += 1
while nums[i] <= temp:
i += 1
nums[j] = nums[i]
j -= 1
nums[i] = temp
if i == k - 1 or i == k - 2:
return
elif i > k - 1:
return Partition(nums[:i], k)
else:
return Partition(nums[i + 1:], k - i - 1)

Partition(tinput, k)
return sorted(tinput[:k])

连续子数组的最大和

Q:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。

思路:

两个变量分别记录当前累加值(self.temp)与最大累加值(self.Max)。从头到尾累加数字如果self.temp<0则在每次累加之前将其置0。最关键一点就是用self.temp记录最大值

动态规划思想:用f(i)表示以第i个数字结尾的子数组的最大和则max(f(i))可由一下迭代公式求f(i)=Datai<=0) f(i)=f(i-1)+Datai>0)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution29:
def __init__(self):
self.temp = -99
self.Max = -99
def FindGreatestSumOfSubArray(self, array):
# write code here
for i in range(len(array)):
if self.temp < 0:
self.temp = 0
self.temp += array[i]
if self.temp > self.Max:
self.Max = self.temp
return self.Max

整数中1出现的次数

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

思路:

10个数里面有1个个位1;每100个数里面有10个十位1(10、11、12……19);每1000个数里面有100个百位1 ……

另外需要判断是否应该考虑剩余部分,剩余部分需要判断如115 里面有 10 + (115-110+1) 个十位1

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution30:
def NumberOf1Between1AndN_Solution(self, n):
# write code here
if n < 1:
return 0
if n<10:
return 1
result = 0
# count代表n的位数
count = len(str(n))
# 这里相当于两位到 count-1位 第count 位要单独讨论
for i in range(1,count+1):
# count为完整的倍数
times = n//(10**i)
# num 为每一份对应的1的个数
num = 10 ** (i-1)
# rest 为除掉完整的份数剩下的
rest = n - times*(10**i)
result += times * num
if rest >= 2 * (10**(i-1)):
result += 10**(i-1)
elif rest < (10**(i-1)):
result += 0
else:
result += rest - (10**(i-1)) + 1
return result

将数组排成最小的数

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

思路:全部转化为字符串,用itertools.permutations列出全组合,直接用min 找全组合中最小的

注意:对itertools.permutations、map()、’ ‘.join的应用

Code

1
2
3
4
5
6
7
8
9
class Solution31:
def PrintMinNumber(self, numbers):
# write code here
if not numbers:
return ''
for i in range(len(numbers)):
numbers[i] = str(numbers[i])
List = map(''.join,list(itertools.permutations(numbers,len(numbers))))
return int(min(List))

序列化二叉树

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

思路1:非递归,用栈

序列化:先序遍历得到字符串

反序列化:用栈记录字符串的节点,非#时入栈,flag指向添加方式1为左0为右,flag= =0时出栈,新元素入栈时flag = =1 遇到#号时flag= =0

注意:链接节点时候一定要注意指针。要用原节点去链接,而不是构造与原节点相同的节点链接(见注释)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution_7_mine:
def Serialize(self, root):
# write code here
if not root:
return "#"
else:
return str(root.val)+','+self.Serialize(root.left)+','+self.Serialize(root.right)
def Deserialize(self, s):
# write code here
s = s.split(',')
if not s:
return None
if len(s) == 1:
return TreeNode(s[0])
root = TreeNode(s[0])
stack = [root]
i = 1
flag = 1 # flag==1指示left添加且不用退栈,flag==0指示右边添加且要退栈
while i<len(s):
if s[i] != '#':
if flag == 1:
stack[-1].left = TreeNode(s[i])
# stack.append(TreeNode(s[i])) 是错误的!!!这不是链接原节点,而是构造与原节点相同的节点链接
stack.append(stack[-1].left)
i += 1
else:
stack[-1].right = TreeNode(s[i])
pop_node = stack[-1]
stack = stack[:-1]
# stack.append(TreeNode(s[i])) 是错误的!!!这不是链接原节点,而是构造与原节点相同的节点链接
stack.append(pop_node.right)
i += 1
flag = 1
else:
if flag == 1:
#stack[-1].left = None
flag = 0
i += 1
else:
#stack[-1].right = None
stack = stack[:-1]
i += 1
return root

思路2:精简的递归思路

①通过 def init(self):构造flag全局变量指示遍历位置

②通过self.flag指示list位置建树,建树过程类似遍历过程,只不过遇到#return

③注意l元素本身为字符,给节点赋值时注意int化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def __init__(self):
self.flag = -1
def Serialize(self, root):
# write code her
if not root:
return '#'
return str(root.val)+','+self.Serialize(root.left)+','+self.Serialize(root.right)
def Deserialize(self, s):
# write code here
self.flag += 1
l = s.split(',')
if self.flag >= len(l):
return None
if l[self.flag] == '#':
return None
else:
root = TreeNode(int(l[self.flag]))
root.left = self.Deserialize(s)
root.right = self.Deserialize(s)
return root

二叉树的第K个节点

Q:给定一颗二叉搜索树,请找出其中的第k大的结点。例如, 5 / 3 7 / / 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4。

思路:二叉搜索树中序遍历就是升序

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution_5:
# 返回对应节点TreeNode
def KthNode(self, pRoot, k):
# write code here
if k == 0 or not pRoot:
return
res = []
def dfs(root,res=[]):
if not root:
return
dfs(root.left,res)
res.append(root)
dfs(root.right,res)
dfs(pRoot,res)
return res[k-1] if k<=len(res) else None

矩阵中的路径

Q:请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径,但是矩阵中不包含”abcb”路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

思路:先用嵌套for循环找出所有起始位置,对每个位置依次用递归函数搜寻

注意:每次开始要用新的空list记录路径

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution_2:
def hasPath(self, matrix, rows, cols, path):
# write code here
ok = []
for i in range(rows):
ok.append([])
for _ in range(len(matrix)):
ok[_//cols].append(matrix[_])
init = []
for i in range(rows):
for j in range(cols):
if ok[i][j] == path[0]:
init.append([i,j])
def search(i,j,rows,cols,ok,path,List=[]):
if not path:
return True
if i<0 or j<0 or i>=rows or j>=cols or [i,j] in List :
return False
if ok[i][j] == path[0]:
List.append([i,j])
return True and (search(i+1,j,rows,cols,ok,path[1:],List) or search(i,j+1,rows,cols,ok,path[1:],List)
or search(i-1,j,rows,cols,ok,path[1:],List) or search(i,j-1,rows,cols,ok,path[1:],List))
else:
return False
for x in range(len(init)):
if search(init[x][0],init[x][1],rows, cols, ok, path,[]):
return True
return False

机器人运动范围

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

思路:递归模拟机器人走路,用个列表记录机器人走过的路就行

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution_1:
def movingCount(self, threshold, rows, cols):
# write code here
def Sum(x):
res = 0
while x != 0:
res += x % 10
x = x//10
return res
def search(i,j,rows,cols,threshold,List=[]):
if threshold<0:
return 0
if i>=cols or j>=rows or Sum(i)+Sum(j)>threshold or [i,j] in List:
return 0
else:
List.append([i,j])
return 1+search(i+1,j,rows,cols,threshold,List)+search(i,j+1,rows,cols,threshold,List)
return search(0,0,rows,cols,threshold)

二叉树的下一个节点

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

思路:有right就沿着right的left一直找下去找到尽头没有right就沿着父节点一直向上找,直到导找到该节点是父节点的left

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def GetNext(self, pNode):
# write code here
if not pNode:
return pNode
p = pNode
if p.right:
post = p.right
while post.left:
post = post.left
return post
while p.next:
if p.next.left == p:
return p.next
p = p.next

二叉树的深度

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

思路1:用self.temp记录当前深度,self.Max记录最大深度。先序self.temp+1,后序self.temp-1注意:不要思维定式先中后序只用一个

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def __init__(self):
self.temp = 0
self.Max = 0
def TreeDepth(self, pRoot):
# write code here
if not pRoot:
return 0
self.temp += 1
if self.temp > self.Max:
self.Max = self.temp
self.TreeDepth(pRoot.left)
self.TreeDepth(pRoot.right)
self.temp -= 1
return self.Max

**思路2:更棒的方法

通过 左子树或右子树最大深度+1为当前子树深度 进行递归

Code

1
2
3
4
5
6
7
8
class Solution:
def TreeDepth(self, pRoot):
# write code here
if not pRoot:
return 0
left = self.TreeDepth(pRoot.left)
right = self.TreeDepth(pRoot.right)
return max(left, right)+1

平衡二叉树

Q:输入一棵二叉树,判断该二叉树是否是平衡二叉树。

思路1:写一个递归函数判断深度,注意对max(left,right)的运用,即左子树或右子树最大深度+1为当前子树的深度(写出递归的关键所在)然后从根节点开始递归判断每个节点

缺点:根节点开始递归判断每个节点缺点:重复遍历节点,时间复杂度高

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def IsBalanced_Solution(self, pRoot):
# write code here
if not pRoot:
return True
if abs( self.TreeDepth(pRoot.left) - self.TreeDepth(pRoot.right) ) > 1:
return False
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
def TreeDepth(self, pRoot):
if not pRoot:
return 0
left = self.TreeDepth(pRoot.left)
right = self.TreeDepth(pRoot.right)
return max(left,right) + 1

思路2:同样写一个递归函数判断深度,但是一旦出现不满足返回值便为 -1 ,同时在后序中 left < 0 or right < 0 的运用保证了一旦出现非平衡子树,-1就一直会传递到最后,最后只需在主函数中判断深度是否 >=0 。

对 -1 的传递真是太赞,好好体会

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def IsBalanced_Solution(self, pRoot):
# write code here
return self.TreeDepth(pRoot) >= 0
def TreeDepth(self, pRoot):
if not pRoot:
return 0
left = self.TreeDepth(pRoot.left)
right = self.TreeDepth(pRoot.right)
if (left < 0 or right < 0 or abs(left - right) > 1):
return -1
return max(left, right) + 1

对称的二叉树

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

思路:写递归函数(输入为两个节点)递归比较,递归方式为haha(left.left,right.right) and haha(left.right,right.left)

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def isSymmetrical(self, pRoot):
# write code here
if not pRoot:
return True
return self.haha(pRoot.left,pRoot.right)
def haha(self,left,right):
if not left and not right:
return True
if not left or not right or left.val != right.val :
return False
return self.haha(left.left,right.right) and self.haha(left.right,right.left)

把二叉树打印成多行

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

思路:据层序遍历修改。将val按照嵌套列表方式存储(即每个元素list为一层的val)。while 每次循环处理一层,NextLayer为贮存下层节点的临时list,遍历处理完本层节点后通过Nodeque = NextLayer一下子将本层节点更换为下层节点来推进循环

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
# 返回二维列表[[1,2],[4,5]]
def Print(self, pRoot):
# write code here
if not pRoot:
return []
NodeList = [pRoot]
res = []
while NodeList:
NextLayer = []
ValList = []
for node in NodeList:
ValList.append(node.val)
if node.left:
NextLayer.append(node.left)
if node.right:
NextLayer.append(node.right)
res.append(ValList)
NodeList = NextLayer
return res

按之字形打印二叉树

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

思路:据层序遍历修改。将val按照嵌套列表方式存储(即每个元素list为一层的val)。while 每次循环处理一层,NextLayer为贮存下层节点的临时list,遍历处理完本层节点后通过Nodeque = NextLayer一下子将本层节点更换为下层节点来推进循环。最后按照奇偶顺序修改val列表即可。

注意:将节点加入NextLayer时要判断存在与否,否则空类型也会被添加

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
def Print(self, pRoot):
# write code here
if not pRoot:
return []
# Nodeque为循环遍历的node list
Nodeque = [pRoot]
# res为嵌套list,每个元素list为每层的val
res = []
# 通过Nodeque = NextLayer一下子将本层节点更换为下层节点来推进循环
# 即每一圈while为每层的处理
while Nodeque:
# NextLayer为本层节点的所有孩子节点
NextLayer = []
# ValList存取本层所有节点的val
ValList = []
for node in Nodeque:
ValList.append(node.val)
if node.left:
NextLayer.append(node.left)
if node.right:
NextLayer.append(node.right)
res.append(ValList)
Nodeque = NextLayer
transres = []
for i,v in enumerate(res):
if i % 2:
transres.append(v[::-1])
else:
transres.append(v)
return transres

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

Q:输入两个链表,找出它们的第一个公共结点。这里的是指两个链表在某个节点之后会汇入同一个链表。

思路:最后两个链表汇入一个链表,即最后公共长度是一样的。因此可以先遍历两个链表,得出长度差在较长链表上提前多走长度差的步数,再一一比较

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
if not pHead1 or not pHead2:
return None
p1 = pHead1
p2 = pHead2
length1 = 0
length2 = 0
while p1:
length1 += 1
p1 = p1.next
while p2:
length2 += 1
p2 = p2.next
p1 = pHead1
p2 = pHead2
differ = abs(length1 - length2)
if length1 > length2:
for i in range(differ):
p1 = p1.next
else:
for i in range(differ):
p2 = p2.next
while p1 and p2:
if p1.val == p2.val:
return p1
p1 = p1.next
p2 = p2.next
return None

数组中出现次数超过一半的元素

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

思路1:用哈希记录每个元素出现的次数

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution27:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
if len(numbers) == 1:
return numbers[0]
dic = {}
for i in range(len(numbers)):
if numbers[i] not in dic:
dic[numbers[i]] = 1
else:
dic[numbers[i]] += 1
if dic[numbers[i]]>len(numbers)/2:
return numbers[i]
return 0

思路2:如果有个元素出现超过一半,那么这个元素比其他元素都多(废话)。据此,count记录所存储元素的计数,temp记录所存取元素。count == 0时,temp变为当前元素,count置1;count != 0时, 当前元素与temp相等,count+1否则-1;结束遍历一遍temp元素,看看是否次数超过一半。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
count = 0
temp = -99
for i in numbers:
if count == 0:
temp = i
count += 1
else:
if i != temp:
count -= 1
else:
count += 1
if count == 0:
return 0
kan = 0
for i in numbers:
if i == temp:
kan += 1
if kan > len(numbers) // 2:
return temp
else:
return 0

丑数

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

思路:考虑o(N)的用丑数生成丑数,不再遍历多余的非丑数。建立uglynums列表按顺序保存丑数。除了1以外,丑数肯定是排在之前的丑数乘以2、3、5的结果。问题在于怎样确保列表里面的丑数是排好顺序的。假设最大丑数为M,计算下一个丑数时小于M的肯定已经在列表当中。对于乘以2而言,肯定存在某一个丑数,排在它之前的每个丑数乘以2都小于M,排在它之后的每个丑数乘以2都远大于M,我们只需要记录下这个丑数的位置m2,对于乘以3和5,同样存下m3、m5.

1
2
3
4
5
注意:
1.更新标记只需要 +1 即可,+1之后再用到肯定大于M
2.此代码精彩的地方在于省略了对新丑数是否=M的判断,见下一条
3.有可能有几个数同时得到要添加的数值,如62*33*2)则m2,m3需要同时更新,这里的三个并列的if相当于省略了对更新的数
是否=M的判断

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def GetUglyNumber_Solution(self, index):
# write code here
uglynums = [1]
m2 = m3 = m5 =0
if index < 1:
return 0
if index == 1:
return 1
for i in range(1,index+1):
uglynums.append(min(uglynums[m2]*2, uglynums[m3]*3, uglynums[m5]*5))
if uglynums[i] == uglynums[m2]*2:
m2 += 1
if uglynums[i] == uglynums[m3]*3:
m3 += 1
if uglynums[i] == uglynums[m5]*5:
m5 += 1
return uglynums[index-1]

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

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

思路:二分查找找到一个target,返回index,然后往两边扩展

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
def Getindex(self, data, left, right, k):
if left > right:
return -1
mid = (left + right) // 2
if data[mid] == k:
return mid
if data[mid] < k:
return self.Getindex(data, mid+1, right,k)
else:
return self.Getindex(data,left,mid-1,k)
def GetNumberOfK(self, data, k):
# write code here
if not data:
return 0
left = 0
right = len(data) - 1
flag = self.Getindex(data, left, right, k)
if flag < 0:
return 0
else:
l = r = flag
while l >= 1 and data[l-1] == k:
l -= 1
if data[0] == k:
l =0
while r <= len(data) - 2 and data[r+1] == k:
r += 1
if data[right] == k:
r = right
return r - l + 1

数组中的逆序对

Q:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。

思路:根据归并排序改编,每次合并两个数组排序时,查找两个数组中的逆序对,因为单个数组已经排好序,所以只需考虑两个数组之间的逆序对。具体方法是,见代码注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution34:
def __init__(self):
self.count = 0
def InversePairs(self, data):
# write code here
self.guibing(data)
return self.count
def guibing(self,data):
if len(data) == 1:
return data
mid = len(data) // 2
left = self.guibing(data[:mid])
right = self.guibing(data[mid:])
# left_len 用于left、right合并最后right剩余时候计算剩余right的逆序对
left_len = len(left)
res = []
while left and right:
# 比较left、right最后一位,将大的从头插入res
# 如果left[-1]大,此时right的长度就是left[-1]对应的逆序对数
if left[-1] > right[-1]:
self.count += len(right)
res.insert(0, left.pop(-1))
else:
res.insert(0, right.pop(-1))
if left:
return left + res
if right:
return right + res

孩子们的游戏

Q:让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢?(注:小朋友的编号是从0到n-1)

思路:用取余数操作表示循环队列,kid存储每轮剩余孩子编号。每次的(余数$-1$)相当于下次多走的步数,同时每次过后 $hc$(除数)$-1$,并在kid中pop掉。

注意:余数是$0$相当于下次多走(除数$-1$)步!而不是多走$-1$步!
每次更新$M$要用$m$!不能用$M$!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
if n < 1:
return -1
kid = list(range(n))
hc = n #当前圈里还剩的孩子个数
M = m #M表示每次要走的步数
while hc > 1:
temp = M % hc
kid.pop(temp-1)
if temp:
M = temp + m -1
else:
M = m
hc -= 1
return kid[0]

0%