Python3刷题系列（五）

用户5473628

发布于 2019-08-08 14:58:10

4910

发布于 2019-08-08 14:58:10

文章被收录于专栏：MiningAlgorithms

1，leetcode-200（岛屿的个数）

2，leetcode-36（有效的数独）

3，leetcode-146（LRU）

4，leetcode-10（正则表达式匹配）

5，leetcode-64（最小路径和）

6，leetcode-322（零钱兑换）

7，leetcode-121（买卖股票的最佳时机）

8，leetcode-152（乘积最大子序列）

9，leetcode-120（三角形最小路径和）

1，Number of Islands（岛屿的个数）：

英文版：https://leetcode.com/problems/number-of-islands/description/

中文版：https://leetcode-cn.com/problems/number-of-islands/description/

class Solution:
    def numIslands(self, grid):
        res = 0
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == "1":
                    self.dfs(grid, r, c)
                    res += 1
        return res
        
    def dfs(self, grid, i, j):
        dirs = [[-1, 0], [0, 1], [0, -1], [1, 0]]
        grid[i][j] = "0"
        for dir in dirs:
            nr, nc = i + dir[0], j + dir[1]
            if nr >= 0 and nc >= 0 and nr < len(grid) and nc < len(grid[0]):
                if grid[nr][nc] == "1":
                    self.dfs(grid, nr, nc)

2，Valid Sudoku（有效的数独）：

英文版：https://leetcode.com/problems/valid-sudoku/

中文版：https://leetcode-cn.com/problems/valid-sudoku/

class Solution:
    def isValidSudoku(self, board):
        raw = [{},{},{},{},{},{},{},{},{}]
        col = [{},{},{},{},{},{},{},{},{}]
        cell = [{},{},{},{},{},{},{},{},{}]
        for i in range(9):
            for j in range(9):                                 
                num = (3*(i//3) + j//3)#找单元
                temp = board[i][j]
                if temp != ".":
                    if temp not in raw[i] and temp not in col[j] and temp not in cell[num]:
                        raw [i][temp] = 1
                        col [j][temp] = 1
                        cell [num][temp] =1
                    else:
                        return False    
        return True

3，leetcode-146：“最近最少使用”算法

class LRUCache(object):

    def __init__(self, capacity):
        self.capacity = capacity
        self._cache = []   
        self._cache_look_up = {}

    def get(self, key):
        if key not in self._cache_look_up:
            return -1

        self._cache.remove(key)
        self._cache.append(key)

        return self._cache_look_up[key]

    def put(self, key, value):
        if key in self._cache_look_up:
            self._cache_look_up[key] = value
            self._cache.remove(key)
            self._cache.append(key)
            return
        else:
            if len(self._cache) == self.capacity:
                del_key = self._cache[0]
                self._cache = self._cache[1:]
                del self._cache_look_up[del_key]

            self._cache.append(key)
            self._cache_look_up[key] = value

4，Regular Expression Matching（正则表达式匹配）

英文版：https://leetcode.com/problems/regular-expression-matching/

中文版：https://leetcode-cn.com/problems/regular-expression-matching/

# leetcode-10:
class Solution(object):
    def isMatch(self, s, p):
        """ :type s: str :type p: str :rtype: bool """
        dp = [[False for _ in range(len(p) + 1)] for _ in range(len(s) + 1)]
        dp[0][0] = True
        for j in range(2,len(p) + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]  
        for i in range(1,len(s) + 1):
            for j in range(1,len(p) + 1):
                if p[j - 1] == '*':
                    dp[i][j] = dp[i][j-1] or dp[i][j-2] or (dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))
                elif p[j-1] == '.' or s[i-1] == p[j - 1]:
                    dp[i][j] = dp[i-1][j-1]

        return dp[len(s)][len(p)]
# reference:http://www.voidcn.com/article/p-zioiffqq-mm.html

5，Minimum Path Sum（最小路径和）

英文版：https://leetcode.com/problems/minimum-path-sum/

中文版：https://leetcode-cn.com/problems/minimum-path-sum/

# leetcode-64: O(m*n),逐步更新grid元素为最短路径值，是一种时间复杂度对高的解法
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)  # 行数
        n = len(grid[0])  # 列数
        # 更新第一列元素这为路径值
        for i in range(1,m):
            grid[i][0] += grid[i-1][0]
        # 更新第一行值为路径值
        for j in range(1, n):
            grid[0][j] += grid[0][j-1]
        # 从第二行第二列开始更新[i][j]数值为路径值
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        return grid[m-1][n-1]

