提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

---

递归

70. 爬楼梯

• 问：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
• 答：
  $$f(n)=\{\begin{array}{ll}1,& \text{n=1}\\ 2,& \text{n=2}\\ f(n-1)+f(n-2),& \text{n>2}\end{array}$$

# 时间复杂度O(n^2)
# 暴力递归
class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""if n == 1:return 1if n == 2:return 2if n>2:return self.climbStairs(n-1)+self.climbStairs(n-2)

# 时间复杂度O(n)
# 哈希hashmap储存
hashmap = {}
class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""if n == 1:return 1if n == 2:return 2if n in hashmap.keys:return hashmap[n]else:result = self.climbStairs(n-1)+self.climbStairs(n-2)hashmap[n] = resultreturn result

---

112. 路径总和

• 问：
  • 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum
  • 判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum
  • 如果存在，返回 true ；否则，返回 false
• 答：
  $$Path(root,targerSum)=\{\begin{array}{ll}False,& \text{空}\\ root.val==targerSum?,& \text{root.left and root.right 都为空}\\ Path(root.left,targerSum-root.val)orPath(root.right,targerSum-root.val),& \text{都不为空}\end{array}$$

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def hasPathSum(self, root, targetSum):""":type root: TreeNode:type targetSum: int:rtype: bool"""if not root:return Falseif not root.left and not root.right:return root.val == targetSumelse:return self.hasPathSum(root.left,targetSum-root.val) or self.hasPathSum(root.right,targetSum-root.val) 

---

509. 斐波那契数

• 问：
  • 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。
  • 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
• 答：
  $$f(n)=\{\begin{array}{ll}0,& \text{n=0}\\ 1,& \text{n=1}\\ f(n-1)+f(n-2),& \text{n>1}\end{array}$$

---

f = {}
class Solution(object):def fib(self, n):""":type n: int:rtype: int"""if n == 0:return 0if n == 1:return 1if n in f.keys():return f[n]else:result = self.fib(n-1)+self.fib(n-2)f[n] = resultreturn result

---

---

分治

169. 多数元素

• 问：
  • 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
  • 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

class Solution(object):def majorityElement(self, nums):""":type nums: List[int]:rtype: int"""hashmap = {}count = 0for i in nums:if i in hashmap.keys():hashmap[i] +=1else:hashmap[i] = 1 max_ = max(hashmap.values())return [key for key,value in hashmap.items() if value == max_][0]

---

240.搜索二维矩阵 II — 二分查找

class Solution(object):def searchMatrix(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""import bisect #二分函数for row in matrix:idx = bisect.bisect_left(row,target)#如果列表里面不存在target 会返回可以插入的位置if idx < len(row) and row[idx] == target:return Truereturn False

#自己写二分函数
class Solution(object):def searchMatrix(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""for row in matrix:idx = self.search(row,target)if idx != -1:return Truereturn Falsedef search(self,nums,target):len_ = len(nums)right = len_-1left = 0while left <= right:middle = int(left+(right-left)/2)if nums[middle] < target:left = middle+1elif nums[middle] > target:right = middle-1else:return middlereturn -1

---

---

单调栈 —「找最近一个比当前值大/小」的问题

739. 每日温度

• 问：
  • 给定一个整数数组 temperatures ，表示每天的温度
  • 返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。
  • 如果气温在这之后都不会升高，请在该位置用 0 来代替。
• 答：
  • 遍历下标存入栈
  • 当找到与之匹配的下一个最大值时，出栈
  • 典型—从左往右:

class Solution(object):def dailyTemperatures(self, temperatures):""":type temperatures: List[int]:rtype: List[int]"""n = len(temperatures)stack = []ans = [0]*nfor ind,val in enumerate(temperatures):while stack and val > temperatures[stack[-1]]:clean_ind = stack.pop()ans[clean_ind] = ind-clean_indstack.append()return ans

从右往左：

class Solution(object):def dailyTemperatures(self, temperatures):""":type temperatures: List[int]:rtype: List[int]"""n = len(temperatures)stack = []ans = [0]*nfor i in range(n-1,-1,-1):t = temperatures[i]while stack and t >= temperatures[stack[-1]]:stack.pop()if stack:ans[i] = stack[-1] - istack.append(i)return ans

---

503. 下一个更大元素 II

• 问：
  • 给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
  • 数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
• 答：
  • 与739题 多的是需要遍历两次数组 取模遍历 因为最后一个数无法判断下一个更大元素

class Solution(object):def nextGreaterElements(self, nums):""":type nums: List[int]:rtype: List[int]"""n = len(nums)stack = []ans = [-1]*n#从左往右# for i in range(n*2-1):#     val = nums[i%n]#     while stack and val>nums[stack[-1]]:#         clean_ind = stack.pop()#         ans[clean_ind] = val#     stack.append(i%n)#从右往左for i in range(n*2-2,-1,-1):val = nums[i%n]while stack and val >= nums[stack[-1]]:stack.pop()if stack:ans[i%n] = nums[stack[-1]]stack.append(i%n)return ansnums = [1,2,1]
a = Solution().nextGreaterElements(nums)
print(a)

---

84. 柱状图中最大的矩形

• 问：
  • 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
  • 求在该柱状图中，能够勾勒出来的矩形的最大面积。
• 答：
  • 暴力解法 O(n^2)
    • 找到该长度的左边界与右边界，右-左+1=宽度
    • 左右两边都必须>=当前长度
    • 宽度*长度的max值

class Solution(object):def largestRectangleArea(self, heights):""":type heights: List[int]:rtype: int"""h_len = len(heights)max_ = 0for i in range(h_len):left = iright = iwhile left-1 >= 0 and heights[left-1] >= heights[i]:left-=1while right+1 >= 0 and heights[right+1] >= heights[i]:right+=1max_ = max(heights[i]*(right-left+1),max_)return max_

• 单调栈 O(n)
  • 找到左右边界最小值的index 先进后出原则
  • right_ind - left_ind -1 = 宽度

class Solution(object):def largestRectangleArea(self, heights):""":type heights: List[int]:rtype: int"""len_ = len(heights)stack = []left = [0]*len_right = [0]*len_for i in range(len_):val = heights[i]while stack and heights[stack[-1]]>=val:stack.pop()left[i] =stack[-1] if stack else -1stack.append(i)stack = []for i in range(len_):val = heights[i]while stack and heights[stack[-1]]>=val:stack.pop()right[i] =stack[-1] if stack else len_stack.append(i)return max([(heights[i]*(right[i]-left[i]-1)) for i in range(len_)])

---

85. 最大矩形

• 问：
  • 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
• 答：
  • 将二维转换为求柱状图最大的矩形

class Solution(object):def maximalRectangle(self, matrix):""":type matrix: List[List[str]]:rtype: int"""if not matrix or not matrix[0]:return 0# Initialize the height arraym, n = len(matrix), len(matrix[0])height = [0] * (n + 1)  # Adding an extra 0 height for simplificationmax_area = 0for i in range(m):for j in range(n):# Update the height arrayif matrix[i][j] == '1':height[j] += 1else:height[j] = 0# Use a stack to find the maximum rectangle area in the histogramstack = []for j in range(n + 1):while stack and height[stack[-1]] > height[j]:h = height[stack.pop()]w = j if not stack else j - stack[-1] - 1max_area = max(max_area, h * w)stack.append(j)return max_area

---

---

并查集

• 并查集属于一种数据结构

• 主要分为合并与查询

  • 初始化

  father = []	#父节点
  def init(n):for i in range(n):father[i] = i
  

  • 查询

  def find(x):if father[x] == x:return xelse:return find(father[x])
  

  • 合并

  def merge(i,j):fa[find[i]] = find[j]#1->2->3->4()
  

  • 合并（路径压缩）

  #1->4 2->4 3->4
  def find(x):if father[x] == x:return xelse:father[x] = find(father[x])return father[x]

---

684. 冗余连接

• 问：

  • 树可以看成是一个连通且 无环 的 无向 图。
  • 给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
  • 请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

• 答：

  • 连接两个节点，找出每个节点指向的节点
  • 如果有一个节点两个方向同时指向一个节点，那必定会形成环
  • 1<-2<-3<-4 and1<-4 这必定会形成环

class Solution(object):def findRedundantConnection(self, edges):""":type edges: List[List[int]]:rtype: List[int]"""n = len(edges)father = list(range(n+1))#初始化#查询头节点def find(index):if father[index]!=index:#说明头节点不是自己#找头节点 并指向头节点father[index] = find(father[index])else:	#是头节点return father[index]#合并两个节点 指向头节点def union(node1,node2):#将节点2指向1father[find(node1)] = find(node2)for node1,node2 in edges:#如果两个节点的头节点不一致 合并两个节点if find(node1) != find(node2):union(node1,node2)else: #如果遍历中两个节点的头节点一致 说明是会形成环的return [node1,node2]

---

547. 省份数量

• 问：
  • 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连
  • 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
  • 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
  • 返回矩阵中 省份 的数量。

class Solution(object):def findCircleNum(self, isConnected):""":type isConnected: List[List[int]]:rtype: int"""n = len(isConnected)father = list(range(n))def find(index):if father[index] != index:father[index] =find(father[index])return father[index]def union(node1,node2):if find(node1) != find(node2):father[find(node1)] = find(node2)for i in range(n):for j in range(i+1,n):if isConnected[i][j]==1:union(i,j)return sum(father[i] == i for i in range(n))

---

200. 岛屿数量

• 问：
  • 给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
  • 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
  • 此外，你可以假设该网格的四条边均被水包围

class unionfind(object):def __init__(self,grid):x = len(grid)y = len(grid[0])self.father = [-1]*(x*y)self.count = 0for i in range(x):#行for j in range(y):#列if grid[i][j] == '1':self.father[i*y+j] = i*y+jself.count += 1def find(self,index):if self.father[index] != index:self.father[index] = self.find(self.father[index])return self.father[index]def union(self,node1,node2):n1 = self.find(node1)n2 = self.find(node2)if n1 != n2:self.father[n1] = n2self.count -= 1def getCount(self):return self.count
class Solution(object):def numIslands(self, grid):""":type grid: List[List[str]]:rtype: int"""m,n = len(grid),len(grid[0])if m == '0':return uf = unionfind(grid)for i in range(m):for j in range(n):if grid[i][j] == '1':for node1,node2 in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:if 0<=node1<m and 0<=node2<n and grid[node1][node2] == '1':ori = i*n+jnew = node1*n+node2uf.union(ori,new)return uf.getCount()

---

---

滑动窗口-左右双指针

模板–一般是选出某个字段、子串、序列在某种情况下的最长最短

#right,left,result,bestresult
#最长
while (right<len()):#窗口扩大，加入right对应元素，更新resultwhile (result?):	#不满足要求 移动左指针#窗口缩小，移除left对应的元素，left右移	#更新最优结果bestresultright+=1
return bestresult
#最短
while (right<len()):#窗口扩大，加入right对应元素，更新resultwhile (result?):	#满足要求 移动左指针#更新最优结果bestresult#窗口缩小，移除left对应的元素，left右移	right+=1
return bestresult

---

209. 长度最小的子数组

• 问：
  • 给定一个含有 n 个正整数的数组和一个正整数 target 。
  • 找出该数组中满足其总和大于等于 target 的长度最小的子数组[numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

class Solution(object):def minSubArrayLen(self, target, nums):""":type target: int:type nums: List[int]:rtype: int"""n = len(nums)right,left,result,bestresult = 0,0,0,0while(right<n):result = result+nums[right]while result>=target:if bestresult==0 or right-left+1<bestresult:bestresult = right-left+1result = result-nums[left]left += 1right+=1return bestresult

---

3. 无重复字符的最长子串

• 问：
  • 给定一个字符串 s ，请你找出其中 不含有重复字符的 最长
    子串 的长度。

class Solution(object):def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""right,left,result,bestresult = 0,0,[],0while right<len(s):while s[right] in result:result.remove(s[left])left+=1bestresult = max(bestresult,right-left+1)result.append(s[right])right+=1return bestresult

---

1004. 最大连续1的个数 III

• 问：
  给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

class Solution(object):def longestOnes(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""right,left,result,bestresult = 0,0,0,0while right < len(nums):while k==0 and nums[right]==0:if nums[left]==0:k+=1left+=1if nums[right] == 0:k-=1            result = right-left+1bestresult = max(bestresult,result)right+=1return bestresult

---

1208. 尽可能使字符串相等

• 问：
  • 给你两个长度相同的字符串，s 和 t。
  • 将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。
  • 用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
  • 如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。
  • 如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

class Solution(object):def equalSubstring(self, s, t, maxCost):""":type s: str:type t: str:type maxCost: int:rtype: int"""right,left,result,bestresult = 0,0,0,0while right<len(s):result += abs(ord(s[right])-ord(t[right]))while result>maxCost:result -= abs(ord(s[left])-ord(t[left]))left+=1bestresult = max(bestresult,right-left+1)right+=1return bestresult

---

---

前缀和

• 假设数组$A=[a_1,a_2,a_3...,a_n]$
• 前缀和：
  $$prefix[1]=a_1$$
  $$prefix[2]=a_1+a_2$$
  $...$
  $$prefix[n]=a_1+a_2+...+a_n$$
• 前缀和做差分
  $$prefix[n]-prefix[n-1]=a_n$$
  $$prefix[n-1]-prefix[n-2]=a_{n-1}$$
  $...$

---

724. 寻找数组的中心下标

• 问：
  • 给你一个整数数组 nums ，请计算数组的 中心下标 。
  • 数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
  • 如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
  • Z F如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

class Solution(object):def pivotIndex(self, nums):""":type nums: List[int]:rtype: int"""    total = sum(nums)   sum_ = 0for i in range(len(nums)):if sum_*2+nums[i] == total:return isum_ += nums[i]return -1      

---

560. 和为 K 的子数组

• 问：
  • 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
  • 子数组是数组中元素的连续非空序列。

        #暴力枚举# count = 0# for i in range(len(nums)):#     sum_ = 0#     for j in range(i,-1,-1):#         sum_ += nums[j]#         if sum_ == k:#             count+=1# return count#hashmap 前缀和pre,count,hashmap = 0,0,{0:1}   #哈希表记录前缀和出现的次数初始化 前缀和为0的时候是出现了一次的for i in range(len(nums)):pre+=nums[i]    #前缀和#记录出现的次数if pre-k in hashmap.keys():#如何存在prei-k = prej的情况说明存在和为k的子数组count += hashmap[pre-k]#将前缀和记录于hashmap中hashmap[pre] = hashmap.setdefault(pre,0)+1    #pre出现过+1 没出现过创建键值return count

---

437. 路径总和 III

• 问：
  • 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
  • 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

#前缀和 + 递归
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def pathSum(self, root, targetSum):""":type root: TreeNode:type targetSum: int:rtype: int"""hashmap = {0:1}def dfs(root,pre):if not root:return 0count = 0pre += root.val #前缀和if pre-targetSum in hashmap.keys():count += hashmap[pre-targetSum]hashmap[pre] = hashmap.setdefault(pre,0)+1  #将前缀和出现的次数放入map中# 递归count += dfs(root.right,pre)count += dfs(root.left,pre)hashmap[pre] -=1	#递归时候 防止count再计算多次return countreturn dfs(root,0)    

---

1248. 统计「优美子数组」

• 问：
  • 给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
  • 请返回这个数组中 「优美子数组」 的数目。

class Solution(object):def numberOfSubarrays(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""pre,count,hashmap=0,0,{0:1}for i in range(len(nums)):pre += nums[i]%2 #求余数if pre-k in hashmap.keys():count+=hashmap[pre-k]hashmap[pre] = hashmap.setdefault(pre,0)+1return count

---

---

差分

• 假设数组$A=[a_1,a_2,a_3...,a_n]$
• 差分：
  $$diff[1]=a_1$$
  $$diff[2]=a_2-a_1$$
  $...$
  $$diff[n]=a_n-a_{n-1}$$
• 对差分进行前缀和
  $$diff[1]=a_1$$
  $$diff[1]+diff[2]=a_2$$
  $...$
  $$diff[1]+diff[2]+...+diff[n]=a_n$$

---

1094. 拼车

• 问：
  • 车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
  • 给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
  • 当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

class Solution(object):def carPooling(self, trips, capacity):""":type trips: List[List[int]]:type capacity: int:rtype: bool"""max_ = max([i[2] for i in trips])diff =[0]*(max_+1)count = 0for num_i,from_i,to_i in trips:diff[from_i] += num_idiff[to_i]-=num_ifor i in range(max_+1):count += diff[i]if count > capacity:return Falsereturn True

---

121. 买卖股票的最佳时机

• 问：
  • 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
  • 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
  • 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""min_price = int(1e9)max_profit = 0for p in prices:max_profit = max(p-min_price,max_profit)min_price =min(min_price,p)return max_profit

---

---

拓扑排序-广度/深度优先搜索

---

• 问：
  • 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
  • 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
  • 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

210. 课程表 II

class Solution(object):def findOrder(self, numCourses, prerequisites):""":type numCourses: int:type prerequisites: List[List[int]]:rtype: List[int]"""#广度优先搜索 从入度出发import collectionsedges = collections.defaultdict(list) #节点的入度indeg = [0]*numCoursesfor i in prerequisites:#遍历入度edges[i[1]].append(i[0])indeg[i[0]] += 1q = [i for i in range(len(indeg)) if indeg[i] == 0]result = []while q:u = q.pop(0)    #将入度为0剔除 放入到result中排序result.append(u)for i in edges[u]:indeg[i] -= 1if indeg[i] == 0:q.append(i)if len(result) != numCourses:result = []return result

---

---

字符串

5. 最长回文子串-动态规划-递归的优化

• 问：给你一个字符串 s，找到 s 中最长的回文子串
• 答：

#暴力枚举 时间复杂度O(n^3)
class Solution(object):def longestPalindrome(self, s):""":type s: str:rtype: str"""max_len = 1begin = 0for i in range(0,len(s)-1):for j in range(i+1,len(s)):if j+1-i>max_len and self.validationPalindrome(i,j,s):max_len = j+1-ibegin = iprint(i, j, max_len)return s[begin:begin+max_len]def validationPalindrome(self,left,right,s):while left<right:if s[left] != s[right]:return Falseelse:left += 1right -= 1return True

• 动态规划 ----本质是缩时间涨空间
  • 头尾如果不是相同的字段 必定不是回文子串,递归公式
    $$f(i,j)=\{\begin{array}{ll}True,& \text{i = j}\\ False,& \text{f(i) != f(j)}\\ True,& \text{f(i) = f(j) and j-1<3}\\ f(i+1,j-1),& \text{f(i) = f(j) and j-1>3}\end{array}$$
  • 找寻最长子串

#动态规划
class Solution(object):def longestPalindrome(self, s):""":type s: str:rtype: str"""max_len = 1begin = 0if len(s)<2:return s# s = list(s)dp = [[False] * len(s) for _ in range(len(s))]for i in range(len(s)):dp[i][i] = Truefor j in range(len(s)):for i in range(0,j):if s[i] != s[j]:dp[i][j] = Falseelse:if j-i<3:dp[i][j] = Trueelse:dp[i][j] = dp[i+1][j-1]if dp[i][j] and j-i+1 > max_len:max_len = j-i+1 begin = ireturn s[begin:begin+max_len]

20. 有效的括号

• 问：给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
  有效字符串需满足：
• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 每个右括号都有一个对应的相同类型的左括号。
• 答：
  • 栈先进后出
  • hashmap
  • 判定条件：
    • 如果长度为奇数 必定无效
    • 遍历中或结束 如果没有在hashmap里面找到对应的键 字符串无效
      • 遍历中 栈为空 但找到了键 字符串无效
      • 遍历中 栈最后一个元素 与 键对应的值 不符 字符串无效

class Solution(object):def isValid(self, s):""":type s: str:rtype: bool"""pairs = {")": "(","]": "[","}": "{",}if len(s)%2 == 1:return Falsestack = [] #栈for st in s:if st in pairs:if not stack or pairs[st] != stack[-1]:stack.pop(st)	#出else:stack.append(st)	#进return not stack #只有栈为空时 字符串才有效

---

43. 字符串相乘

• 问：给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
• 答：
  • 从右往左遍历乘数
  • 将乘数的每一位与被乘数相乘得到对应的结果
  • 再将每次得到的结果累加
  • 条件：
    • 0*0 = 0
    • 乘积长度=len(num1)+len(num2) — ansArr 用于存储乘积

class Solution(object):def multiply(self, num1, num2):""":type num1: str:type num2: str:rtype: str"""if num1 == '0' or num2 == '0':return '0'n1 = len(num1)n2 = len(num2)stack = [0]*(n1+n2)for i in range(n1-1,-1,-1):for j in range(n2-1,-1,-1):stack[i+j+1] = int(num1[i])*int(num2[j])for i in range(len(stack)-1,0,-1):stack[i-1] += stack[i]//10	#10进1stack[i] %= 10	#进1后的余数index = 1 if stack[0] == 0 else 0return ''.join(str(i) for i in stack[index:])

---

43. 复原 IP 地址

---

---

二分查找

• 模板

#左边为蓝色区域 右边为红色区域 找定义的边界
l = -1 r = N
while l+1 != r:mid = int((l+r)/2)if isbule(m):l = melse:r = m
return l r...

---

34. 在排序数组中查找元素的第一个和最后一个位置

• 问：
  • 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
  • 如果数组中不存在目标值 target，返回 [-1, -1]。
  • 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""if not nums:return -1n = len(nums)right,left = n,-1while left+1!=right:mid = int((right+left)/2)if nums[mid] == target:return midif nums[0] <= nums[mid]:if nums[0]<=target<nums[mid]:right = midelse:left = midelse:if nums[mid]<target<=nums[n-1]:left = midelse:right = midreturn -1

---

33. 搜索旋转排序数组

• 问：
  • 整数数组 nums 按升序排列，数组中的值 互不相同 。
  • 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
  • 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
  • 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""if not nums:return -1n = len(nums)right,left = n,-1while left+1!=right:mid = int((right+left)/2)if nums[mid] == target:return midif nums[0] <= nums[mid]:if nums[0]<=target<nums[mid]:right = midelse:left = midelse:if nums[mid]<target<=nums[n-1]:left = midelse:right = midreturn -1

---

---

BFS/DFS/回溯

529. 扫雷游戏 BFS

board = [["E","E","E","E","E"],["E","E","M","E","E"],["E","E","E","E","E"],["E","E","E","E","E"]]
click = [3,0]
direction = [[0,0,1,-1,1,-1,1,-1],[1,-1,0,0,1,-1,-1,1]
]
def is_avaliable(x,h):return 0<=x<=h-1queue = []
skip = []   #记录
visited = []
def bfs(board,x,y):h = len(board)l = len(board[0])queue.append([x,y])while len(queue)!=0:cur = queue.pop(0)x = cur[0]y = cur[1]skip.append(cur)#！！记录 空组 Bcount = 0#周围的地雷for i in range(8):x_new = x+direction[0][i]y_new = y+direction[1][i]print(x_new, y_new,'============')if not (is_avaliable(x_new,h) and is_avaliable(y_new,l)):print('--')continue #超过边界 啥也不干 继续print(x_new, y_new)if board[x_new][y_new]=='M':count+=1print(count)if count>0:#说明当前xy的数值=countboard[x][y]=str(count)else:#周围没有地雷board[x][y] = 'B'#四周8个方位都可以去探索一下for i in range(8):x_new = x + direction[0][i]y_new = y + direction[1][i]print(x_new, y_new, '============')if is_avaliable(x_new, h) and is_avaliable(y_new, l) and board[x_new][y_new]=='E' and [x_new,y_new] not in visited:queue.append([x_new,y_new])visited.append([x_new,y_new])x = click[0]
y = click[1]
if board[x][y] == 'M':board[x][y]='X'
else:bfs(board,x,y)print(board)

---

815. 公交路线 BFS

class Solution(object):def numBusesToDestination(self, routes, source, target):""":type routes: List[List[int]]:type source: int:type target: int:rtype: int"""import collectionsh = len(routes)bus_ =collections.defaultdict(list)for i in range(h):for j in routes[i]:bus_[j].append(i)#if source not in bus_ or target not in bus_:return -1 if source != target else 0queue = [source]res = {source:0}while queue:cur = queue.pop(0)x = curcount = res[x]for i in bus_[x]:if routes[i]:for j in routes[i]:if j not in res:res[j]=count+1queue.append(j)routes[i] = Nonereturn res.get(target,-1)

---

---

动态规划

139. 单词拆分

class Solution(object):def wordBreak(self, s, wordDict):""":type s: str:type wordDict: List[str]:rtype: bool"""n = len(s)dp = [False]*(n+1)dp[0] = Truefor i in range(n):for j in range(i+1,n+1):if dp[i] and s[i:j] in wordDict:dp[j] = Truereturn dp[n]

---

---

总结

提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。