LeetCode【#66】Plus One

题目链接:

点击跳转

 

题目：

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.

题目分析：

给定一个整型数组，其中每个元素表示一个数的某一位。最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。现在要将这个 整数+1，输出最后结果（也还是用vector 存储每一位）。

 

解题思路：

简单模拟题，数组vector 的首位是最高位，末位是最低位。模拟一个加法操作。

也就是最低为 +1，然后判断是否有进位，如果没有进位，结束遍历；如果有进位，那就把进位加到下一位上。然后循环这个过程，直至遍历数组所有元素。（从末位往首位遍历）。

例子：4 3 2 1

先 1+1 = 2，进位为0，所以结束遍历

最后 4 3 2 2

会出现一种情况，如 9 9，当 9+1 = 10 = 0，进位为1，然后下一位 9+1=10- > 0，进位为1。此时已经遍历完数组了，数组现在为 0 0 。但实际上，应该最后输出是 1 0 0。所以要最后判断，遍历结束时，如果进位不为0，那就给数组的首位多加上一个元素 1； 否则不用处理。

 

AC代码：

class Solution { public: vector<int> plusOne(vector<int>& digits) { int c = 0; int len = digits.size(); digits[len-1] = digits[len-1] + 1 + c; c = digits[len-1] / 10; digits[len-1] %= 10; for(int i = len-2;i >= 0;--i){ if(c == 0) break; digits[i] = digits[i] + c; c = digits[i] / 10; digits[i] %= 10; } if(c != 0) digits.insert(digits.begin(),1); return digits; } };