今天我们一起掌握 leetocode 的 43, 46, 53 题。涉及到3种题型，值得一做。

1. lc 43 - 字符串相乘

题目来源

  • 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
  • 难度：中等

注意：不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

1.1 解题思路 - 模拟「竖式乘法」

由题目知，不能直接将输入转换为整数来处理，例如 int(num1)。因此，我们可以采用我们平时在纸上计算乘数的思路解题。

此题中，以 num1 为被乘数， num2 为乘数。从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加。 ​
同时，注意除了最低位以外，其余的每一位的运算结果都需要补0。

具体流程图：

1.2 时间复杂度

  • 时间复杂度：O(m * n+n^2)，其中 m,n 是 num1, num2 的长度。需要从右往左遍历 num2，对于 num2 的每一位，都需要和 num1 的每一位计算乘积，因此计算乘积的总次数是 mn。字符串相加操作共有 n 次，相加的字符串长度最长为 m+n，因此字符串相加的时间复杂度是 O(m * n+n^2)
  • 空间复杂度：O(m+n)。空间复杂度取决于存储中间状态的字符串，由于乘积的最大长度为 m+n，因此存储中间状态的字符串的长度不会超过 m+n。

1.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == '0' or num2 == '0' : return "0"
        l1 = list(map(int,list(num1))) # 用列表储存num1的每一数位
        l2 = list(map(int,list(num2))) # 用列表储存num2的每一数位
        
        carry2 = 1 # 帮助 num2 中乘数的进位  
        res = 0
        
        # 累加 乘数的每一位与被乘数相乘得到的结果
        while l2: 
            carry1 = 1 # 帮助 num1 中被乘数的进位 
            tmp = 0 # 储存在未进位时，乘数的每一位与被乘数相乘得到的结果
            factor2 = l2.pop()
            # 将被乘数的每一位与乘数的当前位相乘，得到的结果累加，并存入tmp
            for i in range(len(l1)-1,-1,-1):
                print(i)
                tmp += l1[i]*factor2*carry1
                carry1 *= 10  # 被乘数进位
 
            res += tmp * carry2
            carry2 *= 10 # 乘数进位
        return str(res)

2. lc 46 - 全排列

题目来源

  • 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
  • 难度：中等

2.1 解题思路 - 递归

看了部分解析，皆采用回溯法。今天，我们将用简单的递归，一样也能解题。

我们会用到recursion(choosen:list,candidates:list)递归函数。choosen会储存被选中加入排序的元素，剩下的没被选择的，作为排列的候选。

举例，nums = [1,2,3,4]，则第一个递归choosen为[1],candidates = [2,3,4]；第二次递归中，choosen为[2],candidates = [1,3,4]，以此类推。

2.2 时间复杂度

  • 时间复杂度：O(n*n!)。递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数。显然代码中递归次数是排列的可能情况 n！，而每次递归操作最坏情况为 n（遍历长度为n的candidates）。
  • 空间复杂度：O(n)。其中 n 为序列的长度。除答案数组以外，递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，这里可知递归调用深度为 O(n) 。

2.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 0: return []

        self.res = []
        self.length = len(nums)
        self.recursion([],nums)
        return self.res
        
    '''
    choosen列表储存一种新的排列的元素
    candidates列表存储待选的元素
    '''
    def recursion(self,choosen,candidates):
        if len(choosen) == self.length: # 当 choosen 长度达到要求，加入返回列表res中
            self.res.append(choosen)  
            return
        for i in range(len(candidates)): # 遍历 candidates列表 每个待选，放入到choosen，递归直到产生一种新的排序
            tmp1 = choosen.copy() 
            tmp1.append(candidates[i])

            tmp2 = candidates.copy() 
            del (tmp2[i])

            self.recursion(tmp1,tmp2)

3. lc 53 - 连续子数组的最大和

题目来源

  • 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。
  • 难度：简单

3.1 解题思路 - 动态规划

我们用遍历输入数组 nums 时，所有以当前元素 nums[i] 为结尾的连续子数组最大和，是可以获得的。这个值 max_value 必然是当前元素和（0或者一个正值）的加和。若这个值也是正值，又可以作为 i+1 时的正值。

用一个额外数组 res 储存 nums 每一位时对应的max_value。然后求取 res 中的最大值，也就是 nums 每一个 nums[i] 为结尾的连续子数组最大和，之中的最值，便是整个 nums 所有子数组的和的最大值。

此外，我们也可以用「动态规划」的思想解题：

3.2 时间复杂度

  • 时间复杂度：O(n) 线性遍历数组
  • 空间复杂度：O(n)
  • 改进：空间复杂度：O(1)：由于省去 dp 列表使用的额外空间，因此空间复杂度从 O(n) 降到 O(1)

3.3 代码

1
2
3
4
5
6
7
8
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_value = 0
        res = []
        for i in range(len(nums)):
            max_value = max(0,max_value) + nums[i]
            res.append(max_value)
        return max(res)

优化空间复杂度：

1
2
3
4
5
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] += max(nums[i - 1], 0)
        return max(nums)

参考

[1] 递归的时间复杂度计算. https://www.zhihu.com/question/63075755

[2] lc 53 题解. https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/mian-shi-ti-42-lian-xu-zi-shu-zu-de-zui-da-he-do-2/