让我们一起啃算法----加一

三斤和他的喵的个人博客 / 65 / 1 / 创建于 3年前 / 更新于 3年前

加一（ 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]++ ，是因为有进位 1 需要加上
    }

    // i 已经越界，并且 digits[0] 为 0 表示存在一个进位 1 ，因此需要对数组扩容
    digits = append([]int{1}, digits...)
    return digits
}

总结

每天进步一点点，加油！
算法教程项目，每天更新一题，点个 star 支持一下呀：
https://github.com/wx-satellite/learning-a…

算法数据结构 leetcode

本作品采用《CC 协议》，转载必须注明作者和本文链接

三斤

三斤和他的喵

课程读者 172 声望

一个PHPer的修行之路。欢迎大家关注我的公众号《三斤和他的喵》

3 人点赞

从零开发一个电商项目，功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等

你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程，JWT 概念及使用和 API 开发相关的进阶知识。

推荐文章：

更多推荐...

面试 POPER 的后端开发工程师的离奇经历 34 / 104 |

分享创造

📙《高并发的哲学原理》开源图书发布十一天 star 数已经破千！ 47 / 16 |

博客

PHP面试高薪宝典系列: 常见基础算法（附完整代码） 23 / 3 |

博客

强一致性的分布式事务几种模式对比（php有了新方案） 33 / 20 |

博客

PHP实现汉诺塔算法 21 / 9 |

博客

PHP使用动态规划实现最优红包组合 33 / 5 |

讨论数量: 1

captain2021

Laravel 5.8 译者 421 声望 / 开发 @ 谈笑风生

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

感谢楼主又教会了我一个算法

3年前评论

三斤和他的喵（楼主）

加油 :muscle:

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

让我们一起啃算法----加一

加一（ Plus-One ）

解题思路

代码实现

GO语言实现

总结

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

让我们一起啃算法----加一

加一（ Plus-One ）

解题思路

代码实现

GO语言实现

总结

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录