Python3刷题系列（十）

# leetcode-416：动态规划， beats 56.04%
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        c = sum(nums)
        if c % 2 != 0:
            return False
        c = c//2  # 取整
        w = [False] * (c+1)
        w[0] = True
        for num in nums:
            for i in range(c, num-1, -1):
                w[i] = w[i] or w[i-num]
        return w[c]

# leetcode-17：回溯法,beats 83.25%
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        self.keys = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
        combinations, prefix = [], ''
        if not digits:
            return combinations
        self.doCombinations(prefix, combinations, digits)
        return combinations
    
    def doCombinations(self, prefix:str, combinations: List[str], digits: str):
        if len(prefix) == len(digits):
            combinations.append(prefix)
            return
        for i in self.keys[int(digits[len(prefix)])]:
            prefix += i
            self.doCombinations(prefix, combinations, digits)
            prefix = prefix[:-1]

# leetcode-64：最小路径和，beats 68.36%
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        r = len(grid)  # 行数
        c = len(grid[0])  # 列数
        dp = [0] * c
        for i in range(r):
            for j in  range(c):
                if j == 0:
                    dp[j] = dp[j]
                elif i == 0:
                    dp[j] = dp[j-1]
                else:
                    dp[j] = min(dp[j-1], dp[j])
                dp[j] += grid[i][j]
        return dp[c-1]

# leetcode-70：斐波那契数列
class Solution:  # beats 17.26%
    def climbStairs(self, n: int) -> int:
        if n < 3:
            return n
        pre2, pre1 = 1, 2
        for i in range(2, n):
            pre1, pre2 = pre1+pre2, pre1
        return pre1

# leetcode-279:广度优先搜索(DFS),beats  51.82%
class Solution:
    def numSquares(self, n: int) -> int:
        squares = []
        square, interval = 1, 3
        while square <= n:
            squares.append(square)
            square += interval
            interval += 2
        list.reverse(squares)
        q = [(0, n)]
        used = [False for i in range(n+1)]
        while q:
            temp = q.pop(0)
            if temp[1] == 0:
                return temp[0]
            for s in squares:
                if temp[1] - s >= 0 and not used[temp[1] - s]:
                    q.append((temp[0] + 1, temp[1] - s))
                    used[temp[1] - s] = True
        return -1

# leetcode-695:广度优先搜索(DFS),beats 44.88%
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        self.r, self.c, max_area = len(grid), len(grid[0]), 0
        for i in range(self.r):
            for j in range(self.c):
                max_area = max(max_area, self.dfs(grid, i, j))
        return max_area
    
    def dfs(self, grid: List[List[int]], n: int, m: int) -> int:
        if n < 0 or n >= self.r or m<0 or m>=self.c or grid[n][m] == 0:
            return 0
        area, grid[n][m] = 1, 0
        area += self.dfs(grid, n-1, m)
        area += self.dfs(grid, n+1, m)
        area += self.dfs(grid, n, m+1)
        area += self.dfs(grid, n, m-1)
        return area

# leetcode-343:动态规划,beats 57.79%
class Solution:
    def integerBreak(self, n: int) -> int:
        sums = [0, 1]
        for i in range(2, n+1):
            tmp = 0
            for j in range(1, i):
                tmp = max(tmp, j*sums[i-j], j*(i-j))
            sums.append(tmp)
        return sums[n]

# leetcode-583:动态规划,beats 87.48%
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m = len(word1)
        n = len(word2)
        dp = [[0] * (n+1) for i in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])
        return m+n- 2 * dp[m][n]

# leetcode-303:
class NumArray:  # 动态规划， beats 83.14%

    def __init__(self, nums: List[int]):
        self.nums = nums
        self.sums = [-1] * (len(self.nums) + 1)
        for i in range(1, len(self.nums) + 1):
            self.sums[i] = self.sums[i-1] + self.nums[i-1]

    def sumRange(self, i: int, j: int) -> int:
        return self.sums[j+1] - self.sums[i]

# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

class NumArray:  # 记忆性搜索法，beats 7.05%

    def __init__(self, nums: List[int]):
        self.nums = nums
        self.sums = [-1] * (len(self.nums) + 1)
        
    def sumRange(self, i: int, j: int) -> int:
        if self.sums[i] == -1:
            self.sums[i] = self.sum_x(i)
        if self.sums[j+1] == -1:
            self.sums[j+1] = self.sum_x(j+1)
        return self.sums[j+1] - self.sums[i]
    
    def sum_x(self, x):
        sum = 0
        for i in range(x):
            sum += self.nums[i]
        return sum

# leetcode-300：动态规划，beats 53.08%
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        LIS = [1] * len(nums)
        for i in range(1, len(nums)):
            LIS[i] = max([1+LIS[j] for j in range(i) if nums[j] < nums[i]] + [1])
        return max(LIS)

# leetcode-309:动态规划，beats 95.44%
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        buy, pre_buy, sell, pre_sell = -max(prices), 0, 0, 0
        for p in prices:
            pre_buy = buy
            buy = max(pre_sell - p, pre_buy)
            pre_sell = sell
            sell = max(pre_buy + p, pre_sell)
        return sell