6，Coin Change （零钱兑换）

英文版：https://leetcode.com/problems/coin-change/

中文版：https://leetcode-cn.com/problems/coin-change/

# leetcode-322: BFS广度优先搜索，怎么保证路径最短的？
class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        if amount == 0:
            return 0
        value1 = [0]
        value2 = []
        nc =  0
        visited = [False]*(amount+1)  # 记录是否来过这里
        visited[0] = True  # 已经来过amount=0这个数额的money
        while value1:
            nc += 1  # 记录步数
            for v in value1:
                for coin in coins:   # 广度搜索：遍历一遍cions中的元素
                    newval = v + coin
                    if newval == amount:
                        return nc  # 出口一：存在路径
                    elif newval > amount:
                        continue   # 跳出for coin循环，但是，仍然在外层的for循环中，继续遍历下一个value1中的元素v
                    elif not visited[newval]:
                        visited[newval] = True
                        value2.append(newval)
            value1, value2 = value2, []   # 当value2=[]时，跳出while循环，执行return -1 语句

        return -1   # 出口二：不存在路径

7，Best Time to Buy and Sell Stock（买卖股票的最佳时机）

英文版：https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

中文版：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

# leetcode-121:
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0
        prof = 0
        min_p = prices[0]
        for i in prices:
            min_p = min(i, min_p)
            prof = max(i - min_p, prof)
        return prof
        
# 暴力解法（超时）：
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
      if not prices:
        return 0   # 如果prices为空[]，则返回0.

      l = len(prices)
      res = []
      
      for i in range(l):
          for j in range(i+1, l):
              res.append(prices[j] - prices[i])
      
      if not res:
        return 0   # 如果res为空[]，则返回0.
      else：
        return max(max(res), 0)

8，Maximum Product Subarray（乘积最大子序列）

英文版：https://leetcode.com/problems/maximum-product-subarray/

中文版：https://leetcode-cn.com/problems/maximum-product-subarray/

# leetcode-152：动态优化，与上题leetcode-121极其相似
class Solution:  # O(n)
    def maxProduct(self, nums: List[int]) -> int:
        max_p = min_p = nums[0]
        res = nums[0]
        for i in range(1, len(nums)):
            lastmax = max_p
            max_p = max(min_p*nums[i], lastmax*nums[i], nums[i])
            min_p = min(min_p*nums[i], lastmax*nums[i], nums[i])
            res = max(res, max_p)
        return res

# 暴力解法：O(n^2)
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
        
        l = len(nums)
        res = []
        element = 1
        for i in range(l):
            for j in range(i+1, l):
                for r in range(i, j+1):
                    element = element * nums[r]
                res.append(element)
                element = 1
        if not res:
            return 0
        else:
            return max(max(res), max(nums))

9，Triangle（三角形最小路径和）

英文版：https://leetcode.com/problems/triangle/

中文版：https://leetcode-cn.com/problems/triangle/

# leetcode-120: O(n(n-1)/2):时间复杂度仍为O(n^2),逐个修改矩阵元素值为最短路径值，时间复杂度最高的一种解法，但让然战胜了82.66%
class Solution:  # 自顶向下更新矩阵
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        l = len(triangle)
        if l == 0:
            return 0
        if l == 1:
            return triangle[0][0]
        for i in range(1, l):
            for j in range(1, i):
                triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])
            triangle[i][i] += triangle[i-1][i-1]  # 需要注意矩阵行向量的index=0，-1 的元素，要单独更新
            triangle[i][0] += triangle[i-1][0]
        return min(triangle[l-1])

# 法二：自底向上更新矩阵, 时间复杂度与上面一样，但是，之战胜了24.81%
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        l = len(triangle)
        if l == 0:
            return 0
        if l == 1:
            return triangle[0][0]
        for i in range(l-2, -1, -1):
            for j in range(0, i+1):
                triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])
            
        return triangle[0][0]

Reference：

https://blog.csdn.net/fuxuemingzhu/article/details/81126995

https://blog.csdn.net/weixin_42304045/article/details/80600022

https://blog.csdn.net/laughing2333/article/details/70231547

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-04-27，如有侵权请联系 cloudcommunity@tencent.com 删除

https