发表于 | 分类于
字数统计: 1.3k 字 | 阅读时长 ≈ 6 分钟

今日总结：做题效果不是很好，出现各种状况。感觉不是很难的题，就是陷入思维误区。还有两道题（18，22），暂且搁置。有点窝火，再努力吧。

16. 最接近的三数之和（C）

分析：跟之前的题很相识，一个求和，这个是求近似。直观想法还是老套路，排序，然后遍历，比较。

方法一：排序遍历比较，注意下，近似使用abs求绝对值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        if len(nums)<3:
            return None
        
        gol_ans = nums[0]+nums[1]+nums[2]
        for i in range(len(nums)-2):
            j = i+1
            k = len(nums)-1
            while j<k:
                cur_ans = nums[i]+nums[j]+nums[k]
                if cur_ans == target:
                    return cur_ans
                if abs(cur_ans-target) < abs(gol_ans-target):
                    gol_ans=cur_ans
                if cur_ans > target:
                    k-=1
                else:
                    j+=1
        return gol_ans

方法二：优化运算时间，想法就是优先考虑两端情况，最大最小。然后其余情况正常，最后将结果。绝对值排序。选出最优。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        closest = []
        length = len(nums)
        for i, num in enumerate(nums[0:-2]):
            l,r = i+1, length-1
            if num+nums[r]+nums[r-1] < target:
                closest.append(num+nums[r]+nums[r-1])
            elif num+nums[l]+nums[l+1] > target:
                closest.append(num+nums[l]+nums[l+1])
            else:
                while l<r:
                    closest.append(num+nums[r]+nums[l])
                    if num+nums[l]+nums[r] > target:
                        r -= 1
                    elif num+nums[l]+nums[r] < target:
                        l += 1
                    else:
                        return target
        closest.sort(key=lambda x:abs(x-target))
        return closest[0]

17. 电话号码的字母组合（C）

分析：每个数字列出对应字母，先读一个数字放入列表。再依次拼接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: 
            return []
        table = {'2': ['a', 'b', 'c'],            
                 '3': ['d', 'e', 'f'],
                 '4': ['g', 'h', 'i'],
                 '5': ['j', 'k', 'l'],
                 '6': ['m', 'n', 'o'],
                 '7': ['p', 'q', 'r', 's'],
                 '8': ['t', 'u', 'v'],
                 '9': ['w', 'x', 'y', 'z']
                }
        result = ['']
        for digit in digits:
            str_list = []
            for char in table[digit]:
                str_list += [x + char for x in result]
            result = str_list
        return result

优化后（A）。yield生成器返回结果。学习到了。还有函数构造这个也很巧妙。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        
        dict = {'2': ['a', 'b', 'c'],            
                 '3': ['d', 'e', 'f'],
                 '4': ['g', 'h', 'i'],
                 '5': ['j', 'k', 'l'],
                 '6': ['m', 'n', 'o'],
                 '7': ['p', 'q', 'r', 's'],
                 '8': ['t', 'u', 'v'],
                 '9': ['w', 'x', 'y', 'z']
                }
        def helper(digits, comb = ''):
            if len(digits) > 0:
                for i in dict[digits[0]]:
                    yield from helper(digits[1:], comb + i)
                else:
                    yield comb
        return list(helper(digits)) if digits != '' else []

18. 四数之和（C）（暂）

分析：emmm~四数之和来了，首先考虑顺着三数之和的思路，4个指针，固定两个数。两个数往中间逼近。考虑可能存在多种情况，需要加一条判断。双嵌套复杂度太高了，直接借鉴优化代码。

（A）可以通过递归解决n个数之和。

  • 考虑将n数之和降低为一个数加上n-1数之和
  • 分化为二数之和
  • target = target - nums[i]来调用nSum（）方法。递归
  • 注意列表的拼接。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        def nSum(nums, target, n, result, results):
            if len(nums) < n or n < 2 or n * nums[0] > target or n * nums[-1] < target:
                return []
            if n == 2:
                begin, end = 0, len(nums)-1
                while begin < end:
                    sums = nums[begin] + nums[end]
                    if sums < target:
                        begin += 1
                    elif sums > target:
                        end -= 1
                    else:
                        plet  = [nums[begin], nums[end]]
                        results.append(result + plet)
                        while begin < end and nums[begin] == plet[0]: begin += 1
                        while begin < end and nums[end] == plet[1]: end -= 1
            else:
                for i in range(len(nums) - n + 1):
                    if (i > 0 and nums[i] == nums[i-1]) or (nums[i] + (n-1)*nums[len(nums)-1]<target):
                        continue
                    if n * nums[i] > target:
                        break
                    if n * nums[i] == target and i + n - 1 < len(nums) and nums[i+n-1] == nums[i]:
                        plet = [nums[i]] * n
                        results.append(result + plet)
                        break
                    nSum(nums[i + 1:], target - nums[i], n - 1, result + [nums[i]], results)
        results = []
        nums.sort()
        nSum(nums, target, 4, [], results)
        return results

