企业官网建设流程全解析

网站的主题与风格说明,长春网站开发公司哪家好,国外免费舆情网站有哪些软件,天津市建设厅注册中心网站1.子数组/子串是连续的 子序列不一定是连续的 abcde中ace就是子序列2.给定两个字符串#xff0c;求两个的最长公共子序列#xff0c;dfs(i,j)定义#xff1a;序列1的前i个字母和序列2的前j个字母 的最长公共子序列下一个问题#xff1a;序列1前i-1个字母和序列二前j-1个…1.子数组/子串是连续的 子序列不一定是连续的 abcde中ace就是子序列2.给定两个字符串求两个的最长公共子序列dfs(i,j)定义序列1的前i个字母和序列2的前j个字母 的最长公共子序列下一个问题序列1前i-1个字母和序列二前j-1个字母序列1前i个字母和序列二前j-1个字母序列1前i-1个字母和序列二前j个字母可以简化dfsi,j dfsi-1j-11 s[i]t[j]dfsi,j maxdfs(i-1,j),dfs(i,j-1)) s[i]≠t[j]最长公共子序列1.回溯法时间复杂度 nm 空间复杂度 nmclass Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: n len(text1) m len(text2) cache def dfs(i,j): if i0 or j0: return 0 if text1[i]text2[j]: return dfs(i-1,j-1)1 else: return max(dfs(i-1,j),dfs(i,j-1)) return dfs(n-1,m-1)2.递推先得到递推公式f[i][j] f[i-1][j-1]1 s[i]t[j]max(f[i-1][j],f[i][j-1] s[i]≠t[j]f [[0]*(m1)for _ in range(n1)] for i,x in enumerate(text1): for j,y in enumerate(text2): if xy: f[i1][j1] f[i][j]1 else: f[i1][j1] max(f[i][j1],f[i1][j]) return f[n][m]3.空间优化可以发现更新f[i1][j1]需要三个值左边上面左上但左上的数据会被覆盖引入pre变量pre f[0]不能写在循环外面核心原因是进入 j 循环后pre会逐步保存「上一个 j 位置的旧值」精准匹配二维 DP 中dp[i-1][j-1]的语义。空间复杂度 mf [0]*(m1) for i,x in enumerate(text1): pre f[0] for j,y in enumerate(text2): tmp f[j1] if xy: f[j1] pre1 else: f[j1] max(f[j1],f[j]) pre tmp return f[m]编辑距离为什么叫编辑距离“编辑”指对字符串的修改操作插入、删除、替换是文本编辑中最基础的三种操作距离 操作次数越少差异越小距离越近dfs(i, j)的定义表示将s[0..i]s 的前 i1 个字符转换为t[0..j]t 的前 j1 个字符所需的最少操作数。dfs(i-1, j) 1→ 对应「删除操作」含义先将s[0..i-1]转换为t[0..j]操作数是dfs(i-1, j)再删除s[i]1 次操作dfs(i, j-1) 1→ 对应「插入操作」含义先将s[0..i]转换为t[0..j-1]操作数是dfs(i, j-1)再插入t[j]到 s 中1 次操作。dfs(i-1, j-1) 1→ 对应「替换操作」含义先将s[0..i-1]转换为t[0..j-1]操作数是dfs(i-1, j-1)再将s[i]替换为t[j]1 次操作而如果s[i] t[j]则不需要任何操作直接继承dfs(i-1, j-1)的结果这是 “无操作” 的情况。1.回溯法1.回溯公式dfs(i,j) dfs(i-1,j-1) if s[i] t[j]dfs(i,j) min(dfs(i,j-1),dfs(i-1,j),dfs(i-1,j-1)) 1 if s[i] ≠ t[j]插入 删除 替换2.边界条件if i0:return j1 把j全加一遍就相同了if j0:return i1 把i全删了就相同了class Solution: def minDistance(self, word1: str, word2: str) - int: n len(word1) m len(word2) cache def dfs(i,j): if i0:return j1 if j0:return i1 if word1[i]word2[j]: return dfs(i-1,j-1) else: return min(dfs(i,j-1),dfs(i-1,j),dfs(i-1,j-1))1 return dfs(n-1,m-1)2.递推我卡住的地方if i0:return j1if j0:return i1 怎么转换到二维数组里首先 dfs 的定义是将 text1 前 i 转换为 text2 前 j 最少需要的操作次数DP 的f[0][j]对应递归的i-1此时 DP 的j对应递归的j-1→ 应返回(j-1)1 j而非j1综上i0 对应的是 f[0][j] 数组的第一行 j1 在这是 jj0对应的是 f[i][0]数组的第一列 i1在这是i所以边界条件for j in range(m1):f[0][j] jfor i in range(n1):f[i][0] if [[0]*(m1)for _ in range(n1)] for j in range(m1): f[0][j] j for i in range(n1): f[i][0] i for i,x in enumerate(word1): for j,y in enumerate(word2): if xy: f[i1][j1] f[i][j] else: f[i1][j1] min(f[i1][j],f[i][j1],f[i][j])1 return f[n][m]3.空间优化和最长公子序列不同的是这个题的二维数组的第一行和第一列是动态的而最长公子序列的第一行和第一列都是0所以这个题要考虑的更多1.一维数组的创建f [j for j in range(m1)] 并不是简单的创了一个全是0 的数组2.pre f[0] f[0] i1 pre记录旧值f[0] i1对应的是dfs的 for i in range(n1):f[i][0] i的操作综合起来达到动态的f[0]的效果f [j for j in range(m1)] for i,x in enumerate(word1): pre f[0] f[0] i1 for j,y in enumerate(word2): temp f[j1] if xy: f[j1] pre else: f[j1] min(f[j],f[j1],pre) 1 pretemp return f[m]最长递增子序列1.回溯法若用常见的选或不选思路进行回溯会递归遍历所有可能的子序列比如数组长度为 n 时子序列总数是 2ⁿ修改思路dfs(i)专注于 “以 i 结尾” 的子序列长度外部遍历所有i是为了覆盖 “以任意元素结尾” 的所有可能从而得到全局最长长度。此时dfs(i)的定义以nums[i]结尾的最长递增子序列长度外边再遍历一遍所有结尾情况就能得出答案了回溯公式dfs(i) max {dfs(j)} 1 ji and nums[j]nums[i]回溯代码def dfs(i):temp 0for j in range(i):if nums[j] nums[i]:temp max(temp,dfs[j])return temp1class Solution: def lengthOfLIS(self, nums: List[int]) - int: n len(nums) ans 0 cache def dfs(i): temp0 for j in range(i): if nums[j]nums[i]: temp max(temp,dfs(j)) return temp1 for i in range(n): ans max(ans,dfs(i)) return ans2.递推递推公式f[i] max{f(j)} 1 ji and nums[j]nums[i]f [0]*n for i in range(n): for j in range(i): if nums[j]nums[i]: f[i] max(f[i],f[j]) f[i] 1 return max(f)