66. 加一

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        digits_idx = len(digits) - 1
        while digits_idx >= 0 and digits[digits_idx] == 9:
            digits[digits_idx] = 0
            digits_idx-= 1
        if digits_idx >= 0:
            digits[digits_idx] +=1
        else:
            digits = [1] + digits
        return digits

• 审题是难点，写得太不清楚了。主要目的是，实现一个类似“人类计算加法”的过程，即从最后一位加1，满10则进一位。
• 本题关键是，从最后一位开始遍历，因此首先是digits_idx = len(digits) - 1
• 最开始写时，while条件写得不对，主要有两个判断逻辑，（1）当前数前是否还有数值，有则进入while继续遍历；（2）判断当前数是否是9，是，则置零，并看前面一位是什么数，判断如何进位。
• 第一个if，如果不是9，直接加1即可。
• else 即为前面不再有数字，最前方加个1即可。

724. 寻找数组的中心下标

# 暴力做法
class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            left_res = sum(nums[:i])
            right_res = sum(nums[(i+1):])
            if left_res == right_res:
                return i
        return -1

presum解法，即从左向右遍历数组，当遍历到数组的 i 位置时，preSum表示 i 位置左边的元素之和。

class Solution:
    def pivotIndex(self, nums):
        total = sum(nums)
        pre_sum = 0
        for i in range(len(nums)):
            if total - nums[i] == pre_sum * 2:
                return i
            pre_sum += nums[i]
        return -1

• 如果是存在中心点的数组，构造是这样的xxxxAyyyy，前半部分和后半部分长度无要求，取值范围是[0, +∞]，presum可以理解为前半部分的和。
• 从前往后遍历，假设这个A存在，使用total-A，即判断挖去A的总和==前半部分*2
• 不断的累加presum，直至遍历到最后一个点。

189. 轮转数组

# 直接切片做
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        len_list = len(nums)
        step = k % len_list  # 这里非常易错，k可以是len的倍数，因此用k除len_list
        nums[:] = nums[len_list - step:] + nums[: len_list - step]

这种解法感觉很巧妙，但是更加“算法化”，考虑三次反转

• 三次反转的核心是：找到两段；对两段分别反转；再对整体反转。
• 找到两段。（1）因为k可能是好几倍数组长度的叠加，因此首先进行k=k%n，以此找到两段的索引范围。（2）第一段是下标为[0,1,2,…,n-k-1]的部分，第二段是下标为[n-k,…,n-1]的部分。
• 交换部分，两头夹击做法

# 交换部分
def swap(l, r):
	while l < r:
		nums[l], nums[r] = nums[r], nums[l]
		l += 1
		r -= 1

# 最后整体代码
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n=len(nums)
        k=k%n
        def swap(l,r):
            while(l<r):
                nums[l],nums[r]=nums[r],nums[l]
                l=l+1
                r=r-1
        swap(0,n-k-1)
        swap(n-k,n-1)
        swap(0,n-1)