栈方法解leetcode之66-加1

这题用栈好解决，因为涉及到进位，后面再将数据遍历出来

题目描述

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

示例 1：

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

示例 2：

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

解题思路:

初始化一个栈，一个是否进位的标记。从尾部遍历数组。因为尾部代表数组的最小位，所以第一次一定要执行加1操作的。
如果加1操作==10，则栈放入0，并将进位继续设置进位。如果不==10，则将原值+1，并重置进位为0
最后退出循环后，还要判断一次是否进位，是栈进入。像999+1,最后三位数变成四位数
将栈里的数据依次出栈放入结果集，即为结果

go示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


func plusOne(digits []int) []int {
    // 数组模拟栈
   stack := make([]int, 0)
   isPlus := 1
   for i := len(digits) - 1; i >= 0; i--{
       if isPlus == 1 {
           // 值相加==10，进位，并继续下一个循环
           if digits[i] + 1 == 10 {
               stack = append(stack, 0)
               isPlus = 1
               continue
           }
           // 值相加不为10
           stack = append(stack, digits[i] + 1)
           isPlus = 0
       } else {
           stack = append(stack, digits[i])
           isPlus = 0
       }
   }
   // 判断最后一个数是不是要进们，即二位变成三位数这种情况
   if isPlus == 1 {
       stack = append(stack, 1)
   }
   // 后面代码类似出栈，将原数组逆序放入结果集
   length := len(stack) - 1
   results := make([]int, len(stack))
   for i := length; i >= 0; i-- {
       results[length - i] = stack[i]
   }
   return results
}

文章目录