LeetCode刷题笔记（一）数组

一. 数组

数组题目经常会使用到循环，背以下三种循环方式：

for idx, x in enumerate(nums): # 正向循环
    print(x)

for idx in range(0, len(nums), 1): # 正向循环
    print(nums[idx])

for idx in range(len(nums)-1, -1, -1): # 反向循环
    print(nums[idx])

26. 删除有序数组中的重复项

题目描述：给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
输入：nums = [1,1,2]
输出：2, nums = [1,2]

    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) == 0: # 边界条件
            return 0
        cur = nums[0] # 初始化第0个数
        i_cur = 1 
        for idx in range(1, len(nums)): # 从第1个数开始循环
            if nums[idx] != cur: # 找不同的数，填值到数组的前边。
                nums[i_cur] = nums[idx]
                cur = nums[i_cur]
                i_cur += 1
        return i_cur

66. 加一

题目：加1
输入：digits = [1,2,3]
输出：[1,2,4]

    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)
        if digits[n-1] < 9: # 末尾数不是9 就很好解决
            digits[n-1] += 1
            return digits
        flag = False # 如果数组里全是9，则flag值为True
        for i in range(n-1, -1, -1):
            if digits[i] == 9: # 逆向找9
                digits[i] = 0
                if i == 0:
                    flag = True
            else: # 逆向找到不是9，就可以停了
                digits[i] += 1
                break
        if flag == True:
            digits.insert(0, 1) # 如果数组里全是9，在头部填1
        return digits

88. 合并两个有序数组

题目描述：给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
思考：如果你想正向的填数，那代码会出现很多判断和切片赋值。学会逆向思考。

    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        if n == 0: # 边界条件
            return nums1
        idx_1 = m - 1 # nums1的下标
        jdx_2 = n - 1 # nums2的下标
        index_final = m + n - 1 # 最后返回的nums1的下标
        while jdx_2 >= 0 and idx_1 >= 0: # 逆向循环，找大填数
            if nums1[idx_1] > nums2[jdx_2]:
                nums1[index_final] = nums1[idx_1]
                idx_1 = idx_1 - 1
            else:
                nums1[index_final] = nums2[jdx_2]
                jdx_2 = jdx_2 - 1
            index_final = index_final - 1
        if index_final >= 0 and jdx_2 >= 0: # 如果nums2还有剩下的数，全部仿真nums1的前端
            nums1[0: index_final+1] = nums2[0: index_final+1]
        return nums1

228. 汇总区间

题目：汇总区间
输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]

    def summaryRanges(self, nums: List[int]) -> List[str]:
        res = []
        if len(nums) == 0:
            return res
        start = nums[0]
        for i in range(0, len(nums)-1):
            if nums[i] + 1 != nums[i+1]: # 查看数组间隔不为1就要输出了
                if start != nums[i]:
                    res.append(str(start) + '->' + str(nums[i]))
                    start = nums[i+1]
                else:
                    res.append(str(start))
                    start = nums[i+1] # 记录当前的start
        # 收尾工作
        if start == nums[-1]: # 到达最后一个
            res.append(str(start)) # 如果一样只填一个数
        else:
            res.append(str(start) + '->' + str(nums[-1])) # 如果不一样填一个区间
        return res

283. 移动零

题目描述：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
输入：[0,1,0,3,12]
输出：[1,3,12,0,0]

    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        left = right = 0 # 双指针法
        while right < n:
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1 # left用来记录第几个非0元素
            right += 1 # 不停的循环向前移动