欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java算法题(来自lettcode)----14 加一 思路 详解

程序员文章站 2024-03-23 15:59:10
...

题目:

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

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

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

示例 1:

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

示例 2:

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

我的解法:

虽然我的解法可能有点笨,但是我觉得应该是比较容易理解的

    public static int[] plusOne(int[] digits) {
		int len = digits.length;
		StringBuffer sb = new StringBuffer();
		// 跳出双层循环
		flag: for (int i = len - 1; i >= 0; i--) {
			// 判断最低位是否为9,如果为9,进入循环判断后面的
			if (i == len - 1 && digits[i] == 9) {
				for (int j = i; j >= 0; j--) {
					// 如果数组的第一项还是9,即全是9
					if (j == 0 && digits[j] == 9) {
						sb.append(0);
						sb.append(1);
						sb.reverse();
						int[] array = new int[sb.length()];
						for (int m = 0; m < sb.length(); m++) {
							array[m] = sb.charAt(m) - '0';
						}
						return array;
					}
					if (digits[j] == 9) {
						sb.append(0);
					}
					// 如果中途出现没有 9 的 如[1,9,2,3,4,9,9]
					if (digits[j] != 9 && digits[j + 1] == 9) {
						sb.append(digits[j] + 1);
						// 如果恰好数组首项不是9如:[8,9,9,9]
						// 如果直接 i = j - 1 , i = -1 会报数组下标越界,会报错
						// 这里是跳出双层循环
						if (j == 0) {
							break flag;
						} else {
							i = j - 1;
							break;
						}

					}
				}
			}
			if (i == len - 1 && digits[i] != 9) {
				sb.append(digits[i] + 1);
				continue;
			}
			sb.append(digits[i]);
		}
		// 由于添加元素是倒着添加的,所以需要调用reverse();
		sb.reverse();
		int[] array = new int[sb.length()];
		for (int m = 0; m < sb.length(); m++) {
			array[m] = sb.charAt(m) - '0';
		}
		return array;
	}

 下面给上lettcode上大神的解法

public int[] plusOne(int[] digits) {
        int len = digits.length;
        for(int i=len-1;i>=0;i--){
            if(digits[i]+1<10){
                digits[i]++;
                return digits;
            }else{
                digits[i]=0;
            }
        }
        int[] res=new int[len+1];
        res[0]=1;
        return res;
    }