|
| 1 | +1.迷宫 |
| 2 | +递归 |
| 3 | +class Solution: |
| 4 | + def minPathSum(self, grid) -> int: |
| 5 | + dirction = [[1,0],[0,1]] |
| 6 | + m = len(grid) |
| 7 | + n = len(grid[0]) |
| 8 | + self.minsum = 100000000 |
| 9 | + def dfs(i,j,tempsum): |
| 10 | + if i==m-1 and j==n-1: |
| 11 | + self.minsum = min(self.minsum,tempsum) |
| 12 | + for h in range(2): |
| 13 | + if i+dirction[h][0]<m and j+dirction[h][1]<n : |
| 14 | + a = i+dirction[h][0] |
| 15 | + b = j+dirction[h][1] |
| 16 | + tempsum1 = tempsum + grid[a][b] |
| 17 | + dfs(a,b,tempsum1) |
| 18 | + dfs(0,0,grid[0][0]) |
| 19 | + return self.minsum |
| 20 | +动态规划 |
| 21 | +class Solution: |
| 22 | + def minPathSum(self, grid: List[List[int]]) -> int: |
| 23 | + if(not grid): |
| 24 | + return 0 |
| 25 | + m=len(grid) |
| 26 | + n=len(grid[0]) |
| 27 | + for i in range(1,n): |
| 28 | + grid[0][i]+=grid[0][i-1] |
| 29 | + for j in range(1,m): |
| 30 | + grid[j][0]+=grid[j-1][0] |
| 31 | + for x in range(1,m): |
| 32 | + for y in range(1,n): |
| 33 | + grid[x][y]+=min(grid[x-1][y],grid[x][y-1]) |
| 34 | + return grid[-1][-1] |
| 35 | +2.解码方法 |
| 36 | +class Solution: |
| 37 | + def numDecodings(self, s: str) -> int: |
| 38 | + if s[0] == '0': |
| 39 | + return 0 |
| 40 | + if len(s) == 1: |
| 41 | + return 1 |
| 42 | + dp = [1] |
| 43 | + for i in range(1, len(s)): |
| 44 | + if s[i] == '0': |
| 45 | + if s[i-1] != '1' and s[i-1] != '2': |
| 46 | + return 0 |
| 47 | + else: |
| 48 | + if i == 1: |
| 49 | + dp.append(1) |
| 50 | + else: |
| 51 | + dp.append(dp[i-2]) |
| 52 | + continue |
| 53 | + if s[i-1] == '1': |
| 54 | + dp.append(dp[i-2]+dp[i-1]) |
| 55 | + elif s[i-1] == '2' and (s[i] >= '1' and s[i] <= '6'): |
| 56 | + dp.append(dp[i-1]+dp[i-2]) |
| 57 | + else: |
| 58 | + dp.append(dp[i-1]) |
| 59 | + |
| 60 | + return dp[-1] |
| 61 | +思路：顺序遍历，计算字符串从开始位到当前位的解码方式总数，按照与字符串索引对应的位置存入dp数组 |
| 62 | + |
| 63 | +如果第一个元素等于'0'，直接返回0 |
| 64 | +如果元素长度等于1，直接返回1 |
| 65 | +定义dp数组为[1]，然后从字符串s的第二个字母开始遍历 |
| 66 | +如果第i个元素是‘0’，检查第i-1个元素是不是‘1’或‘2’，如果不是，返回0；如果是，判断一下i是否等于1，来决定dp.append(dp[i-2])或者是dp.append(1) (防止数组越界) |
| 67 | +如果第i-1个元素是‘1’，或者第i-1个元素是‘2’且第i个原始大于‘0’且小于‘7’：dp.append(dp[i-2]+dp[i-1]) |
| 68 | +其余情况dp.append(dp[i-1]) |
| 69 | +返回s最后一个元素对应的dp值 |
| 70 | +3.最长有效括号 |
| 71 | +class Solution(object): |
| 72 | + def longestValidParentheses(self, s): |
| 73 | + """ |
| 74 | + :type s: str |
| 75 | + :rtype: int |
| 76 | + """ |
| 77 | + if not s: return 0 |
| 78 | + stack = [-1] |
| 79 | + max_long = 0 |
| 80 | + _max = 0 |
| 81 | + for idx, i in enumerate(s): |
| 82 | + if i == "(": |
| 83 | + stack.append(idx) |
| 84 | + else: |
| 85 | + stack.pop(-1) |
| 86 | + if not stack: |
| 87 | + stack.append(idx) |
| 88 | + else: |
| 89 | + if len(stack)==1: |
| 90 | + _max = idx - stack[0] |
| 91 | + else: |
| 92 | + _max = idx - stack[-1] |
| 93 | + max_long = max(max_long, _max) |
| 94 | + return max_long |
| 95 | + 4.编辑距离 |
| 96 | + class Solution: |
| 97 | + def minDistance(self, word1: str, word2: str) -> int: |
| 98 | + if len(word2) == 0: |
| 99 | + return len(word1) |
| 100 | + elif len(word1) == 0: |
| 101 | + return len(word2) |
| 102 | + m = [ [0 for i in range(len(word2))] for j in range(len(word1))] |
| 103 | + p = 0 |
| 104 | + for j in range(len(word2)): #初始化第0行 |
| 105 | + if word1[0] == word2[j]: |
| 106 | + p = 1 |
| 107 | + m[0][j] = j + 1 - p |
| 108 | + p = 0 |
| 109 | + for i in range(0, len(word1)): #初始化第0列 |
| 110 | + if word1[i] == word2[0]: |
| 111 | + p = 1 |
| 112 | + m[i][0] = i + 1 - p |
| 113 | + |
| 114 | + for i in range(1, len(word1)): |
| 115 | + for j in range(1, len(word2)): |
| 116 | + if word1[i] == word2[j]: |
| 117 | + m[i][j] = m[i - 1][j - 1] |
| 118 | + else: |
| 119 | + m[i][j] = min(m[i - 1][j - 1], m[i - 1][j], m[i][j - 1]) + 1 |
| 120 | + return m[-1][-1] |
0 commit comments