前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Python3刷题系列(五)

Python3刷题系列(五)

作者头像
用户5473628
发布2019-08-08 14:58:10
4860
发布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/

代码语言:javascript
复制
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/

代码语言:javascript
复制
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:“最近最少使用”算法

代码语言:javascript
复制
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/

代码语言:javascript
复制
# 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/

代码语言:javascript
复制
# 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/

代码语言:javascript
复制
# 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/

代码语言:javascript
复制
# 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/

代码语言:javascript
复制
# 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/

代码语言:javascript
复制
# 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 删除

本文分享自 MiningAlgorithms 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档