1.【数组】二维数组中的查找
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
Solution
从左下角或者右上角开始查找，沿着一个方向找，因为这里二维矩阵的特性，导致一个元素的左上区域的所有元素必然比它小，同时其右下区域的所有元素必然比它大，因此可以像贪吃蛇那样，交替沿着横轴和纵轴移动，直到找到target或者抵达数组边界返回false
Code
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
if not len(array):
return False
R,C = len(array),len(array[0])
if not C:
return False
row = R-1
col = 0
while row >= 0 and col < C:
if target > array[row][col]:
col += 1
elif target < array[row][col]:
row -= 1
else:
return True
return False
复杂度分析
假设数组是\(m*n\)的
- 时间复杂度: \(O(m+n)\)
- 空间复杂度：\(O(1)\)
2.【字符串】替换空格
题目描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
Solution
-
对于Python来说，由于没有char的概念，将字符串转换为list，遍历空格
%20即可，然后数组转换为str，用''.join(s) -
对C++，Java等语言则较为麻烦，则需要考虑char的占位问题，因为
%20比
Code
# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
s = list(s)
for i in range(len(s)):
if s[i] == ' ':
s[i] = '%20'
return ''.join(s)
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
3.【链表】从头到尾打印链表
题目描述
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
Solution
- 对于Python，不要使用insert插入list，而是使用切片，在append完之后用
[::-1] - 对于C++，由于没有内部优化的STL容器，因此每次添加用insert插入头部
Code
# -*- 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
res = []
while listNode:
res.append(listNode.val)
listNode = listNode.next
return res[::-1]
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
4.【树】重构二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
Solution
本题采用DFS，递归或者用stack非递归，前序序列的第一个元素为root，在中序序列中找到root的位置，则左边是左子树，右边是右子树，从而不断递归构建
Code
# -*- 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 len(pre) == 0:
return None
if len(pre) == 1:
return TreeNode(pre[0])
else:
flag = TreeNode(pre[0])
flag.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[:tin.index(pre[0])])
flag.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1:] )
return flag
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(log(n))\)
5.【栈、队列】用两个栈实现队列
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
Solution
Queue是FIFO，Stack是FILO，因此要用stack实现queue，需要两个stack，翻转两次即可实现FIFO
Code
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack_push = []
self.stack_pop = []
def push(self, node):
# write code here
self.stack_push.append(node)
def pop(self):
# return xx
if len(self.stack_pop):
return self.stack_pop.pop()
# 鲁棒性检验：stack_push不能为空，否则pop失败
if not len(self.stack_push):
raise IndexError
while len(self.stack_push):
self.stack_pop.append(self.stack_push.pop())
return self.stack_pop.pop()
复杂度分析
- 时间复杂度：
- push,empty：\(O(1)\)
- pop,top：\(O(n)\)
- 空间复杂度：\(O(n)\)
6.【数组】旋转数组的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
Solution
排序的数组只翻转了一次，那么从后往前遍历，一旦前面的数比后面大，就是翻转点
Code
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray) == 0: return 0
rotateArray = rotateArray[::-1]
res = rotateArray[0]
for val in rotateArray[1:]:
if val <= res:
res = val
else:
break
return res
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
7.【动态规划】斐波那契数列
题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
Solution
memo自底向上，空间效率最高。另外有一个trick：
声明数组有两个元素，例如 x = [0,1]
如果n<2，则直接返回 x[n]
否则更新 x[0],x[1] = x[1],x[0]+x[1]
Code
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
x = [0,1]
if n < 2:
return x[n]
i = 1
while i < n:
x[0],x[1] = x[1],x[0]+x[1]
i += 1
return x[1]
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
8.【动态规划】跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
Solution
此题就是斐波那契数列的变形，假设对于第n阶台阶，智能跳1阶或者2阶，那么只能从第n-1阶或者第n-2阶跳上，即有 \(f(n) = f(n-1) + f(n-2)\) 从而变形为斐波那契的题，完全同样的解法，注意初始值(没有0)即可
Code
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
x = [1,2]
if number < 3:
return x[number-1]
for _ in range(2,number):
x[0], x[1] = x[1], x[0]+x[1]
return x[1]
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
9.【动态规划】变态跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
Solution
依然是递归变形，但是要复杂一些，考虑n级台阶，假设前n-1阶台阶的次数已知，那么有 \(f(n) = f(n-1) + f(n-2) + ... + f(1)\) 同理， \(f(n-1) = f(n-2) + f(n-3) + ... + f(1)\) 从而能够推导出通项公式为： \(f(n) = \begin{cases} 1 &(n=0) \\ 1 &(n=1) \\ 2*f(n-1) &(n \geq 2) \end{cases}\)
可以使用上述同样的方法实现，但是有一个更取巧的答案（一行）：
return 1 << number-1
Code
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
return 1 << number-1
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
10.【动态规划】矩形覆盖
题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
Solution
和跳台阶类似，将长度为n的矩形分为n-1和n-2两种情况，从而解法完全相同
Code
# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if not number:
return number
x = [1,2]
if number < 3:
return x[number-1]
for _ in range(2,number):
x[0], x[1] = x[1], x[0]+x[1]
return x[1]
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
11.【位运算】二进制中1的个数
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
Solution
该题在位运算总结里有，这里不再赘述，核心是运用x&(x-1)消去二进制最后一位1
Code
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
# write code here
res = 0
if n < 0:
n = 2**32+n
while n:
res += 1
n = n & (n-1)
return res
复杂度分析
- 时间复杂度：\(O(1)\)，看二进制中1的个数，由于题目限制，最多为32，默认常数
- 空间复杂度：\(O(1)\)
12.【位运算】数值的整数次方
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 (即求pow(x,n))
保证base和exponent不同时为0
Solution
同样在位运算总结 核心是对于exponent进行二分/右移，减少乘积次数
Code
# -*- coding:utf-8 -*-
# x为base，n为exponent
class Solution:
def Power(self, x, n):
if n < 0:
x = 1 / x
n = -n
ans = 1
while n:
if n & 1:
ans *= x
x *= x
n >>= 1
return ans
复杂度分析
- 时间复杂度：\(O(logn)\)
- 空间复杂度：\(O(1)\)
13.【数组】调整数组顺序使奇数位于偶数前面
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
Solution
- 空间换时间，新建2个数组，偶数放一个数组，奇数放一个数组，最后拼接
- 插入排序的思想，遍历一次，两个方向都可以：
- 从前往后遍历，则不断往前插入奇数
- 从后往前遍历，则不断往后插入偶数
Code
# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self, array):
# write code here
odd_array,even_array = [],[]
for val in array:
if val%2 == 0:
odd_array.append(val)
else:
even_array.append(val)
return even_array + odd_array
复杂度分析
- 空间换时间
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
- 内部排序
- 时间复杂度：\(O(n)\)，最差情况，偶数动n次，整体2n
- 空间复杂度：\(O(1)\)
14.【链表】链表中倒数第k个节点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
Solution
双指针，一个指针先向前走k步，另外一个指针再开始从头开始移动，两个指针一起走，知道前面的指针到头，后面的指针即指向倒数第k个节点
Code
# -*- 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
p_k = head
while k:
if not head:
return None
head = head.next
k -= 1
while head:
p_k = p_k.next
head = head.next
return p_k
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
15.【链表】反转链表
题目描述
输入一个链表，反转链表后，输出新链表的表头。
Solution
这题算是链表的基本操作题，有一个trick：自行构建空表头，使开头节点指向它，这样可包含空链表的情况
Code
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
emptyHead = None
prevNode = emptyHead
curNode = pHead
while curNode:
tmp = curNode.next
curNode.next = prevNode
prevNode = curNode
curNode = tmp
return prevNode
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
16.【链表】合并两个排序的链表
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
Solution
链表基础操作，判断哪个小插入新表即可
trick：新建空表头ListNode(-1)，可以减少链表头插入的代码
Code
# -*- 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
head = ListNode(-1)
cur = head
while pHead1 and pHead2:
if pHead1.val < pHead2.val:
tmp = pHead1
pHead1 = pHead1.next
else:
tmp = pHead2
pHead2 = pHead2.next
cur.next = tmp
cur = cur.next
if pHead1:
cur.next = pHead1
else:
cur.next = pHead2
return head.next
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
17.【树】树的子结构
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
Solution
递归判断，非递归要用stack很麻烦，推荐用递归，逻辑较为清晰
Code
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def checkSubtree(self, pRoot1, pRoot2):
if not pRoot2:
return True
if not pRoot1:
return False
if pRoot1.val != pRoot2.val:
return False
return self.checkSubtree(pRoot1.left, pRoot2.left) \
and self.checkSubtree(pRoot1.right, pRoot2.right)
def HasSubtree(self, pRoot1, pRoot2):
# write code here
if not pRoot1 or not pRoot2:
return False
if pRoot1.val == pRoot2.val:
if self.checkSubtree(pRoot1, pRoot2):
return True
return self.HasSubtree(pRoot1.left, pRoot2) \
or self.HasSubtree(pRoot1.right, pRoot2)
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(logn)\)
18.【树】二叉树的镜像
题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。 输入描述:
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
Solution
同样递归操作，将根节点左右互换，并递归子树同样的操作，直到叶节点即可
Code
# -*- 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)
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(logn)\)
19.【数组】顺时针打印矩阵
题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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.
Solution
考验编程功底，双重循环，同时需要：
- flag：记录当前方向，或者在一个循环中写好上下左右4次移动
- cnt：记录元素个数，当
cnt==size，说明打印结束 - margin：转了几圈，在遍历的时候需要根据margin判断一个方向的移动在何处停止
Code
# -*- coding:utf-8 -*-
class Solution:
# matrix类型为二维列表，需要返回列表
def printMatrix(self, matrix):
# write code here
res = []
row = len(matrix)
if not row:
return res
col = len(matrix[0])
if not col:
return res
cnt = 0
size = row*col
margin = 0
i = j = 0
while cnt < size:
# turn right
while j < col-margin:
res.append(matrix[i][j])
cnt += 1
if cnt == size:
return res
j += 1
j -= 1
i += 1
# turn down
while i < row-margin:
res.append(matrix[i][j])
cnt += 1
if cnt == size:
return res
i += 1
i -= 1
j -= 1
# turn left
while j >= margin:
res.append(matrix[i][j])
cnt += 1
if cnt == size:
return res
j -= 1
j += 1
i -= 1
# turn up
margin += 1
while i >= margin:
res.append(matrix[i][j])
cnt += 1
if cnt == size:
return res
i -= 1
i += 1
j += 1
return res
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)，存储结果需要的空间
20.【栈】包含min函数的栈
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
Solution
既然时间复杂度要为\(O(1)\)，那么必然是空间换时间，用两个栈，一个栈放数据，一个栈记录最小值即可
Code
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.st = []
self.st_min = []
def push(self, node):
# write code here
self.st.append(node)
if len(self.st_min)==0 or self.st_min[-1]>node:
self.st_min.append(node)
else:
self.st_min.append(self.st_min[-1])
def pop(self):
# write code here
if len(self.st)==0:
raise IndexError
self.st = self.st[:-1]
self.st_mi
n = self.st_min[:-1]
def top(self):
# write code here
if len(self.st) == 0:
raise IndexError
return self.st[-1]
def min(self):
# write code here
if len(self.st_min) == 0:
raise IndexError
return self.st_min[-1]
复杂度分析
- 时间复杂度：\(O(1)\)
- 空间复杂度：\(O(n)\)
21.【栈】栈的压入、弹出序列
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
Solution
用栈模拟该过程，按照压入顺序压入栈，同时判断是否是弹出序列中的值，如果是，弹出栈顶，同时弹出序列向后走一位，如果遍历结束了，弹出序列不为空，说明序列不符
Code
# -*- coding:utf-8 -*-
class Solution:
def IsPopOrder(self, pushV, popV):
# write code here
st = []
while len(pushV):
st.append(pushV[0])
pushV = pushV[1:]
while len(popV) and st[-1]==popV[0]:
st.pop()
popV = popV[1:]
if len(popV):
return False
return True
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
22.【树】从上往下打印二叉树
题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
Solution
按层次遍历，BFS，非递归用queue实现
Code
# -*- 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
res = []
if not root:
return res
q = [root] # queue
lc = len(q) # layer count
while len(q):
node = q[0]
q = q[1:]
res.append(node.val)
lc -= 1
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if lc == 0:
lc = len(q)
return res
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
23.【树】二叉搜索树的后序遍历序列
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
Solution
BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。
Code
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
size = len(sequence)
if size == 0:
return False
if size == 1:
return True
root = sequence[-1]
sequence = sequence[:-1]
flag = False
split = -1
for i in range(size-1):
if flag and sequence[i]<root:
return False
if sequence[i]>root:
flag=True
split = i
if split in [-1,0]:
return self.VerifySquenceOfBST(sequence)
else:
return self.VerifySquenceOfBST(sequence[:split]) \
and self.VerifySquenceOfBST(sequence[split:])
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
24.【树】二叉树中和为某一值的路径
题目描述
输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
Solution
相当于是前序遍历的时候累加val，到叶节点判断是否等于期望值（其实不到叶节点也很简单，中途遍历每个节点的时候都判断即可），注意添加路径即可。
P.S. 我一开始以为用非递归的Stack好做一些，结果发现很臃肿，完全不如递归的清晰（捂脸），这里还是贴出递归的版本了
Code
# -*- 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 not root:
return []
tmp = []
if not root.left and not root.right and root.val == expectNumber:
return [[root.val]]
else:
left = self.FindPath(root.left,expectNumber-root.val)
right = self.FindPath(root.right,expectNumber-root.val)
for item in left+right:
tmp.append([root.val]+item)
return tmp
复杂度分析
- 时间复杂度：\(O(n)\)，二叉树，则每个节点最多走3次，所以是3N
- 空间复杂度：\(O(logn)\)
25.【链表】复杂链表的复制
题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
Solution
-
字典的方法不详细说了，不过有个trick：用id(node)作为key比直接用node作为key要快一些，也节省空间一些，不过空间的优化可以忽略不计吧。
-
主要说一下In-place的复制方法：
- 第一遍复制node的值，将新的node插入每一个原node之后，即假如原链表是
1->2->3->4->5
经过处理之后成为
1->1->2->2->3->3->4->4->5->5
- 【核心】第二遍复制node的random指针，可以想到，新node的random即为原node的random的next，如此就避免了需要使用dict记录random
- 拆分两个链表，返回新链表
- 第一遍复制node的值，将新的node插入每一个原node之后，即假如原链表是
Code
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
if not pHead:
return None
cur = pHead
# 第一次遍历复制值
while cur:
tmp = RandomListNode(cur.label)
tmp.next = cur.next
cur.next = tmp
cur = tmp.next
# 第二次遍历复制random指针
cur = pHead
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
# 拆分两个链表
cur = pHead
ans = nxt = pHead.next
while cur:
nxt = cur.next
if nxt.next:
cur.next = nxt.next
nxt.next = nxt.next.next
else:
cur.next = None
cur = cur.next
return ans
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
26.【树、链表】二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
Solution
相当于中序遍历，但是修改left和right指针的时候需要注意，左子树需要处理之后获取最右侧的节点，同样右子树要获取最左侧的节点，详细见代码
Code
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def Convert(self, pRootOfTree):
if not pRootOfTree:
return pRootOfTree
if not pRootOfTree.left and not pRootOfTree.right:
return pRootOfTree
# 处理左子树
self.Convert(pRootOfTree.left)
left=pRootOfTree.left
# 连接根与左子树最大结点
if left:
while(left.right):
left=left.right
pRootOfTree.left,left.right=left,pRootOfTree
# 处理右子树
self.Convert(pRootOfTree.right)
right=pRootOfTree.right
# 连接根与右子树最小结点
if right:
while(right.left):
right=right.left
pRootOfTree.right,right.left=right,pRootOfTree
while(pRootOfTree.left):
pRootOfTree=pRootOfTree.left
return pRootOfTree
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(logn)\)
27.【字符串】字符串的排列
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
Solution
python有一行的解决方案：
sorted(list(set(map(''.join,itertools.permutations(list(ss))))))
但是更通用的做法还是用set记录所包含的所有字母，然后做BFS
Code
class Solution:
def Permutation(self, ss):
if not ss:
return []
if len(ss)==1:
return [ss]
else:
result=[]
a=ss[-1]
for ii in self.Permutation(ss[:-1]):
for j in range(len(ii)+1):
result.append(ii[:j]+a+ii[j:])
result=list(set(result))
result.sort()
return result
复杂度分析
- 时间复杂度：\(O(n^2)\)
- 空间复杂度：\(O(logn)\)
28.【数组】数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
Solution
- 通用解法是用dict存储{数字：次数}，当次数＞数组一半长度就返回，否则遍历完返回0
- 高级做法是用Boyer-Moore投票算法，具体参考github
Code
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
n_cnts = {}
line = int(len(numbers)/2)
for n in numbers:
if n in n_cnts:
n_cnts[n] += 1
else:
n_cnts[n] = 1
if n_cnts[n] > line:
return n
return 0
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
29.【堆】最小的K个数
题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
Solution
看排名的代码都是sorted……，那都没意义了，按题目要求应该用最大堆，并维持堆大小为K。
在Python中heapq默认只支持最小堆，那么将数值取负就相当于构建最大堆了，输出的时候再转换回去
Code
import heapq
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
heap = []
if len(tinput)==0 or k==0 or k>len(tinput):
return heap
# 取反数值，用最小堆接口实现最大堆
for x in tinput:
if len(heap) < k:
heapq.heappush(heap, -x)
elif -x > heap[0]:
heapq.heappop(heap)
heapq.heappush(heap, -x)
return [-heapq.heappop(heap) for _ in range(len(heap))][::-1]
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
30.【动态规划】连续子数组的最大和
题目描述
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
Solution
用动态规划的思想来思考，假设t-1时刻的最大和已知，对于t位置的值来说 \(f(t) = max\{V(t), f(t-1)+V(t)\}\) 可以维护一个dp数组，也可以用一个res保存结果，在每次遍历里比较f(t)的值，比res大就赋值，否则不变即可
Code
class Solution:
def FindGreatestSumOfSubArray(self, array):
sum_lis = array[0]
res = sum_lis
for x in array[1:]:
sum_lis = max(x, sum_lis+x)
res = max(res, sum_lis)
return res
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
31.【分治】整数中1出现的次数（从1到n整数中1出现的次数）
题目描述
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
Solution
对每一位数单独进行分析，假设n=12345，取第三位，即i=3，则：
- 用
n//3和n%3分别获取第i位的前缀pre和后缀post，以例子解释，pre代表着有123个100，post代表100的余数为45 - 对第i位的取值分情况讨论:
- 如果
n[i]==0：那么第i位的1就出现了\((pre//10)*10^{i-1}\)次，假设n=12045，则计算得1200 - 如果
n[i]==1：除了要加上等于0时的次数，还要再加上余数+1次，假设n=12145，则计算得1246 - 如果
n[i]>=2：那么第i位的1就出现了\(((pre//10)+1)*10^{i-1}\)次（其实就是0和1加起来），假设n=12345，则计算得1300
- 如果
最后，根据过程写出对应的循环程序即可
trick:由于0和2以上很相似，不用加上余数，0比2以上的情况少\(10^{i-1}\)次，因此可以用(pre+8)//10来包括两种情况
Code
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
base = 1
digit = 0
pre = post = 0
cnt = 0
while base <= n:
pre = n // base
post = n % base
digit = pre % 10
cnt += (pre+8)/10 * base
if digit == 1:
cnt += post + 1
base *= 10
return cnt
复杂度分析
- 时间复杂度：\(O(log_{10}(n))\)
- 空间复杂度：\(O(1)\)
32.【排序】把数组排成最小的数
题目描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
Solution
这题的核心是用自定义排序，将str数组按照特定规则排序过后直接拼接输出就可以得到答案，排序需要比较a+b和b+a的大小，因为要组成最小的数，就是看拼接a和b后谁更小，比如3和32，拼接之后就是332和323，是323更小，所以32要在3前面，即32比3“小”。
Code
代码有一些trick：
list(map(str, ...))cmp+lambda"".join()lstrip()
class Solution:
def PrintMinNumber(self, numbers):
# write code here
if not numbers:
return ""
numbers = list(map(str, numbers))
numbers.sort(cmp=lambda x, y: cmp(x + y, y + x))
return "".join(numbers).lstrip('0') or'0'
复杂度分析
- 时间复杂度：\(O(nlogn)\)，排序
- 空间复杂度：\(O(n)\)
33.【指针】丑数
题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
Solution
用一个数组存放已知的丑数数组，然后分别用3个指针指向上一次只乘以2、只乘以3和只乘以5的位置，因为丑数只包含因子2、3、5，所以在对应位置乘以2，3，5，只要比数组最后一位大（已排序），则是新的元素，同时比较2，3，5的新元素，取最小值，就是下一位丑数
Code
class Solution:
def GetUglyNumber_Solution(self, index):
# write code here
if index == 0:
return 0
arr = [1]
p2 = p3 = p5 = 0
while index > len(arr):
val2 = arr[p2] * 2
while val2 <= arr[-1]:
p2 += 1
val2 = arr[p2] * 2
val3 = arr[p3] * 3
while val3 <= arr[-1]:
p3 += 1
val3 = arr[p3] * 3
val5 = arr[p5] * 5
while val5 <= arr[-1]:
p5 += 1
val5 = arr[p5] * 5
new_val = min(val2, val3, val5)
arr.append(new_val)
return arr[index-1]
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
34.【hash表】第一个只出现一次的字符
题目描述
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
Solution
因为要获取第一个的位置，所以：
- 要么字符串遍历2遍
- 要么用hash存放次数以及第一次的位置
前者时间换空间，后者空间换时间。通常采用后者，下面的代码也是如此
Code
class Solution:
def FirstNotRepeatingChar(self, s):
# write code here
cnts = {}
ans = -1
for i in range(len(s)):
if s[i] in cnts:
cnts[s[i]] = (cnts[s[i]][0], False)
else:
cnts[s[i]] = (i, True)
for key in cnts:
val = cnts[key]
if not val[1]:
continue
else:
if ans == -1:
ans = val[0]
else:
ans = min(ans, val[0])
return ans
还有个1行的版本
class Solution:
def FirstNotRepeatingChar(self, s):
return s.index(list(filter(lambda c:s.count(c)==1,s))[0]) if s else -1
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
35.【归并排序】数组中的逆序对
题目描述
题目描述 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007 输入描述: 题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
示例1
输入
1,2,3,4,5,6,7,0
输出
7
Solution
用归并排序，并在排序过程中计数逆序对的个数，如此可以将时间复杂度从\(O(n^2)\)降低到\(O(nlogn)\)
Code
Python2没有nonlocal因此用global进行全局计数
count = 0
class Solution:
def InversePairs(self, data):
global count
def MergeSort(lists):
global count
if len(lists) <= 1:
return lists
num = int( len(lists)/2 )
left = MergeSort(lists[:num])
right = MergeSort(lists[num:])
r, l=0, 0
result=[]
while l<len(left) and r<len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
count += len(left)-l
result += right[r:]
result += left[l:]
return result
MergeSort(data)
return count%1000000007
复杂度分析
- 时间复杂度：\(O(nlogn)\)
- 空间复杂度：\(O(n)\)
36.【双指针】两个链表的第一个公共结点
题目描述
输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
Solution
假设公共部分的节点有n个，链表A的节点有a个，链表B的节点有b个，那么用同向双指针，分别从链表A->链表B以及链表B->链表A的路径走，那么必然在第二趟的时候在第一个公共节点处碰头。
Code
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
p1,p2=pHead1,pHead2
while p1!=p2:
p1 = p1.next if p1 else pHead2
p2 = p2.next if p2 else pHead1
return p1
复杂度分析
- 时间复杂度：\(O(n+a+b)\)
- 空间复杂度：\(O(1)\)
37.【二分查找】数字在排序数组中出现的次数
题目描述
统计一个数字在排序数组中出现的次数。
Solution
二分查找，分别查找起点和终点，和LeetCode 34题相同，可以参考本人对该题的总结
Code
python的内置函数，二分查找可以查看上面LeetCode代码
class Solution:
def GetNumberOfK(self, data, k):
return data.count(k)
复杂度分析
- 时间复杂度：\(O(logn)\)
- 空间复杂度：\(O(logn)\)，递归开销
38.【递归】二叉树的深度
题目描述
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
Solution
递归，求左右子树的深度，取max，再+1
Code
class Solution:
def TreeDepth(self, pRoot):
if not pRoot:
return 0
return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))+1
复杂度分析
- 时间复杂度：\(O(logn)\)
- 空间复杂度：\(O(logn)\)
39.【递归】平衡二叉树
题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
Solution
和上题一样，递归求左右子树高度，如果高度差超过1，则不平衡。 注意递归函数要单独写，因为返回int值
Code
class Solution:
def Tree_Depth(self, pRoot):
if not pRoot:
return 0
else:
return max(self.Tree_Depth(pRoot.left),\
self.Tree_Depth(pRoot.right))+1
def IsBalanced_Solution(self, pRoot):
if not pRoot:
return True
left_depth = self.Tree_Depth(pRoot.left)
right_depth = self.Tree_Depth(pRoot.right)
if abs(left_depth - right_depth) > 1:
return False
return True
复杂度分析
- 时间复杂度：\(O(logn)\)
- 空间复杂度：\(O(logn)\)
40.【hash、位运算】数组中只出现一次的数字
题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
Solution
-
针对题目，因为重复的次数只出现2次，因此可以用set（否则用map记录次数），如果元素在set中，则删除，这样遍历完数组后set中只剩下2个单独的数字。
-
位运算：异或，因为只有2次的重复数字异或之后为0，异或的结果就是单独的2个数字异或的结果。我们就取第一个1所在的位数，假设是第3位，接着把原数组分成两组，分组标准是第3位是否为1。如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。
Code
set
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
filter_set = set()
for x in array:
if x not in filter_set:
filter_set.add(x)
else:
filter_set.remove(x)
return list(filter_set)
位运算
class Solution:
def FindNumsAppearOnce(self, array):
if not array:
return []
# 对array中的数字进行异或运算
tmp = 0
for i in array:
tmp ^= i
# 获取tmp中最低位1的位置
idx = 0
while (tmp & 1) == 0:
tmp >>= 1
idx += 1
a = b = 0
for i in array:
if self.isBit(i, idx):
a ^= i
else:
b ^= i
return [a, b]
def isBit(self, num, idx):
"""
判断num的二进制从低到高idx位是不是1
:param num: 数字
:param idx: 二进制从低到高位置
:return: num的idx位是否为1
"""
num = num >> idx
return num & 1
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
41.【双指针】和为S的连续正数序列
题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
Solution
- 根据数学公式，计算得到
- 双指针
Code
数学计算
class Solution:
def FindContinuousSequence(self, tsum):
res=[]
for i in range(1,tsum//2+1):
sumRes=i
for j in range(i+1,tsum//2+2):
sumRes+=j
if sumRes==tsum:
res.append(list(range(i,j+1)))
break
elif sumRes>tsum:
break
return res
双指针
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
//存放结果
ArrayList<ArrayList<Integer> > result = new ArrayList<>();
//两个起点，相当于动态窗口的两边，根据其窗口内的值的和来确定窗口的位置和大小
int plow = 1,phigh = 2;
while(phigh > plow){
//由于是连续的，差为1的一个序列，那么求和公式是(a0+an)*n/2
int cur = (phigh + plow) * (phigh - plow + 1) / 2;
//相等，那么就将窗口范围的所有数添加进结果集
if(cur == sum){
ArrayList<Integer> list = new ArrayList<>();
for(int i=plow;i<=phigh;i++){
list.add(i);
}
result.add(list);
plow++;
//如果当前窗口内的值之和小于sum，那么右边窗口右移一下
}else if(cur < sum){
phigh++;
}else{
//如果当前窗口内的值之和大于sum，那么左边窗口右移一下
plow++;
}
}
return result;
}
}
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
42.【双指针】和为S的两个数
题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
Solution
相向双指针，分别从头和尾向中间移动，如果和大于S，则right减1，如果和小于S，则left加1，如果和等于S，直接返回，因为第一次等于S的乘积必然是最小的（left和right差值最大）
Code
class Solution:
def FindNumbersWithSum(self, arr, target):
left,right = 0,len(arr)-1
res = []
while left < right:
s = arr[left] + arr[right]
if s == target:
res = [arr[left], arr[right]]
break
elif s > target:
right -= 1
else:
left += 1
return res
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
43.【指针】左旋转字符串
题目描述
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
Solution
剑指offer书上写的方法是翻转2次字符串：
- 翻转全部字符串
- 翻转前len(s)-n个字符串
- 翻转后面n个字符串 用python的话，切片就好
Code
class Solution:
def LeftRotateString(self, s, n):
if not s:
return s
n = n % len(s)
return s[n:] + s[:n]
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
44.【数组，字符串】翻转单词顺序列
题目描述
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
Solution
将s按空格切分成数组，然后用空格倒序拼接数组即可
Code
class Solution:
def ReverseSentence(self, s):
arr = s.split(' ')[::-1]
s = ' '.join(arr)
return s
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
45.【hash表】扑克牌顺子
题目描述
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。
Solution
需要3个变量：hash表map，2个int（max、min），map记录出现次数，如果非0值出现2次，则不能组成顺子；max和min分别记录非0的最大值和最小值，如果max和min的差值>4，则返回True，否则返回False。
另外，开头要判断数组长度，如果不等于5返回False
Code
class Solution:
def IsContinuous(self, numbers):
if len(numbers) != 5:
return False
m = {}
min_card = -1
max_card = -1
for x in numbers:
m[x] = 1 if x not in m else m[x]+1
if x and m[x] > 1:
return False
if min_card == -1 and x:
min_card = x
elif x:
min_card = min(min_card, x)
if max_card == -1 and x:
max_card = x
elif x:
max_card = max(max_card, x)
if max_card - min_card > 4:
return False
else:
return True
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
46.【递归、链表】孩子们的游戏(圆圈中最后剩下的数)
题目描述
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
如果没有小朋友，请返回-1
Solution
该问题属于约瑟夫环问题，按照wiki的说法：
比较简单的做法是用循环单链表模拟整个过程，时间复杂度是O(n*m)。如果只是想求得最后剩下的人，则可以用数学推导的方式得出公式。
显然，该题只要最后的人，所以用数学推导：
递推公式:
令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]。
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
Code
class Solution:
def LastRemaining_Solution(self, n, m):
# Python的max recursion deep限制，默认1000，按照用例调整可以AC
sys.setrecursionlimit(5000)
if n == 0:
return -1
if n == 1:
return 0
else:
return (self.LastRemaining_Solution(n-1, m)+m)%n
如果递归有空间限制，那依然只能用链表模拟
class Node:
def __init__(self, val):
self.val = val
self.next = None
class Solution:
def LastRemaining_Solution(self, n, m):
if n == 0:
return -1
head = prev = Node(0)
cur = None
for i in range(1,n):
cur = Node(i)
prev.next = cur
prev = cur
prev.next = head
while head.next:
for _ in range(m-1):
prev = head
head = head.next
if head.next == prev:
prev.next = None
head = prev
else:
prev.next = head.next
head = head.next
return head.val
复杂度分析
- 时间复杂度：\(O(logn)\)
- 空间复杂度：\(O(logn)\)
47.【递归】求1+2+3+…+n
题目描述
求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
Solution
当题目要求不能用条件判断关键字时，通常想到用递归。
该题还要用到逻辑短路的技巧，在python中，逻辑短路是a and b，如果a是True则返回a，否则返回b；而在c++中因为赋值语句也有左值（返回ans本身），因此可以直接赋值。
两种语言的具体区别见代码
Code
python
class Solution:
def Sum_Solution(self, n):
n += (n and self.Sum_Solution(n-1))
return n
c++
class Solution {
public:
int Sum_Solution(int n) {
int ans = n;
ans && (ans += Sum_Solution(n-1));
return ans;
}
};
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
48.【位运算】不用加减乘除做加法
题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
Solution
不能用四则运算，那明显用位运算：
首先看十进制是如何做的： 5+7=12，三步走
第一步：相加各位的值，不算进位，得到2。
第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。
第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。
同样我们可以用三步走的方式计算二进制值相加： 5-101，7-111 第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。
第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。
第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。
继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。
Code
class Solution:
def Add(self, num1, num2):
while num2:
tmp = (num1^num2)
num2 = (num1&num2)<<1
num1 = tmp
return num1
复杂度分析
- 时间复杂度：\(O(nlogn)\)
- 空间复杂度：\(O(n)\)
49.【字符串】把字符串转换成整数
题目描述
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
Solution
没太多说的吧，按照要求循环处理即可，需要注意的是python中不好直接将char转换为int（不用built-in的话），因此要用map来做映射
Code
class Solution:
def StrToInt(self, s):
if not s:
return 0
is_neg = False
if s[0] == '-':
is_neg = True
s = s[1:]
elif s[0] == '+':
s = s[1:]
ans = 0
m = {str(x):x for x in range(10)}
for c in s:
if c in m:
ans = ans*10 + m[c]
else:
ans = 0
break
return ans if not is_neg else -ans
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
50.【hash表】数组中重复的数字
题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
Solution
简单的set应用，也没什么说的吧
Code
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
dup_set = set()
for x in numbers:
if x in dup_set:
duplication[0] = x
return True
else:
dup_set.add(x)
return False
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
51.【动态规划】构建乘积数组
题目描述
给定一个数组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]。不能使用除法。（注意：规定
B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）
Solution
最关键的思想是存储已经计算过的中间变量，就是DP的思想。中间变量分为2部分，一部分计算位置i之前的乘积（对应下图下三角部分），另一部分计算位置i之后的乘积（对应下图上三角部分），所以要遍历2次。
Code
class Solution:
def multiply(self, A):
a = b = 1
B = [1 for _ in range(len(A))]
for i in range(1, len(A)):
a *= A[i-1]
B[i] = a
for i in range(len(A)-2, -1, -1):
b *= A[i+1]
B[i] *= b
return B
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
52.【回溯】正则表达式匹配
题目描述
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，
而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。
例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
Solution
字符串匹配时比较复杂的问题（个人觉得），目前来说见过的题就是2种做法：回溯和DP。这个题用回溯的思想来做。主要麻烦在处理*的时候，因为不知道重复了几次，所以分别尝试不同的分支，一旦成功返回True
Code
class Solution:
# s, pattern都是字符串
def match(self, s, pattern):
# 如果s与pattern都为空，则True
if len(s) == 0 and len(pattern) == 0:
return True
# 如果s不为空，而pattern为空，则False
elif len(s) != 0 and len(pattern) == 0:
return False
# 如果s为空，而pattern不为空，则需要判断
elif len(s) == 0 and len(pattern) != 0:
# pattern中的第二个字符为*，则pattern后移两位继续比较
if len(pattern) > 1 and pattern[1] == '*':
return self.match(s, pattern[2:])
else:
return False
# s与pattern都不为空的情况
else:
# pattern的第二个字符为*的情况
if len(pattern) > 1 and pattern[1] == '*':
# s与pattern的第一个元素不同，则s不变，pattern后移两位，相当于pattern前两位当成空
if s[0] != pattern[0] and pattern[0] != '.':
return self.match(s, pattern[2:])
else:
# 如果s[0]与pattern[0]相同，且pattern[1]为*，这个时候有三种情况
# pattern后移2个，s不变；相当于把pattern前两位当成空，匹配后面的
# pattern后移2个，s后移1个；相当于pattern前两位与s[0]匹配
# pattern不变，s后移1个；相当于pattern前两位，与s中的多位进行匹配，因为*可以匹配多位
return self.match(s, pattern[2:]) or self.match(s[1:], pattern[2:]) or self.match(s[1:], pattern)
# pattern第二个字符不为*的情况
else:
if s[0] == pattern[0] or pattern[0] == '.':
return self.match(s[1:], pattern[1:])
else:
return False
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
53.【字符串】表示数组的字符串
题目描述
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。
Solution
正常做的话，就是用各种条件分支判断+|-符号、.小数点、e[+-]科学计数法等。
更为实践的做法是用正则，如下方代码
Code
import re
class Solution:
# s字符串
def isNumeric(self, s):
return re.match('^[+-]?[0-9]*(\\.[0-9]*)?([eE][+-]?[0-9]+)?$', s)
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
54.【Hash表】字符流中第一个不重复的字符
题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”
Solution
用map计数，并记录起始位置，需要返回的时候返回1次的最小起始位置对应的char
因为输入的是字符流，所以class内有2个函数，对应的map和一些变量也定义为类成员变量
Code
class Solution:
# 返回对应char
def __init__(self):
self.s = ''
self.m = {}
self.p = 0
self.fsc = ''
def FirstAppearingOnce(self):
while self.p < len(self.s):
c = self.s[self.p]
if c not in self.m:
self.m[c] = self.p
if self.fsc in ('#', ''):
self.fsc = c
else:
self.m[c] = -1
min_pos = len(self.s)
if self.fsc == c:
self.fsc = '#'
for key in self.m:
if self.m[key] != -1 and self.m[key] < min_pos:
min_pos = self.m[key]
self.fsc = key
self.p += 1
return self.fsc
def Insert(self, c):
# write code here
self.s += c
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
55.【链表、双指针】链表中环的入口结点
题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
Solution
设置快慢指针，都从链表头出发，快指针每次走两步，慢指针一次走一步，假如有环，一定相遇于环中某点(结论1)。接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一步，最终相遇于环入口(结论2)。以下是两个结论证明：
两个结论： 1、设置快慢指针，假如有环，他们最后一定相遇。 2、两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇与环入口。
Code
class Solution:
def EntryNodeOfLoop(self, pHead):
fast = pHead
slow = pHead
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
break
if not fast or not fast.next:
return None
circle = pHead
while circle != fast:
fast = fast.next
circle = circle.next
return circle
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
56.【链表】删除链表中重复的结点
题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
Solution
链表操作，没太多说的，考验编程基本功，注意可以使用自建表头ListNode(-1)减少一些逻辑判断
Code
class Solution:
def deleteDuplication(self, pHead):
cur = pHead
prev = ListNode(-1)
prev.next = pHead
pHead = prev
del_flag = False
while cur and cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
del_flag = True
else:
if del_flag:
prev.next = cur.next
del_flag = False
else:
prev = cur
cur = cur.next
if del_flag:
prev.next = None
return pHead.next
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
57.【树】二叉树的下一个结点
题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
Solution
分为两种情况：
- 节点有右子树，那么中序遍历的下一个节点必然在右子树的最左边
- 节点没有右子树，则不断查找父节点，直到父节点为空或者该节点不在对应父节点的右子树下
Code
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
def GetNext(self, pNode):
target = pNode.right
if target:
while target.left:
target = target.left
return target
else:
target = pNode
while target.next and target.next.right == target:
target = target.next
return target.next
复杂度分析
- 时间复杂度：\(O(logn)\)
- 空间复杂度：\(O(1)\)
58.【树、递归】对称的二叉树
题目描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
Solution
递归判断：
- 左子树的left == 右子树的right？
- 左子树的right == 右子树的left？
Code
class Solution:
def isSymmetricalCore(self, root1, root2):
if not root1 and not root2:
return True
if not root1 or not root2:
return False
if root1.val != root2.val:
return False
return self.isSymmetricalCore(root1.left, root2.right) \
and self.isSymmetricalCore(root1.right, root2.left)
def isSymmetrical(self, pRoot):
if not pRoot:
return True
return self.isSymmetricalCore(pRoot.left, pRoot.right)
复杂度分析
- 时间复杂度：\(O(logn)\)
- 空间复杂度：\(O(logn)\)
59.【树、栈】按之字形顺序打印二叉树
题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
Solution
这种反复更改顺序的题，通常做法是用两个stack。不过python有切片[::-1]，所以也可以用标记flag将节点进行整体翻转
Code
class Solution:
def Print(self, pRoot):
if not pRoot:
return []
nodeStack=[pRoot]
result=[]
while nodeStack:
res = []
nextStack=[]
for i in nodeStack:
res.append(i.val)
if i.left:
nextStack.append(i.left)
if i.right:
nextStack.append(i.right)
nodeStack=nextStack
result.append(res)
returnResult=[]
for i,v in enumerate(result):
if i%2==0:
returnResult.append(v)
else:
returnResult.append(v[::-1])
return returnResult
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
60.【BFS，队列】把二叉树打印成多行
题目描述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
Solution
树的按层遍历，BFS，用队列实现
Code
class Solution:
# 返回二维列表[[1,2],[4,5]]
def Print(self, pRoot):
if not pRoot:
return []
q = [pRoot]
res = [[pRoot.val]]
vec = []
while q:
node = q[0]
q = q[1:]
if node.left:
vec.append(node.left)
if node.right:
vec.append(node.right)
if len(q) == 0 and vec:
res.append([x.val for x in vec])
q = vec
vec = []
return res
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
61.【递归、树】序列化二叉树
题目描述
请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
例如，我们可以把一个只有根节点为1的二叉树序列化为”1,”，然后通过自己的函数来解析回这个二叉树
Solution
树的问题，基本递归都能解决，该题也如此。但是反序列化的时候较为麻烦，用flag计数和标记位置，具体处理见代码
Code
class Solution:
def __init__(self):
self.flag = -1
def Serialize(self, root):
if not root:
return '#,'
return str(root.val)+','+self.Serialize(root.left)+self.Serialize(root.right)
def Deserialize(self, s):
self.flag += 1
l = s.split(',')
if self.flag >= len(s):
return None
root = None
if l[self.flag] != '#':
root = TreeNode(int(l[self.flag]))
root.left = self.Deserialize(s)
root.right = self.Deserialize(s)
return root
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)，主要是递归函数占用的空间。如果树的结构接近线性了，那就是\(O(n)\)，平均应当是\(O(log(n))\)
62.【递归】二叉搜索树的第k个结点
题目描述
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
Solution
树+递归，按照中序遍历的方法做，每次到根节点计数+1，当计数==k时，返回节点
Code
class Solution:
# 返回对应节点TreeNode
def __init__(self):
self.cnt = 0
def KthNode(self, pRoot, k):
if not pRoot:
return None
ans = self.KthNode(pRoot.left, k)
if ans:
return ans
self.cnt += 1
if self.cnt == k:
return pRoot
return self.KthNode(pRoot.right, k)
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
63.【堆】数据流中的中位数
题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
Solution
利用最大堆和最小堆实现，详细过程和更多思路可以看LeetCode刷题总结
Code
class Solution:
def __init__(self):
self.minNums=[]
self.maxNums=[]
def maxHeapInsert(self,num):
self.maxNums.append(num)
lens = len(self.maxNums)
i = lens - 1
while i > 0:
if self.maxNums[i] > self.maxNums[(i - 1) / 2]:
t = self.maxNums[(i - 1) / 2]
self.maxNums[(i - 1) / 2] = self.maxNums[i]
self.maxNums[i] = t
i = (i - 1) / 2
else:
break
def maxHeapPop(self):
t = self.maxNums[0]
self.maxNums[0] = self.maxNums[-1]
self.maxNums.pop()
lens = len(self.maxNums)
i = 0
while 2 * i + 1 < lens:
nexti = 2 * i + 1
if (nexti + 1 < lens) and self.maxNums[nexti + 1] > self.maxNums[nexti]:
nexti += 1
if self.maxNums[nexti] > self.maxNums[i]:
tmp = self.maxNums[i]
self.maxNums[i] = self.maxNums[nexti]
self.maxNums[nexti] = tmp
i = nexti
else:
break
return t
def minHeapInsert(self,num):
self.minNums.append(num)
lens = len(self.minNums)
i = lens - 1
while i > 0:
if self.minNums[i] < self.minNums[(i - 1) / 2]:
t = self.minNums[(i - 1) / 2]
self.minNums[(i - 1) / 2] = self.minNums[i]
self.minNums[i] = t
i = (i - 1) / 2
else:
break
def minHeapPop(self):
t = self.minNums[0]
self.minNums[0] = self.minNums[-1]
self.minNums.pop()
lens = len(self.minNums)
i = 0
while 2 * i + 1 < lens:
nexti = 2 * i + 1
if (nexti + 1 < lens) and self.minNums[nexti + 1] < self.minNums[nexti]:
nexti += 1
if self.minNums[nexti] < self.minNums[i]:
tmp = self.minNums[i]
self.minNums[i] = self.minNums[nexti]
self.minNums[nexti] = tmp
i = nexti
else:
break
return t
def Insert(self, num):
if (len(self.minNums)+len(self.maxNums))&1==0:
if len(self.maxNums)>0 and num < self.maxNums[0]:
self.maxHeapInsert(num)
num = self.maxHeapPop()
self.minHeapInsert(num)
else:
if len(self.minNums)>0 and num > self.minNums[0]:
self.minHeapInsert(num)
num = self.minHeapPop()
self.maxHeapInsert(num)
def GetMedian(self,n=None):
allLen = len(self.minNums) + len(self.maxNums)
if allLen ==0:
return -1
if allLen &1==1:
return self.minNums[0]
else:
return (self.maxNums[0] + self.minNums[0]+0.0)/2
复杂度分析
- 时间复杂度：\(O(1)\)
- 空间复杂度：\(O(n)\)
64.【双端队列】滑动窗口的最大值
题目描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。
Solution
这题是比较经典的题目了，用双端队列实现，LeetCode也有对应的题目，总结在此
Code
class Solution:
def maxInWindows(self, num, size):
queue,res,i = [],[],0
while size>0 and i<len(num):
if len(queue)>0 and i-size+1 > queue[0]:
queue.pop(0)
while len(queue)>0 and num[queue[-1]]<num[i]:
queue.pop()
queue.append(i)
if i>=size-1:
res.append(num[queue[0]])
i += 1
return res
复杂度分析
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
65.【回溯】矩阵中的路径
题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如 \(\begin{bmatrix} a & b & c & e\\ s & f & c & s\\ a & d & e & e \end{bmatrix}\) 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
Solution
因为要尝试不同的分支，显然用回溯（Backtracking）
Code
trick：走过的地方将matrix[i][j]置空为’‘，尝试完之后再变回原来的值（这是in-place改动了，如果有不让改动矩阵的要求，就需要自己创建一个矩阵记录状态）
class Solution:
def hasPath(self, matrix, rows, cols, path):
if not matrix:
return False
if not path:
return True
x = [list(matrix[cols*i:cols*i+cols]) for i in range(rows)]
for i in range(rows):
for j in range(cols):
if self.exist_helper(x, i, j, path):
return True
return False
def exist_helper(self, matrix, i, j, p):
if matrix[i][j] == p[0]:
if not p[1:]:
return True
matrix[i][j] = ''
if i > 0 and self.exist_helper(matrix, i-1, j, p[1:]):
return True
if i < len(matrix)-1 and self.exist_helper(matrix, i+1, j ,p[1:]):
return True
if j > 0 and self.exist_helper(matrix, i, j-1, p[1:]):
return True
if j < len(matrix[0])-1 and self.exist_helper(matrix, i, j+1, p[1:]):
return True
matrix[i][j] = p[0]
return False
else:
return False
复杂度分析
- 时间复杂度：\(O(n*4^p)\)，忽略边界的情况，每次尝试有4个方向，p长度，以矩阵的每个元素作为起点进行回溯
- 空间复杂度：\(O(n)\)，最长递归空间为p，而p不可能大于n
66.【回溯】机器人的运动范围
题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
Solution
可以用染色法的思想，或者数组存储状态+回溯，其实思想是类似的。
另外如果染色法可以，并查集是否可以呢？有时间可以尝试下
Code
class Solution:
def movingCount(self, threshold, rows, cols):
self.row, self.col = rows, cols
self.dict = set()
self.search(threshold, 0, 0)
return len(self.dict)
def judge(self, threshold, i, j):
return sum(map(int, list(str(i)))) + sum(map(int, list(str(j)))) <= threshold
def search(self, threshold, i, j):
if not self.judge(threshold, i, j) or (i, j) in self.dict:
return
self.dict.add((i, j))
if i != self.row - 1:
self.search(threshold, i + 1, j)
if j != self.col - 1:
self.search(threshold, i, j + 1)
复杂度分析
- 时间复杂度：\(O(n)\)，因为有存储状态，最多所有元素尝试一遍
- 空间复杂度：\(O(n)\)
67.【动态规划】剪绳子
题目描述
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
Solution
-
动态规划DP：从1到n，不断计算并存储长度为i时的最大成绩，计算过程是从1到n-1遍历所有数组与i的成绩，即
dp[i]*dp[n-i]，然后取最大值 -
数学总结规律：
题目分析： 先举几个例子，可以看出规律来。 4 ： 22 5 ： 23 6 ： 33 7 ： 223 或者43 8 ： 233 9 ： 333 10：2233 或者433 11：2333 12：3333 13：22333 或者4333
下面是分析： 首先判断k[0]到k[m]可能有哪些数字，实际上只可能是2或者3。 当然也可能有4，但是4=22，我们就简单些不考虑了。 5<23,6<33,比6更大的数字我们就更不用考虑了，肯定要继续分。 其次看2和3的数量，2的数量肯定小于3个，为什么呢？因为222<33，那么题目就简单了。 直接用n除以3，根据得到的余数判断是一个2还是两个2还是没有2就行了。 由于题目规定m>1，所以2只能是11，3只能是21，这两个特殊情况直接返回就行了。 乘方运算的复杂度为：O(log n)，用动态规划来做会耗时比较多。
Code
class Solution:
def cutRope(self, number):
if number == 0:
return 0
elif number in (1,2):
return 1
elif number == 3:
return 2
return self.subFunction(number)
def subFunction(self, number):
tempL = [0]*(number+1)
tempL[0] = 1
maxV = 0
if tempL[number] != 0:
return tempL[number]
for i in range(1, number+1):
ans = i*self.subFunction(number-i)
if ans>maxV:
maxV = ans
tempL[number] = maxV
return maxV
复杂度分析
- 时间复杂度：\(O(n^2)\)
- 空间复杂度：\(O(n)\)
