企业官网建设流程全解析

自己做的网站怎样赚钱,胶州哪家公司做网站,多用户商城系统的优势,延吉有没有做网站的1.爬楼梯1.最关键的一点就是得知道dfs#xff08;i#xff09;代表的什么代表一直到台阶i的时候有多少种走法2.这样就能得到dfs#xff08;i#xff09;dfs#xff08;i-1#xff09;dfs#xff08;i-2#xff09;3.dfs#xff08;0#xff09; 1因为dfs#xff08;…1.爬楼梯1.最关键的一点就是得知道dfsi代表的什么代表一直到台阶i的时候有多少种走法2.这样就能得到dfsidfsi-1dfsi-23.dfs0 1因为dfs22 dfs11 所以dfs0必须等于1回溯代码时间复杂度2^n 空间复杂度nclass Solution: def climbStairs(self, n: int) - int: def dfs(i): if i 1: return 1 return dfs(i-1)dfs(i-2) return dfs(n)记忆型代码cachecache是装饰器必须紧贴在被装饰的函数定义上方时间复杂度n 空间复杂度n递推型代码时间复杂度n 空间复杂度nclass Solution: def climbStairs(self, n: int) - int: f [0]*(n1) f[0]f[1]1 for i in range(2,n1): f[i]f[i-1]f[i-2] return f[n]怎么创建数组ff【0】*n1我写的是f [0]*n这样会产生一个长度为n的数组那就没有f[n]了最大是f[n-1]所以需要一个长度为n1的空间优化时间复杂度n 空间复杂度1class Solution: def climbStairs(self, n: int) - int: f0f11 for i in range(n-1): newff0f1 f0 f1 f1 newf return f12.使用最小花费爬楼梯回溯法我错误的地方if i1: return min(cost[0],cost[1])i为0或者1 的时候取什么值读题目没读懂你可以选择从下标为0或下标为1的台阶开始爬楼梯结合dfsi的定义到第i层台阶需要花费多少钱所以dfs(0),dfs(1)到第0第1层不需要钱时间2^n空间nclass Solution: def minCostClimbingStairs(self, cost: List[int]) - int: n len(cost) def dfs(i): if i1: return min(cost[0],cost[1]) return min(dfs(i-1)cost[i-1],dfs(i-2)cost[i-2]) return dfs(n)记忆性cachecache必须依附于装饰的函数cache是装饰器必须紧贴在被装饰的函数定义上方时间复杂度n 空间复杂度nclass Solution: def minCostClimbingStairs(self, cost: List[int]) - int: n len(cost) cache def dfs(i): if i1: return 0 return min(dfs(i-1)cost[i-1],dfs(i-2)cost[i-2]) return dfs(n)递推型代码时间复杂度n 空间复杂度nclass Solution: def minCostClimbingStairs(self, cost: List[int]) - int: n len(cost) f [0]*(n1) f[0]f[1]0 for i in range(2,n1): f[i] min(f[i-1]cost[i-1],f[i-2]cost[i-2]) return f[n]空间优化时间复杂度n 空间复杂度1class Solution: def minCostClimbingStairs(self, cost: List[int]) - int: n len(cost) f0f10 for i in range(2,n1): newf min(f1cost[i-1],f0cost[i-2]) f0 f1 f1 newf return f13.爬楼梯Ⅱ回溯法cache多了一个跳三阶和cost计算公式其实没啥本质区别多计算一个dfs2其实也不用还是只需要计算 i0 和i 1计算i2是怕 i-3的时候越界但其实会归到i0的地方min(dfs(i-1)costs[i-1]1,dfs(i-2)costs[i-1]4,dfs(i-3)costs[i-1]9)class Solution: def climbStairs(self, n: int, costs: List[int]) - int: cache def dfs(i): if i0: return 0 if i1: return costs[0]1 return min(dfs(i-1)costs[i-1]1,dfs(i-2)costs[i-1]4,dfs(i-3)costs[i-1]9) return dfs(n)递推自己写的代码ac但是相比灵神冗余但是对自己来说好理解class Solution: def climbStairs(self, n: int, costs: List[int]) - int: f[0]*(n1) f[0] 0 f[1] costs[0]1 if n1: f[2] min(f[1]costs[1]1,f[0]costs[1]4) for i in range(3,n1): f[i] min(f[i-1]costs[i-1]1,f[i-2]costs[i-1]4,f[i-3]costs[i-1]9) return f[n]空间优化太冗余了看着都想笑主要就是对i2的判断class Solution: def climbStairs(self, n: int, costs: List[int]) - int: f0 0 f1 costs[0]1 if n1: f2 min(f1costs[1]1,f0costs[1]4) for i in range(3,n1): newf min(f2costs[i-1]1,f1costs[i-1]4,f0costs[i-1]9) f0 f1 f1 f2 f2 newf if n1: return f1 if n1: return f2灵神版class Solution: def climbStairs(self, _, costs: List[int]) - int: f0 f1 f2 0 for c in costs: f0, f1, f2 f1, f2, min(f0 9, f1 4, f2 1) c return f2 。4.打家劫舍房子首尾相连就是在打家劫舍的基础上多加一个判断nums[0]如果取了nums[0]做第三座房子到倒数第二座房子的打家劫舍没取 做第二家房子到最后一家房子的打家劫舍我的错误因为在rob里面又嵌套了一个rob1所以要注意参数里面的就不是nums[ ]class Solution: def rob(self, nums: List[int]) - int: n len(nums) def rob1(arr): f0f10 for x in arr: newf max(f1,f0x) f0 f1 f1 newf return f1 return max(rob1(nums[2:n-1])nums[0],rob1(nums[1:n]))5.mxn棋盘最小路径和左上走到右下回溯法1.dfsi,j定义走到gridi,j一共走了多少路径2.边界条件 if i0 or j 0:return 多少0-1return inf设置一个 “无效的极大值”让它在min()比较中被自动忽略if i0 and j0赋初值3.怎么得到右下角的坐标毕竟是mxn的只知道一个数组grid [[1,3,1],[1,5,1],[4,2,1]]要根据grid求出右下角的坐标所以 横坐标是 len(grid)-1,纵坐标是len(grid[0])-1class Solution: def minPathSum(self, grid: List[List[int]]) - int: cache def dfs(i,j): if i0 or j 0: return inf if i 0 and j 0: return grid[0][0] return min(dfs(i,j-1),dfs(i-1,j))grid[i][j] return dfs(len(grid)-1,len(grid[0])-1)递推先根据dfs式子改成f式子f[i 1][j 1] min(f[i 1][j], f[i][j 1]) grid[i][j]初始值f[0][j]f[i][0]∞给整个grid左边上边加一排inff[1][1]grid[0][0]f[0][1]f[1][0]0 保证f[1][1] 也可以用递推式计算难点1.怎么创建一个m*n的f[[][]],并且全部赋初值infm是len(grid) n是lengrid[0]f [[inf] * (n 1) for _ in range(m 1)]难点2.把每一行的列元素取出来for i, row in enumerate(grid):for j, x in enumerate(row):时间复杂度mn 空间复杂度nclass Solution: def minPathSum(self, grid: List[List[int]]) - int: m, n len(grid), len(grid[0]) f [[inf] * (n 1) for _ in range(m 1)] f[0][1] 0 for i, row in enumerate(grid): for j, x in enumerate(row): f[i 1][j 1] min(f[i 1][j], f[i][j 1]) x return f[m][n]空间优化可以优化到1看不动了...