20. 有效的括号（D）

分析：字符串问题，很好实现。

第一种，利用replace直接替换。不需要考虑其他位置。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def isValid(self, s: str) -> bool:
        n = len(s)
        if n == 0:
            return True
        if n % 2 != 0:
            return False
        while '()' in s or '[]' in s or '{}' in s:
            s = s.replace('()',"").replace('[]',"").replace('{}',"")
        return s == ""

第二种，利用堆栈的方式，匹配之后用pop删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for char in s:
            if char in ['(','{','[']:
                stack.append(char)
            elif not stack:
                return False
            elif (char == ')') and (stack[len(stack)-1]=='('):
                stack.pop()
                
            elif (char == ']') and (stack[len(stack)-1]=='['):
                stack.pop()
                
            elif (char == '}') and (stack[len(stack)-1]=='{'):
                stack.pop()
            else:
                return False
        return len(stack) == 0

22. 括号生成（B）（暂）

分析：跟20题逻辑相逆。

方法1：暴力法，生成所有括号序列，再判断是否有效。数目够就匹配（）是否是对应的。如果，出现）在前，直接返回结果。正好相等时，判断返回True。然后添加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate(A = []):
            if len(A) == 2*n:
                if valid(A):
                    ans.append("".join(A))
            else:
                A.append('(')
                generate(A)
                A.pop()
                A.append(')')
                generate(A)
                A.pop()
        def valid(A):
            bal = 0
            for C in A:
                if C == '(': bal += 1
                else: bal -= 1
                if bal < 0: return False
            return bal == 0
        ans = []
        generate()
        return ans

方法二？（A）：递归生成有效序列。方法二为什么就递归了。知识漏洞！

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def backtrack(S = '',left = 0, right = 0):
            if len(S) == 2 * n:
                ans.append(S)
                return
            if left < n:
                backtrack(S+'(', left+1, right)
            if right < left:
                backtrack(S+')', left, right+1)     #取出一个值后，为什么再次递归。
        ans = []
        backtrack()
        return ans

发表于 | 分类于
字数统计: 989 字 | 阅读时长 ≈ 4 分钟

LeetCode日常打卡11~15

11. 盛最多水的容器

分析：比较简单的一道题，面积问题，宽高都很容易理解。暴力法会超时。使用双指针即可。

扩展思考，这道题感觉没什么好挖掘的。变化顶多是坐标尺变换一下。判断时注意一下就好。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxArea(self, height: List[int]) -> int:
        #双指针
        max_area = left = 0
        right = len(height) - 1
        while left < right:
            max_area = max(max_area,(right - left)*min(height[left],height[right]))
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1
        return max_area

12. 整数转罗马数字

分析：实现不难。不过，看到优秀解答。忍不住拷贝下来。发散思路真的很重要。

参考luohaha

