首页 > 试题广场 >

加一

[编程题]加一
  • 热度指数:12887 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给出用数字数组表示的一个非负整数,请对该整数加1。
示例1

输入

[1]

输出

[2]
示例2

输入

[1,2,3]

输出

[1,2,4]
//题目还是小伙伴解释才看懂。。。输入的数组digits表示一个大整数,每个表示一位。
class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
        const int num = 1;  //待加数
        int carry = num;    //进位
        for (int i = digits.size() - 1; i >= 0; i--) {
            digits[i] += carry;
            carry = digits[i] / 10;
            digits[i] %= 10;
        }
        if (carry > 0)
            digits.insert(digits.begin(),1);
        return digits;
    }
};

发表于 2016-09-01 17:34:12 回复(5)
import java.math.BigDecimal;
public class Solution {
    public int[] plusOne(int[] digits) {
		String s = "";
        for (int i:digits){
			s += i;
        }
		s = new BigDecimal(s).add(BigDecimal.valueOf(1)).toString();
		int[] res = new int[s.length()];
		for (int i = 0; i < s.length(); i ++ ) {
			res[i] = s.charAt(i) - '0';
		}
		return res;
	}
}

发表于 2016-11-05 16:39:21 回复(1)
//从右往左判断数字加一是否为10,如果为10则该位置0并继续往左,当到首位时则需要在首位前添加1,
//如果不为10则该位加一结束退出
class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
        for(int i = digits.size()-1; i >= 0; i--){
            if((digits[i] + 1) != 10){
                digits[i] += 1;
                break;
            }
            else if(digits[i] + 1 == 10){
                digits[i] = 0;
                if(i == 0){
                    digits.insert(digits.begin(), 1);
                }
            }
        }
        return digits;
    }
};
发表于 2020-03-25 15:29:35 回复(0)
/**
 * 66. Plus One
 * 加一
 * 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。

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

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

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
 * @author shijiacheng
 *
 */
public class Solution {
    public int[] plusOne(int[] digits) {

        int n = digits.length;
        for(int i = n-1;i>=0;i--) {
            if(digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }

        int[] newDigits = new int[n+1];
        newDigits[0] = 1;

        return newDigits;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] digits = {9};
        int[] newDigits = s.plusOne(digits);
        System.out.println(newDigits[0]);
    }
}
发表于 2018-09-06 12:50:50 回复(0)

读题读了半天。。
一次遍历。

class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
       if(digits.size()==0)
           return digits;
        int i=digits.size();
        int c=1;
        vector<int>res;
        while(i){
            if(c+digits[i-1]>9){
                res.push_back(0);
                c=1;
            }
            else{
                res.push_back(digits[i-1]+c);
                c=0;
            }
            i--;
        }
        if(c)
            res.push_back(c);
        reverse(res.begin(),res.end());
        return res;
    }
};
发表于 2018-06-28 22:15:34 回复(0)
/*
* 一个数以数组形式给你,加1后以数组形式返回,最低位开始按位相加即可,temp保存进位信息。
*/
 public int[] plusOne(int[] digits) {
        int temp=1;
        for(int i=digits.length-1;i>=0;i--) {
            int num = digits[i];
            digits[i] =(num+temp)%10;
            temp = (num+temp)/10;
        }
        if(temp==1) {
            int[] array=new int[digits.length+1];
            array[0]=1;
            return array;
        }else {
            return digits;
        }
    }

发表于 2018-05-27 19:56:46 回复(0)
class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
        for(int i=digits.size()-1;i>=0;i--)
        {
            if(digits[i]==9)
                digits[i]=0;
            else
            {
                digits[i]++;
                break;
            }
        }
        if(digits[0]==0)
        {
            
            digits.insert(digits.begin(),1);
        }
        return digits;
    }
};


发表于 2017-10-14 10:01:59 回复(0)
public class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length;
        int[] res = new int[len];
        int c = 0;
        digits[len-1] = digits[len-1]+1;
        for(int i=len-1;i>=0;i--) {
            int temp = digits[i]+c;
            res[i] = temp%10;
            c = temp/10;
        }
        if(c!=0) {
            int[] newRes = new int[len+1];
            newRes[0] = c;
            for(int i=1;i<len+1;i++) {
                newRes[i] = res[i-1];
            }
            return newRes;
        }
        return res;
    }
}

