【力扣】66.加一 这是一道让人容易马失前蹄的算法题
Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。
春招打卡第22天第32篇。
勤学似春起之苗，不见其增，日有所长；辍学如磨刀之石，不见其损，日有所亏。
掘金的活动真多哇，这个月决定每天用go刷题，一方面提升一下算法水平，另一方面沉淀一下go语言的学习。
Let's GO!
题目描述
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例
示例 1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
示例 2：
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
示例 3：
输入：digits = [0]
输出：[1]
提示：
1 <= digits.length <= 100
0 <= digits[i] <= 9
题目分析
很简单哇，获得数组的最后一个元素，进行加一处理，再拼接回去就行啦。
（正如题目所说：这是一道容易让人马失前蹄的算法题）
才没这么简单呢！我们还要考虑最后一位为9的情况、最后几位为9的情况和全部是9的情况。
思路讲解
总结归纳一下，其实就以下这三种情况：
如果数组的末尾没有 9，例如 [1, 2, 3]，那么我们直接将末尾的数加一，得到 [1, 2, 4] 就ok了；
如果数组的末尾有若干个 9，例如 [3, 2, 1, 9, 9]，我们需要找出从末尾开始的第一个不为 9 的元素，也就是1，将该元素加一，得到 [3, 2, 1, 9, 9]。然后将末尾的 9 全部置零，得到 [3, 2, 2, 0, 0]就ok了。
如果数组的所有元素都是 9，例如 [9, 9, 9]，那么答案为 [1, 0, 0, 0]。这种情况下需要构造一个长度比输入数组大1的新数组，将首元素设置为1，其余元素置为0就ok了。
AC代码
func plusOne(digits []int) []int { //获得输入数组长度 n := len(digits) //遍历数组 for i := n - 1; i >= 0; i-- { //元素不为9的情况 if digits[i] != 9 { digits[i]++ for j := i + 1; j < n; j++ { digits[j] = 0 } return digits } } // digits 中所有的元素均为 9 digits = make([]int, n+1) digits[0] = 1 return digits }运行结果
总结
复杂度总结
时间复杂度：O(n)，其中 n 是数组的长度。
空间复杂度：O(1)。
来源说明
来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/pl…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
最后
感谢阅读，欢迎大家三连：点赞、收藏、投币（关注）！！！