01.02.02 练习题目（第 03 天）

1. 0066. 加一

1.1 题目大意

描述：给定一个非负整数数组，数组每一位对应整数的一位数字。

要求：计算整数加 $1$ 后的结果。

说明：

• $1\le digits.length\le 100$。
• $0\le digits[i]\le 9$。

示例：

• 示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123，加 1 之后为 124。

• 示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

解题思路：

该问题中只需要在末尾加1即可，但是需要考虑的是进位。有以下两种情况：

1. 连续进位 例如：1999999
2. 进位导致结果多出一位，例如： 99999

我的解决办法是，从后向前检验10的存在，有10则进1,然后要在下标为0的位置加一个特判

我的题解

class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        l = len(digits)
        digits[l - 1] += 1
        for i in range(l):
            if digits[l - 1 - i] == 10:
                if(i == l-1 and digits[l - 1 - i] == 10):
                    digits[l - 1 - i] = 0
                    digits.insert(0,1)
                    return digits
                digits[l - 1 - i] = 0
                digits[l - 1 - i - 1] += 1 
                continue
            return digits

2. 0724. 寻找数组的中心下标

2.1 题目大意

描述：给定一个数组 $nums$。

要求：找到「左侧元素和」与「右侧元素和相等」的位置，若找不到，则返回 $-1$。

说明：

• $1\le nums.length\le 10^4$。
• $-1000\le nums[i]\le 1000$。

示例：

• 示例 1：

输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11，二者相等。

• 示例 2：

输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。

解题思路：

对于该题，也就是求两侧和的过程，用一个遍历即可，需要注意的是，要先把左值初始化为0

class Solution(object):
    def pivotIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        left = 0
        right =sum(nums[1:])
        ind = 0
        while(ind < len(nums) - 1):
            if left == right:
                return ind
            left += nums[ind]
            right -= nums[ind + 1]
            ind += 1
        if left == right:
                return ind
        return -1

3. 0189. 轮转数组

3.1 题目大意

描述：给定一个数组 $nums$，再给定一个数字 $k$。

要求：将数组中的元素向右移动 $k$ 个位置。

说明：

• $1\le nums.length\le 10^5$。
• $-2^{31}\le nums[i]\le 2^{31}-1$。
• $0\le k\le 10^5$。
• 使用空间复杂度为 $O(1)$ 的原地算法解决这个问题。

示例：

• 示例 1：

输入: 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]

• 示例 2：

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

解题思路：

在python当中我们可以很好的利用列表的切片来完成，可以省去一个个移动的麻烦，但是需要注意的是，在k值可能是大于n，所以我们需要用k%n来定位

我的题解

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        nums[:] = nums[-k % n:] + nums[:-k % n]