leetcode 41-50（2024.08.19）

立个flag，1-100题每天分配10题，不会就先空着（4，10）。

1. 41：缺失的第一个正数

class Solution:def firstMissingPositive(self, nums: List[int]) -> int:n = len(nums)for i in range(n):if nums[i] <= 0 or nums[i] >= n:nums[i] = nfor i in range(n):if 0 < abs(nums[i]) < n:if nums[nums[i]] > 0:nums[nums[i]] = - nums[nums[i]]for i in range(n):if nums[i] > 0:breakreturn i

2. 42：接雨水

class Solution:def trap(self, height: List[int]) -> int:max_left = 0max_right = 0left = []right = []res = 0for i in range(0, len(height) - 2, 1):if height[i] > max_left:max_left = height[i]left.append(max_left)for i in range(len(height) - 1, 1, -1):if height[i] > max_right:max_right = height[i]right.append(max_right)right = right[::-1]for i in range(1, len(height) - 1):if min(left[i-1], right[i-1]) > height[i]:res = res + min(left[i-1], right[i-1]) - height[i]return res

3. 43：字符串相乘

class Solution:def multiply(self, num1: str, num2: str) -> str:sum = 0leng1 = len(num1)for i in num1:leng2 = len(num2)for j in num2:sum = sum + int(i) * 10 ** (leng1 - 1) * int(j) * 10 ** (leng2 - 1)leng2 = leng2 - 1leng1 = leng1 - 1return str(sum)

4. 44：通配符匹配 

5. 45：跳跃游戏2

class Solution:def jump(self, nums: List[int]) -> int:res = 0distance = 0end = 0for i in range(len(nums) - 1):distance = max(distance, i + nums[i])if i == end:res = res + 1end = distancereturn res

6. 46：全排列

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:def backtracking(nums, path, res):if len(path) == len(nums):res.append(path.copy())returnfor i in nums:if i in path:continuepath.append(i)backtracking(nums, path, res)path.pop()res = []path = []backtracking(nums, path, res)return res

7. 47：全排列2

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:def backtrack(nums, used, res, path):if len(path) == len(nums):res.append(path.copy())returnfor i in range(len(nums)):if used[i]:continueif i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:continueused[i] = 1path.append(nums[i])backtrack(nums, used, res, path)used[i] = 0path.pop()res = []path = []used = [0] * len(nums)nums.sort()backtrack(nums, used, res, path)return res

8. 48：旋转图像

class Solution:def rotate(self, matrix: List[List[int]]) -> None:"""Do not return anything, modify matrix in-place instead."""n = len(matrix)for i in range(n // 2):for j in range((n + 1) // 2):temp = matrix[i][j]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] = temp

9. 49：字母异位词分组

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:res = []haxi = {}for i in strs:sort_i = "".join(sorted(i))if sort_i in haxi:haxi[sort_i].append(i)else:haxi[sort_i] = [i]for key in haxi:res.append(haxi[key])return res

10. 50：Pow(x, n)