方法1：第一种方法，依次取出个十百千位，然后转为字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def intToRoman(self, num: int) -> str:
        from collections import deque

        roman = {1: 'I', 4: 'IV', 5: 'V', 9: 'IX', 10: 'X', 40: 'XL', 50: 'L', 90: 'XC',
                 100: 'C', 400: 'CD', 500: 'D', 900: 'CM', 1000: 'M'}
        q = deque()

        i = 0
        while num:
            num, digit = divmod(num, 10)
            times = pow(10, i)
            digit *= times
            i += 1
            if digit in roman:
                q.appendleft(roman[digit])
            elif digit >= 5 * times:
                q.appendleft(roman[times] * ((digit - 5 * times) // times))
                q.appendleft(roman[5 * times])
            else:
                q.appendleft(roman[times] * (digit // times))

        return ''.join(q)

第二种方法，题目范围位1-3999，用字典保存个十百千位上可能出现的所有罗马数字，依次取出千百个十位，在字典中找到数字对应的罗马数字即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def intToRoman(self, num: int) -> str:
        roman = [
            ['', "M", "MM", "MMM"],
            ['', "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"],
            ['', "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"],
            ['', "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"],
        ]
        num_l = [1000, 100, 10, 1]
        roman_num = ''

        for k, v in enumerate(num_l):
            roman_num += roman[k][num//v]
            num %= v
        return roman_num

第三种解法，将数字依次递减，直到减为0，将减去的数字替换为罗马数字即可

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def intToRoman(self, num: int) -> str:
        values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        reps = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        roman_num = ''

        for i in range(13):
            while num >= values[i]:
                num -= values[i]
                roman_num += reps[i]
        return roman_num

13. 罗马数字转整数

分析：相比上一道题差不多。巧妙一处在于如何处理，满减情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def romanToInt(self, s: str) -> int:
        dic = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}
        last = 0
        now = 0
        result = 0
        for i in s:
            now = dic[i]
            if now > last and last != 0:
                result = (result - last)+(now-last)
            else:
                result += now
                last = now
        return result

14. 最长公共前缀

分析：本以为只是一道简单的题，发掘出不错方法。学到了。

方法一： 利用python的max()和min()，在Python里字符串是可以比较的，按照ascII值排，举例abb， aba，abac，最大为abb，最小为aba。所以只需要比较最大最小的公共前缀就是整个数组的公共前缀 。

1
2
3
4
5
6
7
8
9
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ""
        s1 = min(strs)
        s2 = max(strs)
        for i,x in enumerate(s1):
            if x != s2[i]:
                return s2[:i]
        return s1

2、利用python的zip函数，把str看成list然后把输入看成二维数组，左对齐纵向压缩，然后把每项利用集合去重，之后遍历list中找到元素长度大于1之前的就是公共前缀

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ""
        ss = list(map(set, zip(*strs)))
        res = ""
        for i, x in enumerate(ss):
            x = list(x)
            if len(x) > 1:
                break
            res = res + x[0]
        return res

15. 三数之和

分析：先排序，建立列表。建立三数之和，然后判断。注意如果相等，需要往中间逼近。逼近同时注意去掉数字相同情况，减少运算复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res =[]
        i = 0
        for i in range(len(nums)):
            if i == 0 or nums[i]>nums[i-1]:
                l = i+1
                r = len(nums)-1
                while l < r:
                    s = nums[i] + nums[l] +nums[r]
                    if s ==0:
                        res.append([nums[i],nums[l],nums[r]])
                        l +=1
                        r -=1
                        while l < r and nums[l] == nums[l-1]:
                            l += 1
                        while r > l and nums[r] == nums[r+1]:
                            r -= 1
                    elif s>0:
                        r -=1
                    else :
                        l +=1
        return res

发表于 | 分类于
字数统计: 2.5k 字 | 阅读时长 ≈ 12 分钟

动态规划（Dynamic Programming）

Those who cannot remember the past are condemned to repeat it.

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。

三个核心元素：最优子结构、边界、状态转移方程式

多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。

动态规划一般可分为

  • 线性动规，etc:拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；

  • 区域动规，etc:石子合并， 加分二叉树，统计单词个数，炮兵布阵等；

  • 树形动规，etc:贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；

  • 背包动规。etc:背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶

    同类问题通常有三种方式思考

  • 简单递归

  • 备忘录算法 （优化时间复杂度）

  • 动态规划 （优化时间，空间复杂度）

    利用简洁的自底向上的递推方式，实现了时间和空间上的最优化。

缺点局限：

时间复杂度（n*w）空间复杂度（w）当所求单位很多时，需要很多空间。反而不如简单递归（跟w无关）。

LeetCode 选题

  • 菜 53、70、121
  • 中 62、63、322
  • 死 32 、44、174、403

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

1
2
3
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解：

思路：动态规划最简单的应用，max

1
2
3
4
5
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i]= nums[i] + max(nums[i-1], 0)
        return max(nums)

70. 爬楼梯

思路：正常做法，就是最简单的动态规划。省略代码。

看到一个有趣的。做法二：通过设置缓存区，通过递归法运行时间测试。

1
2
3
4
5
6
7
8
9
10
11
from functools import lru_cache

class Solution:
    @lru_cache(10**8)   #设置个缓存
    def climbStairs(self, n):
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            return self.climbStairs(n - 1) + self.climbStairs(n - 2)

121. 买卖股票的最佳时机

思路：很简单的一道题，需要注意的就是取最低点买入。然后在高点卖出。满足，低点在前，高点在后。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 0:
            return 0
        min_ = prices[0]
        result = 0        
        for i in range(1, len(prices)):
            min_ = min(min_, prices[i])
            result = max(result, prices[i] - min_)
            
        return result

62. 不同路径

思路：

这个题其实可以用排列组合的方式来做。

以模拟的[4, 7]的例子,每一条路径：

  1. 向右的肯定有6步;
  2. 向左的肯定有3步;

问题即为:c(9,3) = (9 8 7) / (1 2 3) = 84

组合数公式：c(m,n) = m! / (n! * (m - n)!)

解法1：python一行式！

1
2
3
class Solution:
    def uniquePaths(self, m, n):
        return int(math.factorial(m + n - 2) / math.factorial(m -1) / math.factorial(n-1))

解法2：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def uniquePaths(self, m, n):
        if m <= 0 or n <= 0:
            return 0
        res = [0 for _ in range(0, n)]
        res[0] = 1
        for i in range(0, m):
            for j in range(1, n):
                res[j] += res[j-1]
        return res[n-1]

解法3：

1
2
3
4
5
6
7
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]   
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

63. 不同路径 II

思路：加了障碍物。看了几种做法。

解法1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class solution(object):
    def uniquePathsWithobstacles(self, obstacleGrid):
        m,n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        if obstacleGrid[0][0] == 0:
            dp[0][0] = 1
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    if i != 0:
                        dp[i][j] += dp[i - 1][j]
                    if j != 0:
                        dp[i][j] += dp[i][j - 1]
        return dp[m - 1][n - 1]

解法2：进行优化。利用Python语言特性来减少判断次数。我们遍历的方向是第一行从左到右，然后再第二行从左到右的方式进行的，这样如果把dp全部初始化成了0，那么当计算第一行的时候dp[-1][j]实际上就是最后一行的dp，也就是0.同样的，dp[i][-1]实际上是最后一列的dp，但是还没遍历到过，所以也是0.总之，虽然dp数组在计算第一行和第一列的时候用到了最后一行最后一列的dp数据，但是由于还没有遍历到，那么dp数组实际上是0，所以完全可以省去判断。这种方式对于C++和Java不能进行负数索引的不能用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        if obstacleGrid[0][0] == 0:
            dp[0][0] = 1
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 0:
                    if i == j == 0:
                        continue
                    else:
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

322. 零钱兑换

思路：参考powcai 的解题代码。一题多解。可以用0/1背包,深度遍历(dfs),广度遍历(bfs)

有时间细化一下，各种解法。

解法1：动态规划

1
2
3
4
5
6
7
8
9
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0
        for i in range(1,amount + 1):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i-coin]+1)
        return dp[-1] if dp[-1] != float('inf') else -1

