编辑距离(一)，动态规划，空间O(min(m,n) 尾部元素str[i]和str[j]相等，不用编辑，编辑距离就是str1[:i]到str2[:j]的编辑距离。尾部元素str[i]和str[j]不等：修改，对应的编辑距离是str1[:i]到str2[:j]的编辑距离+1。尾部元素str[i]和str[j]不等：删除，对应的编辑距离是str1[:i]到str2[:j+1]的编辑距离+1。尾部元素str[i]和str[j]不等：添加，对应的编辑距离是str1[:i+1]到str2[:j]的编辑距离+1。 class Solution: def editDistance(self , str1: s...

主持人调度（二）,官方题解1精简版（7行）与超详细思路梳理 官方题解1挺巧妙的，试着梳理一下思路。求最小的主持人数，等价于求最大区间重叠数。然而区间在哪里具有最大重叠我们是不知道的，如果一个一个遍历去找时间得O(n^2)，如何O(nlogn)实现呢。 我们的目标是找最大重叠，只要起点终点不混，不同区间的起点交换或者终点交换并不会影响最大重叠。所以，对起点和终点分别进行排序，在排序后的起点终点构成新的区间上找最大重叠。由于起点终点都是排好序的，在每个新的区间内出现的其他区间的起点数+1就是该区间内的最大重叠数。 也就是说，我们只需要遍历每个新区间，然后依次统计每个区间内的最大重叠数，然后维护一个...

矩阵最长递增路径，dfs+动态规划 心路历程：看一眼题，求最长路径，欧，简单，就是从一个起点开始，用dfs把每条能走的道都走一遍，最后看所有的路中谁最长，类似于求树的深度嘛。根据这样的想法写完代码，什么，居然没有过。再瞄了一眼题，欧，原来起点不固定，那加个循环，把矩阵中所有点都遍历一边，这样总能找到最大值了吧，就像岛屿问题，写完提交，什么，居然超时了。欧，也是，里面涉及好多重复运算。怎么减少重复运算呢，咦，如果算一次记录点东西，就可以避免重复计算了撒。但是记录什么呢，欧，有了，每到一个点(i,j)，就记录以该点为起点的最长递增路径长。提交，什么，还是超时。突然想到，dfs的时候就已经遍历了很多...

盛水最多的容器，把求面积放入条件内，多一行代码，但会比官方题解快 class Solution: def maxArea(self , height: List[int]) -> int: res = left = 0 right = len(height)-1 while left < right: if height[left] < height[right]: res = max(res, (right-left)*height[left]) left += 1 else: res = max(res, (right-left)*height[right]) right...

旋转数组，完全基于两两交换实现数组移位，时间O(n)，空间O(1) 思路：不断让前m和尾m个元素交换，维护一个指针start，它是交换完元素的终点，未交换元素的起点。每交换完成m个元素，start往右移动m。要注意的边界条件是，当start靠近尾部时，交换区间会重叠，此时交换之后，重叠区域会被错误的交换到末尾。就需要把重叠区域移到start后，问题就从原来的把末尾m位移动到start后变成了把重叠区域移动到start后，即m=len(重叠区域)。继续交换，直到start+m越界。 class Solution: def solve(self , n: int, m: int, a: List[...

最长无重复子数组极简实现——8行 方法1：主要借助列表的in属性，内部属性更快，自己手写查找会超时。借助index属性可以直接跳到重复元素后，提升速度。双指针，如果不在子数组内，右边扩张，如果在子数组内，左边跳到重复元素后。 class Solution: def maxLength(self , arr: List[int]) -> int: i = j = max_len = 0 while j < len(arr): if arr[j] not in arr[i:j]: j += 1 else: i += arr[i:j].index(arr[j])+1 # 直接跳到重复值后...

寻找峰值，复杂一点的解法+对官方题解的理解 如果峰值存在于一个区间内，必有左端和右端单调性相反。由于没有想到官方题解 那种间接使用nums[−1]=nums[n]=−∞和间接得到峰值的方法，所以添加了几对数组首尾的边界条件。 对官方题解理解：数组首尾的单调性是已知的，左单增，右单减，所以官方题解直接利用这点，找到中点，如果此处是单减的nums[mid+1]<nums[mid]，则左、中单调性相反，左、中必然存在峰值，保留中点处较大者nums[mid]，因为它有可能就是峰值，此时区间缩小一半，区间首尾单调性同样是已知的，左单增，右单减。再次找到中点，如果此处是单增的nums[mid+1]&...

N皇后问题-官方题解简化版 典型的回溯-排列问题，关键在于判断当前位置放皇后是否合法。最费力的方法是把与当前位置同列，左斜线，右斜线的所有坐标都遍历一遍，看这些坐标中是否已经有皇后了，但这样会涉及很多没有必要的访问。由于两个点（i,j）(m,n)在一条斜线上会满足，abs(i-m)=abs(j-n)的数学关系，那么通过当前点和之前皇后的坐标，就可以直接判断两点是否在一条斜线上。所以只需遍历已放置的皇后位置即可知道当前点是否可以放置一个皇后。 class Solution: def Nqueen(self , n: int) -> int: visited = [] count = 0 d...

把数字翻译成字符串，动态规划，时间O(n)， 空间O(1) 数组任何一个位置的数字，既可以只看当前位置组成个位数，也可以结合之前位置构成多位数。由于字母编码只在1-26之间，所以只有两种方式——只取当前数字组成1位数编码或者取当前位置+前一个位置组成两位数编码。如果以nums[:i+1]译成字符串的可能数为状态dp[i]，它可以由dp[i-1]和dp[i-2]转移而来，这很类似于跳台阶，不过这里并不是每次都可以从两个地方来，需要满足条件。 class Solution: def solve(self , nums: str) -> int: dp1 = dp2 = 1 # dp1与dp2...

最长上升子序列(一)，动态规划 当前的元素，只有与之前的某个元素相接时才能组成最长上升子序列。只要之前元素比当前元素小，就可以相接，但最终与谁相接，则要看以谁结尾的上升子序列最长。相接即状态转移，若以元素i结尾的最长上升子序列长度为状态dp[i]，则它可能与之前i-1个状态相关，需遍历取满足条件的最大者作为其前一个状态。 class Solution: def LIS(self , arr: List[int]) -> int: if not arr: return 0 dp = [1]*len(arr) # 长度至少为1，故初始为1，dp[i]表示以arr[i]结尾的最长上升子序列 m...

矩阵的最小路径和，动态规划，时间O(mn)，空间O(m) 动态规划的核心：初始状态+状态转移方程 class Solution: def minPathSum(self , matrix: List[List[int]]) -> int: m, n = len(matrix), len(matrix[0]) dp = [0] for i in range(n): # 第一行状态 dp.append(dp[i]+matrix[0][i]) dp[0] = 50001 # 给一个足够大值值，保证不会从占状态过来 for i in range(1, m): for j in range(n):...

买卖股票的最好时机(四)，动态规划，时间O(kn)，空间O(k) 买需在卖后，卖需在买后，股票的持有和卖出状态不能统一成一个状态，需要分别表示两个状态。同样的，第j次交易需要在第j-1次交易完成（买入卖出）之后，不能统一成一个操作，需要分别表示每一次操作的两个状态，那么k次交易就有2k个状态。从子问题规模为1开始，逐步增加规模，最后到原问题规模，此时第k次不持有状态即为解。根据子问题更新状态时，只与前一个子问题的状态有关，所以不需要单独表示每个子问题的2k个状态。 class Solution: def maxProfit(self , prices: List[int], k: int) -...

兑换零钱，动态规划，不同的初始状态 i元可以不加当前一枚硬币凑成dp[i]，也可以加当前一枚硬币凑成dp[i-coin]+1。所以新状态需要综合dp[i]和dp[i-coin]+1。如果表达式不相同，原因在于dp初始化方式不同。 class Solution: def minMoney(self , arr: List[int], aim: int) -> int: if not aim: return 0 dp = [0]*(aim+1) # aim+1维dp数组，dp[i]表示能凑成i元的最小硬币数，dp[0]=0 for coin in arr: # 用每种硬币更新状态 dp[co...

最长公共子串，动态规划，时间O(mn)，空间O(min(m,n)*k), k为最长公共子序列长度（超时） 分析过程类似于：https://www.nowcoder.com/discuss/388075528203378688公共子串条件是：同时含有并且连续（[s1[i-1], s1[i]]与[s2[j-1], s1[j]]连续），存在很多局部情况，所以原问题的解不一定包含所有子问题的解，直接以最长公共子串为状态不好互相转换。以包含（i,j）点值的局部公共子串为状态，再维护一个最大最长公共子串。遍历m*n空间搜索满足条件的点，如果s1[i]=s2[j]，则同时含有的条件满足，现在只需要找到与之连...