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

三斤和他的朋友们 · · 622 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

加一( 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...


有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:三斤和他的朋友们

查看原文:让我们一起啃算法----加一

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

622 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传