为什么我要给出完整解答,因为要搜索个题目的解答,很多都偷懒只给个方法的实现,结果跑都跑不起来。于是我就决定,每一题,都给出Java&C两种完整的解答,直接就可以运行,Debug。
Leetcode题目来源:66.加一
给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
#include <iostream>
#include <vector>
using namespace std;
int main() {
//声明一下数组
vector<int> plusOne(vector<int> &digits);
vector<int> arr;
/*arr.push_back(1);
arr.push_back(2);*/
arr.push_back(9);
plusOne(arr);
for (int i = 0; i < arr.size(); ++i) {
cout<<arr[i]<<",";
}
return 0;
}
/*从后向前遍历数组,使用tag记录当前位加1后的结果,再将tag%10赋给当前位。当出现以下情况之一时停止遍历:
1.数组已遍历完成(此时如果首位是9,加1后需进位(即在数组最前面插入一个1),因此需要进行2.中的判断)
2.当前位加1后不需要进位,即tag<10。
如果原数组首位(如果i<0则tag为原数组首位加1结果)加1结果大于10,需要进位,使用insert()函数在数组前面插入一个1。
作者:yj-eden-2
链接:https://leetcode-cn.com/problems/two-sum/solution/cti-jie-by-yj-eden-2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
*/
vector<int> plusOne(vector<int> &digits) {
//获取当前数组的长度
int i = digits.size() - 1;
//tag记录当前位加1后的结果
int tag = 0;
//当i>=0时候,进行遍历循环
while (i >= 0){
//从后向前遍历
tag = digits[i]+1;
//除10取余
digits[i] = tag % 10;
i--;
//如果tag小于10,不需要进位,退出循环
if (tag < 10){
break;
}
}
//如果大雨或者等于10,需要进位
if (tag >= 10){
//在数组的开始位置插入一个元素1
digits.insert(digits.begin(),1);
}
return digits;
}
public class Main {
public static void main(String[] args) {
int[] arr = {9,1,1};
int[] result = plusOne(arr);
for (int i = 0; i < result.length; i++) {
System.out.println(result[i]);
}
}
/*垃圾算法,没有考虑到999*/
/*public static int[] plusOne(int[] digits) {
int end = digits.length-1;
int num = digits[end]+1;
if ( num >= 10){
int[] arr = new int[digits.length+1];
for (int i = 0; i < digits.length-1; i++) {
for (int j = 0; j < arr.length; j++) {
arr[j] = digits[i];
}
}
arr[arr.length-2] = num/10;
arr[arr.length-1] = 0;
return arr;
}else {
digits[end] = digits[end] + 1;
return digits;
}
}*/
/*根据题意加一,没错就是加一这很重要,因为它是只加一的所以有可能的情况就只有两种:
除 99 之外的数字加一;
数字 99。
加一得十进一位个位数为 00 加法运算如不出现进位就运算结束了且进位只会是一。
所以只需要判断有没有进位并模拟出它的进位方式,如十位数加 11 个位数置为 00,如此循环直到判断没有再进位就退出循环返回结果。
然后还有一些特殊情况就是当出现 9999、999999 之类的数字时,循环到最后也需要进位,出现这种情况时需要手动将它进一位。
作者:yhhzw
链接:https://leetcode-cn.com/problems/two-sum/solution/java-shu-xue-jie-ti-by-yhhzw/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
*/
public static int[] plusOne(int[] digits){
//从末尾向前进行遍历
for (int i = digits.length -1; i >= 0 ; i--) {
//结尾数字加1
digits[i]++;
//末尾数字取余,如果是0-8,取余依然是原数值
digits[i] = digits[i]%10;
//故,当取余后的值不为0的时候,停止遍历,直接返回
if (digits[i] != 0){
return digits;
}
//而,如果数字为9的话,需要遍历。
//例如数组为[9,9]
//第一次遍历digits[1] = 9,9+1=10,0%10=0。将0赋值给digits[1]
//第二次遍历digits[0] = 9,9+1=10,0%10=0。将0赋值给digits[0]
//i-- ,i=-1,退出循环,此时[0,0]
}
//对数组进行扩容
digits = new int[digits.length + 1];
//最终数组就是[1,0,0]
digits[0]=1;
return digits;
}
}
好啦,祝大家都能成为算法大神!