解法2：深度遍历dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def coinChange(self, coins: 'List[int]', amount: 'int') -> 'int':
        from collections import defaultdict
        lookup = defaultdict(int)
        if amount < 1:
            return 0

        def helper(amount):
            if amount < 0:
                return -1
            if amount == 0:
                return 0
            if lookup[amount]:
                return lookup[amount]
            min_num = 2 ** 31 - 1
            for coin in coins:
                res = helper(amount - coin)
                # min_num = min(min_num,res + 1)
                if res >= 0 and res < min_num:
                    min_num = res + 1
                    lookup[amount] = min_num if min_num != 2 ** 31 - 1 else -1
                    return lookup[amount]

                return helper(amount)

解法3:广度遍历bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
        def coinChange(self, coins: 'List[int]', amount: 'int') -> 'int':
            
            #广度遍历bfs
            res = 0
            cur = [0]
            visited = set()
            coins.sort()
            while cur:
                next_time = []
                res += 1
                for tmp in cur:
                    for coin in coins:
                        sum_num = tmp + coin
                        if sum_num == amount:
                            return res
                        elif sum_num > amount:
                            break
                        elif sum_num < amount and sum_num not in visited:
                            next_time.append(sum_num)
                            visited.add(sum_num)
                cur = next_time
            return -1 if amount else 0

解法4：约束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
       def coinChange(self, coins: 'List[int]', amount: 'int') -> 'int':
           self.res = float("inf")
           n = len(coins)
           if amount == 0:
               return 0
           coins.sort(reverse=True)
           if amount < coins[-1]:
               return -1
   
           def dfs(loc, remain, count):
               if remain == 0:
                   self.res = min(self.res, count)
               else:
                   for i in range(loc, n):
                       if coins[i] <= remain < coins[i] * (self.res - count):
                           dfs(i, remain - coins[i], count + 1)
   
           for i in range(n):
               dfs(i, amount, 0)
           return self.res if self.res != float("inf") else -1

Hard

32. 最长有效括号

分析：问题并不难。关键在于，运用一个列表暂存，一个列表计数。这个方式真的很不错。还有enumerate函数的运用，用取max方式获取最大子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        st, b = [], [0]*len(s)
        for i, val in enumerate(s):
            if val == '(':
                st.append(i)
            elif st:
                b[st.pop()], b[i] = 1, 1  #清空，记录

        c, mc = 0, 0
        for i in b:
            if i:
                c += 1
            else:
                mc = max(c, mc)  #排除单“括号”，中断后获取最大子串。
                c = 0

        return max(c, mc)

