算法练习——最长子数组和 leetcode.53 python

目录

正文：最长子数组和

附录：

Q1：青蛙跳台阶

         Q2：不同路径（leetcode 62）

Q3：编辑距离 （leetcode 72 困难）

---

正文：最长子数组和

题目描述：

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

子数组 是数组中的一个连续部分。

C语言的解法可以参考 @weiambt 的这篇文章。

连续子数组的最大和问题（五种解法）_weiambt的博客-CSDN博客https://blog.csdn.net/Supreme7/article/details/117398880思路一：暴力穷举

class Solution:
    def maxSubArray(self, nums):
        length = len(nums)
        ret = nums[0]
        for i in range(0, length):  # 从i开始
            for j in range(i, length):  # 到j结束
                temp_max = 0
                for k in range(i, j+1):  # 求i到j之间的累加和
                    temp_max = temp_max + nums[k]
                ret = max(ret,temp_max)
        return ret

时间复杂度：O(n3)

思路二：动态规划（本题最常用思路）

第i个状态只与第i-1个状态有关。

告别动态规划，连刷40道动规算法题，我总结了动规的套路_Hollis Chuang的博客-CSDN博客https://blog.csdn.net/hollis_chuang/article/details/103045322?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165216164316782425139035%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165216164316782425139035&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-103045322-null-null.142%5Ev9%5Econtrol,157%5Ev4%5Econtrol&utm_term=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92&spm=1018.2226.3001.4187在这篇文章中，作者总结了动态规划类问题的求解思路：（在附录中，会更新其中例题的解法：）

1、定义数组元素的含义

2、找出数组元素之间的关系式

3、找出初始值

class Solution:
    def maxSubArray(self, nums):
        length = len(nums)
        # 第一步骤：dp[i]的含义是以i结尾的数组字串的最大和
        dp = [0] * length
        # 第三步骤：初始值
        dp[0] = nums[0]
        for i in range(1,length):
            # 第二步骤：状态转移方程
            # 如果dp[i-1]为正，则也要计算前面的字串；如果dp[i-1]为负，则从i重新计算最大和
            dp[i] = max(dp[i-1]+nums[i], nums[i])
        res = max(dp)
        return res

时间复杂度：O(n) 

 思路三：扫描法

当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和。

class Solution:
    def maxSubArray(self, nums):
        res = nums[0]
        sum_temp = nums[0]
        length = len(nums)
        for i in range(1,length):
            if sum_temp < 0:
                sum_temp = nums[i]
            else:
                sum_temp += nums[i]
            res = max(res,sum_temp)
        return res

时间复杂度：O(n) 

附录：

动态规划三步法练习：

Q1：青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？

def frogJump(n):
    if n <= 1:
        return n
    # 第一步骤：dp[i]的含义是跳上第i层台阶所有可能的跳发
    dp = [0] * (n+1)
    # 第三步骤：初始值
    dp[0] = 0
    dp[1] = 1
    dp[2] = 2
    for i in range(3,n+1):
        # 第二步骤：状态转移方程
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

Q2：不同路径（leetcode 62）

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

class Solution:
    def uniquePaths(self, m, n):
        if m<=0 or n<=0:
            return 0
        # 步骤一：dp[m-1][n-1]表示机器人走到（m,n）的路径总数
        dp = [[0 for col in range(n)] for row in range(m)]
        # 步骤三：由状态转移方程，可知，要对迷宫边缘的点进行初始化
        # 否则i-1，j-1会让数组越界
        # 一直向左走、一直向下走都是唯一走法
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        # 步骤二：状态转移方程
        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]

注意使用python创建二维数组的方法：先列后行

dp = [[0 for col in range(n)] for row in range(m)]

Q3：编辑距离 （leetcode 72 困难）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少 *** 作数。

你可以对一个单词进行如下三种 *** 作：

插入一个字符
删除一个字符
替换一个字符

class Solution:
    def minDistance(self,word1,word2):
        len1 = len(word1)
        len2 = len(word2)
        # 步骤一：dp的含义是 长度为i的word1 转化为 长度为j的word2时所需要的最小转换次数
        dp = [[0 for cow in range(len2+1)]for row in range(len1+1)]
        # 步骤三：由状态转移方程，可知，要对i=0或j=0的点进行初始化
        # 否则i-1，j-1会让数组越界
        # i=0时 word1转化为word2只能进行插入 *** 作
        for j in range(1,len2+1):
            dp[0][j] = dp[0][j-1]+1
        # j=0时 word1转化为word2只能进行删除 *** 作
        for i in range(1,len1+1):
            dp[i][0] = dp[i-1][0]+1
        # 步骤二：状态转移方程
        for i in range(1,len1+1):
            for j in range(1,len2+1):
                # 如果word1[i]和word2[j]相等，不需要进行任何 *** 作
                if word1[i-1:i] == word2[j-1:j]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                # 不相等的话分三种情况讨论
                # 如果把字符 word1[i]替换成与word2[j]相等，则有 dp[i][j] = dp[i-1][j-1]+1
                # 如果在字符串word1末尾插入一个与word2[j]相等的字符，则有 dp[i][j] = dp[i][j-1]+1
                # 如果把字符 word1[i] 删除，则有 dp[i][j] = dp[i-1][j]+1
                    dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1
        return dp[len1][len2]