加一

看到这个标题,大家肯定会觉得,不就是“加1”嘛,这么简单的问题我可以!但是就是这么简单的“加1”可是面试的高频题哦,所以我们就一起来看看吧。按照往例,我们还是从一道LeetCode题开始吧。

01、题目分析

第66题:加一
给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。

最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外,这个整数不会以零开头。

示例 1:

  1. 输入: [1,2,3]
  2. 输出: [1,2,4]
  3. 解释: 输入数组表示数字 123

示例 2:

  1. 输入: [4,3,2,1]
  2. 输出: [4,3,2,2]
  3. 解释: 输入数组表示数字 4321


题目分析:

根据题目,我们需要加一!没错,加一很重要。因为它只是加一,所以我们会考虑到两种情况:

  • 普通情况,除9之外的数字加1。

  • 特殊情况,9加1。(因为9加1需要进位)

所以我们只需要模拟这两种运算,就可以顺利进行求解!

02、题目图解

假设我们的数为[1,9,9]

大概是下面这样:(这个图解…真的有点太简单了…)

PNG

当然,这里我们需要考虑一种特殊情况,就是类似99,或者999,我们需要进行拼接数组。具体如下图:

PNG

通过以上分析,我们最后只需要将其转换成代码即可!这样看来,“加1”是不是也不像想象中的那么简单?

03、GO语言示例

根据以上分析,我们可以得到下面的题解:

  1. func plusOne(digits []int) []int {
  2. var result []int
  3. addon := 0
  4. for i := len(digits) - 1;i >= 0; i-- {
  5. digits[i]+=addon
  6. addon = 0
  7. if i == len(digits) - 1 {
  8. digits[i]++
  9. }
  10. if digits[i] == 10 {
  11. addon = 1
  12. digits[i] = digits[i] % 10
  13. }
  14. }
  15. if addon == 1 {
  16. result = make([]int, 1)
  17. result[0] = 1
  18. result = append(result,digits...)
  19. }else{
  20. result = digits
  21. }
  22. return result
  23. }

提示:

  1. append(a,b...) 的含义是:将b切片中的元素追加到a中。