Leetcode刷题笔记——数组与字符串篇

一、数组

第一题

Leetcode14：最长公共前缀：简单题 （详情点击链接见原题）

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""

当前字符串数组长度为0时则公共前缀为空，直接返回
令最长公共前缀ans的值为第一个字符串进行初始化
遍历后面的字符串，依次将其与ans进行比较，两两找出公共前缀，最终结果即为最长公共前缀
如果查找过程中出现了ans为空的情况，则公共前缀不存在直接返回

python代码解法:

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        res = strs[0]   # 初始化strs中的第一个字符串为最长公共前缀
        for i in range(1, len(strs)):
            ans = ''
            temp = strs[i]
            for j in range(0, min(len(temp), len(res))):
                if temp[j] == res[j]:
                    ans += temp[j]
                else:
                    break
            res = ans
            if not ans:		# 如果查找过程中出现了ans为空的情况，则公共前缀不存在直接返回
                break
        return res

第二题

Leetcode977. 有序数组的平方：简单题 （详情点击链接见原题）

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序

解题思路：借助额外的空间，数组其实是有序的，只不过负数平方之后可能成为最大数了，那么数组平方的最大值就在数组两端，不是左边就是右边，不可能是中间
python代码解法:

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        result = [0] * len(nums)
        left, right = 0, len(nums) - 1
        i = right
        while i >= 0:
            if nums[left] ** 2 < nums[right] ** 2:
                result[i] = nums[right] ** 2
                right -= 1
            elif nums[left] ** 2 >= nums[right] ** 2:
                result[i] = nums[left] ** 2
                left += 1
            i -= 1
        return result

第三题

Leetcode48:旋转图像/面试题:旋转矩阵：中等题 （详情点击链接见原题）

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)

        # 一圈一圈的转,一共需要转 n // 2 圈
        # 注意循环不变量原则: 我是按照左闭右开的形式进行旋转,所以是 n - 1 - i
        for i in range(n // 2):
            for j in range(i, n - i - 1):
                temp = matrix[i][j]  # 保存左上

                matrix[i][j] = matrix[n - 1 - j][i]  # 1.左下赋给左上

                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]  # 2.右下赋给左下

                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]   # 3.右上赋给右下

                matrix[j][n - 1 - i] = temp    # 4.保存起来的左上赋给右上

第四题

Leetcode59. 螺旋矩阵 II：中等题 （详情点击链接见原题）

给你一个正整数 n ，生成一个包含 1 到 n² 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix

python代码解法:

"""
# n = 5
1     2     3     4     5
16    17    18    19    6
15    24    25    20    7
14    23    22    21    8
13    12    11    10    9


# n = 6
1     2     3     4     5     6
20    21    22    23    24    7
19    32    33    34    25    8
18    31    36    35    26    9
17    30    29    28    27    10
16    15    14    13    12    11
"""
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = [[0] * n for _ in range(n)]
        loop = n // 2      # 确定迭代次数
        mid = n // 2       # 当 n 为奇数的时候用于填充最后一个位置的空缺
        start_x, start_y = 0, 0     # 在每轮迭代填充数据时的定位
        count = 1
        # offset = 1 填充最外圈
        # offset = 2 填充次外圈
        # offset = 3
        # offset = ...
        for offset in range(1, loop + 1):   # offset用来表示每次循环的圈数控制,每轮填充时预留最后一个位置用于下轮填充的起始位置
            for c in range(start_y, n - offset):       # 固定首行,变换列
                matrix[start_x][c] = count
                count += 1
            for r in range(start_x, n - offset):       # 固定尾列,变换行
                matrix[r][n - offset] = count
                count += 1
            for c in range(n - offset, start_y, -1):        # 固定尾行,变换列
                matrix[n - offset][c] = count
                count += 1
            for r in range(n - offset, start_x, -1):        # 固定首列,变换行
                matrix[r][start_y] = count
                count += 1

            start_x += 1
            start_y += 1
        if n % 2 != 0:
            matrix[mid][mid] = count

        return matrix

第四题进阶

Leetcode54：螺旋矩阵：中等题 （详情点击链接见原题）

