leetcode 71-80（2024.08.22）

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

1. 71：简化路径

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        paths = path.split("/")
        for i in paths:
            if i == "." or i == "":
                continue
            elif i == "..":
                if stack:
                    stack.pop()
            else:
                stack.append(i)
        path = "/" + "/".join(stack)
        return path

2. 72：编辑距离

3. 73：矩阵置零

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        haxi_row = []
        haxi_col = []
        m = len(matrix)
        n = len(matrix[0])
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    if i not in haxi_row:
                        haxi_row.append(i)
                    if j not in haxi_col:
                        haxi_col.append(j)
        for i in range(m):
            for j in range(n):
                if i in haxi_row or j in haxi_col:
                    matrix[i][j] = 0

4. 74：搜索二维矩阵

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        nums = []
        for i in range(m):
            nums = nums + matrix[i]
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return True
            elif nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
        return False

 5. 75：颜色分类

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        slow = 0
        fast = 0
        while fast < len(nums):
            if nums[fast] == 0:
                temp = nums[slow]
                nums[slow] = nums[fast]
                nums[fast] = temp
                slow = slow + 1
            fast = fast + 1
        fast = slow
        while fast < len(nums):
            if nums[fast] == 1:
                temp = nums[slow]
                nums[slow] = nums[fast]
                nums[fast] = temp
                slow = slow + 1
            fast = fast + 1

6. 76：最小覆盖子串

7. 77：组合

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtracking(n, k, start, path, res):
            if len(path) == k:
                res.append(path.copy())
                return
            for i in range(start, n + 1):
                path.append(i)
                backtracking(n, k, i + 1, path, res)
                path.pop()

        res = []
        path = []
        start = 1
        backtracking(n, k, start, path, res)
        return res

8. 78：子集

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtracking(nums, start, path, res):
            res.append(path.copy())
            if len(path) == len(nums):
                return
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtracking(nums, i + 1, path, res)
                path.pop()

        res = []
        path = []
        start = 0
        backtracking(nums, start, path, res)
        return res

9. 79：单词搜索

10. 80：删除有序数组中的重复项2

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 0
        fast = 0
        while fast < len(nums):
            if slow > 1 and nums[fast] == nums[slow - 2]:
                fast = fast + 1
            else:
                nums[slow] = nums[fast]
                slow = slow + 1
                fast = fast + 1
        return slow