66.加一

LeetCode LeetCode 数组数学

发布时间 : 2000-01-10 00:06

字数:1.2k 阅读 :

评论:

66.加一

66.加一

66.1 题目

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：digits = [0]
输出：[1]

提示：

1 <= digits.length <= 100
0 <= digits[i] <= 9

66.2 题解

方法一：从右开始，进位继续，不进结束

思路

模拟加一操作，从数组末尾开始处理。对当前位加一：如果结果小于10，没有进位，直接返回；如果结果是10，当前位置0，继续处理前一位。如果所有位都是9（如 [9,9,9]），加一后变成 [1,0,0,0]，需要创建新数组，首位为1。

核心思想：模拟加法进位，处理全9的特殊情况。

具体步骤：

从数组末尾开始遍历。
当前位加一：
- 如果 < 10：直接返回
- 如果 == 10：当前位置0，继续处理前一位
如果遍历结束仍有进位：创建新数组，首位为1。

举例：对于 digits = [1,2,3]：

digits[2] = 3 + 1 = 4 < 10，直接返回 [1,2,4]

举例：对于 digits = [9,9,9]：

digits[2] = 9 + 1 = 10，置0，继续
digits[1] = 9 + 1 = 10，置0，继续
digits[0] = 9 + 1 = 10，置0，继续
创建新数组 [1,0,0,0]

复杂度分析

时间复杂度：O(n)，最坏情况遍历整个数组。
空间复杂度：O(1) 或 O(n)，只有全9的情况需要新数组。

代码

// 方法一：从右开始，进位继续，不进结束 
// 模拟加一操作，逆序遍历数组
// 从数组的末尾开始遍历，逐位加一，处理进位
static int[] PlusOne1(int[] digits)
{
    // 从数组的末尾开始遍历
    for (int i = digits.Length - 1; i >= 0; i--)
    {
        // 当前位加一
        digits[i]++;

        // 如果当前位是10（有进位），将当前位置为0
        if (digits[i] == 10)
        {
            digits[i] = 0;
        }
        else
        {
            // 如果当前位不是10，说明没有进位，直接返回结果
            return digits;
        }
    }

    // 如果循环结束仍然有进位，说明原先数组全为9，进位后后面都是0
    // 在数组前面插入一个1即可，后面都是0不需要动
    digits = new int[digits.Length + 1];
    digits[0] = 1;
    return digits;
}

66.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
        // 最高位数字存放在数组的首位，数组中每个元素只存储单个数字。
        // 你可以假设除了整数 0 之外，这个整数不会以零开头。

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

        // 示例 2：
        // 输入：digits = [4,3,2,1]
        // 输出：[4,3,2,2]
        // 解释：输入数组表示数字 4321。

        // 示例 3：
        // 输入：digits = [0]
        // 输出：[1]

        // 提示：
        // 1 <= digits.length <= 100
        // 0 <= digits[i] <= 9

        #endregion

        #region 测试

        // 示例 1
        int[] arr1 = { 1, 2, 3 };
        int[] result1 = PlusOne1(arr1);
        Console.WriteLine($"示例1 方法1 输出：[{string.Join(",", result1)}]");

        // 示例 2
        int[] arr2 = { 4, 3, 2, 1 };
        int[] result2 = PlusOne1(arr2);
        Console.WriteLine($"示例2 方法1 输出：[{string.Join(",", result2)}]");

        // 示例 3
        int[] arr3 = { 0 };
        int[] result3 = PlusOne1(arr3);
        Console.WriteLine($"示例3 方法1 输出：[{string.Join(",", result3)}]");

        #endregion
    }

    #region 答案

    // 方法一：从右开始，进位继续，不进结束 
    // 模拟加一操作，逆序遍历数组
    // 从数组的末尾开始遍历，逐位加一，处理进位
    static int[] PlusOne1(int[] digits)
    {
        // 从数组的末尾开始遍历
        for (int i = digits.Length - 1; i >= 0; i--)
        {
            // 当前位加一
            digits[i]++;

            // 如果当前位是10（有进位），将当前位置为0
            if (digits[i] == 10)
            {
                digits[i] = 0;
            }
            else
            {
                // 如果当前位不是10，说明没有进位，直接返回结果
                return digits;
            }
        }

        // 如果循环结束仍然有进位，说明原先数组全为9，进位后后面都是0
        // 在数组前面插入一个1即可，后面都是0不需要动
        digits = new int[digits.Length + 1];
        digits[0] = 1;
        return digits;
    }



    #endregion
}

66.4 运行结果

示例1 方法1 输出：[1,2,4]
示例2 方法1 输出：[4,3,2,2]
示例3 方法1 输出：[1]

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com