66.加一[Leetcode 力扣 Java&C完整解答]

小咪咪 2021-12-12 06:33 216阅读 0赞

> 为什么我要给出完整解答，因为要搜索个题目的解答，很多都偷懒只给个方法的实现，结果跑都跑不起来。于是我就决定，每一题，都给出Java&C两种完整的解答，直接就可以运行，Debug。

Leetcode题目来源：[66.加一][66.]  
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

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

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

示例 1:

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

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

*  一、C++版本

#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;
    }

*  二、Java版本

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;
        }
    }

好啦，祝大家都能成为算法大神！

[66.]: https://leetcode-cn.com/problems/plus-one/