给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素

python代码解法:

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        up, down, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
        result = []
        while True:
            for l_to_r in range(left, right + 1):  # 从左到右
                result.append(matrix[up][l_to_r])
            up += 1
            if up > down:
                break
            for u_to_d in range(up, down + 1):      # 从上到下
                result.append(matrix[u_to_d][right])
            right -= 1
            if right < left:
                break
            for r_to_l in range(right, left - 1, -1):  # 从右到左
                result.append(matrix[down][r_to_l])
            down -= 1
            if down < up:
                break
            for d_to_u in range(down, up - 1, -1):       # 从下到上
                result.append(matrix[d_to_u][left])
            left += 1
            if left > right:
                break
        return result

第五题

Leetcode189.轮转数组：中等题 （详情点击链接见原题）

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数

nums = [1,2,3,4,5,6,7], k = 3
1 2 3 | 4 5 6 7
step1：先整体倒叙 7 6 5 | 4 3 2 1
step2：将字符串分为两个部分，再对两部分进行局部倒叙 5 6 7 | 1 2 3 4

python代码解法:

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if k > len(nums):
            k %= len(nums)

        def reverse(num, start, end):
            i, j = start, end
            while i < j:
                num[i], num[j] = num[j], num[i]
                i += 1
                j -= 1

        reverse(nums, 0, len(nums) - 1)
        reverse(nums, 0, k - 1)
        reverse(nums, k, len(nums) - 1)

第六题

Leetcode238. 除自身以外数组的乘积：中等题 （详情点击链接见原题）

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内

初始化：数组res，其中res[0] = 1，辅助变量temp = 1
计算res[i]的下三角各元素的乘积，直接乘入res[i]
计算 res[i]的上三角各元素的乘积，记为 temp，并乘入res[i]

python代码解法:

from typing import List


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1] * len(nums)
        temp = 1
        for i in range(1, len(nums)):
            res[i] = res[i - 1] * nums[i - 1]
        for i in range(len(nums) - 2, -1, -1):
            temp *= nums[i + 1]
            res[i] = res[i] * temp
        return res

第七题

Leetcode289. 生命游戏：中等题 （详情点击链接见原题）

生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机

python代码解法:

import copy


