算法题每日一练---第73天：加一

一、问题描述

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

题目链接：加一

二、题目要求

样例 1

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

样例 2

输入： nums = [9,9]
输出： [1,0,0]

考察

数学思想、进位
建议用时15~35min

三、问题分析

这一题我刚开始看的时候，觉得这题这么简单，直接末位+1，秒杀。提交的时候才发现，题目要求要满10进一，相当于10进制的运算。

首先，我们要从下标0开始存储，最后翻转一下数组就行了，这样可以避免进位不足的情况。

定义r表示进位，满10进1，初始值为1，因为题目要+1，后面只需要对应的下标加上进位r就行。

这种情况还需要满足一个特殊的情况，就是r最后还需要向前进位，但下标到头了，这种情况要补一位。

四、编码实现

classSolution {
public:
vector<int>plusOne(vector<int>&digits) {
inti,n=digits.size(),r=1,k;//初始化数据vector<int>v;//存储数据for(i=0;i<n;i++)//数组从0~n-1存储        {
k=digits[n-1-i]+r;//计算v.push_back(k%10);//存储r=k/10;//判断是否向前进位        }
if(r!=0)//还需要向前进位v.push_back(r);
reverse(v.begin(),v.end());//翻转数组returnv;//输出结果    }
};

五、测试结果