发表于 2017-09-06 01:09:43 回复(0)
class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
        vector<int> num = digits;
        int n = digits.size();
		int C = 0;
		num[n-1] += 1;
		for(int i=n-1;i>=0;i--)
		{
			num[i] += C + 1;
			if(num[i] > 9)
			{
				C = 1;
				num[i] = num[i]%10;
			}else{
				C = 0;
			}
		}
		if(C == 1)
			num.insert(num.begin(),1);
		return num;        
    }
};
发表于 2017-08-11 00:38:23 回复(0)
/**
*   题目的意思是输入一个数字,这个数字用数组表示,对这个数字加1后用数组返回
*/

import java.util.*;
public class Solution {

      public int[] plusOne(int[] digits) {
        if (digits == null) {
            return null;
        }
        int[] res;
        //如果最后以为加上1不会引起进位,直接加1返回
        //clone是为了不改变输入参数
        if (digits[digits.length - 1] < 9) {
            res = digits.clone();
            res[digits.length - 1]++;
        }

        res = new int[digits.length + 1];
        //保存进位
        int carry = 1;
        for (int i = digits.length - 1; i >= 0; i--) {
            res[i + 1] = (digits[i] + carry) % 10;
            carry = (digits[i] + carry) / 10;
        }
        //最高位的进位
        res[0] = carry;
        //数字加上1后最高位没有产生进位
        if (carry == 0) {
            return Arrays.copyOfRange(res, 1, res.length);
        }
        return res;
    }
}
发表于 2017-06-21 15:14:35 回复(0)
void plusone(vector<int> &digits)
{ int n = digits.size();
	for (int i = n - 1; i >= 0; --i)
	{ if (digits[i] == 9)
		{ digits[i] = 0;
		} else { digits[i]++; return;
		}
	} digits[0] =1; digits.push_back(0);
		
}

发表于 2017-03-12 12:12:50 回复(1)
#include<algorithm>
class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
        int add = 1;//进位值
        vector<int> res;
        for (int i = digits.size()-1; i >=0 ; i--){
            res.push_back((add + digits[i]) % 10);
            add = (add + digits[i]) / 10;
        }
        if (add){
            res.push_back(add);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

发表于 2016-06-10 17:05:25 回复(0)
class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
        int i = digits.size() - 1;
        // 末尾9全部置0
        while(i >= 0 && digits[i] == 9) {
            digits[i] = 0;
            --i;
        }
        // 是否为全9数字
        if(i >= 0) ++digits[i];
        else {
            // 头部insert效率不高,改成首部改0,尾部再加一个0
            digits.push_back(0);
            digits[0] = 1;
        }
        return digits;
    }
};

发表于 2017-10-15 18:14:23 回复(0)
//1.不需要flag! 从右向左,遇到9就变0,非9就加1,然后break;
//2.digits[0]如果等于0,说明长度增加了1,则新建数组,首位为1,其他位为0;   
 public int[] plusOne(int[] digits) {
        for (int i = digits.length-1; i >= 0 ; i--) {
            if (digits[i] == 9)digits[i] = 0;
            else {
                digits[i] = digits[i]+1;
                break;
            }
        }
        if (digits[0] == 0){
            int[] arr = new int[digits.length+1];
            arr[0] = 1;
            for (int i = 1; i < arr.length; i++) arr[i] = 0;
            return arr;
        }
        return digits;
    }

编辑于 2017-09-04 17:24:02 回复(3)
import java.util.*;


public class Solution {
    /**
     * 
     * @param digits int整型一维数组 
     * @return int整型一维数组
     */
    public int[] plusOne (int[] digits) {
        int num = 0;
       
        for(int i=0;i<digits.length;i++){
            num+=digits[digits.length-1-i]*(Math.pow(10,i));
         
        }
        num++;
        String newNum = String.valueOf(num);
        int[] newArr = new int[newNum.length()];
        for(int j = 0;j<newNum.length();j++){
            newArr[j]=Integer.parseInt( String.valueOf(newNum.charAt(j)));
        }
        return newArr;
    }
}
发表于 2022-08-01 21:59:50 回复(0)
我的想法其实挺简单的,就是先把这个数组转换为一个字符串s,然后把该字符串转换为一个数字num并加一,再把加一后的num转换为一个字符串t。根据t的长度定义一个相同长度的数组result,再将t里的每个字符的ASCII值减去0的ASCII值后依次放入result中。