44. 通配符匹配

分析：虽然是hard难度，但理解题意。还是很简单的。关键点在于，“*”和“？”的适配情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[bool(0) for _ in range(n+1) ]for _ in range(m+1)]
        dp[0][0] = bool(1)
        for i in range(n):
            if dp[0][i] and p[i] == '*':
                dp[0][i+1] = bool(1)
       
        #动态规划        
        for i in range(m):
            for j in range(n):
                if p[j] == '*':
                    dp[i + 1][j + 1] = dp[i][j+1] or dp[i+1][j]
                elif p[j] == '?' or s[i] == p[j]:
                    dp[i+1][j+1] = dp[i][j]
        return dp[m][n]

174. 地下城游戏

分析：保证血量>=1.还是经典的动态规划做法，从后往前推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        # 参考
        x, y = len(dungeon), len(dungeon[0])
        dp = [[0]*y for _ in range(x)]  # 能到达最后在这个位置的最小体力值,>=1
        dp[-1][-1] = max(1, 1-dungeon[-1][-1])
        for j in range(y-2, -1, -1):  # 最后一行
            dp[-1][j] = max(1, dp[-1][j+1]-dungeon[-1][j])
        for i in range(x-2, -1, -1):
            dp[i][-1] = max(1, dp[i+1][-1]-dungeon[i][-1])
        for j in range(y-2, -1, -1):  # 从右到左
            for i in range(x-2, -1, -1):  # 从下到上
                # 找这个位置下边或右边需要的较少体力值
                dp[i][j] = max(1, min(dp[i][j+1], dp[i+1][j])-dungeon[i][j])
        return dp[0][0]

403. 青蛙过河

分析：大概是这几道题中最有难度的一道了。国区的评论区竟然没有python3的答案。看别的程序思路有的用哈希表，有的用回溯法+贪心策略+剪枝。感觉一时半会没有好的思路，暂且存疑吧。等到修炼一段时间，再回顾。贴一下英文原站的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def canCross(self, stones: List[int]) -> bool:
        '''
        let canCross(stones, i, k) be whether the frog can jump start from position i and frog's previou jump size is k. Then next jump can be either k - 1, k, or k + 1 so
        canCross(stones, i, k) = canCross(stones, i + k - 1, k - 1) or canCross(stones, i + k, k) or canCross(stones, i + k + 1, k + 1)
        if i + k - 1 or i + k or i + k + 1 be a stone position, otherwise canCross(stones, i, k) = False
        if i == stones[-1], the frog already sits on the last stone. Return True.
        '''
        self.memo = {}
        stonePos = set(stones)
        return self._canCross_helper(stones, 0, 0, stonePos)
        
    def _canCross_helper(self, stones:List[int], i: int, k:int, stonePos:set)->bool:
        if (i, k) in self.memo:
            return self.memo[(i, k)]
        ans = False
        if i == stones[-1]:
            ans = True
            self.memo[(i, k)] = ans
            return ans
        if k - 1 > 0:
            if i + k - 1 in stonePos:
                ans = ans or self._canCross_helper(stones, i + k - 1, k - 1, stonePos)
        if k > 0:
            if i + k in stonePos:
                ans = ans or self._canCross_helper(stones, i + k, k, stonePos)
        if i + k + 1 in stonePos:
            ans = ans or self._canCross_helper(stones, i + k + 1, k + 1, stonePos)
        self.memo[(i, k)] = ans
        return ans

发表于 | 分类于
字数统计: 229 字 | 阅读时长 ≈ 1 分钟

经过了三天的时间，博客雏形终于完成了。本应该是很容易解决达成的目标。走了各种弯路，见证了好多项目的兴衰。不得不感慨一句，下次如果再没有收罗足够的信息就开始盲目做。我就是瓜皮。(¦3」∠)

虽然做了很多无用功，功能改来改去。bug大概遇到30多个，感觉就像自己做了一个不大不小的项目。不过也不能说了浪费时间吧。首先磨炼了心性，在无人指导，搜索无门的情况下，自己各种钻牛角尖。如果不是实力不够，我就直接修改底层代码了。

本来还想写个教程。鉴于博客搭建的并没有很满意，加上实在是看的厌烦。暂且搁置吧。

最后特别感谢黎静小姐姐的友情支持。

发表于
字数统计: 73 字 | 阅读时长 ≈ 1 分钟

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

0%
undefined