专栏首页MiningAlgorithmsPython3刷题系列(五)

Python3刷题系列(五)

目录:

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

本文分享自微信公众号 - MiningAlgorithms(gh_d0cc50d1ed34)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 生信(七)生信中常用命令

    (说明:我们拿到的bed文件时常是客户在Windows系统下编辑好的,其行尾是\r\n,在进行NGS分析前最好将其转换为Unix风格的行尾\n。)

    一只羊
  • 【趣学程序】集群之间配置SSH无密码登录

    注意 假设以上配置是在A机器上配置的,目标机器为B。那么我们就可以在A机器上通过 ssh B的IP 访问B这台机器了 如果你想在B电脑上也可以免密登录A机器,那...

    趣学程序
  • 【趣学程序】Linux基础命令

    常用:/home /etc /mnt /root /opt /tmp /usr /var

    趣学程序
  • Shell(一)好的操作习惯

    前一段时间顺丰运维人员将生产数据库删除的传闻着实成为了新闻热词,如果传闻是真的,相信那位运维也是无心之过,可能只是一瞬的手误。但是代价太大了,业内人员都懂的。

    一只羊
  • 【趣学编程】linux常用命令(二)

    趣学程序
  • 通过脚本在Docker环境中一键安装mysql主从环境

    其中hostip是必须修改的,其他配置可以酌情修改. 注意: 如果你的Docker环境是通过Docker Toolbox,且是安装在windows环境,建议将...

    明哥的运维笔记
  • 【趣学程序】Linux流的重定向

    趣学程序
  • 如何在Linux中发现IP地址冲突

    你们都知道什么是IP地址,是吧?它们被分配给网络上的设备来代表它们。它们通过DHCP服务器分配并且会经常改变。现在有两种IP地址。动态的一种会经常改变(几天一次...

    小小科
  • Flume安装及部署

    (adsbygoogle =window.adsbygoogle ||[]).push({});

    猿码优创
  • 【趣学程序】Hadoop运行模式

    注意:Namenode 和 ResourceManger 如果不是同一台机器,不能在 NameNode 上启动 yarn,应该在 ResouceManager ...

    趣学程序

扫码关注云+社区

领取腾讯云代金券