该方法的难点主要在于用例数组长度可能会很大,导致字符串s转换为数字后大小会超过int型和long型的范围而报错,因此必须采用没有大小限制的BigInteger。
import java.util.*;
import java.math.*;

public class Solution {
    public int[] plusOne (int[] digits) {
        // write code here
        String s = "";
        for(int i=0;i<digits.length;i++){
            s += digits[i];
        }
        BigInteger a = new BigInteger(s);
        BigInteger num = a.add(BigInteger.valueOf(1));
        String t = ""+num;
        int []result = new int[t.length()];
        for(int i=0;i<t.length();i++){
            result[i] = t.charAt(i)-'0';
        }
        return result;
    }
}


编辑于 2022-06-01 09:18:47 回复(0)
class Solution {
public:
    /**
     * 
     * @param digits int整型vector 
     * @return int整型vector
     */
    vector<int> plusOne(vector<int>& digits) {
        // write code here
        //将一个数组表示的大数加一,[1,2,3]表示123
        const int num=1; //待加数
        int carry=num; //进位
        for(int i=digits.size()-1;i>=0;i--){
            digits[i]+=carry;
            carry=digits[i]/10;
            digits[i]%=10;
        }
        if(carry>0){
            digits.insert(digits.begin(), 1);
        }
        return digits;
    }
};

发表于 2021-10-25 15:15:12 回复(0)
class Solution {
public:
    /**
     * 
     * @param digits int整型vector 
     * @return int整型vector
     */
    vector<int> plusOne(vector<int>& digits) {
        // write code here
       // reverse(digits.begin(),digits.end());
        vector<int> res(digits.rbegin(),digits.rend());
        int t=1;
        for(int i=0;i<res.size();++i) {
            t = res[i]+t;
            if(t<=9) {
                res[i] = t;
                t = 0;
                break;
            }else {
                //t>10
                res[i] = t%10;
                t/=10;
                
            }
        }
        if(t) res.push_back(1);
        reverse(res.begin(),res.end());
        
        
        return res;
        
    }
};

发表于 2021-04-11 19:01:36 回复(0)
import java.util.*;
public class Solution {
    public int[] plusOne (int[] digits) {
        int len=digits.length;
        int carry=0;
        for(int i=len-1;i>=0;){
            if(digits[i]<9){
                digits[i]+=1;
                return digits;
            }else{
                if(i==0){
                    break;
                }
                digits[i]=0;
                i--;
            }
        }
        String str="";
        for(int i=0;i<len;i++){
            str+="0";
        }
        str=1+str;
        int[] res=new int[str.length()];
        for(int i=0;i<str.length();i++){
            res[i]=str.charAt(i)-'0';
        }
        return res;
    }
}

发表于 2020-11-03 23:08:03 回复(0)

关键在于看懂题目的意思:将一个数组表示的大数加一

所以问题的关键在于模拟进位,步骤如下:

  1. 拷贝整个数组
  2. 从数组最后一个数开始加1
    1. 如果有进位,将下一个数加一
    2. 如此循环,如果第一个元素仍有进位,向最前面插入一个元素

代码如下:

//
// Created by jt on 2020/9/26.
//
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param digits int整型vector
     * @return int整型vector
     */
    vector<int> plusOne(vector<int>& digits) {
        // write code here
        vector<int> res;
        for (auto d : digits) res.push_back(d);
        int carry = 1;
        for (int i = res.size() - 1; i >= 0; --i) {
            res[i] += carry;
            if (res[i] > 9) { res[i] = 0; carry = 1; }
            else { carry = 0; break; }
        }
        if (carry == 1) res.insert(res.begin(), 1);
        return res;
    }
};
编辑于 2020-09-26 16:08:03 回复(0)