Leetcode 算法面试冲刺 热题 HOT 100 刷题（42 46 48 49 53 55） （五十六）

• 42. 接雨水
• 46. 全排列
• 48. 旋转图像
• 49. 字母异位词分组
• 53. 最大子数组和
• 55. 跳跃游戏

直接看答案了。

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        
        n = len(height)
        leftMax = [height[0]] + [0] * (n - 1)
        for i in range(1, n):
            leftMax[i] = max(leftMax[i - 1], height[i])

        rightMax = [0] * (n - 1) + [height[n - 1]]
        for i in range(n - 2, -1, -1):
            rightMax[i] = max]rightMax[i + 1], height[i])

        ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))
        return ans

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        left, right = 0, len(height) - 1
        leftMax = rightMax = 0

        while left < right:
            leftMax = max(leftMax, height[left])
            rightMax = max(rightMax, height[right])
            if height[left] < height[right]:
                ans += leftMax - height[left]
                left += 1
            else:
                ans += rightMax - height[right]
                right -= 1
        
        return ans

居然bug free了。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if not nums or len(nums) == 0:
            return 
        pth = []
        res = []
        

        def backtracking(nums, pth):
            if len(pth) == len(nums):
                res.append(pth[:])
                return
            for num in nums:
                if num not in pth:
                    pth.append(num)
                    backtracking(nums, pth)
                    pth.pop()
        
        backtracking(nums, pth)
        return res

不会

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        # Python 这里不能 matrix_new = matrix 或 matrix_new = matrix[:] 因为是引用拷贝
        matrix_new = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                matrix_new[j][n - i - 1] = matrix[i][j]
        # 不能写成 matrix = matrix_new
        matrix[:] = matrix_new

下面是我写的，可以过，但是不符合题目原地转化：

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        if not matrix or len(matrix) == 0:
            return 
        n = len(matrix)
        matrix_new = [[0] * n for _ in range(n)]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                matrix_new[j][n - 1 - i] = matrix[i][j]
        matrix[:] = matrix_new

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        # 设矩阵行列数为 n
        n = len(matrix)
        # 起始点范围为 0 <= i < n // 2 , 0 <= j < (n + 1) // 2
        # 其中 '//' 为整数除法
        for i in range(n // 2):
            for j in range((n + 1) // 2):
                # 暂存 A 至 tmp
                tmp = matrix[i][j]
                # 元素旋转操作 A <- D <- C <- B <- tmp
                matrix[i][j] = matrix[n - 1 - j][i]
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
                matrix[j][n - 1 - i] = tmp

bug free

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        if not strs or len(strs) == 0:
            return [[""]]
        res = []
        dic = {}
        for s in strs:
            l = list(s)
            l.sort()
            ss = "".join(l)
            if ss in dic:
                dic[ss].append(s) 
            else:
                dic[ss] = [s]
        for key, val in dic.items():
            res.append(val)
        return res
            

下面是官方的答案：

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)

        for st in strs:
            key = "".join(sorted(st))
            mp[key].append(st)
        
        return list(mp.values())

过了，开心

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums or len(nums) == 0:
            return 
        n = len(nums)
        max_val = 0
        res = float('-inf')
        for i in range(n):
            max_val += nums[i]
            if max_val < 0:
                res = max(res, max_val)
                max_val = 0
                continue
            else:
                res = max(res, max_val)
        return res

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        size = len(nums)
        if size == 0:
            return 0
        dp = [0 for _ in range(size)]

        dp[0] = nums[0]
        for i in range(1, size):
            if dp[i - 1] >= 0:
                dp[i] = dp[i - 1] + nums[i]
            else:
                dp[i] = nums[i]
        return max(dp)

from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        size = len(nums)
        pre = 0
        res = nums[0]
        for i in range(size):
            pre = max(nums[i], pre + nums[i])
            res = max(res, pre)
        return res

不会，直接答案：

class Solution:
    def canJump(self, nums) :
        max_i = 0       #初始化当前能到达最远的位置
        for i, jump in enumerate(nums):   #i为当前位置，jump是当前位置的跳数
            if max_i>=i and i+jump>max_i:  #如果当前位置能到达，并且当前位置+跳数>最远位置  
                max_i = i+jump  #更新最远能到达位置
        return max_i>=i

尝试写了一下，没写对：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_distance = 0
        n = len(nums)
        if n == 1: return True

        for i in range(n - 1):
            if nums[i] == 0:
                max_distance = 0
            else:
                max_distance = i + nums[i]
            if max_distance >= n - 1:
                return True

        return False