计算阶乘
list_ = [1]
for i in range(1, n): list_.append(list_[i-1] * (i+1))
三项和为0==a+b+c
def threeSum(nums):
res = []
for i in range(0, len(nums)):
a = nums[i]
start, end = 0, len(nums)-1
while start < end and start >= 0 and end < len(nums) and start < i and i < end:
sum_ = a + nums[start] + nums[end]
if sum_ == 0:
res.append([a, nums[start], nums[end])
start += 1
end -= 1
elif sum > 0:
end -= 1
elif sum < 0:
start += 1
return res
二分查找：
def binarySearch(nums, target):
left, right = 0, len(nums)-1
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid+1
return left
def reverse(head):
if not head:
return head
p = head
pre = None
while p:
#1 3 4 ---- 4 3 1
cur = p
p.next = pre
p = cur.next
pre = cur
快排：
def partition(nums, left, right):
pivot = nums[right]
i, j = left, right
while i < j:
while i < j and nums[i] <= pivot:
i += 1
if i < j:
nums[i], nums[j] = nums[j], nums[i]
while i < j and nums[j] >= pivot:
j -= 1
if i < j:
nums[i], nums[j] = nums[j], nums[i]
return i
def quickSort(nums, left, right):
if left < right:
mid = partition(nums, left, right)
quickSort(nums, left, mid - 1)
quickSort(nums, mid + 1, right)
def QuickSort(nums):
quickSort(nums, 0, len(nums))
- LRU Cache
- 问题：设计一个LRU缓存Least Recently Used
- 思路：用一个hash表来保存已经存在的key, 然后用另外一个线性容器来存储其key-value值, 我们可以选择链表list, 因为需要调整结点的位置, 而链表可以在O(1)时间移动结点的位置, 数组则需要O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25import collections
class LRUCache(object):
def __init__(self, capacity):
self.dict = collections.OrderedDict()
self.length = 0
self.capacity = capacity
def get(self, key):
if key in self.dict:
val = self.dict[key]
del self.dict[key]
self.dict[key] = val
return val
return -1
def put(self, key, val):
if key in self.dict: # 若存在
del self.dict[key]
self.dict[key] = val
return
if self.length == self.capacity:
self.dict.popitem(last=False)
self.dict[key] = val
self.length -= 1
else:
self.dict[key] = val
self.length += 1
Array
Find the Duplicate Number
- 问题：找出重复的数字，O(1)空间，不能排序
- 思路：
- 抽象为链表的cycle问题
1
2
3
4
5
6
7
8
9
10
11
12def findDuplicate(self, nums):
head = 0
slow = nums[head]
fast = nums[nums[head]]
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
fast = head
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return fast
- 抽象为链表的cycle问题
Shortest Unsorted Continuous Subarray
- 问题：找到最小的只需要排序的连续子串长度，使其sort可以使得整个字符串有序
- 思路：
- 法一：排序比较，不好O(nlog(n))时间复杂度
- 法二：
- 从左向右扫描，更新max，找到最右边的一个小于max的数，记录下标end
- 从右向左扫描，更新min，找到最左边的一个大于min的数，记录下标start
- 返回end-start+1
- 如果已经是ascending则返回0
- Move Zeroes
- 问题：nums=[0,1,0]，修改为[1,0,0],inplace
- 思路：
- 法一：
- length = len(nums)
- nums[:] = [t for t in nums if t != 0]
- nums.extend([0]*(length - len(nums)))
- 法一：
- Product of Array Except Self
- 问题：除自我之外的数组元素乘积，输入[1,2,3,4]，输出[24,12,8,6];without division and in O(n).
- 思路：
- 从左到右一遍，再从右到左的乘积，两者相乘
- res = [1]*len(nums)
- for i in range(1, len(nums)):
- res[i] = res[i-1]*nums[i-1] # 累乘nums[i]左边的值
- right = 1
- for j in range(len(nums)-1, -1, -1):
- res[j] *= right
- right *= nums[j] # 累乘nums[i]右边的值
- Palindrome Number
- 问题：判断一个int数字是否是回文数，不能使用额外string等类型空间，不能reverse
- 思路：
- 法一：
- 简单数学逻辑，将n的逆序数求出来;外循环x的位数次
- m, k = x, 0
- while m > 0: # x<0则为false
- k = k*10 + m%10
- m //= 10
- return k == x
- 法二：
- 纯数学逻辑判断，将12321的12和21进行比较；外循环x的位数次/2
- 21用一个int变量存，翻转21用该变量进行*10计算
- 难点在于：10这种类型的数据的特殊处理，直接判断为False即可。
- while x > temp:
- temp = temp*10 + x%10
- x = x//10
- return x == temp or x == temp // 10
- 法三：处理大数字，用字符串处理的方式；回文数中心对称，只需要处理对称的数即可
- x_ = str(x)
- for i in range(len(x_)//2+1):
- if x_[i] != x_[len(x_)-1-i]:
- return False
- return True
- 法四：栈的思想，压栈左边一半，比较栈元素和剩下的串右边元素
- stack_ = []; x_ = str(x) ; i=0
- while i < len(x_)//2:
- stack_.append(x_[i])
- i += 1
- if len(x_)%2 == 1: i += 1
- while len(stack_) and i < len(x_): # 比较剩下的右边一半
- temp = stack_.pop(-1)
- if temp != x_[i]: return False
- i += 1
- return True
- 法一：
- Palindromic Substrings
- 问题：字符串的回文子串数目
- 思路：
- 法一：遍历一次，每次把当前i作为回文子串的中间点
- def helper(s, i, j, res):
- while i >= 0 and j < len(s) and s[i] == s[j]:
- res[0] += 1
- i -= 1; j += 1
- res = [0]
- for i in range(len(s)):
- helper(s, i, i, res) # i作为奇数对的中间
- helper(s, i, i+1, res) # i作为偶数对的中间左边一个
- return res[0]
- 法二：dp
- dp[i][j]定义为范围i到j之间的子字符串的个数，这样比较复杂，还需要额外一个二维数组记录字符串i，j是否是回文串；所以直接把dp[i][j]定义为[i,j]子串是否是回文串就行了，然后从n-1往0遍历，j从i往n-1遍历，看s[i]和s[j]是否相等即可。
- dp = [[False]len(s) for i in range(len(s))] # 记住二维的定义，[]是复制引用
- for i in range(len(s)-1, -1, -1):
- for j in range(i, len(s)):
- dp[i][j] = (s[i]==s[j]) and (j-i<=2 or (j-i > 2 and dp[i+1][j-1]))
- if dp[i][j]: res+=1
- return res
- 法一：遍历一次，每次把当前i作为回文子串的中间点
- Rotate Image
- 问题：顺时针旋转矩阵90度，要求in-place
- 思路：先上下翻转矩阵，转化为旋转问题，然后再旋转，swap每个值即可。时间复杂度O(n^2),空间O(1)
- Set Matrix Zeroes
- 问题：把含有0的行列都置为0
- 思路：使用两个数组，遍历1次保存每行每列为0的标志，然后遍历2次分别处理行和列
Sort Colors
- 问题：颜色对应0,1,2，对一个序列进行排序，尽量只遍历一次，且inplace
- 思路：
- 法一：双指针，两两交换
- for i in range(len(nums)):
- while i < right and nums[i] == 2:
- nums[i], nums[right] = nums[right], nums[i]
- right -= 1
- while left < i and nums[i] == 0:
- nums[i], nums[left] = nums[left], nums[i]
- left += 1
- 法二：partition
- mid, l, r = left, left, right
- while mid <= r:
- if nums[mid] < pivot:
- nums[l], nums[mid] = nums[mid], nums[l]
- l += 1; mid += 1
- elif nums[mid] == pivot:
- mid += 1
- elif nums[mid] > pivot:
- nums[mid], nums[r] = nums[r], nums[mid]
- r -= 1
- 法一：双指针，两两交换
Find All Numbers Disappeared in an Array
- 问题：找出[1,..n]数组中没出现的数字，数组中存在出现1次或2次的数字。时间O(n),空间inplace
- 思路：
- 法一：交换位置
- 充分利用1-n数组的特点，下标正常为[0,1,2,3,4],即[1,2,3,4,5]
- 数组为：[2,1,1,3,4]
- 交换每个元素到原来的位置上，转换为：[1,2,3,4,1]
- 在比较每个位置的值和index+1是否相等即可。
- 法二：将每个元素值对应的index-1变为负值
- 变为[-1,-2,-3,-4,1]
- 寻找大于0的元素，返回index+1
- 法一：交换位置
hash table
Find All Anagrams in a String
- 问题：查找字符串中的所有anagrams，s=”abab”,p=”ab”，返回[0,1,2]
- 思路：
- 方法：滑动窗口slide windows
1. 先统计所有的字母数目
- dict_p = {}
- slide_dict_s = {}
- for i in s[:len(p)-1]:
- if i not in slide_dict_s:
- slide_dict_s[s[i]] = 1
- else:
- slide_dict_s[s[i]] += 1
2. 开始滑动slide
- for i in range(len(p)-1, len(s)):
2.1 slide进最右边
- if s[i] not in slide_dict_s:
- slide_dict_s[s[i]] = 1
- else:
- slide_dict_s[s[i]] += 1
2.2 判断
- if slide_dict_s == dict_p:
- res.append(i - len(p) + 1)
2.3 slide出最左边
- slide_dict_s[s[i-len(p)+1]] -= 1
- if slide_dict_s[s[i-len(p)+1]] == 0:
- slide_dict_s.pop(s[i-len(p)+1])
- return res
Subarray Sum Equals K
- 问题：子数组的和为k的情况个数
- 思路：
- 暴力法：直接累加和
- hash保存记录的和：相当于记录：a+k = b，记录和为b时候的k的个数
- dict_sum = {0:1} # 初始化为0-1
- for i in range(len(nums)):
- sum_ += nums[i]
- if sum_ - k in dict_sum:
- res += dict_sum[sum_-k]
- if sum_ in dict_sum:
- dict_sum[sum_] += 1
- else:
- dict_sum[sum_] = 1
- return res
stack
- Min Stack
- 问题：定义栈结构，实现一个能够找到栈最小元素的min函数，min、push、pop时间复杂度都是O(1)
- 思路：
- 把每次遇到的更小的元素保存在一个辅助栈里；
- 每次push压入value，辅助栈压入新的更小的元素，否则压入辅助栈自己的栈顶top元素
- pop的时候，两个stack同时pop
- min的时候，辅助栈top()
- Largest Rectangle in Histogram
- 问题：求最大的连续矩形面积
- 思路：单调递增栈
- 把每个当前的height看做最小的，然后往后寻找大的height则添加进栈
- 如果下一个height小于或等于heights[stack.top()]，则h=heights[stack.top()]，stack.pop()，side=stack.top() if len(stack) >0 else -1,result=max(result, h*(i-side-1))
- 注意点：
- [1,1]这种情况发生了会无返回结果，所以比较简单的处理方式就是把heights添加一个0，0一定小于所有的heights，所以一定会返回结果。
- stack保存的是下标。
- Maximal Rectangle
- 问题：求一个01矩阵的含1的最大矩形面积
- 思路：参考https://blog.csdn.net/magicbean2/article/details/68486631
- 法一：暴力法：TLE，时间复杂度O(mnn)，可以优化到O(mnmin(m, n))，空间O(n)
- 每次有1的时候计算面积，更新最大的面积res，取最小height，所以0会截断，所以没毛病
- 0 0 1 0转换为：0 0 1 0
- 0 0 0 1 0 0 0 1
- 1 0 1 1 1 0 1 2
- 1 0 1 1 1 0 2 3
- 对每行出现1的数继续循环计算
- 法二：动态规划
- 防止重复搜索，记录每行中，每个位置的左右1的边界
- height = [0]*len(matrix[0])
- left, right = [0]len(height), [9999]len(height)
- 法三：单调栈
- 每行都看做是一个柱形图的底
- 同样先转换为暴力法的转换图
- 然后对转换后的结果，进行每行单调栈求最大面积。
- 法一：暴力法：TLE，时间复杂度O(mnn)，可以优化到O(mnmin(m, n))，空间O(n)
queue
- Sliding Window Maximum
- 问题：nums，滑窗为k，返回经过滑窗后的每个滑窗的最大值
- 思路：
- 暴力法，可以通过。。
- 法二：优先队列
- 优先队列 头部保存最大值，
- 上一次的队列的值小于当前值，则扔掉上次的值/队列尾部
- 添加当前值到队列
- 如果间隔达到k了，就去掉双端队列的最左边left
- 从k-1开始返回结果加入res，就返回队列头的index对应的值，即res+=nums[d[0]]
Divid and Conquer
- Search a 2D Matrix
- 问题：从左往右每行递增，且每行的第一个大于上一行的所有数，也就是一个s型矩阵
- 思路：
- 法一：直接剪枝O(m+n)
- 按第一列找到所在的行
- 再遍历所在的行
- 法二：二分法O(log(m+n))
- 二维数组二分法：利用矩阵转换为一行m*n数组的下标对应关系
- index = matrix[index//n][index%n]
- while left < right:
- mid = left+(right-left)//2
- mid_value = matrix[mid//n][mid%n]
- if mid_value==target:return True
- if mid_value < target: left = mid + 1
- if mid_value > target: right = mid
- return False
- 法一：直接剪枝O(m+n)
- Search a 2D Matrix II
- 问题：矩阵从左往右每行递增，从上往下每行递增，找target
- 思路：
- 法一：暴力法O(m*n)
- 法二：二分法O(mlog(n))，先二分找可能的列，然后遍历
- 法三：分治法O(m+n)
- 利用左下角和右上角的特性
- 选右上角，排除>target的列
- 对剩下的继续排除行
- j = len(matrix[0])-1
- for i in range(0, len(matrix)):
- while j and matrix[i][j] > target: j -= 1
- if matrix[i][j] == target: return True
- return False
- Kth Largest Element in an Array
- 问题：无序数组的第k大个元素
- 思路：
- 法一：heap
- 最小堆
- 堆数目小于k 或者 元素大于堆顶元素，则入堆，
- 堆数目大于k则删除堆头
- 法二：quick select
- 选取一个基准元素pivot，将数组切分partition为两个子数组，然后递推地切分子数组
- quick select只对目标子数组做切分
- 若切分后的左子数组的长度 > k，则第k大元素必出现在左子数组中；
- 若切分后的左子数组的长度 = k-1，则第k大元素为pivot；
- 若上述两个条件均不满足，则第k大元素必出现在右子数组中。
1
2
3
4
5
6
7
8
9def findKthSmallest(self, nums, k):
if nums:
pos = self.partition(nums, 0, len(nums)-1)
if k > pos+1:
return self.findKthSmallest(nums[pos+1:], k-pos-1)
elif k < pos+1:
return self.findKthSmallest(nums[:pos], k)
else:
return nums[pos]
- 若上述两个条件均不满足，则第k大元素必出现在右子数组中。
- 法一：heap
bit-manipulation位运算
- Single Number
- 问题：一个数组，每个元素都出现两次，除了1个只出现1次
- 思路：
- 逐项异或
- res = 0
- for i in nums: res ^= i
- Hamming Distance
- 问题：输出x，y的二进制的不同位个数
- 思路：
- 法一：直接计算
- 法二：利用python内置函数
- return bin(x^y).count(‘1’)
- Partition Equal Subset Sum
- 问题：
- 把一个集合分为和相等的两个子集,target = sum//2
- 思路：
- 若采用dfs，会超时，所以一般只需要返回值的，就用dp
- 法一：动态规划
- dp[i]表示能构成值为i的子集合
- dp = [False] * (target+1)
- dp[0] = True
- for i in range(len(nums)):
- for j in range(target, nums[i]-1, -1):
- dp[j] = dp[j] or dp[j - nums[i]]
- return dp[-1]
- 法二：位图
- bit位运算的每一位，为’1’表示可能的和
- bitset = 1
- for item in nums: bitset |= bitset << item
- return sum%2==0 and bin(bitset)[2:][-(sum/2+1)]==’1’
- 问题：
Sum of Two Integers
- 问题：不使用加减法，两个int相加
- 思路：
- python解法存在问题，python没有无符号右移操作，并且当左移操作的结果超过最大整数范围时，会自动将int类型32位转换为long类型。
- MAX_INT = 0x7FFFFFFF
- MASK = 0x100000000
- while b:
- carry = a & b
- a = (a^b) % MASK
- b = (carry << 1) % MASK
- return a if a <= MAX_INT else a | (~MASK+1)
Number of 1 Bits
- 问题：计算一个数的二进制所含1的个数，即hamming weight
- 思路：
- 法一：338的思路，超时
- 法二：移位法，右移；时间：O(1)因为循环次数是固定32位数； 空间 O(1)
- while n:
- if n&1 == 1: res += 1
- n >>= 1
- return res
- 法三：Brian Kernighan减一相与法，i&(i-1)；时间O(1)因为循环是固定的含有的1的个数，空间O(1)
- while n:
- n &= (n-1) # 111 & 110 = 110,相当于每次消去末尾的1
- res += 1
- return res
Hamming Distance
- 问题：计算x，y两个数的二进制表示的不同，也就是汉明距离
- 思路：
- 法一：
- n = x ^ y
- res = 0
- while n:
- n &= (n-1)
- res += 1
- return res
- 法一：
Counting Bits
- 问题：给定nums=5，返回0-5的每个数字的二进制表示所含0的个数[0,1,1,2,1,2]
- 思路：
- 法一：暴力法，不让用
- for i in range(nums+1): res.append(bin(i)[2:].count(‘1’))
- 法二：奇偶规律：
- 法三：巧妙利用i&(i-1)
- 法一：暴力法，不让用
Backtracking回溯法=递归+循环
- Subsets
- 问题：
- 给定nums=[1,2,3]，返回[[],[1],[2],[3],[1,2],[2,3],[1,3],[1,2,3]]
- 思路：
- 回溯法dfs：
- def dfs(nums, res, temp, index):
- res.append(temp)
- for i in range(index, len(nums)):
- temp.append(nums[i])
- dfs(nums, res, temp+[], i+1)
- temp.pop(-1)
- dfs(nums, res, [], 0)
- return res
- 问题：
- Number of Islands
- 问题：
- 求孤岛的数量，值为1，且上下左右都是0的才是孤岛，有一个互联的是同一个孤岛
- 思路：
- 法一：dfs深度优先搜索一个点的上下左右，将点1的上下左右的值为1的点改为0，则最后剩下的所含1的个数即为解
- def dfs(grid, x, y):
- if x < 0 or y < 0 or x > len(grid) or y >= len(grid[0]): return
- if grid[x][y] != ‘1’: return
- grid[x][y] = ‘0’
- dfs(grid, x+1, y); dfs(grid, x-1, y); dfs(grid, x, y+1); dfs(grid, x, y-1)
- res = 0
- for i in range(len(grid)):
- for j in range(len(grid[0])):
- if grid[x][y] == ‘1’: res+= 1; dfs(grid, i, j);
- return res
- 问题：
Course Schedule
- 问题：
- 给定[[1,0],[0,1]]，返回是否有环
思路：
法一：拓扑排序，递归DFS,时间复杂度O(n):
- 拓扑排序：在最后的排序结果中，顶点u总是在顶点v的前面。
1
2
3
4
5
6
7
8
9
10
11
12for each node:
if not marked:
if (dfs(node) == CYCLE): return False
return True
def dfs(node):
if node is marked as visited: return True
if node is marked as visiting: return False
mark node is visiting
for each new_node in node.neighbors:
if dfs(new_node) == False: return False
mark node is visited
return True
- 拓扑排序：在最后的排序结果中，顶点u总是在顶点v的前面。
法二：迭代dfs：
- 从DAG图中选择一个没有前驱(即入度为0)的顶点并输出
- 从图中删除该顶点和所有以它为起点的有向边，visit[i] -= 1
- 重复1和2，直到当前DAG图为空或当前图中不存在无前驱的顶点为止；后一种情况说明有向图中必然存在环
- 问题：
- Course Schedule II
- 问题：按依赖顺序返回结果
- 思路：
- 法一：递归dfs，未完成？
- 法二：迭代dfs，保存dfs的结果
- if visit[i] == 0: res.append(i) # 两处：初始无入度点，过程中无入度点
- res.reverse()
- return res
- Course Schedule III
- 问题：给定(t, d)，t为持续时间，d为截止日期
- 思路：贪心算法
- 按照第二列d截止日期排序；
- 构造一个优先队列或最大堆，每次把t持续时间保存进优先队列
- 注意python的优先队列默认是基于最小堆实现的，所以保存的是-t
- 注意优先队列比最大堆更慢些，最好用heapq最小堆实现，效率更高。
- 累积时间time，if time + t > d: time -= heappop() # 弹出最大的持续时间t
DFS
- Path Sum
- 问题：是否存在root-to-leaf的路径和等于sum
- 思路：
- DFS：
- def helper(root, sum):
- if root == None: return 0
- return root.val == sum and root.left == root.right==None or helper(root.left, sum - root.val) or helper(root.right, sum - root.val)
- return helper(root, sum) > 0
- Path Sum II
- 问题：找到所有root-to-leaf的路径
- 思路：
- DFS：
- def helper(root, sum, temp_list):
- if root == None: return
- if root.left == root.right == None and root.val == sum:
- temp_list.append(root.val)
- res_list.append(temp_list)
- helper(root.left, sum - root.val, temp_list+[root.val])
- helper(root.right, sum - root.val, temp_list+[root.val])
- helper(root, sum, [])
- return res_list
- Path Sum III
- 问题：找到满足parent nodes to child nodes的path个数
- 思路：
- 法一：双递归DFS，时间：O(n2),空间O(n)
- 利用上面的root-to-leaf的思路，去掉叶子节点的判断即可
- 每个节点作为路径根节点进行前序遍历，查找每一条路径的权值是否与sum相等
- def helper(root, sum):
- if root == None: return 0
- return int(root.val == sum) + helper(root.left, sum - root.val) + helper(root.right, sum - root.val)
- if root == None: return 0
- return helper(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum) # 递归遍历所有起点
- 法二：前缀和，时间O(n)，空间O(h)
- 用hash表记录当前遍历路径中的子路径权值和对应出现的次数
1
2
3
4
5
6
7
8
9
10
11m = {}
m[0] = 1
def helper(root, sum, curSum):
if root == None: return 0
curSum += root.val
res = m.get(curSum-sum, 0) # 用m[curSum - sum]会报错，因为不安全！
m[curSum] += 1
res += helper(root.left, sum, curSum) + helper(root.right, sum, curSum)
m[curSum] -= 1
return res
return helper(root, sum, 0)
Permutation组合数系列
- Next Permutation
- 问题：输出按照正常顺序一个序列的下一个排列组合
- 思路：
- 若已经排序好，则返回为上一次的交换：最大和次大
- 首先从最尾端开始往前寻找两个相邻元素，令第一元素为i,第二元素为ii,且满足i<ii。
- 找到这样一组相邻元素后，再从最尾端开始往前检验，找出第一个大于i的元素，令为j，将i,j元素对调(swap)。
- 再将ii之后的所有元素颠倒(reverse)排序
- Permutations
- 问题：给一行数字，返回所有可能的组合
- 思路：
- 法一：回溯法，递归实现：
- 逐一向中间集添加元素，并将当中间集元素个数等于 nums 长度的时候，将中间集添加到结果集中，并终止该层递归
- 法二：回溯法，递归实现：
- 每次回溯的时候交换两个元素位置，当最终长度等于nums时，终止递归
- 法一：回溯法，递归实现：
Permutations II
- 问题：给定一行数字，但可能含有重复的元素，返回所有可能的组合数
- 思路：
- 先排序，然后多用一个used_list数组保存是否一个元素被访问过了，然后使用dfs递归遍历，在每次下一个dfs前，判断是否被访问，以及是否和前一个相等，才进行下次dfs调用。
Permutation Sequence
- 问题：给定n，输出n的全排列中字典序第k小的排列。
- 思路：
- 直接用dfs枚举排列来查找会TLE，所以需要数学推导：
- 第一个开头的数字，分别有(n-1)!种
- k/(n-1)! 就是开头的数字
- k%(n-1)! 就是第二个开头的数字
- 用一个list1保存n!,用另外一个list2保存1-n的index
- 直接for循环，遍历，依次取第一个数字，。。
- 取完一个数字后，就在list2中删除该值。
Combination Sum系列
- Combination Sum
- 问题：
- 给定一个集合(不含重复)和target，求出所有的组合数结果，组合数之和为target，每个集合的元素可以重复任意次
- 思路：
- 方法：使用DFS通用方法，算法复杂度因为是NP问题，所以自然是指数量级的，对于fn中有n次循环的递归，O(n!)
- 构造dfs函数：dfs(结果，原始数据集，中间结果，指向当前数据，目标target):
- def dfs(res, input, temp, cur, target):
- if 数据非法: return # 终止条件
- if cur == len(input): res.append(temp) # 收敛条件
- if (可以剪枝): return # 剪枝
- for (…): # 执行所有可能的扩展动作
- 执行动作，修改temp
- dfs(res, input, temp+[], i, target-input[i]) # 记住这里是i不是cur
- temp.pop(-1) # 恢复temp
- 问题：
- Combination Sum II
- 问题：
- 和上题类似，但是input集合可能含有重复元素，且每个集合的元素只能被使用一次，
- 思路：
- 方法：通用的DFS方法
- input.sort()
- def dfs(res, input, temp, cur, target):
- if target < 0: return # 终止
- if target == 0: res.append(temp); return # 收敛
- for i in range(cur, len(input)):
- if target - input[i] < 0: return # 剪枝
- if i > cur and input[i] == input[i-1]: continue # 重复的跳过，因为重复的已经在上一次的递归中i+1考虑到了
- temp.append(input[i])
- dfs(res, input, temp+[], i+1, target-input[i]) # i+1，只使用一次元素
- temp.pop(-1)
- dfs(res, input, [], 0, target)
- return res
- 重复处理方法：
- 在res.append(temp)前，加入限制条件：if temp not in res: res.append(temp)这种方法，增加时间复杂度
- 先sort(),然后在每次递归到重复元素之前，跳过，因为已经在上次递归的i+1中考虑到了；sort()只是预先运行，不会增加时间复杂度
- 问题：
- Combination Sum III
- 问题：
- 给定k和目标n，要求在1-9的数字中找出k个数，和为n，且k个数不相同
- 思路：
- def dfs(res, input, temp, cur, target):
- if target < 0 or len(temp) > k: return
- if target == 0 and len(temp) == k:
- res.append(temp); return
- for i in range(cur, 9):
- #if target - input[i] < 0: return
- dfs(res, input, temp+[i+1], i+1, target-input[i])
- 问题：
- Combination Sum IV
- 问题：
- 给定nums和target，求和为target的所有可能情况数，允许重复使用任意次，顺序不同为不同结果
- 思路：
- 递归dfs无法使用，超时，属于动态规划问题
- 设dp[i]表示给定nums后，和为i的时候有多少种排列方式
- if i >= x: dp[i] += dp[i-x]
1
2
3
4
5
6
7
8dp[0] = 1
nums.sort()
for i in range(1, target+1):
for x in nums:
if i > x:
dp[i] += dp[i-x]
else:
break # 排序之后剪枝
- 问题：
动态规划
- Unique Paths
- 问题：
- 在m*n的棋盘的左下角，走到右上角，有多少种走法
- 思路：
- 方法一：只需要求走法，直接comb(m+n, m)即可，注意此题小人是占据了一个坐标点，所以需要m-1,n-1
- 方法二：动态规划
- dp[i,j]表示步数
- dp[i,j] = dp[i-1,j] + dp[i,j-1]
- 注意点：
- dp = [[1] n] m # 注意m n的内外顺序，要与下面的一致
- for i in range(1, m):
- for j in range(1, n):
- dp[i][j] = dp[i-1][j] + dp[i][j-1]
- return dp[m-1][n-1]
- 问题：
Unique Paths II
- 问题：
- 同上，只是存在一个obstacle，输入为一个m*n的矩阵，其中obstacle位置为1，其余为0
- 思路：
- 法一：组合数comb(a+b, a) * comb(m+n-a-b, m-a)
- 法二：动态规划
- 不在用二维数组来保存dp结果了
- 遍历每行，第2行后的每行内满足dp[i] += dp[i-1]
- 问题：
Minimum Path Sum
- 问题：给定m*n非负矩阵，找到从左上到右下的最小路径和
- 思路：
- 动态规划1：空间O(mn)
- dp[i][j]表示到达i,j时的最小sum
- dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
- 动态规划2：空间O(n)
- dp[i]表示到达i行的最小sum
- dp[i] = min(dp[i-1], dp[i]) + grid[i][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15dp = [grid[0][0]]*col
for i in range(1, col): # 初始化第一行
dp[i] = dp[i-1] + grid[0][i]
for i in range(1, row):
dp[0] += grid[i][0] # 每次大循环进来后，先处理第一列，累加
for j in range(1, col):
dp[j] = min(dp[j-1], dp[j]) + grid[i][j] # 处理右下的部分
return dp[-1]
或
dp = [0] + [float('inf')] * (col-1)
for i in range(row):
dp[0] += grid[i][0]
for j in range(1, col):
dp[j] = min(dp[j-1], dp[j]) + grid[i][j]
return dp[-1]
- 动态规划1：空间O(mn)
House Robber
- 问题：
- 小偷不能偷相邻的house，求最大能偷到的money
- 思路：
- 动态规划
- dp[i] = max(dp[i-1], dp[i-2]+nums[i])
- 问题：
House Robber II
- 问题：
- house变成环状，也就是第一个最后一个是相邻的
- 思路：
- 动态规划
- 连续两次，第一个是1:n-1，第二次是2:n，取两次的最大偷到的money
- 注意：边界条件，以及下标的顺序
- 问题：
House Robber III
- 问题：
- 树状house
- 思路：
- 法一：直接递归，指数复杂度，TLE
* - 法二：动态规划
- 考虑重叠，使用一个dict记录重叠的子树结果
- 记当前房间为root，如果偷窃当前房间，则其左右孩子left和right均不能偷窃；而其4个孙子节点（ll，lr，rl，rr）不受影响。
- 法三：DFS
- 考虑偷与不偷
- 法一：直接递归，指数复杂度，TLE
- 问题：
Word Break
- 问题：
- s=”leetcode”,dict=[“leet”,”code”]，因为”leetcode”可以被分为”leet code”，所以返回True。
- 思路：
- 逆序表示，dp[i]表示从s的第i个位置开始往后的子串是否可以被dict里面分割
- 关系式：dp[i] = (dp[j] and s[i:j] in dict)
- 问题：
Word Break II
- 问题：
- s = “catsanddog”,dict = [“cat”, “cats”, “and”, “sand”, “dog”].
- A solution is [“cats and dog”, “cat sand dog”].
- 思路：
- 法一：DP+DFS
- 先用DP记录所有位置可能wordbreak的点；
- DFS回溯记录所有的word，并利用DP排除不可能的break点，进行剪枝。
- 法二：Trie树
- 法三：DP超时，DP中间记录所有solution，超时。
- 法一：DP+DFS
- 问题：
Perfect Squares
- 问题：12 = 4+4+4，return 3，n=13，return 2
- 思路：
- 法一：动态规划
- dp = [i for i in range(n+1)]
- squares = [i*i for i in range(1, int(n**0.5) + 1)]
- for i in range(1, n+1):
- for sq in squares:
- if i < sq: break
- dp[i] = min(dp[i], dp[i - sq] + 1)
- return dp[-1]
- 法二：纯数学，找规律
- while n % 4 == 0: n/=4
- if n % 8 == 7: return 4
- a = 0
- while (a**2) <= n:
- b = int(math.sqrt(n - a**2))
- if ((a2) + (b 2)) == n:
- return 1 + (1 if not(not(a)) else 0) # 对a是否为0的判断
- a += 1
- return 3
- 法一：动态规划
Longest Increasing Subsequence
- 问题：最长递增子序列
- 思路：
- 法一：动态规划O(n2)
- dp[i]表示第i个位置的最长子序列数目
- if not nums: return 0
- dp = [1] * len(nums)
- for i in range(1, len(nums)):
- for j in range(0, i):
- if nums[i] > nums[j]:
- dp[i] = max(dp[i], dp[j] + 1)
- return max(dp)
- 法二：动态规划，O(nlog(n))，维护一个当前递增长度的最大值
- 法三：辅助数组单调递增子序列
- 原理：依次读取数组元素x与数组末尾元素top比较，因为单调递增子序列能否增长，值取决于最后一个元素，替换内部的元素并不影响
- for i in range(0, len(list_)):
- if len(temp) == 0: temp.append(list_[i]); continue
- for j in range(0, len(temp)):
- if list_[i] <= temp[j]:
- temp[j] = list_[i]
- break
- else:
- if j == len(temp)-1:
- temp.append(list_[i])
- return len(temp)
- 法四：辅助数组单调递增子序列+二分查找
- for i in range(1, len(nums)):
- if nums[i] > res[-1]:
- res.append(nums[i])
- else:
- res[binarySearch(nums, nums[i])] = nums[i]
- return len(res)
- 法一：动态规划O(n2)
Coin Change
- 问题：coins=[1,2,5],amount=11,return 3 因为11=5+5+1
- 思路：
- 法一：迭代，动态规划,时间O(n*amount),空间O(amount)
- 状态转移方程：dp[i] = min(dp[i-coins[j]], dp[i])
- for i in coins:
- for j in range(i, amount+1):
- if dp[j-i] != 9999:
- dp[i] = min(dp[i], dp[j-i]+1)
- return -1 if dp[amount] == 9999 else dp[amount]
- 法二：递归，DFS，时间O(amount^n/(coin_0coin_1…*coin_n))，空间O(n)
- return dp[amount] = dp[amount] == MAX_INT ? -1 : dp[amount]
- c++语法：return a=b；等价于a=b; return a;
- 法三：递归，使用hash表的DFS
- 法一：迭代，动态规划,时间O(n*amount),空间O(amount)
Target Sum
- 问题：[1,1,1,1,1]，s=3，求多少种+-组合方式，满足操作结果为s
思路：
暴力法：DFS也可以做，时间O(2^n)，n=20，AC=585ms，空间O(n)
- 枚举所有可能的组合2^n
1
2
3
4
5
6def dfs(nums, target, cur):
if cur == len(nums):
if target == 0: self.res += 1
return
dfs(nums, target - nums[cur], cur+1)
dfs(nums, target + nums[cur], cur+1)
- 枚举所有可能的组合2^n
优化1：用dp数组记录中间值，避免重复计算
*- 最优解：DP，时间O(nS)
- 枚举所有的值S<<2^n，且DP擅长于计数
- sum(P)-sum(N)=target，sum(P) = (target+sum)/2
- 转换为0-1背包问题：是否能够找到一些数字的和为(target+sum)/2
- dp[i]表示和为i的个数
- for i in range(len(nums)):
- for j in range(sum, nums[i]-1, -1): # pull的方法，本质还是二维dp，但倒序扫描就可以降维，因为不会影响其他元素
- dp[i][j] = dp[i-1][j] + dp[i-1][j-num]
- 等价于：dp[j] += dp[j-num]
- dp[j] += dp[j-nums[i]]
- return dp[sum]
Maximal Square
- 问题：矩阵中找到只含有 1’s and return its area
- 思路：
- DP
- dp[i][j]表示从左上角到i,j的最大连续1的长度
- dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
- return (max([max(i) for i in dp]))**2
Greedy贪心
Task Scheduler
- 问题：每个任务的执行需要一个时隙，两个相同任务之间必须至少相差n个时隙，没有任务的时隙表示为idle。求问怎么安排任务，才能使得所需时隙数最少。
- 思路：
- 贪心算法
- 相同的任务需要间隔n个时隙以上，因此，使得总时隙长的主要原因是相同任务需要间隔分布，所以找到出现次数最多的任务，将其作为框架，这就是贪心选择；
- 假设频数最高的任务频数为k，则框架中有k-1个大间隔，之后一次向间隔中插入频数递减的任务，一次插一个任务，k-1个间隙轮流插入，保证足够均匀
- A___A___A___A，依次插入B，AB__AB__AB__A，以此类推
- 证明：
- 若大间隔被填满了，此时所需要的时隙数就是任务书，所以len(tasks)
- 若大间隔没被填满，则所需要的时隙数为(n+1)*(freq(A)-1) + k
- k为频数和最高频数任务A一样的任务数
- max_task = max(dict_task.values())
count_same = 0
for i in dict_task:
if dict_task[i] == max_task: count_same += 1
return max(len(tasks), (max_task - 1) * (n+1) + count_same)
Queue Reconstruction by Height
- 问题：(h,k)表示高度、前面比自己高的个数，排序
- 思路：
- 贪心：
- 按照h逆序，k升序的顺序排序
- 然后按k位置逐渐插入
- people.sort(key=lambda (h,k):(-h, k))
- res = []
- for p in people: res.insert(p[1], p)
- return res
股票买卖
- Best Time to Buy and Sell Stock
- 问题：只能执行一次交易，也就是买卖的过程，求最大收益
- 思路：
- 动态规划，空间O(1)
- dp全局最大值，局部最值
- temp_max = 0 # 局部最大值，选择第i天的时候买卖交易的最大收益
temp_min = prices[0] # 局部最小值，第i天前的最小值
dp = 0 # 全局最大值
for i in range(1, len(prices)):
return dptemp_max = max(temp_max, prices[i] - temp_min) temp_min = min(temp_min, prices[i]) dp = max(temp_max, dp)
- Best Time to Buy and Sell Stock II
- 问题：最佳买入和卖出股票，可以执行多笔交易，一天只能买或卖，求最大收益
- 思路：
- 贪心：
- 第i天要进行的决策为d[i],
- if price[i+1] > price[i]: 则第i天买入，第i+1天卖出第i天买入的
- if price[i+1] < price[i]: 则第i天不买入，不操作
- Best Time to Buy and Sell Stock III
- 问题：可以执行2次交易，求最大收益
- 思路：
- 法一：二分+动态规划，时间O(n2)，TLE
- 法二：分治+动态规划，空间换时间，
- 法三：纯动态规划
# 建模: 一个是当前到达第i天可以最多进行j次交易，最好的利润是多少（global[i][j]）， # 一个是当前到达第i天最多可进行j次交易，并且最后一次交易在当天卖出的最好的利润是多少（local[i][j]） # diff = (prices[i+1] - prices[i]) # local_dp[i][j] = max(global_dp[i-1][j-1] + max(diff, 0), local_dp[i-1][j]+diff) # 解释：第一个是全局到i-1天进行j-1次交易，然后加上今天的交易，如果今天是赚钱的话（也就是前面只要j-1次交易，最后一次交易取当前天），第二个量则是取local第i-1天j次交易，然后加上今天的差值（这里因为local[i-1][j]比如包含第i-1天卖出的交易，所以现在变成第i天卖出，并不会增加交易次数，而且这里无论diff是不是大于0都一定要加上，因为否则就不满足local[i][j]必须在最后一天卖出的条件了） # global_dp[i][j] = max(global_dp[i-1][j], local_dp[i][j]) # 解释：当前局部最好的，和过去全局最好的中大的那个（因为最后一次交易如果包含当前天一定在局部最好的里面，否则一定在过往全局最优的里面） # k = 2 # global_dp = [[0] * (k + 1) for i in range(len(prices))] # 注意二维数组的初始化，不能[[0]*5]*5 # local_dp = [[0] * (k + 1) for i in range(len(prices))] # if len(prices) < 1: return 0 # for i in range(1, len(prices)): # diff = prices[i] - prices[i-1] # for j in range(1, k+1): # local_dp[i][j] = max(global_dp[i-1][j-1] + max(diff, 0), local_dp[i-1][j] + diff) # global_dp[i][j] = max(global_dp[i-1][j], local_dp[i][j]) # return global_dp[len(prices)-1][k] - 法四：进一步优化空间,空间优化为O(n)
# k = 2 # global_dp = [0] * (k+1) # local_dp = [0] * (k+1) # for i in range(0, len(prices)-1): # diff = prices[i+1] - prices[i] # for j in range(k, 0, -1): # # 优化空间，空间复杂度O(n) # local_dp[j] = max(global_dp[j-1] + (diff if diff else 0), local_dp[j] + diff) # global_dp[j] = max(global_dp[j], local_dp[j]) # return global_dp[k] - 法五：简单逻辑法，时间复杂度O(n)
- 只需记录每次的最大值，和最小值
- oneBuy = twoBuy = -10000
oneBuyoneSell = twoBuytwoSell = 0
for i in prices:
return max(oneBuyoneSell, twoBuytwoSell)oneBuy = max(oneBuy, - i) oneBuyoneSell = max(oneBuyoneSell, oneBuy + i) twoBuy = max(twoBuy, oneBuyoneSell - i) twoBuytwoSell = max(twoBuytwoSell, twoBuy + i)
- Best Time to Buy and Sell Stock IV
- 问题：一共可以操作k次，求最大收益
- 思路：
Math数学
牛客-剑指offer：求1+2+3…+n，要求不能用乘除法、for、while、if、else、switch、case等关键词及(A?B:C)等：
- 思路：无外乎循环和递归
+ python:
* def f(self, n):
* return n and (n+self.f(n-1))
- Add Digits
- 问题：
- 找数字，38，3+8=11,1+1=2，返回2
- 思路：
- 法一：循环计算
- 法二：找规律
- 除了第一个0以外，都在1~9之间循环。
- 除以9的余数，为0时，对应的结果是9，而不为0时，余数等于对应的结果，
- 代码：return 0 if num==0 else 1+(num-1)%9
- 问题：
Nim Game
- 问题：
- 每次只能移动1-3个石头，谁最后移动一块石头即为获胜
- 思路：
- 找规律
- n == 1,2,3 时，先动作的必胜
- n == 4时，先动作的必输
- n > 4时，return !(f(n - 1) + f(n-2) + f(n-3)) 循环5,6,7胜，8输。。。
- 代码：return n%4 != 0
- 问题：
Ugly Number
- 问题：ugly number丑陋数是指只包含质因子2, 3, 5的正整数；如6,8是，而14不是；数字1也被视为丑陋数
- 思路：
- 对num进行除2/3/5运算，直到余数为不再为0停止；
- for ugly in [2,3,5]:
- while num%ugly == 0: num/=ugly
- return num == 1
- 约瑟夫环问题：有n个人围成一圈，顺序编号。从第1个人开始报数（从1-m报数），凡报到m的人退出圈子，问最后留下的是原来第几号的那位？
- nums = [i for i in range(1, n+1)]
- i = j = k = 0
- while j < n - 1:
- if nums[i] != 0: k+=1 # 剩下的人报数计数
- if k == m:
- nums[i] = 0 # 报数到m的退出圈子
- k = 0
- j += 1
- i += 1
- if i == n: i = 0
- for i in nums:
- if i != 0: print(i)
- 素数判断：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15def isprime(n):
if n <= 1: return False
i = 2
if n % 2 == 0: return False # 对偶数进行剪枝
while i*i <= n:
if n % i == 0: return False
i += 1
return True
```
- 拼多多1：给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)
+ 思路：只有两种可能，一种是最大的3个正数的乘积，一种是最大的正数和两个最小的负数的乘积，所以遍历3次，分别得到最大的3个数和最小的2个数，比较乘积即可。
+ max_index1 = -1; max_value1 = -999; min_index1 = -1; min_value1 = 999
- 拼多多2：
+ 思路：按位移位计算,用x的每一位乘以y
X, Y = [x for x in input().strip(‘\n’).split(‘ ‘)]
def big(x, y):
n = len(x) + len(y)
res = [‘0’] n
index = 0 #
over = 0 # 进位
for i in range(1, len(x)+1):
over = 0
for j in range(1, len(y)+1):
pre_res = int(res[-j-index])
sum_ = int(x[-i]) int(y[-j]) + over + pre_res
over = sum_ // 10
res[-j-index] = str(sum_ % 10)
if over != 0:
res[-j-index-1] = str(over) # 注意保留下一个进位
index += 1
for i in range(len(res)):
if res[i] != ‘0’: return ‘’.join(res[i:])
print(big(X, Y))
大整数乘法的时间复杂度优化
def big(x, y):
n = max(len(str(x)), len(str(y)))
if n == 1: return str(int(x) int(y))
ten1 = 10 n
ten2 = 10 (n // 2)
a, b = x[:n], x[n:]
c, d = y[:n], y[n:]
ac = big(a, c)
ad = big(a, d)
bc = big(b, c)
bd = big(b, d)
res = int(ac) ten1 + (int(ad) + int(bc)) * ten2 + int(bd)
#abcd = big((a-b), (d-c))
#res = ac * ten1 + (abcd + ac + bd) * ten2 + bd
return str(res)
1 |
|
def catch(nums, n):
state = [i+1 for i in range(n)]
def change(state, n):
res = {}
for i in state:
if i + 1 <= n and i + 1 not in res: res[i+1] = None
if i - 1 >= 1 and i - 1 not in res: res[i-1] = None
res_list = list(res.keys())
return res_list
for i in nums:
state.remove(i)
if len(state) == 0: return True
state = change(state, n)
return False1
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
312. 使序列有序的最少交换次数1，只能交换相邻两数
- 就是求逆序对数
3. 使序列有序的最少交换次数2：可以交换任意位置
- 思路：如果用冒泡排序，每次交换次数就加一，而最快的方式则是：交换使得数组值等于其下标值。
4.
## 注意点
1. 空指针null、None；空字符串""，正负号，溢出
2. 无穷大：
- float('inf'):表示正无穷
- -float('inf')或者float('-inf'):表示负无穷
- inf也可以写成Inf
3.
# 牛客网
## python
- 输入的时候：使用input()会变慢
- 改用:import sys
- N = int(sys.stdin.readline().strip('\n'))
- 最大整数：
+ python2：sys.maxint
+ python3：sys.maxsize
- 组合数：
+ from itertools import permutations
+ for i in permutations(list_, 2): print(i)
- debug：
+ 注意输出，有时候ac不能100%，就是因为多于的print浪费时间
+ 下面招商银行2018实习题14，直接在每次dfs的时候print，不用在最后保存了结果后再次进行print
+ print([1,2,3]) # 是会保存[]打印出来的，不符合标准题意
+ print(' '.join(['1','2','3'])) # 需要在每次添加元素时候就str(i+1)，而不是最后保存后，再次遍历list进行str操作
+ 这就是一开始ac为66%的原因，但是牛客网不会告诉你什么错的。。。
import sys
[length, target] = [int(t) for t in sys.stdin.readline().strip('\n').split(' ')]
def dfs(res, temp, index, target):
if target < 0: return
if target == 0 and len(temp) == length: print(' '.join(temp)); res.append(temp); return
if len(temp) >= length: return
for i in range(index, 9):
if target < i+1: return
dfs(res, temp+[str(i+1)], i+1, target-i-1)
res = []
dfs(res, [], 0, target)
if len(res) < 1: print(None)
```
提高效率：
- 用[1]*N 要比 [i for i in range(N)] 快很多
- 分治法的写法：
- mid = left + (right-left) // 2 # 即可
- mid = left + ((right-left) >> 1) # 位操作的优先级很低，注意加括号，但是速度没有加快
头条2018-1：
-问题：P为给定的二维平面整数点集。定义 P 中某点x，如果x满足 P 中任意点都不在 x 的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9) 内）
如下图：实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。- 解决：80%ac，超出空间，
- import sys
nums = int(sys.stdin.readline().strip(‘\n’))
points = []
for i in range(0, nums):
points.append([int(t) for t in sys.stdin.readline().strip(‘\n’).split(‘ ‘)])
points.sort() # 排序，元组排序会先按第一个数排，再按第二个数排
max_x2y = points[nums - 1][1]
index = nums - 2
for j in range(nums - 2, -1, -1): # 倒过来求
if points[j][1] > max_x2y:
for i in range(index+1, nums):points[index] = points[j] max_x2y = points[j][1] index -= 1
print(str(points[i][0]) + ‘ ‘ + str(points[i][1]))
- indeed-小房的第二次-2
- 问题：一个数组，经过最少的*-1的次数，变为递增序列
- 思路：
- 法一：dfs方法，但是结果有不过的case
- 法二：dp方法，
- 定义两个dp，
- dp1[i]表示第i次不乘-1，而能变为递增序列的最小次数
- dp2[i]表示第i次乘以-1，而能变为递增序列的最小次数
- dp1[0] = 0
- dp2[0] = 1
- for i in range(1, N):
- if nums[i] >= -nums[i-1] and nums[i] >= nums[i-1]:
- dp1[i] = min(dp1[i-1], dp2[i-1])
- elif nums[i] > -nums[i-1] and nums[i] < nums[i-1]:
- dp1[i] = dp1[i-1]
- elif nums[i] < -nums[i-1] and nums[i] >= nums[i-1]:
- dp1[i] = dp2[i-1]
- if -nums[i] >= nums[i-1] and -nums[i] >= -nums[i-1]:
- dp2[i] = min(dp1[i-1], dp2[i-1]) + 1
- elif -nums[i] > nums[i-1] and -nums[i] < -nums[i-1]:
- dp2[i] = dp1[i-1] + 1
- elif -nums[i] < nums[i-1] and -nums[i] >= -nums[i-1]:
- dp2[i] = dp2[i-1] + 1
- if nums[i] < nums[i-1] and nums[i] < -nums[i-1] and -nums[i] < nums[i-1] and -nums[i-1] < -nums[i-1]:
- dp1[i] = -1
- dp2[i] = -1
笔试题杂
在如下4*5的矩阵中，请计算从A移动到B一共有__种走法？要求每次只能向上或向右移动一格，并且不能经过P。
法一：组合数，A-B路径总数=C(m, n)
不考虑经过P：从A到B必须要向上走3步，向右走4步，所以从A到B，一共有C(7,3)种走法考虑经过P：从A到P必须要向上走2步，向右走2步，所以一共是C(4,2)种
从P到B必须要向上走1步，向右走2步，所以一共是C(3,1)种
则考虑P，从A到B一共有C(7,3)-C(4,2)*C(3,1) = 17种走法
- 法二：写出每个格子的路径种数，其中，每个格子的路径种数 = 左边格子种数 + 下边格子种数
- 法三：递归方式求解：f(m,n) = f(m-1,n)+f(m,n-1)
- 哈夫曼树最小编码位数
- 问题：字符串”alibaba”的二进制哈夫曼编码有多少位，答案：13
- 解：
- 统计各个字符出现的频率：3 2 1 1
- 根据权值，构建哈夫曼二叉树
- 7
- 3 4
- 2 2
- 1 1
- 对应字符编码为：
- a:0
- b:10
- l:110
- i:111
- 最终为：0 100 101 11 0 11 0，13长度
- 均匀筛子的熵值为多少比特：
- H(x) = E(-plogp) = - (1/6) log2(1/6)) = log2(6) = log2(3) + log2(2) = 1 + lg3 / lg2 = 1 + 0.47 / 0.3 = 2.6
- 正则化式子：
- - 矩阵相乘ABC，mn, np, p*q, m<n<p<q，效率最高的为：(AB)C
- (AB)C:花费乘法=mpn+mqp
- A(BC):花费乘法=mnq+npq
- SELECT Persons.Id, Persons.name, Orders.Id LEFT JOIN 关键字会从左表 (Persons) 那里返回所有的行，即使在右表 (Orders) 中没有匹配的行。
- 朴素贝叶斯可以不需要迭代
- 一个具有n个节点的完全二叉树,其叶子节点的个数为多少？
- 设：叶子节点个数为n0,度为1的节点个数为n1,度为2的节点个数为n2
- n0+n1+n2=n
- 对于二叉树：n0 = n2 + 1
- 所以：n0 = (n+1-n1)/2
- 由满二叉树性质：n1=0或1
- 所以：n0 = (n+1)/2 或者 n/2
- 不可能是快速排序第二趟排序结果的是
- 每次排序，就会有一个元素排在了最终的位置上
- n次排序后，至少有n个元素落在了最终的位置上。
- 求10000!尾数0的个数：
- 32！：32/5 + 32/25 =7
1024!：1024/5 + 1024/25 + 1024/125 + 1024/625 = 253 - 迅速写python求解：
- for i in range(1, 10):
- if 5i<a: s+=(a//5i)
- print(s)
- 32！：32/5 + 32/25 =7
- 做三次至少一次发生的概率是0.95，求发生一次的概率：
- 1-(1-p)3 = 0.95, (1-p)3 = 0.05, p = 1-0.368=0.63
- n天后是星期几？
- 今天为周日，则N天后，是星期 N%7
- 如果在一次大选中某人的支持率为55%，而置信水平0.95以上的置信区间是（50%,60%），那么他的真实支持率有百分之九十五的机率落在百分之五十和百分之六十之间，因此他的真实支持率不足一半的可能性小于百分之5。
- =SUM(SUMIF(C2:C9,{“<10”,”<6”})*{1,-1})
- sumif返回一个向量，=23-9=14
- SQL执行的顺序
- sql执行顺序和语法顺序不一致
- 语法顺序：SELECT[DISTINCT]；FROM；WHERE；GROUP BY；HAVING；UNION；ORDER BY
- 执行顺序：FROM；WHERE；GROUP BY；HAVING；SELECT；DISTINCT；UNION；ORDER BY
- 注意：
- from执行的第一步
- select是在大部分语句执行完之后才执行
- select在from和group by之后执行，所以说where中不能使用select设定的别名字段
- x和y都服从正态，且不相关，则
- 只有当（X,Y）服从二维正态的时候，X与Y不相关，才等价于X与Y独立
- X、Y都服从正态，且相互独立，才能推出（X,Y)服从二维正态
- 要求X与Y相互独立时，才能推出X+Y服从一维正态；
- 所以：X与Y未必独立
- 个人收入右偏，均值为5000，标准差1200，随机抽取900，收入的均值分布？
- 近似正态分布，均值为5000，标准差为40
- 右偏的意思：数据在均值左侧的数量较多，均值右偏了~所以达到平衡，分布图有一个很长的右边拖尾；
- 众数 < 中位数 < 均值
- 有20个人去看电影，电影票50元。其中只有10个人有50元钱，另外10个人都只有一张面值100元的纸币，电影院没有其他钞票可以找零，问有多少种找零的方法？
- 卡特兰数问题：C(n,2n)/(n+1)=C(10,20)/11=16796
- 2堆宝石，A和B一起玩游戏，假设俩人足够聪明，规则是每个人只能从一堆选走1个或2个或3个宝石，最后全部取玩的人获胜，假设2堆宝石的数目为12和13，请问A怎么可以必胜？
- A先去13的1，然后让B任意选：
- B选1，A选相同堆的3；
- B选2，A选2；
- B选3，A选1；
- A先去13的1，然后让B任意选：
- 6*6的棋盘，放入相同的4个棋子，且同一行列不能有两个棋子，求多少种可能？
- 先选列：C(6,4)
- 再选行：C(6,4)
- 在进行排列：P(
- 4,4)
- 所以一共：5400
- Ａ/Ｂ/Ｃ/Ｄ/Ｅ五个人互相传球，由A开始第一次传球，经5次传球后传回到A的手上，其中A与B不会相互传球，C只会传给Ｄ，Ｅ不会传给Ｃ，共有多少种传法？
- 思路：设接球人的序列为:AXXXXA,其中中间4位是未知的.
- 通过正则：
- 找出数组中超过一半的数
- 法一：直接排序，则中间的数就是结果，O(nlogn)
- 法二：遍历数组，如果两个数不相同，则删除这两个，最后剩下的数组的中间的数就是结果
- 已知1-5的整数随机数生成器，如何设计一个1-7的随机数生成器？
- 已知a的，设计b的？
- 如果a>b,则a可以生成b的，只要选取a中在b的范围内的值作为b的结果即可。
- 证明：p(x=1)=1/7 + (2/7)(1/7) + (2/7)**2(1/7)+… = 1/7*(1+2/7+(2/7)**2..等比数列) = 1/5所以成立。
- 第一次生成rand7，第二次是rand7生成的(第一次概率是2/7)，第三次是rand7生成的。。。
- 如果a<b，则需要凑：5*(rand5()-1)+rand5()
- rang5()范围是：1-5
- rand5()-1是：0-4
- 5*(rand5()-1)是：0-20
- 5*(rand5()-1)+rand5()是：1-25
- 而且是每个数都可以取到，每个数也只由一种组合得到，所以可以等概率的生成1-25
- 优化：这样的话需要保留1-7的，废弃8-25的，很浪费，所以可以考虑保留1-21的，然后取个7的余数即可。
- def rand7():
- x = 9999
- while x > 21:
- x = 5 * (rand5()-1) + rand5()
- return x % 7 + 1
- n条直线划分平面？
- 3条最多7个部分；4条最多11个部分；n条最多1 + n(n+1)/2
- 证明：f(n-1),当n时，要想最大化，则需要与前n-1条都相交，产生n-1个交点，会把第n条直线分割为2条射线和n-2条线段，而每条射线和线段都会把已有的区域一分为二，所以就多了n个区域，所以f(n) = f(n-1) + n = 1 + n*(n+1) / 2
- 变体：平面分割空间区域（三维分割）
- 二维分割中，分割平面与线的交点有关，交点决定射线和线段的条数，从而决定新增的区域数；
- 三维分割中，分割空间与交线有关；
- f(n-1),当n时，要想最大化，则需要与前n-1个平面都相交，且不能有共同的交线，即最多有n-1条交线，而这n-1条交线把第n个平面最多分割为g(n-1)个区域，g(n)表示二维分割中直线分割平面的个数，此平面将原有的空间一分为二，则最多增加g(n-1)个空间，
- 所以f(n) = f(n-1) + g(n-1) = f(n-1) + 1+n*(n+1)/2 = (n**3+5n)/6+1
- 35+57+。。。+99*101
- 35=（4-1）（4+1）
- s = 4*sum(i**2) - 49, i 从2-50
- s = 4*sum(i**2) - 50 - 3, 从1-50
- s = 4 (n(n+1)*(2n+1)/6) - 50 -3, n=50
- s = 171647
- 各种loss
- LR：
- P(Y=1|x) = pi(x) = exp(wx) / (1+exp(wx)), P(Y=0|x) = 1-pi(x)
- 似然函数：multi(pi(xi)^yi)*(1-pi(xi))^(1-yi)
- 对数似然：L(w) = sum(yilog(pi(xi) + (1-yi)log(1-pi(xi))) = sum(yilog((pi(xi)/(1-pi(xi)))) + log(1-pi(xi))) = sum(yi(wxi) - log(1+exp(wxi))
- SVM：
- 线性支持向量机的loss：sum(1-yi(wx+b))+ + r||w||^2
- LR：
- SMO
- 序列最小最优化算法，是一种启发式算法，包括：求解两个变量二次规划的解析方法和选择变量的启发式方法
- 如果所有变量的解都满足该优化问题的KKT条件，那么这个最优化问题的解就找到了；否则的话就选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题；这个二次规划问题的解应该是更接近原始二次规划问题的解，因为会使loss变小，最主要的是，这时子问题的解可以通过解析方法来求解，极大提高计算速度；
- 子问题的两个变量中，只有一个是自由变量，如果a2确定，那么a1也确定，所以子问题中是同时更新两个变量的；
- N从1开始，每个操作可以选择对N加1或者对N加倍，最少需要多少个操作？
- 转换为二进制，然后取含0的个数为a，含0的个数为b
- res = (a-1) * 2 + b
- 子序列和最大 与 子序列绝对值和最大？
- 用最少的比较次数找出一个list的最大和最小值
- 只找max，至少需要n-1次比较
- 同时找max，min,最常见的做法是，对每个元素，分别和最小值和最大值都比较一下，这样每个元素都需要2次比较
- 优化：同时取出两个元素，先让他们自己比较一下，然后大的和max比较，小的和min比较，这样2个元素只需要3次比较就能完成，节省1次比较时间
- 并行计算：
- P1：计算 60ms—————-I/O 80ms—————–计算 20ms
P2：计算 120ms————–I/O 40ms—————–计算 40ms
P3：计算 40ms—————-I/O 80ms—————–计算 40ms
调度程序的执行时间忽略不计,完成这三道程序比单道运行节省的时间是 - 先p1计算60，然后p1计算80msIO的时候，同时计算P2的80ms计算，节约：80ms
- 然后P1计算完IO后，继续计算20ms，然后P2继续完成剩下的40ms，然后进入p2的IO，同时计算P3的40ms，节约40ms
- 然后计算P3的80msIO，同时计算P2的40ms，然后后续就是P3完成剩下的计算即可；节约：40ms
- 总共节约：160ms
- P1：计算 60ms—————-I/O 80ms—————–计算 20ms
- 游戏碰撞检测：
数据库
spark、hadoop、hive、
- SELECT SUM(TRADE_AMT) AS ALL_TRADE_AMT
FROM TRADE_DTL WHERE TRADE_DATE = ‘2018-03-27’ - SELECT CUS_ID, SUM(TRADE_AMT) as all_Trade_AMT
FROM TRADE_DTL WHERE TRADE_CITY = ‘北京’ OR TRADE_CITY = ‘上海’
ORDER BY all_Trade_AMT DESC - SELECT CUS_MOBILE, avg(TRADE_AMT) AS avgTRADE
FROM TRADE_DTL, CUS_DTL
WHERE CUS_ID = CUS_ID and TRADE_AMT > avgTRADE
带
p(青年) = 5 / 14
p(中) = 5 / 14
p(男) = 7 /14
p(买) = 9 / 14
p(买| 青年) = 2 / 5
p(买| 中) = 4 / 5
p（买|男） = 6 / 7
p(买，青年，中，男) = 1 / 14
p(买| 青年，中，男) = p(青年，中，男| 买) / p(买，青年，中，男)
= p(青年|买) p(中|买) p(男|买) / p
= p(青年,买) p(中,买) p(男,买) / (p p(买)**3)
= p(买|青年) p(青年) *
GAN
import tensorflow as tf
flags.DEFINE_float(“learning_rate”, 0.1, “Learning”)
FLAGs = flags.FLAGS
