LeetCode 66. 加一 Plus One
Table of Contents
中文版：
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
英文版：
Given a non-empty array of digits representing a non-negative integer, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself. Example 1: Input: [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123. Example 2: Input: [4,3,2,1] Output: [4,3,2,2] Explanation: The array represents the integer 4321.
My answer：
# version 1： class Solution: def plusOne(self, digits: List[int]) -> List[int]: num = 0 for i in range(1,len(digits)+1): num = num + 10 ** (i-1) * digits[-i] # 数组结尾是个位 res_num = num + 1 res = [] while res_num != 0: temp = [res_num % 10] res = temp + res res_num = res_num // 10 # 注意 Python3 的语法：一个 / 是正常除法，会得到小数，两个 // 才是取商 return res
# version 2: class Solution: def plusOne(self, digits: List[int]) -> List[int]: i = len(digits) - 1 while i >= 0: if digits[i] != 9: digits[i] = digits[i] + 1 break else: digits[i] = 0 if i == 0: digits.insert(i,1) # 如 9，+1 后是10 i -= 1 return digits
解题报告：
version 1 算法是先把数组变为数字，把数字 + 1 后再取出每一位放入数组。
要考虑这道题的出题目的，会发现以上算法的缺陷，如果数字特别大不能用整数表示，而转为存成数组，此时不可用转成数字+1 的方法来做。要想办法直接在数组上操作。
10 ** (i-1) 表示 10 的 i-1 次方：数组倒数第二位就是数字的十位，也就是 10 的 1 次方，再乘以该数字，比如5，就得到 50.
version 2 解决了 version 1 的缺陷，直接在数组上进行操作。
分为两种情况： = 9 和 != 9，如果不是9，直接 +1 即可。否则涉及到进位，需要把原来是 9 的位置 改为 0，此时还要再分为两种情况，如果此时 i = 0 说明 9 前面没有其他数字，就要在第一位加个1；如果 i 不是 0 则 i = i -1，将前一位数字 + 1即可。
