目录
双指针
二分查找
滑动窗口
递归法
回溯法
分治法
深度优先搜索（DFS）
广度优先搜索（BFS）
贪心算法
并查集
记忆化搜索：
动态规划
排序算法
一道经典例题200. 岛屿数量
又一道非常典型的题：
一类会议安排题目：leetcode会员题
【注意：列出来的题目大部分是简单题；列出来的题目其最优解法不一定是本文中所说的算法，列举只是为了辅助更好的理解算法；有错误请帮我指出谢谢！】
双指针
普通双指针，碰撞双指针，快慢双指针
141. 环形链表 - 力扣（LeetCode）
881. 救生艇 - 力扣（LeetCode）
二分查找
一个特点是必须有序，然后一般与双指针结合在一起，一头一尾两个指针，往中间移动。704. 二分查找 - 力扣（LeetCode）35. 搜索插入位置 - 力扣（LeetCode）162. 寻找峰值 - 力扣（LeetCode）74. 搜索二维矩阵 - 力扣（LeetCode）
'''
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
'''
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums) -1
while (l<=r):
mid = l + (r-l)//2
if target < nums[mid]:
r = mid +1
elif target >nums[mid]:
l = mid - 1
return l
总结！！！！！重点！！！！！！！！！！！！！！！！！！！！！！！！
一共三种：
第一种：左右都是闭区间
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1 ###闭区间为[left, right]
while left <= right: ####区间不能为空
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
第二种：左闭右开
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) ###左闭右开[left, right）
while left < right: ####区间不能为空
mid = (left + right) // 2
if nums[mid] < nums[mid+1]:
left = mid + 1
else:
right = mid
return left
第三种：左开右开
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left = -1
right = len(nums) ###开区间（left, right）
while left + 1 < right: ####区间不能为空
mid = (left + right) // 2
if nums[mid] < nums[mid+1]:
left = mid
else:
right = mid
return right
'''
注意，这三个模板都是针对： >= 来说的
还有 >, <, <= 三种情况怎么办：
正常大于等于就是 searchInsert（target）
!!!!比如>的情况就可以看成是 >x+1，就比如上题目找的大于8，就可以改成>8+1,即>9：：
searchInsert（target+1）
!!!!对于小于的情况，可以看成是： （>=8）-1，就是大于等于8的左边的那个数：
searchInsert（target）-1
！！！对于小于等于的情况，可以看成是：（>x）-1：
searchInsert（target+1）-1
'''
滑动窗口
解决数组中的定长问题，一般还有连续，一般滑动窗口也是使用双指针，然后改变j指针来改变窗口大小。209. 长度最小的子数组 - 力扣（LeetCode）1456. 定长子串中元音的最大数目 - 力扣（LeetCode）
#经典题目：209. 长度最小的子数组，就是说返回数组中个数最小的连续子数组，这个连续子数组的和等于target：
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
i = 0
j = 0
total = 0
res = len(nums)+1
while(j total += nums[j] j+=1 while(total>=target): res = min(res , j-i) total -= nums[i] i+=1 if res == len(nums)+1: return 0 else: return res 还有一种是只用一个指针i，然后判断i-k的值和i的值到底符不符合题意，然后计算，例题：1456. 定长子串中元音的最大数目 class Solution: def maxVowels(self, s: str, k: int) -> int: if s is None or len(s)==0 or len(s) return 0 res= 0 count = 0 vowels = {'a', 'e', 'i', 'o', 'u'} for i in range(0,k): if s[i] in vowels: count = count +1 res = max(res, count) for i in range(k,len(s)): if s[i-k] in vowels: count = count -1 if s[i] in vowels: count = count +1 res = max(res,count) return res 递归法 有一个标准的模板：509. 斐波那契数 - 力扣（LeetCode）206. 反转链表 - 力扣（LeetCode）344. 反转字符串 - 力扣（LeetCode） recursion(int n): #####首先这个就是那个递归函数，n是输入的参数 if n == 0: ###终止条件，这个时不需的 return 0 m = recursion(n-1) ###拆解（如何递归到下一层） return m #返回值 以反转字符串这一题为例（最好的方法是双指针，但这里用递归）： class Solution: def reverseString(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead. """ if len(s)==0 or s==None: return left = 0 right = len(s)-1 self.reverse(s,left,right) return s def reverse(self, s, left,right): if left>=right: return self.reverse(s, left+1,right-1) s[left],s[right] = s[right],s[left] 回溯法 一般用于查找“所有的”这类题型。一个经典例题，【1，2，3】求所有子集，回溯法就是要先分层，然后套公式 22. 括号生成 - 力扣（LeetCode）78. 子集 - 力扣（LeetCode） class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: result = [[]] for i in range (1,len(nums)+1): self.backtracking(nums,i,[],result,0)######重点就是这个backtracking怎么定义 return result def backtracking(self,nums,length,subset,result,index): if len(subset)==length: ####这一块就是递归中的中止条件(剪枝的过程) result.append(subset[:]) return for i in range(index,len(nums)): subset.append(nums[i]) self.backtracking(nums,length ,subset,result,i+1)####这里i+1需要注意，因为不允许重复 subset.pop() ####记得pop，因为还要返回走另一条路，所以要将新加的删去 22. 括号生成 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 class Solution: def generateParenthesis(self, n: int) -> List[str]: result = [] str = '' self.backtracking(n, 0, 0 ,result , str) return result def backtracking(self, n ,left, right, result, str): if left return if left == right == n: result.append(str) if left < n: self.backtracking(n, left+1, right,result, str+'(') if left>right: self.backtracking(n,left,right+1,result,str+')') 分治法 应用了递归的思想，则需要一个终止条件，然后将大问题分解为小问题169. 多数元素 - 力扣（LeetCode）53. 最大子数组和 - 力扣（LeetCode） func(nums)——>int: return getmax(nums,0,len(nums)-1) def getmax(nums,left,right):###实际上还是递归，不过分成几个小问题递归 if left==right: return nums[left] ##### 终止条件 mid = left + (right-left)//2 leftmax = self.getmax(nums,left,mid) rightmax = self.getmax(nums,mid+1,right) return max(leftmax,rightmax) ###这只是一个例子，具体问题具体分析 一个例子：53. 最大子数组和 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 深度优先搜索（DFS） 从root开始，尽可能深的搜索一个分支，把一个分支搜索完，再去搜索下一个分支 78. 子集 - 力扣（LeetCode）938. 二叉搜索树的范围和 - 力扣（LeetCode）200. 岛屿数量 - 力扣（LeetCode） class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: result = [] self.dfs(nums,result,0,[]) return result def dfs(self, nums, result, index, subset): result.append(subset[:]) if index == len(nums): ##终止条件 return for i in range(index, len(nums)): subset.append(nums[i]) self.dfs(nums,result,i+1,subset) subset.pop() ###还是那道经典例题，【1，2，3】求子集 没有什么技巧，就好好理解吧，画个图理解 #结构就是先定义dfs，dfs肯定是一个递归，然后也许有循环，也许没有，总之肯定有一个标志符，index或者level ##层层递进，一般是+1，再dfs这样 广度优先搜索（BFS） 就是一层一层遍历，一般和队列，链表等结合，这两个例子都是二叉树 102. 二叉树的层序遍历 - 力扣（LeetCode）107. 二叉树的层序遍历 II - 力扣（LeetCode） from collections import deque class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: result = [] if root is None: return result q = deque([]) q.append(root) while len(q)>0: size = len(q) ls = [] while size>0: cur = q.popleft() ls.append(cur.val) if cur.left is not None: q.append(cur.left) if cur.right is not None: q.append(cur.right) size = size-1 result.append(ls[:]) return result 贪心算法 每一步都取最好最大的，然后看能不能达到结果，不能就返回？大概这意思吧，一般和回溯什么的结合一下322. 零钱兑换 - 力扣（LeetCode）（背包问题，也可以回溯）1217. 玩筹码 - 力扣（LeetCode）55. 跳跃游戏 - 力扣（LeetCode） class Solution: def canJump(self, nums: List[int]) -> bool: ''' 贪心： 先每一步都走到最远，然后判断下一步能不能走到这个最远距离，能走到的话， 那就再在这个最远距离内找最远距离 一直更新这个最远距离，直到走到末尾 如果以及到大最远了还是没有到达末尾那就输出false ''' rightmost = 0 for i in range(len(nums)): if i <= rightmost: rightmost = max(rightmost,nums[i]+i) if rightmost >= len(nums)-1: return True return False 并查集 模板 class UnionFind: def __init__(self, grid): row = len(grid) col = len(grid[0])##看题目给的数据是什么 self.root =[-1] * (row*col)###这里是定义一个数组的长度，n也可以 self.count = (row*col) ###一般会有一个计数的 for i in range(row*col): self.root[i] = i ####先把其节点定为自身 def find(self, x): if x ==self.root[x]: return self.root[x]#判断x的根节点是否是其本身，是就返回 else: self.root[x] = self.find(self.root[x])#不是的话，就寻找其根节点的根节点 return #**** self.root[x] ####这个是快速find def find(self, x): if x !=self.root[x]: self.root[x] = self.find(self.root[x])#不是的话，就寻找其根节点的根节点 return self.root[x] def union(self, x, y):#####这个函数是将两个数的节点改为一个 rootX = self.find(x) rootY = self.find(y) if rootX != rootY: self.root[rootX] = rootY ###将X的根节点改为Y的根节点 self.count -= 1 ####这个是快速union def union(self, x, y):#####这个函数是将两个数的节点改为一个 rootX = self.find(x) rootY = self.find(y) if rootX != rootY: if self.rank[rootX] > self.rank[rootY]: self.root[rootY] = rootX elif self.rank[rootX] < self.rank[rootY]: self.root[rootX] = rootY else: self.root[rootY] = rootX self.rank[rootX] += 1 记忆化搜索： 就是将已经算过的值，存起来，之后要用就直接取509. 斐波那契数 - 力扣（LeetCode）322. 零钱兑换 - 力扣（LeetCode） 动态规划 1、动态规划有三要素：初始状态，最终状态和方程式（状态方程式获得中间状态）2、动态规划一般用于：求有多少种方式，方法，路径；求最值：机器人从左到右的最大路径和；求存在性：有没有从左到右的一个路径可能509. 斐波那契数 - 力扣（LeetCode）62. 不同路径 - 力扣（LeetCode）121. 买卖股票的最佳时机 - 力扣（LeetCode）70. 爬楼梯 - 力扣（LeetCode）279. 完全平方数 - 力扣（LeetCode）221. 最大正方形 - 力扣（LeetCode） 动态规划比较难，但确实很有效 一个比较经典简单的问题：机器人从左上到左下一共有几种路径（只能往下往右走） 分析：一个位置的总路径，就是他上面的总路径加下面的总路径 class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [[1]*n for _ in range(m)] 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[-1][-1] 排序算法 ''' 快速排序 快速排序的思想就是：先顶一个基准，一般以数组第一个数为基准 然后大于基准的放到后面，小于基准的放到前面 同时用low和high两个指针来记录前面和后面，先while循环high 因为此时low已经作为基准了，相当于low是空的，先从high遍历，可以将high值先放入到low中 这样low和high交替互换，最终得到结果 用递归是，每一次base都将nums分为左右两个nums，总nums排序完后，分nums也需要排序 ''' class Solusion: def quicksort(self, nums, start, end): if start >= end: return ####这个是结束条件 low = start high = end base = nums[start] ##一般以第一个为基准 while low < high: while low < high and nums[high] >= base: high -= 1 ###如果大于基准就让其在右边不动，然后high指针往前挪 nums[low] = nums[high] ##这里是已经跳出循环了，也就是nums[high]小于base了，就将这个数移动到low的位置 while low < high and nums[low] < base: low += 1 nums[high] = nums[low] ##同理，也是已经跳出while循环了，将大于base的low移动到high的位置 nums[low] = base ###已经全部循环完了，low和high已经重合了，这个位置就是最终base要填入的位置，这里写成nums[high]也是一样的 self.quicksort(nums, start, low - 1) ###递归，第一轮排完序了，开始排序第二轮左边的nums，这时候，开始还是0，但结束就是low-1 self.quicksort(nums, low + 1, end) ###排序第二轮的右边 return nums a = Solusion() nums = [54, 26, 93, 17, 77, 31, 44, 55, 20] b = a.quicksort(nums, 0, len(nums)-1) print(b) ''' 归并排序 归并排序就是先通过一半一半这样分，直到分成一个一个的后， 然后两个两个这个合，一路向上回归 ''' def merge(left, right): ###这个一块是归并 result = [] while left and right: if left[0] < right[0]: result.append(left.pop(0)) else: result.append(right.pop(0)) if left: result += left else: result += right return result def merge_sort(lists): ####这一块是递推 if len(lists) <= 1: return lists mid = len(lists)//2 arr1 = lists[:mid] arr2 = lists[mid:] left = merge_sort(arr1) right = merge_sort(arr2) return merge(left, right) # lists = [17, 56, 71, 38, 61, 62, 48, 28, 57, 42] print(merge_sort(lists)) 一道经典例题200. 岛屿数量 DFS法：一个一个遍历，当遇到"1”时，结果就加1，然后就用dfs将其上下左右都变为0，然后继续往后遍历 class Solution: def numIslands(self, grid: List[List[str]]) -> int: if grid is None or len(grid) ==0: return 0 result = 0 row = len(grid) col = len(grid[0]) for i in range(0,row): for j in range(0,col): if grid[i][j] == '1': result += 1 self.dfs(grid, i, j, row,col) return result def dfs(self, grid, x, y, row, col): if x<0 or y<0 or x>=row or y>=col or grid[x][y] == '0': return grid[x][y] = '0' self.dfs(grid, x-1 , y, row,col) self.dfs(grid, x+1 , y, row,col) self.dfs(grid, x , y-1, row,col) self.dfs(grid, x , y+1, row,col) BFS法：道理是一样的，也是寻找1，找到一个1就将result+1，然后将周围的1变为0，但是BFS就和队列结合在一起，检测到一个1就加入到队列，然后循环再将其pop出去，再检测其周围的1，这样下去。队列的目的，应该就是使用while循环 from collections import deque class Solution: def numIslands(self, grid: List[List[str]]) -> int: if grid is None or len(grid) ==0: return 0 result = 0 row = len(grid) col = len(grid[0]) q = deque() for i in range(0,row): for j in range(0,col): if grid[i][j] == '1': result += 1 q.append([i,j]) grid[i][j] = '0' while(len(q))>0: cur = q.pop() x = cur[0] y = cur[1] if x-1>=0 and grid[x-1][y] =='1': grid[x-1][y] ='0' q.append([x-1,y]) if x+1 < row and grid[x+1][y] =='1': grid[x+1][y] ='0' q.append([x+1,y]) if y-1>=0 and grid[x][y-1] =='1': grid[x][y-1] ='0' q.append([x,y-1]) if y+1 < col and grid[x][y+1] =='1': grid[x][y+1] ='0' q.append([x,y+1]) return result 并查集法：这个方法就是首先将所有的值都找一个和她本身一样的一个祖先，然后遍历，一旦找到一个1，就将其上下左右的1的祖先都变成和他一个祖先，然后就可以将count-1，然后还有计算water(也就是0)的数量，要将所有的water也减去，这样算下来的就是岛屿的数量。 from collections import deque class UnionFind: def __init__(self, grid): row = len(grid) col = len(grid[0])##看题目给的数据是什么 self.root =[-1] * (row*col)###这里是定义一个数组的长度，n也可以 self.count = row*col for i in range(row*col): self.root[i] = i ####先把其节点定为自身 def find(self, x): if x ==self.root[x]: return self.root[x]#判断x的根节点是否是其本身，是就返回 else: self.root[x] = self.find(self.root[x])#不是的话，就寻找其根节点的根节点 return self.root[x] def union(self, x, y):#####这个函数是将两个数的节点改为一个 rootX = self.find(x) rootY = self.find(y) if rootX != rootY: self.root[rootX] = rootY ###将X的根节点改为Y的根节点 self.count -= 1 class Solution: def numIslands(self, grid: List[List[str]]) -> int: row =len(grid) col = len(grid[0]) if grid is None or len(grid)==0: return 0 water = 0 uf = UnionFind(grid) for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '0': water += 1 else: dinections = [[0,1], [0,-1],[1,0],[-1,0]] for d in dinections: x = i + d[0] y = j + d[1] #####这个用法很特殊，要好好看一下 if x>=0 and x uf.union(x*col+y, i*col+j) ##这一步就是为了同化操作，也是遍历了1的上 #下左右，然后将也为1 ###的祖先改为原本遍历到的1的祖先 return uf.count-water 又一道非常典型的题： 回溯法： class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: result = [[]] for i in range (1,len(nums)+1): self.backtracking(nums,i,[],result,0) return result def backtracking(self,nums,length,subset,result,index): if len(subset)==length: result.append(subset[:]) return for i in range(index,len(nums)): subset.append(nums[i]) self.backtracking(nums,length,subset,result,i+1) subset.pop() DFS法： class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: result = [] self.dfs(nums,result,0,[]) return result def dfs(self, nums, result, index, subset): result.append(subset[:]) if index == len(nums): return for i in range(index, len(nums)): subset.append(nums[i]) self.dfs(nums,result,i+1,subset) subset.pop() 扩展法： class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: result = [] result.append([]) for num in nums: temp = [] for res in result: r = res.copy() r.append(num) temp.append(r) for te in temp: result.append(te) return result 枚举： class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [[]] for num in nums: for index in range(len(res)): s = res[index] c = [num] res.append(s + c) return res ####res.append(s+b)中，s =[1], b=[2],加起来就是【1，2】，很神奇，记住 一类会议安排题目：leetcode会员题 思路：首先对结束时间升序排序，然后找出最早结束的一场作为开始， 然后就依次判断后一场的开始时间是不是比前一场要大，大就算进去 一般比如说出的类型为： [[0,2],[3,4],[4,8],[2,6],[6,7],[7,8]] s = [0, 3, 4, 2, 6, 7] f = [2, 4, 8, 6, 7, 8] ####这是排序过程 for i in range(len(f)): for j in range(0, len(f) - i - 1): if f[j] > f[j + 1]: f[j], f[j + 1] = f[j + 1], f[j] s[j], s[j + 1] = s[j + 1], s[j] print(s) print(f) ''' ziplist = list(zip(f, s)) zipsorted = sorted(ziplist) list1, list2 = zip(*zipsorted) f = list(list1) s = list(list2) print(s) print(f) ''' ####这个就是添加过程 def greedy(s, f, n): a = [True for x in range(n)] # 初始选择第一个活动 j = 0 for i in range(1, n): # 如果下一个活动的开始时间大于等于上个活动的结束时间 if s[i] >= f[j]: a[i] = True j = i else: a[i] = False return a A = greedy(s,f,6) res = [] for k in range(len(A)): if A[k]: res.append('({},{})'.format(s[k],f[k])) print(' '.join(res)) 输出：(0,2) (3,4) (6,7) (7,8) 暂时到这，之后有题目和方法再加。