一、单调数列

class Solution:
    def isMonotonic(self, A: List[int]) -> bool:
        # 递归
        inc = dec = True # 假设最开始认为它既单增又单减
        for i in range(1, len(A)):
            if A[i] > A[i - 1]:
                dec = False # A[i] > A[i - 1]，因此不可能为单减
            if A[i] < A[i - 1]:
                inc = False # A[i] < A[i - 1]，因此不可能为单增
        return inc or dec

一、寻找数组的中心索引

最开始本来想用双指针夹逼，但是发现测试例子中出现了负数！就不行了比如[-1,-1,-1,-1,-1,0]。

1、天平思想

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        # 法1: 天平思想
        left_sum, right_sum = 0, sum(nums) # 先把所有东西都放到最右边
        for i, v in enumerate(nums): # 这个相当于在遍历找中心索引
            right_sum -= v # 必须给中心索引留个位置，所以本句代码在if语句上面
            if left_sum == right_sum: # 相等, 返回当前元素的index即是中心索引
                return i
            left_sum += v # 不等，当前i不是中心索引，将当前元素放到左边
        return -1

2、前缀和

对于此题来说，说白了一个数组的和等于left_sum + right_sum + center_index_nums,
由于题目要求left_sum == right_sum，因此2 * left_sum + center_index_nums== sum_arr

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        left_sum, sums = 0, sum(nums)
        for i, v in enumerate(nums): # 这个相当于在遍历找中心索引
            if 2 * left_sum + v == sums:
                return i
            left_sum += v
        return -1

二、删除排序数组中的重复项

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # 双指针
        # 核心思想，指针i负责修改数据，指针j负责遍历nums，找出和当前指针i所指数不一样的数，然后添加到i+1处
        i = 0
        for j in range(1, len(nums)):
            if nums[i] != nums[j]:
                i += 1
                nums[i] = nums[j]
        return i + 1

上面稍有不足！

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # 代码优化部分：if j - i > 0:
        # 如果是[1,2,3,4,5,6]这种情况，其实就不用执行nums[i] = nums[j]
        # 应该是只在有多个相同数才进行nums[i] = nums[j]
        i = 0
        for j in range(1, len(nums)):
            if nums[i] != nums[j]:
                i += 1
                if j - i > 0: nums[i] = nums[j]
        return i + 1

三、合并两个有序数组

1、易懂题解

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1_copy = nums1[:m] 
        nums1[:] = []
        p1 = 0 
        p2 = 0
        while p1 < m and p2 < n: 
            if nums1_copy[p1] < nums2[p2]: 
                nums1.append(nums1_copy[p1])
                p1 += 1
            else:
                nums1.append(nums2[p2])
                p2 += 1
        if p1 < m: 
            nums1[(p1 + p2):] = nums1_copy[p1:]
        if p2 < n:
            nums1[(p1 + p2):] = nums2[p2:]

2、高配题解

def merge(self, nums1, m, nums2, n):
        while m > 0 and n > 0:
            if nums1[m - 1] > nums2[n - 1]:
                nums1[m + n - 1] = nums1[m - 1]
                m -= 1
            else:
                nums1[m + n - 1] = nums2[n - 1]
                n -= 1
        if n: nums1[:n] = nums2[:n]

四、旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

1、python自带的双端队列

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        dq = collections.deque(nums)
        dq.rotate(k)
        nums[:] = list(dq)[:]

2、切片

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        size = len(nums)
        k %= size
        nums[:] = nums[size - k:] + nums[:size - k]

3、数组翻转

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        k %= len(nums)
        self.reverse(nums, 0, len(nums) - 1)
        self.reverse(nums, 0, k - 1)
        self.reverse(nums, k, len(nums) - 1)

    def reverse(self, num, start, end):
        while start < end:
            num[start], num[end] = num[end], num[start]
            start += 1
            end -= 1