[TOC]
01.二维数组中的查找
- Q：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
- A：从左下或者右上开始查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
rowN = len(array)
colN = len(array[0])
i = rowN - 1
j = 0
while i>=0 and j < colN:
if target == array[i][j]:
return True
elif target > array[i][j]:
j += 1
elif target < array[i][j]:
i -= 1
return False
02.替换空格
- Q：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
- A：先计算空格数量，从后往前替换
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# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
# return s.replace(" ", "%20")
# s1 = s.split(" ")
# return "%20".join(s1)
s = list(s)
count = 0
for c in s:
if c == " ":
count += 1
i = len(s) - 1
s += ["0"] * count * 2
while i >= 0:
if s[i] != " ":
s[i+2*count] = s[i]
else:
count -= 1
s[i+2*count] = "%"
s[i+2*count+1] = "2"
s[i+2*count+2] = "0"
i -= 1
return "".join(s)
03.从尾到头打印链表
- Q：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
- A：头插法
1
2
3
4
5
6
7
8
9
10
11
12
13# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
if listNode == None:
return []
return self.printListFromTailToHead(listNode.next) + [listNode.val] # 递归
04.重建二叉树
- Q：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
- A：【前序遍历：根左右】【中序遍历：左根右】
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# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if not pre or not tin:
return None
root = TreeNode(pre[0]) # list.pop([index=-1])
index = tin.index(root.val) # 左子树有 index 个结点
root.left = self.reConstructBinaryTree(pre[1:index+1], tin[:index])
root.right = self.reConstructBinaryTree(pre[index+1:], tin[index+1:])
return root
'''
# pop() 函数用于移除列表中的一个元素（默认最后一个元素），并且返回该元素的值。
root = TreeNode(pre.pop(0)) # list.pop([index=-1])
index = tin.index(root.val) # 递归操作
root.left = self.reConstructBinaryTree(pre, tin[:index])
root.right = self.reConstructBinaryTree(pre, tin[index+1:])
return root
'''
05.用两个栈实现队列
- Q：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
- A：栈2 辅助 栈1 操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
# write code here
self.stack1.append(node)
def pop(self):
# return xx
if len(self.stack1):
while len(self.stack1):
self.stack2.append(self.stack1.pop())
val = self.stack2.pop()
while len(self.stack2):
self.stack1.append(self.stack2.pop())
return val
else:
return None
06.旋转数组的最小数字
- Q：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0
- A：二分查找的变型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray) == 0:
return 0
else:
L = 0
R = len(rotateArray) - 1
while L < R:
if rotateArray[L] < rotateArray[R]:
return rotateArray[L]
M = (L + R) / 2
if rotateArray[L] < rotateArray[M]: # 左边是有序数组，最小值在右边
L = M + 1
elif rotateArray[M] < rotateArray[R]: # 右边是有序数组，最小值在左边
R = M
else:
L += 1
return rotateArray[L]
07.斐波那契数列
- Q：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39 - A：记住前两个
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# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
if n == 0:
return 0
elif n == 1:
return 1
else:
N = 2
N_2 = 0
N_1 = 1
while n > N:
N += 1
K = N_1
N_1 = N_2 + N_1 # 每次记住前两个
N_2 = K
return N_2 + N_1 # 此时 n == N
# if n == 0:
# return 0
# elif n == 1:
# return 1
# else:
# return self.Fibonacci(n-2) + self.Fibonacci(n-1) # 会溢出
08.跳台阶
- Q：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
- A：推导公式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
if number == 1:
return 1
elif number == 2:
return 2
else:
f1 = 1
f2 = 2
for i in range(3, number+1):
cur = f1 + f2
f1 = f2
f2 = cur
return cur
# if number == 1:
# return 1
# elif number == 2:
# return 2
# else:
# return self.jumpFloor(number-2) + self.jumpFloor(number-1)
09.变态跳台阶
- Q：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
- A：推导
1
2
3
4
5
6
7
8
9
10
11
12
13
14# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
return 2 ** (number-1)
# 先看跳的第一步
# 跳 1 级：剩下 f(n-1)
# 跳 2 级：剩下 f(n-2)
# ...
# 跳 n-1 级：剩下 f(n-(n-1))
# 跳 n 级：剩下 f(n-n)
# f(n)=f(0)+f(1)+...+f(n-1)=2*f(n-1)
# f(1)=1
10.矩形覆盖
- Q：我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
- A：推导
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number == 0:
return 0
elif number == 1:
return 1
elif number == 2:
return 2
else:
f1 = 1
f2 = 2
for i in range(3, number+1):
cur = f1 + f2
f1 = f2
f2 = cur
return cur
# n=0 0 # 容易错
# n=1 1
# n=2 2
# n=3 f(n)=f(n-1)+f(n-2)
11.二进制中1的个数
- Q：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
- A：负数转为正的表示
1
2
3
4
5
6
7
8
9
10
11
12
13
14# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
# write code here
sum = 0
if n < 0:
n = n & 0xffffffff # 先把负数的补码转为正数的表示
while n:
sum += 1
n = (n-1) & n
return sum
# 最高位是符号位，0是正数，1是负数，原码=符号位+数值位
# 反码：对于负数，数符位为1，数符位不变，将数值位诸位取反为反码。
# 补码：对于负数，数符位为1，数符位不变，将反码＋1＝补码。
12.数值的整数次方
- Q：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
- A：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
# write code here
result = 1.0
if exponent == 0:
result = 1
elif exponent > 0:
for i in range(1, exponent+1):
result *= base
else:
for i in range(1, (-exponent)+1):
result *= base
result = 1/result
return result
13.调整数组顺序使奇数位于偶数前面
- Q：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
- A：稳定排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self, array):
# write code here
if len(array) == 0:
return []
L = len(array)
# for i in range(0, L-1): # 冒泡排序
# for j in range(0, L-1-i):
# if array[j]%2==0 and array[j+1]%2==1:
# array[j], array[j+1] = array[j+1], array[j]
# return array
for i in range(1, L): # 插入排序
j = i
while j > 0 and array[j]%2==1 and array[j-1]%2==0:
array[j], array[j-1] = array[j-1], array[j]
j -= 1
return array
14.链表中倒数第k个结点
- Q：输入一个链表，输出该链表中倒数第k个结点。
- A：双指针
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# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindKthToTail(self, head, k):
# write code here
# if head==None or k<=0:
# return None
# a = head # 两个指针协作，相差k-1步 !!!!!!!!
# b = head
# while k > 1:
# if b.next:
# k -= 1
# b = b.next
# else:
# return None
# while b.next:
# a = a.next
# b = b.next
# return a
stack = [] # 链栈
while head:
stack.append(head)
head = head.next
if k>len(stack) or k<=0:
return None
return stack[-k]
15.反转链表
- Q：输入一个链表，反转链表后，输出新链表的表头。
- A：递归 或 循环
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# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead): # 头节点pHead是空的
# write code here
if pHead==None or pHead.next==None:
return pHead
pre = self.ReverseList(pHead.next)
pHead.next.next = pHead
pHead.next = None
return pre
'''
pre = None
cur = pHead
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
'''
16.合并两个排序的链表
- Q：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
- A：循环 或 递归
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# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
newHead = ListNode(0)
tmp = newHead
while pHead1 and pHead2:
if pHead1.val < pHead2.val:
tmp.next = pHead1
pHead1 = pHead1.next
else:
tmp.next = pHead2
pHead2 = pHead2.next
tmp = tmp.next
if pHead1 == None:
tmp.next = pHead2
elif pHead2 == None:
tmp.next = pHead1
return newHead.next
'''
if pHead1 == None:
return pHead2
if pHead2 == None:
return pHead1
if pHead1.val <= pHead2.val:
pHead1.next = self.Merge(pHead1.next, pHead2)
return pHead1
else:
pHead2.next = self.Merge(pHead1, pHead2.next)
return pHead2
'''
17.树的子结构
- Q：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
- A：递归
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# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
# write code here
res = False
if pRoot1 and pRoot2:
if pRoot1.val == pRoot2.val:
res = self.T1_Has_T2(pRoot1, pRoot2)
if not res:
res = self.T1_Has_T2(pRoot1.left, pRoot2)
if not res:
res = self.T1_Has_T2(pRoot1.right, pRoot2)
return res
def T1_Has_T2(self, pRoot1, pRoot2):
if pRoot2 == None: # 先（说明B树已经遍历结束）
return True
if pRoot1 == None: # 后
return False
if pRoot1.val != pRoot2.val:
return False
return self.T1_Has_T2(pRoot1.left, pRoot2.left) and self.T1_Has_T2(pRoot1.right, pRoot2.right)
18.二叉树的镜像
- Q：操作给定的二叉树，将其变换为源二叉树的镜像。
A：递归
1
2
3
4
5
6
7
8
9
10
11
12二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5A：
1
2
3
4
5
6
7
8
9
10
11
12
13
14# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回镜像树的根节点
def Mirror(self, root):
# write code here
if root:
root.left, root.right = root.right, root.left
self.Mirror(root.left)
self.Mirror(root.right)
19.顺时针打印矩阵
- Q：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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.
- A：记录层数
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# -*- coding:utf-8 -*-
class Solution:
# matrix类型为二维列表，需要返回列表
def printMatrix(self, matrix):
# write code here
res = []
if len(matrix) == 0:
return res
rowN = len(matrix)
colN = len(matrix[0])
L = (min(rowN, colN)-1)/2+1 # 层数
for i in range(L):
for k in range(i, colN-i): # 从左到右（层号对应行号）
res.append(matrix[i][k])
for j in range(i+1, rowN-i): # 从右上到右下
res.append(matrix[j][colN-i-1])
for k in range(colN-i-2, i-1, -1): # 从右到左
if rowN-i-1 != i: # 只有1行
res.append(matrix[rowN-i-1][k])
for j in range(rowN-i-2, i, -1):
if colN-i-1 != i: # 只有1列
res.append(matrix[j][i]) # 从左下到左上（层号对应列号）
return res
20.包含min函数的栈
- Q：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
- A：辅助栈放最小值
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# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, node):
# write code here
self.stack.append(node)
if len(self.minStack) == 0:
self.minStack.append(node)
else:
self.minStack.append(min(self.minStack[-1], node))
def pop(self):
# write code here
if len(self.stack) == 0:
return None
self.minStack.pop()
return self.stack.pop()
def top(self):
# write code here
if len(self.stack) == 0:
return None
return self.stack[-1]
def min(self):
# write code here
if len(self.minStack) == 0:
return None
return self.minStack[-1]
21.栈的压入、弹出序列
- Q：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
- A：就按栈的操作进行【入栈期间可以出栈】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17# -*- coding:utf-8 -*-
class Solution:
def IsPopOrder(self, pushV, popV): # 入栈中途可以出栈
# write code here
if pushV == [] or popV == []:
return False
stack = []
for i in pushV:
stack.append(i)
while len(stack) and stack[-1] == popV[0]:
stack.pop()
popV.pop(0)
if len(stack):
return False
else:
return True
22.从上往下打印二叉树
- Q：从上往下打印出二叉树的每个节点，同层节点从左至右打印。
- A：引入一个队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回从上到下每个节点值列表，例：[1,2,3]
def PrintFromTopToBottom(self, root):
# write code here
if root == None:
return []
queue = [] # 队列
res = []
queue.append(root)
while len(queue):
cur = queue.pop(0)
res.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
return res
23.二叉搜索树的后序遍历序列
- Q：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
- A：【后序遍历：左右根】
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# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here 二叉搜索树，二叉排序树，左<根<右
if sequence == []:
return False
root = sequence[-1] # 根
L = len(sequence)
for i in range(L):
if sequence[i] > root: # 左
break
for j in range(i, L):
if sequence[j] < root: # 右
return False
left = True
if i > 0:
left = self.VerifySquenceOfBST(sequence[:i])
right = True
if j < L - 1:
right = self.VerifySquenceOfBST(sequence[i:L-1])
return left and right
24.二叉树中和为某一值的路径
- Q：输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
- A：前序遍历
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# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
# write code here
if root==None or root.val>expectNumber:
return []
if root.left==None and root.right==None and root.val==expectNumber:
return [[root.val]]
else:
expectNumber -= root.val
left = self.FindPath(root.left, expectNumber)
right = self.FindPath(root.right, expectNumber)
res = []
for x in left:
res.append([root.val]+x)
for x in right:
res.append([root.val]+x)
return sorted(res, key=lambda x: -len(x))
25.复杂链表的复制
- Q：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
- A：三步走
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# -*- coding:utf-8 -*-
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
if pHead == None:
return None
pNode = pHead
while pNode: # （1）在旧链表中创建新链表，此时不处理新链表的兄弟结点
pClone = RandomListNode(pNode.label)
pClone.next = pNode.next
pNode.next = pClone
pNode = pClone.next
pNode = pHead
while pNode: # （2）根据旧链表的兄弟结点，初始化新链表的兄弟结点
pClone = pNode.next
if pNode.random:
pClone.random = pNode.random.next
pNode = pClone.next
pNode = pHead
pCloneHead = pCloneNode = pNode.next
pNode.next = pCloneHead.next
pNode = pNode.next
while pNode: # （3）从旧链表中拆分得到新链表（需保留旧链表）
pCloneNode.next = pNode.next
pCloneNode = pCloneNode.next
pNode.next = pCloneNode.next
pNode = pNode.next
return pCloneHead
26.二叉搜索树与双向链表
- Q：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
- A：中序遍历：左根右
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# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def Convert(self, pRootOfTree):
# write code here
if pRootOfTree == None:
return None
if pRootOfTree.left==None and pRootOfTree.right==None:
return pRootOfTree
self.Convert(pRootOfTree.left) # 左边
left = pRootOfTree.left
if left:
while left.right: # 左子树找到最大的结点（即最右边的）
left = left.right
pRootOfTree.left = left
left.right = pRootOfTree
self.Convert(pRootOfTree.right)
right = pRootOfTree.right
if right:
while right.left: # 右子树找到最小的结点（即最左边的）
right = right.left
pRootOfTree.right = right
right.left = pRootOfTree
while pRootOfTree.left:
pRootOfTree = pRootOfTree.left # 返回最左边的结点
return pRootOfTree
27.字符串的排列
- Q：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
- A：固定第一个元素，求后序所有字符的遍历，递归 或者 回溯法
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# -*- coding:utf-8 -*-
class Solution:
def Permutation(self, ss):
# write code here
if len(ss) == 0:
return []
res, charlist = [], list(ss)
self.BackTrack(res, charlist, 0)
return sorted(res)
def BackTrack(self, res, charlist, begin):
if begin == len(charlist) - 1:
res.append("".join(charlist))
for i in range(begin, len(charlist)):
if i!=begin and charlist[i] == charlist[begin]:
continue
charlist[i], charlist[begin] = charlist[begin], charlist[i]
self.BackTrack(res, charlist, begin+1)
charlist[i], charlist[begin] = charlist[begin], charlist[i]
'''
if len(ss) == 0:
return []
if len(ss) == 1:
return list(ss)
charlist = list(ss)
charlist.sort()
res = []
for i in range(0, len(charlist)):
if i>0 and charlist[i] == charlist[i-1]:
continue
tmp = self.Permutation(''.join(charlist[:i]) + ''.join(charlist[i+1:]))
for j in tmp:
res.append(charlist[i] + j)
return res
'''
28.数组中出现次数超过一半的数字
- Q：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
- A：哈希表 或者 排序后中间的数字 或者 摩尔投票法【阵地攻守的思想】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23# -*- coding:utf-8 -*-
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
if len(numbers) == 0:
return 0
num = numbers[0]
cnt = 1
for i in range(1, len(numbers)): # 摩尔投票法
if cnt == 0:
num = numbers[i]
cnt = 1
elif numbers[i] == num:
cnt += 1
else:
cnt -= 1
cnt = 0
for i in range(0, len(numbers)):
if numbers[i] == num:
cnt += 1
return num if 2 * cnt > len(numbers) else 0
29.最小的K个数
- Q：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
- A：大顶堆排序 或者 利用快排 pivot处在第k个位置
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if len(tinput)==0 or k<=0 or len(tinput)<k:
return []
start = 0
end = len(tinput) - 1
index = self.Partition(tinput, start, end)
while index != k - 1:
if index > k - 1:
end = index - 1
else:
start = index + 1
index = self.Partition(tinput, start, end)
return sorted(tinput[:k])
def Partition(self, arr, begin, end): # 划分元素
pivot = arr[begin] # 选取第一个元素作为基准
left = begin + 1
right = end
while True:
while left <= right and arr[left] <= pivot:
left += 1
while left <= right and arr[right] >= pivot:
right -= 1
if left < right:
arr[left], arr[right] = arr[right], arr[left]
else:
break
arr[begin], arr[right] = arr[right], pivot # 划分元素放到中间位置
return right # 返回划分元素的下标
'''
for i in range(k/2-1, -1, -1): # 第k个元素的父结点
self.adjustMaxHeapSort(tinput, i, k-1) # 构建前k个元素的大顶堆（从后往前）
for i in range(k, len(tinput)): # 只放前k个小的
if tinput[i] < tinput[0]:
tinput[i], tinput[0] = tinput[0], tinput[i]
self.adjustMaxHeapSort(tinput, 0, k-1)
# return sorted(tinput[:k])
return self.MaxHeapSort(tinput[:k])
def adjustMaxHeapSort(self, arr, pos, length): # 调整大顶堆（将最大值调整到根结点）
tmp = arr[pos]
while 2*pos+1 <= length:
child = 2 * pos + 1
if child<length and arr[child]<arr[child+1]:
child += 1
if arr[child] < tmp:
break
arr[pos] = arr[child]
pos = child
arr[pos] = tmp
def MaxHeapSort(self, arr):
if len(arr) == 0:
return []
L = len(arr)
for i in range(L/2-1, -1, -1):
self.adjustMaxHeapSort(arr, i, L-1)
for i in range(L-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
self.adjustMaxHeapSort(arr, 0, i-1)
return arr
'''
30.连续子数组的最大和
- Q：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
- A：动态规划 或者 分析规律求解过程
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# f(i)表示：以array[i]为末尾元素的子数组 的和的最大值
# -*- coding:utf-8 -*-
'''
f(i) = arr[i] , i = 0 或者 f(i-1) < 0
f(i) = f(i-1) + arr[i], i != 0 并且 f(i-1) > 0
'''
class Solution:
def FindGreatestSumOfSubArray(self, array):
# write code here
if len(array) == 0:
return 0
pre = array[0]
res = array[0] # 已知的最大值
for i in range(1, len(array)):
cur = max(pre + array[i], array[i]) # f(i)=max(f(i-1)+arr[i], arr[i])
res = max(cur, res)
pre = cur
return res
'''
cur_sum = 0
max_sum = array[0]
for i in range(len(array)):
if cur_sum <= 0:
cur_sum = array[i]
else:
cur_sum += array[i]
if cur_sum > max_sum:
max_sum = cur_sum
return max_sum
'''
31.整数中1出现的次数（从1到n整数中1出现的次数）
- Q：求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
- A：常规方法 %10
1
2
3
4
5
6
7
8
9
10
11# -*- coding:utf-8 -*-
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
# write code here
cnt = 0
for i in range(1, n+1):
while i:
if i%10 == 1:
cnt += 1
i = i / 10
return cnt
32.把数组排成最小的数
- Q：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
- A：排序
1
2
3
4
5
6
7
8
9
10
11
12
13# -*- coding:utf-8 -*-
class Solution:
def PrintMinNumber(self, numbers):
# write code here
if len(numbers) == 0:
return ''
str_num = [str(i) for i in numbers]
for i in range(len(str_num)-1): # 选择排序
for j in range(i+1, len(str_num)):
if str_num[i]+str_num[j] > str_num[j]+str_num[i]:
str_num[i], str_num[j] = str_num[j], str_num[i]
return "".join(str_num)
33.丑数
- Q：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
- A：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22# -*- coding:utf-8 -*-
class Solution:
def GetUglyNumber_Solution(self, index):
# write code here
if index < 0:
return None
if index < 7:
return index
p2, p3, p5 = 0, 0, 0
new_num = 1
arr = [1]
while len(arr) < index: # 下一个丑数是前面的某一个丑数乘以235得到的
new_num = min(arr[p2]*2, arr[p3]*3, arr[p5]*5)
if arr[p2]*2 == new_num:
p2 += 1
if arr[p3]*3 == new_num:
p3 += 1
if arr[p5]*5 == new_num:
p5 += 1
arr.append(new_num)
return new_num
34.第一个只出现一次的字符位置
- Q：在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
- A：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19# -*- coding:utf-8 -*-
class Solution:
def FirstNotRepeatingChar(self, s):
# write code here
if not s:
return -1
hash_table = {}
for i in s:
if i not in hash_table:
hash_table[i] = 0
hash_table[i] += 1
for i in s:
if hash_table[i] == 1:
return s.index(i)
return -1
35.数组中的逆序对
- Q：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
- A：
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
36class Solution {
public:
int InversePairs(vector<int> data) {
return mergeSort(data, 0, data.size()-1);
}
int mergeSort(vector<int> &data, int start, int end)
{
if (start >= end) return 0;
int mid = (start + end)/2;
int left_num = mergeSort(data, start, mid);
int right_num = mergeSort(data, mid+1, end);
vector<int> copy(data);
int i = mid, j = end, k = end;
int cnt = 0;
while (i>=start && j>=mid+1) // 从高位向低位归并
{
if (data[i] > data[j]) // 比最大的还大，加上右边数组长度
{
copy[k--] = data[i--];
cnt += j - mid;
}
else copy[k--] = data[j--];
}
while (i>=start)
copy[k--] = data[i--];
while (j>=mid+1)
copy[k--] = data[j--];
for (int i=start; i<=end; i++)
data[i] = copy[i];
return (left_num + cnt + right_num)%1000000007;
}
};
36.两个链表的第一个公共结点
- Q：输入两个链表，找出它们的第一个公共结点。
- A：
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# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
if pHead1==None or pHead2==None:
return None
L1, L2 = 0, 0
p1, p2 = pHead1, pHead2
while p1:
L1 += 1
p1 = p1.next
while p2:
L2 += 1
p2 = p2.next
p1, p2 = pHead1, pHead2
if L1 > L2:
k = L1 - L2
while k:
p1 = p1.next
k -= 1
elif L1 < L2:
k = L2 - L1
while k:
p2 = p2.next
k -= 1
while p1:
if p1 is p2:
return p1
p1 = p1.next
p2 = p2.next
return None
37.数字在排序数组中出现的次数
- Q：统计一个数字在排序数组中出现的次数。
- A：
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# -*- coding:utf-8 -*-
class Solution:
def GetNumberOfK(self, data, k):
# write code here
if len(data) == 0:
return 0
if k < data[0] or k > data[-1]:
return 0
left = 0
right = len(data) - 1
while left <= right:
mid = (left + right) / 2
if data[mid] < k:
left = mid + 1
else:
right = mid - 1
first = left # 如果没有k，a < k < b，left在b的位置
left = 0
right = len(data) - 1
while left <= right:
mid = (left + right) / 2
if data[mid] > k:
right = mid - 1
else:
left = mid + 1
last = right # 如果没有k，a < k < b，right在a的位置
return last - first + 1
38.二叉树的深度
- Q：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
- A：
1
2
3
4
5
6
7
8
9
10
11
12# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def TreeDepth(self, pRoot):
# write code here
if pRoot == None:
return 0
return 1 + max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right))
39.平衡二叉树
- Q：输入一棵二叉树，判断该二叉树是否是平衡二叉树。
- A：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution: # 它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
def IsBalanced_Solution(self, pRoot):
# write code here
if pRoot == None:
return True
return abs(self.get_depth(pRoot.left) - self.get_depth(pRoot.right))<=1 and \
self.IsBalanced_Solution(pRoot.left) and \
self.IsBalanced_Solution(pRoot.right)
def get_depth(self, pRoot):
if pRoot == None:
return 0
return 1 + max(self.get_depth(pRoot.left), self.get_depth(pRoot.right))
40.数组中只出现一次的数字
- Q：一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字
- A：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
# write code here
hash_ = {}
for i in array:
if i not in hash_:
hash_[i] = 0
hash_[i] += 1
res = []
for i in hash_:
if hash_[i] == 1:
res.append(i)
if len(res) == 2:
break
return res
41.和为S的连续正数序列
- Q：小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!【输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序】
- A：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18# -*- coding:utf-8 -*-
class Solution:
def FindContinuousSequence(self, tsum):
# write code here
res = []
plow, phigh = 1, 2 # 双指针操作
while plow < phigh:
cur = (plow + phigh) * (phigh - plow + 1) / 2 # 等差数列求和
if cur == tsum:
tmp = list(range(plow, phigh+1))
res.append(tmp)
plow += 1
elif cur < tsum:
phigh += 1
else:
plow += 1
return res
42.和为S的两个数字
- Q：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
- A：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
if len(array) < 2:
return []
plow, phigh = 0, len(array)-1
while plow < phigh:
if array[plow] + array[phigh] == tsum: # a和b越远乘积越小，a*(k-a)
return [array[plow], array[phigh]]
elif array[plow] + array[phigh] > tsum:
phigh -= 1
else:
plow += 1
return []
43.左旋转字符串
- Q：汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
- A：
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# -*- coding:utf-8 -*-
class Solution:
def LeftRotateString(self, s, n):
# write code here
if n < 0:
return ""
if len(s) == 0:
return ""
m = n % len(s)
stack = list(s)
self.Reverse(stack, 0, m-1) # YX= (X^T Y^T)^T
self.Reverse(stack, m, len(s)-1)
self.Reverse(stack, 0, len(s)-1)
return "".join(stack)
def Reverse(self, arr, start, end):
while start < end:
arr[start], arr[end] = arr[end], arr[start]
start += 1
end -= 1
'''
for i in range(n%len(s)): # 队列操作
tmp = stack.pop(0)
stack.append(tmp)
return "".join(stack)
'''
44.翻转单词顺序列
- Q：牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
- A：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23# -*- coding:utf-8 -*-
class Solution:
def ReverseSentence(self, s):
# write code here
if len(s) == 0:
return ''
stack = list(s)
self.Reverse(stack, 0, len(s)-1) # 先逆置
head, cur = 0, -1
while cur < len(s):
if cur == len(s)-1 or stack[cur+1] == ' ':
self.Reverse(stack, head, cur) # 按空格区分，逆置单词
cur += 2
head = cur
else:
cur += 1
return "".join(stack)
def Reverse(self, arr, start, end):
while start < end:
arr[start], arr[end] = arr[end], arr[start]
start += 1
end -= 1
45.扑克牌顺子
- Q：LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。
- A：
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# -*- coding:utf-8 -*-
class Solution:
def IsContinuous(self, numbers):
# write code here
if len(numbers) < 5:
return False
min_v = 14
max_v = -1
cnt = {}
for i in numbers:
if i == 0: # 除0外没有重复的数字(牌)
continue
if i in cnt:
return False
else:
cnt[i] = 1
if i > max_v:
max_v = i
if i < min_v:
min_v = i
if max_v - min_v < 5: # max - min <5
return True
else:
return False
46.孩子们的游戏(圆圈中最后剩下的数)
- Q：每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
- A：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22# -*- coding:utf-8 -*-
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
if n == 0:
return -1
res = 0
for i in range(2, n+1):
res = (res + m) % i
return res
'''
f(n,m)： 0 1 2 ... n-3 n-2 n-1 【n个数】每次删除后的最终结果
f(n-1,m)： 0 1 2 ... n-3 n-2 【n-1个数】每次删除后的最终结果
0 1 2 ... k-1 k+1 ... n-2 n-1 删除k，k=m-1
g(n-1,m)： k+1 k+2 ... n-2 n-1 0 1 2 ... k-2 k-1 【n-1个数】
f(n,m) = g(n-1,m) = (f(n-1,m)+k+1)%n
递归公式：
f(1, m) = 0
f(n, m) = (f(n-1, m) + m) % n
'''
47.求1+2+3+…+n
- Q：求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
- A：
1
2
3
4
5
6
7# -*- coding:utf-8 -*-
class Solution:
def Sum_Solution(self, n):
# write code here 利用逻辑与的短路特性实现递归终止
return n and self.Sum_Solution(n - 1) + n
# 利用python中的and特性，a and b，a为False，返回a，a为True，就返回b
48.不用加减乘除做加法
- Q：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
- A：
1
2
3
4
5
6
7
8
9
10# -*- coding:utf-8 -*-
class Solution:
def Add(self, num1, num2):
# write code here
while num2 != 0:
tmp = (num1 ^ num2) & 0xffffffff # 异或 两个数异或：相当于每一位相加，而不考虑进位
carry = ((num1 & num2) << 1) & 0xffffffff # 两个数相与，并左移一位：相当于求得进位
num1 = tmp
num2 = carry
return num1 if num1 <= 0x7fffffff else ~(num1^0xffffffff)
49.把字符串转换成整数
- Q：将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
- A：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22# -*- coding:utf-8 -*-
class Solution:
def StrToInt(self, s):
# write code here
if len(s) == 0:
return 0
numdict = {'0':0, '1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8,'9':9}
res = []
for i in range(len(s)):
if i==0 and (s[i]=='+' or s[i]=='-'):
continue
if s[i] not in numdict:
return 0
else:
res.append(numdict[s[i]])
v = 0
for j in range(len(res)):
v = v * 10 + res[j]
return 0-v if s[0] == '-' else v
50.数组中重复的数字
- Q：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
- A：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
n = len(numbers)
for i in range(n):
index = numbers[i]
if index >= n:
index -= n
if numbers[index] >= n:
duplication[0] = index
return True
numbers[index] += n
return False
51.构建乘积数组
- Q：给定一个数组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]。不能使用除法。
- A：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
# 前一部分 C[i] = A[0]*A[1]*...*A[i-1] = C[i-1]A[i-1]
# 后一部分 D[i] = A[i+1]*A[i+2]*...*A[n-1] = A[i+1]D[i+1]
if len(A) == 0:
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 *= A[i+1]
B[i] *= tmp
return B
52.正则表达式匹配
- Q：请实现一个函数用来匹配包括’.’和’*‘的正则表达式。模式中的字符’.’表示任意一个字符，而’*‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配
- A：
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# -*- coding:utf-8 -*-
class Solution:
# s, pattern都是字符串
def match(self, s, pattern):
# write code here
if s=='' and pattern=='':
return True
elif s!='' and pattern=='':
return False
elif s=='' and pattern!='':
if len(pattern)>1 and pattern[1]=='*':
return self.match(s, pattern[2:])
else:
return False
else:
if len(pattern)>1 and pattern[1]=='*':
if s[0]!=pattern[0] and pattern[0]!='.':
return self.match(s, pattern[2:])
else: # 如果s[0]与pattern[0]相同，且pattern[1]为*，这个时候有三种情况
return self.match(s, pattern[2:]) or \
self.match(s[1:], pattern[2:]) or \
self.match(s[1:], pattern)
# pattern前两位是空、# pattern前两位与s[0]匹配、# pattern前两位与s中多个匹配
else:
if s[0]==pattern[0] or pattern[0]=='.':
return self.match(s[1:], pattern[1:])
else:
return False
53.表示数值的字符串
- Q：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。
- A：
1
2
3
4
5
6
7
8
9
10
11
12# -*- coding:utf-8 -*-
class Solution:
# s字符串
def isNumeric(self, s):
# write code here
t = "0123456789.+-Ee"
valid = ''
power = ''
for i in t:
if i not in t:
return False
54.字符流中第一个不重复的字符
- Q：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。【如果当前字符流没有存在出现一次的字符，返回#字符。】
- A：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.dict_ = {}
self.list_ = []
# 返回对应char
def FirstAppearingOnce(self):
# write code here
if len(self.list_) == 0:
return '#'
for i in self.list_:
if self.dict_[i] == 1:
return i
return '#'
def Insert(self, char):
# write code here
if char not in self.dict_:
self.dict_[char] = 1
self.list_.append(char)
else:
self.dict_[char] += 1
55.链表中环的入口结点
- Q：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
- A：
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
44
45
46
47# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
if pHead == None or pHead.next == None:
return None
p1 = p2 = pHead # 找相遇结点
while p1!=None and p2.next!=None:
p1 = p1.next
p2 = p2.next.next
if p1 == p2: # 找相遇结点
break
if p2 == None or p2.next == None:
return None
meet = p1 # p1 现在是相遇结点
n = 1 # 记录环里面结点的个数
while p1.next != meet:
n += 1
p1 = p1.next
p1 = p2 = pHead
while n > 0:
p2 = p2.next
n -= 1
while p1 != p2: # p2正好多走了一圈
p1 = p1.next
p2 = p2.next
return p1
'''
dic = {}
tmp = pHead
while tmp:
if tmp not in dic:
dic[tmp] = 1
else:
return tmp
tmp = tmp.next
return None
'''
56.删除链表中重复的结点
- Q：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
- A：
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# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplication(self, pHead):
# write code here
if pHead == None or pHead.next == None:
return pHead
newHead = ListNode(-1) # 设置一个trick
newHead.next = pHead
last = newHead # 当前结点的上一个结点
while pHead and pHead.next:
if pHead.val == pHead.next.val:
tmp = pHead.next.val
while pHead and tmp == pHead.val:
pHead = pHead.next
last.next = pHead
else:
last = pHead
pHead = pHead.next
return newHead.next
57.二叉树的下一个结点
- Q：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
- A：
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# -*- coding:utf-8 -*-
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None # 父节点
class Solution:
def GetNext(self, pNode):
# write code here
if pNode == None:
return None
if pNode.right: # 有右子树，下一个是右子树最左边的结点
pNode = pNode.right
while pNode.left:
pNode = pNode.left
return pNode
elif pNode.next and pNode.next.left == pNode: # 没有右子树，有父节点，是父节点的左子树
return pNode.next
elif pNode.next and pNode.next.right == pNode: # 没有右子树，有父节点，是父节点的右子树
pNode = pNode.next
while pNode.next and pNode.next.right==pNode: # 沿右侧往上找
pNode = pNode.next
if pNode.next:
return pNode.next
else:
return None
58.对称的二叉树
- Q：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
- A：
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# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetrical(self, pRoot):
# write code here
if pRoot == None:
return True
else:
return self.Mirror(pRoot.left, pRoot.right)
def Mirror(self, root1, root2):
# write code here
if root1 == None and root2 == None:
return True
elif root1 != None and root2 != None:
return root1.val == root2.val and \
self.Mirror(root1.left, root2.right) and \
self.Mirror(root1.right, root2.left)
else:
return False
59.按之字形顺序打印二叉树
- Q：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
- A：引用两个队列，分别存储当前行和下一行
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# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def Print(self, pRoot):
# write code here
if pRoot == None:
return []
res, nodes = [], [pRoot]
is_odd = True # 是奇数
while len(nodes):
curStack, nextStack = [], []
for i in nodes:
curStack.append(i.val)
if i.left:
nextStack.append(i.left)
if i.right:
nextStack.append(i.right)
if not is_odd: # 偶数行是逆序
curStack = curStack[::-1]
res.append(curStack)
nodes = nextStack
is_odd = not is_odd # 下一行取反
return res
60.把二叉树打印成多行
- Q：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
- A：引入队列，与22题不同的是用二维列表分层放结果
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# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回二维列表[[1,2],[4,5]]
def Print(self, pRoot):
# write code here
if pRoot == None:
return []
res, nodes = [], [pRoot]
while len(nodes):
cur, next_ = [], []
for i in nodes:
cur.append(i.val)
if i.left:
next_.append(i.left)
if i.right:
next_.append(i.right)
res.append(cur)
nodes = next_
return res
61.序列化二叉树
- Q：请实现两个函数，分别用来序列化和反序列化二叉树
- A：
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# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.index = -1
def Serialize(self, root):
# write code here
if root == None:
return '#,'
return str(root.val) + ',' + \
self.Serialize(root.left) + \
self.Serialize(root.right)
def Deserialize(self, s):
# write code here
self.index += 1
s_list = s.split(',')
if self.index > len(s_list):
return None
if s_list[self.index] != '#':
root = TreeNode(int(s_list[self.index]))
root.left = self.Deserialize(s)
root.right = self.Deserialize(s)
return root
else:
return None
62.二叉搜索树的第k个结点
- Q：给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
- A：中序遍历，输出第k个
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# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回对应节点TreeNode 左 < 根 < 右
def __init__(self):
self.n = 0
def KthNode(self, pRoot, k):
# write code here
if k <= 0:
return None
if pRoot:
node = self.KthNode(pRoot.left, k)
if node: # 必须要对递归的返回值做判断
return node
self.n += 1
if self.n == k:
return pRoot # 访问
node = self.KthNode(pRoot.right, k)
if node:
return node
return None
63.数据流中的中位数
- Q：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
- A：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.digit = []
def Insert(self, num):
# write code here
self.digit.append(num)
for i in range(len(self.digit)-1, 0, -1):
if self.digit[i] < self.digit[i-1]:
self.digit[i], self.digit[i-1] = self.digit[i-1], self.digit[i]
def GetMedian(self, n=None):
# write code here
if len(self.digit) == 0:
return None
if len(self.digit) % 2 == 1:
mid = (len(self.digit)-1) / 2
return self.digit[mid]
else:
right = len(self.digit) / 2
left = right - 1
return (self.digit[left] + self.digit[right]) / 2.0
64.滑动窗口的最大值
- Q：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。
- A：
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# -*- coding:utf-8 -*-
class Solution:
def maxInWindows(self, num, size):
# write code here
if len(num)==0 or size<=0 or len(num) < size:
return []
res = []
DeQueue_index = [] # 双端队列存储下标index, 队头放最大值
for i in range(size): # 4
while len(DeQueue_index) and num[i]>num[DeQueue_index[-1]]:
DeQueue_index.pop() # 新元素k，队尾里面比k小的移出，不可能成为最大值
DeQueue_index.append(i)
for i in range(size, len(num)):
res.append(num[DeQueue_index[0]])
while len(DeQueue_index) and num[i]>num[DeQueue_index[-1]]:
DeQueue_index.pop()
if len(DeQueue_index) and DeQueue_index[0]<=i-size: # 队头过期
DeQueue_index.pop(0) # 窗口范围 [i-size+1, i]
DeQueue_index.append(i)
res.append(num[DeQueue_index[0]])
return res
65.矩阵中的路径
- Q：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
- A：
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# -*- coding:utf-8 -*-
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here 回溯法
if matrix==None or rows<1 or cols<1 or path==None:
return False
visited = [0] * rows * cols
pathLength = 0
for row in range(rows):
for col in range(cols):
if self.hasPathCore(matrix, rows, cols, row, col, path, pathLength, visited):
return True
return False
# 判断：matrix[row, col] == path[pathLength] ？
def hasPathCore(self, matrix, rows, cols, row, col, path, pathLength, visited):
if len(path) == pathLength:
return True
has_path = False
if 0<=row<rows and 0<=col<cols and matrix[row*cols + col]==path[pathLength] and \
not visited[row*cols + col]:
pathLength += 1
visited[row*cols + col] = True
has_path = self.hasPathCore(matrix, rows, cols, row, col-1, path, pathLength, visited) or \
self.hasPathCore(matrix, rows, cols, row-1, col, path, pathLength, visited) or \
self.hasPathCore(matrix, rows, cols, row, col+1, path, pathLength, visited) or \
self.hasPathCore(matrix, rows, cols, row+1, col, path, pathLength, visited)
if not has_path:
pathLength -= 1
visited[row*cols + col] = False
return has_path
66.机器人的运动范围
- Q：地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
- A：
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# -*- coding:utf-8 -*-
class Solution:
def movingCount(self, threshold, rows, cols):
# write code here
visited = [0] * rows * cols
return self.movingCountCore(threshold, rows, cols, 0, 0, visited)
def movingCountCore(self, threshold, rows, cols, row, col, visited):
cnt = 0
if 0<=row<rows and 0<=col<cols and self.get_num(row, col)<=threshold \
and not visited[row*cols+col]:
visited[row*cols+col] = True
cnt = 1 + self.movingCountCore(threshold, rows, cols, row-1, col, visited) + \
self.movingCountCore(threshold, rows, cols, row+1, col, visited) + \
self.movingCountCore(threshold, rows, cols, row, col-1, visited) + \
self.movingCountCore(threshold, rows, cols, row, col+1, visited)
return cnt
def get_num(self, row, col):
tmp = str(row) + str(col)
s = 0
for i in tmp:
s += int(i)
return s
