加一

最后更新：2023-12-02

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2cv1c/

题目描述

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

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

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

题目示例

示例 1：示例 2：示例 3：

输入： digits = [1,2,3]

输出： [1,2,4]

解释： 输入数组表示数字 123。

输入： digits = [4,3,2,1]

输出： [4,3,2,2]

解释： 输入数组表示数字 4321。

输入： digits = [0]

输出： [1]

提示：

• \(1 <= digits.length <= 100\)
• \(0 <= digits[i] <= 9\)

解题思路

1. 加1后，位数增加的只有一种情况，就是全是9的情况，这个单独处理，重新申请内存。

2. 不增加位数的，直接对原数组处理，从后往前，如果是9，则值修改为0，置个标志位，直到找到第一个不为0的数字，加1后，跳出循环，返回原数组。

第二种也可以分一下，最后一位不是9，直接加一返回，是9的话再走循环

C解法一C解法二C解法三C解法四Golang直接解题Golang判断Golang

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* plusOne(int* digits, int digitsSize, int* returnSize)
{
    int *res = NULL;
    int i,j = 0;
    int reslen = digitsSize + 1;

    res = (int*)malloc(reslen * sizeof(int));
    if (res == NULL) {
        *returnSize = 0;
        return NULL;
    }

    // 为空，则返回1
    if ((digitsSize == 0) || (digits == NULL)) {
        *returnSize = 1;
        res[0] = 1;
        return res;
    }
    
    // 先给最后一位加1，赋值
    digits[digitsSize - 1]++;
    // 从后往前，赋值其他的，如果为9，前一位加1，不为9，则不变
    for (i = digitsSize - 1; i > 0; i--) {
        if (digits[i] > 9) {
            digits[i] = digits[i] % 10;
            digits[i - 1]++;
        }
    }
    
    // 如果首位大于9，则需要后移一位赋值
    if (digits[0] > 9) {
        j = 1;
        *returnSize = reslen;
        res[0] = 1;
    } else {
        *returnSize = reslen - 1;
    }

    // 赋值
    for (i = 0; i < digitsSize; i++) {
        res[j] = digits[i] % 10;
        j++;
    }

    return res;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* plusOne(int* digits, int digitsSize, int* returnSize)
{
    int flag = 0;
    for (int i = (digitsSize - 1); i >=0 ; i--) {
        if (digits[i] == 9) {
            digits[i] = 0;
            flag = 1;
        } else {
            if (i != (digitsSize - 1)) {
                digits[i] += flag;
            } else {
                digits[i] += 1;
            }
            flag = 0;
            break;
        }
    }

    if (flag == 1) {
        int resLen = digitsSize + 1;

        int* res = (int*)malloc(resLen * sizeof(int));
        if (res == NULL) {
            *returnSize = 0;
            return NULL;
        }

        res[0] = 1;
        memset(&res[1], 0, digitsSize*sizeof(int));
        memcpy(&res[1], digits, digitsSize*sizeof(int));
        *returnSize = digitsSize + 1;
        return res;
    } else {
        *returnSize = digitsSize;
        return digits;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* plusOne(int* digits, int digitsSize, int* returnSize)
{
    int flag9 = 1;
    for (int i = 0; i < digitsSize; i++) {
        if (digits[i] != 9) {
            flag9 = 0;
            break;
        }
    }

    // 全是9，单独处理，因为增加了一位，不能使用源数组，要重新申请内存
    if (flag9 == 1) {
        int resLen = digitsSize + 1;

        int* res = (int*)malloc(resLen * sizeof(int));
        if (res == NULL) {
            *returnSize = 0;
            return NULL;
        }

        res[0] = 1;
        memset(&res[1], 0, digitsSize*sizeof(int));
        *returnSize = digitsSize + 1;
        return res;
    }

    int flag = 0;
    for (int i = (digitsSize - 1); i >=0 ; i--) {
        if (digits[i] == 9) {
            digits[i] = 0;
            flag = 1;
        } else {
            if (i != (digitsSize - 1)) {
                digits[i] += flag;
            } else {
                digits[i] += 1;
            }
            break;
        }
    }

    *returnSize = digitsSize;
    return digits;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* plusOne(int* digits, int digitsSize, int* returnSize)
{
    int flag9 = 1;
    for (int i = 0; i < digitsSize; i++) {
        if (digits[i] != 9) {
            flag9 = 0;
            break;
        }
    }

    // 全是9，单独处理，因为增加了一位，不能使用源数组，要重新申请内存
    if (flag9 == 1) {
        int resLen = digitsSize + 1;

        int* res = (int*)malloc(resLen * sizeof(int));
        if (res == NULL) {
            *returnSize = 0;
            return NULL;
        }

        res[0] = 1;
        memset(&res[1], 0, digitsSize*sizeof(int));
        *returnSize = digitsSize + 1;
        return res;
    }

    // 最后一位不是9，直接加一返回
    if (digits[digitsSize - 1] != 9) {
        digits[digitsSize - 1] += 1;
        *returnSize = digitsSize;
        return digits;
    }

    // 最后一位是9
    for (int i = (digitsSize - 1); i >=0 ; i--) {
        if (digits[i] == 9) {
            digits[i] = 0;
        } else {
            digits[i] += 1;
            break;
        }
    }

    *returnSize = digitsSize;
    return digits;
}

func plusOne(digits []int) []int {
    if digits[0] == 0 {
        digits[0] = 1
        return digits
    }

    flag := 0
    for i := len(digits) - 1; i >= 0; i-- {
        if digits[i] == 9 {
            digits[i] = 0
            flag = 1
        } else {
            if i != len(digits)-1 {
                digits[i] = digits[i] + flag
            } else {
                digits[i] = digits[i] + 1
            }
            flag = 0
            break
        }
    }

    if flag == 1 {
        newDig := []int{1}
        newDig = append(newDig, digits...)
        return newDig
    }

    return digits
}

func plusOneCheck(digits []int) []int {
    // 全9
    flag9 := true
    for _, v := range digits {
        if v != 9 {
            flag9 = false
            break
        }
    }

    if flag9 {
        newDig := []int{1}
        for i := range digits {
            digits[i] = 0
        }
        newDig = append(newDig, digits...)
        return newDig
    }

    // 最后一位不是9
    n := len(digits)
    if digits[n-1] != 9 {
        digits[n-1] += 1
        return digits
    }

    // 最后一位是9
    for i := len(digits) - 1; i >= 0; i-- {
        if digits[i] == 9 {
            digits[i] = 0
        } else {
            digits[i] += 1
            break
        }
    }
    return digits
}

func plusOne(digits []int) []int {
    for i := len(digits) - 1; i >= 0; i-- {
        if digits[i] == 9 {
            digits[i] = 0
        } else {
            digits[i] += 1
            return digits
        }
    }

    newDig := []int{1}
    newDig = append(newDig, digits...)
    return newDig
}