class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """ 
        # 构造 board 的深拷贝
        matrix = copy.deepcopy(board)    # 面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子
        for r in range(len(board)):
            for c in range(len(board[0])):
                if matrix[r][c] == 1:
                    count = 0
                    for x, y in [(r, c - 1), (r, c + 1), (r - 1, c), (r + 1, c), (r - 1, c - 1), (r - 1, c + 1),
                                 (r + 1, c - 1), (r + 1, c + 1)]:
                        if 0 <= x < len(board) and 0 <= y < len(board[0]):
                            if matrix[x][y] == 1:
                                count += 1
                    if count < 2 or count > 3:
                        board[r][c] = 0   # 活细胞死亡

                else:
                    count = 0
                    for x, y in [(r, c - 1), (r, c + 1), (r - 1, c), (r + 1, c), (r - 1, c - 1), (r - 1, c + 1),
                                 (r + 1, c - 1), (r + 1, c + 1)]:
                        if 0 <= x < len(board) and 0 <= y < len(board[0]):
                            if matrix[x][y] == 1:
                                count += 1
                    if count == 3:
                        board[r][c] = 1   # 死细胞复活

第八题

Leetcode27. 移除元素：中等题 （详情点击链接见原题）

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度

python代码解法:

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow_index, fast_index = 0, 0
        while fast_index < len(nums):
            if nums[fast_index] != val:
                nums[slow_index] = nums[fast_index]
                slow_index += 1
            fast_index += 1
        return slow_index

二、字符串

第一题

Leetcode443：压缩字符串：中等题 （详情点击链接见原题）

给你一个字符数组 chars ，请使用下述算法压缩：
从一个空字符串 s 开始。对于 chars 中的每组连续重复字符：
如果这一组长度为 1 ，则将字符追加到 s 中。
否则，需要向 s 追加字符，后跟这一组的长度

第二题

Leetcode151. 反转字符串中的单词：中等题 （详情点击链接见原题）

给你一个字符串 s ，请你反转字符串中单词的顺序。单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。返回单词顺序颠倒且单词之间用单个空格连接的结果字符串

解题思路如下：
如 " the sky is blue "

移除多余空格 the sky is blue
将整个字符串反转 eulb si yks eht
将每个单词反转 blue is the sky the

python代码解法:

class Solution:
    def reverseWords(self, s: str) -> str:
        def remove_extra_space(strs):  # 1.去除首尾以及中间多余的空格
            start, end = 0, len(strs) - 1
            while s[start] == ' ':
                start += 1
            while s[end] == ' ':
                end -= 1
            array = []
            while start <= end:
                temp = s[start]
                if temp != ' ' or array[-1] != ' ':
                    array.append(temp)
                start += 1
            return "".join(array)

        st = remove_extra_space(s)
        st = st[::-1]  # 2.反转整个字符串

        def reverse_str(str1):
            str1 = list(str1)
            i, j = 0, len(str1) - 1
            while i < j:
                str1[i], str1[j] = str1[j], str1[i]
                i += 1
                j -= 1
            return "".join(str1)

        i = 0
        start = 0
        strs = ""
        while i < len(st):
            if st[i] == ' ':
                strs += reverse_str(st[start:i])  # 反转单词
                strs += ' '    # 在单词后面补充空格
                start = i + 1
            elif i == len(st) - 1:
                strs += reverse_str(st[start:i + 1])  # 反转最后一个单词
            i += 1
        return strs

三、其他

第一题

Leetcode13. 罗马数字转整数：简单题 （详情点击链接见原题）

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M

解题思路：
贪心:我们每次尽量使用最大的数来表示,比如 1994 这个数，一次选 1000, 900, 90, 4,会得到正确结果 MCMXCIV
python代码解法:

class Solution:
    def romanToInt(self, s: str) -> int:
        hash_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        pre_num = hash_map[s[0]]
        total = 0
        for i in range(1, len(s)):
            cur_num = hash_map[s[i]]
            if pre_num < cur_num:  # 当小值在大值的左边,则减小值
                total -= pre_num
            else:  # 当小值在大值的右边,则加小值
                total += pre_num
            pre_num = cur_num
        total += pre_num
        return total

第二题

Leetcode12. 整数转罗马数字：中等题 （详情点击链接见原题）

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M

python代码解法:

class Solution:
    def intToRoman(self, num: int) -> str:
        hash_map = {1000: 'M', 900: 'CM', 500: 'D', 400: 'CD', 100: 'C', 90: 'XC', 50: 'L', 40: 'XL', 10: 'X', 9: 'IX',
                    5: 'V', 4: 'IV', 1: 'I'}
        res = ''
        for key in hash_map:
            if num // key != 0:
                remain = num // key  # 提取最高位
                res += hash_map[key] * remain
                num %= key
        return res

第三题

Leetcode1419. 数青蛙：中等题 （详情点击链接见原题）

给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak”
请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目

遍历到c时，看看有没有青蛙刚才发出了k的声音，如果有则复用这只青蛙
遍历到r时，看看有没有青蛙发出c的声音，如果有则复用，否则产生一只新的青蛙从c开始蛙鸣(如果不是从c开始蛙鸣则终止)，其余同理
遍历结束后，所有青蛙必须在最后发出 k 的声音，如果有青蛙在最后发出的声音不是 k 则返回 -1，返回counter[k]即最小的青蛙数目

python代码解法:

class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        counter = Counter()
        previous = {'c': 'k', 'r': 'c', 'o': 'r', 'a': 'o', 'k': 'a'}
        for i in croakOfFrogs:
            pre = previous[i]
            if counter[pre]:	# 遍历到i时,看看发出前一种声音的青蛙能不能复用
                counter[pre] -= 1
            elif i != 'c':		# 如果不能复用则青蛙必须从'c'开始蛙鸣
                return -1
            counter[i] = counter.get(i, 0) + 1
        for ch in "croa":
            if counter[ch] != 0:
                return -1
        return counter['k']