2020-05-02-Go和PHP 实现加一

layout: posttitle: Go和PHP 实现加一
subtitle: Go和PHP 实现加一
date: 2020-05-02
author: he xiaodong
header-img: img/default-post-bg.jpg
catalog: true
tags:
- Go
- PHP
- LeetCode
- 实现加一

原文链接：go leetcode，php 代码个人原创

加一（ Plus-One ）

题干：

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
来源：力扣

题目比较简单，解题思路和 让我们一起啃算法——两数相加 差不多。

解题思路

根据题意，可以将数组的元素以第一个元素为最高位看成一个正整数，记为 number，然后对 number 做 加一 的操作，需要注意 进位（carry）的问题。由于题目明确说明 数组的每个元素只存储单个数字，因此可以得出 只有元素值为 9 才有可能产生进位，且进位值为 1、产生进位的当前元素值会被赋值为 0。

基于上面的分析解题思路自然就出来了：首选初始化 i 指向数组的最后一个元素。接着对数组所表示的正整数进行 加 1操作，即对数组的最后一个元素加一： nums[i] = nums[i] + 1，然后判断 nums[i] 是否产生进位，其实就是判断 nums[i] 是否等于 10，或者 nums[i] % 10 是否等于 0 。如果没有产生进位，则直接返回数组，反之，则 nums[i] = 0， i 向左移动一位，nums[i] = nums[i] + 1（ 因为有低位产生了进位所以要加 1 ），接着判断 nums[i] 是否仍产生进位，重复上面的判断流程。

这里有个注意事项： 当 i 指向了最高位也就是第一个元素时，并且第一个元素是 9，同时又存在进位，则需要对数组扩容。例如 nums 数组为 [9, 9, 9] 这时候加一操作之后 nums 为 [1, 0, 0, 0]。

流程图如下：

Go 实现

func plusOne(digits []int) []int {
    for i := len(digits) -1; i >= 0; i-- {
        // 第一次 加1 操作是题目指定的，后续的 加1 操作是低位的进位
        digits[i] ++
        // 小于10与10相模值不变，等于10与10相模为0，这一步的主要目的就是当存在进位时当前值为 10 需要将其设置为 0
        digits[i] %= 10
        // 如果 不等于0 则表示没有进位，直接返回
        if digits[i] != 0 {
            return digits
        }
        // 等于 0 则表示存在进位，由于上面执行了 digits[i] %= 10 ，这时候当前值已经被设置为 0，后续 i-- 之后，执行 digits[i]++ ，是因为有进位需要加上
    }
    digits = append([]int{1}, digits...)
    return digits
}

PHP 实现

function plusOne(array $digits) :array {
    $count = count($digits) - 1;
    for ($i = $count; $i >= 0; $i--) {
        // 第一次 加1 操作是题目指定的，后续的 加1 操作是低位的进位
        $digits[$i]++;
        // 小于10与10相模值不变，等于10与10相模为0，这一步的主要目的就是当存在进位时当前值为 10 需要将其设置为 0
        $digits[$i] %= 10;
        // 如果 不等于0 则表示没有进位，直接返回
        if ($digits[$i] !== 0) {
            return $digits;
        }
        // 等于 0 则表示存在进位，由于上面执行了 digits[i] %= 10 ，这时候当前值已经被设置为 0，后续 i-- 之后，执行 digits[i]++ ，是因为有进位需要加上
    }
    array_unshift($digits, 1);
    return $digits;
}
return plusOne([9,9]); // output: [1,0,0];
return plusOne([1,2,3]); // output: [1,2,4];

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券