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

昨天周六，摆烂一天。

1. 31：下一个排列

python">class Solution:def nextPermutation(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""i = len(nums) - 1while i > 0:if nums[i - 1] < nums[i]:breakelse:i = i - 1if i == 0:nums.sort()else:idx1 = i - 1num1 = nums[idx1]i = len(nums) - 1while i > idx1:if nums[i] > num1:breakelse:i = i - 1idx2 = inum2 = nums[idx2]nums[idx1], nums[idx2] = num2, num1left = idx1 + 1right = len(nums) - 1while left < right:nums[left], nums[right] = nums[right], nums[left]left = left + 1right = right - 1

2. 32：最长有效括号

3. 33：搜索旋转排序数组

python">class Solution:def search(self, nums: List[int], target: int) -> int:left = 0right = len(nums) - 1while left <= right:mid = left + (right - left) // 2if nums[mid] == target:return midif nums[left] <= nums[mid]:if nums[left] <= target < nums[mid]:right = mid - 1else:left = mid + 1elif nums[left] > nums[mid]:if nums[mid] < target <= nums[right]:left = mid + 1else:right = mid - 1return -1

4. 34：在排序数组中查找元素的第一个和最后一个位置

python">class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:def searchLeft(nums, target):left = 0right = len(nums) - 1while left <= right:mid = left + (right - left) // 2if nums[mid] < target:left = mid + 1elif nums[mid] >= target:right = mid - 1if nums[left] == target:return leftelse:return -1def searchRight(nums, target):left = 0right = len(nums) - 1while left <= right:mid = left + (right - left) // 2if nums[mid] > target:right = mid - 1elif nums[mid] <= target:left = mid + 1if nums[right] == target:return rightelse:return -1if len(nums) == 0 or nums[0] > target or nums[-1] < target:return [-1, -1]else:left = searchLeft(nums, target)right = searchRight(nums, target)return [left, right]

5. 35：搜索插入位置

python">class Solution:def searchInsert(self, nums: List[int], target: int) -> int:left = 0right = len(nums) - 1while left <= right:mid = left + (right - left) // 2if nums[mid] == target:return midelif nums[mid] < target:left = mid + 1elif nums[mid] > target:right = mid - 1return left

6. 36：有效的数独

python">class Solution:def isValidSudoku(self, board: List[List[str]]) -> bool:hang = []lie = []gong = []for i in range(9):hang.append([])lie.append([])gong.append([])for i in range(9):for j in range(9):num = board[i][j]if num == ".":continueif num in hang[i] or num in lie[j] or num in gong[3 * (i // 3) + 1 * (j // 3)]:return Falsehang[i].append(num)lie[j].append(num)gong[3 * (i // 3) + 1 * (j // 3)].append(num)return True

7. 37：解数独

python">class Solution:def solveSudoku(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""def isValid(board, i, j, n):for k in range(9):if n == board[k][j] or n == board[i][k]:return Falsestart_row = (i // 3) * 3start_col = (j // 3) * 3for i in range(start_row, start_row + 3):for j in range(start_col, start_col + 3):if n == board[i][j]:return Falsereturn Truedef backtracking(board):for i in range(9):for j in range(9):if board[i][j] != '.':continuefor num in range(1, 10):if isValid(board, i, j, str(num)):board[i][j] = str(num)if backtracking(board):return Trueboard[i][j] = '.'return Falsereturn Truebacktracking(board)

8. 38：外观数列

9. 39：组合总和

python">class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:def backtracking(candidates, target, start, path, res):if sum(path) == target:res.append(path.copy())returnfor i in range(start, len(candidates)):if candidates[i] + sum(path) > target:breakpath.append(candidates[i])backtracking(candidates, target, i, path, res)path.pop()res = []path = []start = 0candidates.sort()backtracking(candidates, target, start, path, res)return res

10. 40：组合总和2

python">class Solution:def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:def backtracking(candidates, target, start, path, res):if sum(path) == target:res.append(path.copy())returnfor i in range(start, len(candidates)):if i > start and candidates[i] == candidates[i - 1]:continueif candidates[i] + sum(path) > target:breakpath.append(candidates[i])backtracking(candidates, target, i + 1, path, res)path.pop()res = []path = []start = 0candidates.sort()backtracking(candidates, target, start, path, res)return res