LeetCode 66. 加一
LeetCode 66. 加一
LeetCode 66. 加一
一、题目描述：
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 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 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/plus-one 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、思路分析：
这道题考察了什么思想？你的思路是什么？
题目很简单，找到数组最后一个元素加1即可，但是我这里提出一种进阶的要求，返回的是数字怎么办？
我的思路很简单，从末尾开始，每前一位flag乘10，然后再乘数组中的数字。比如：
4321：取1 然后 加1 然后flag 为1 ，取2，然后flag乘以10，为10 2乘10得20，取3，然后flag乘10，为100 3乘以100得300，取4 然后flag乘以10，为1000 得4000，加起来就算4000+300+20+2=4322。
func plusOne(digits []int) []int {
var flag = 1
var sum = 0
digits[len(digits)-1] += 1
for i:=len(digits)-1;i>=0;i--{
var num = digits[i]
sum += (num*flag)
flag *= 10
}
return sum
}做题的时候是不是一次通过的，遇到了什么问题，需要注意什么细节？
不是，我发现我看错题目了！！！
当我们对数组digits 加一时，我们只需要关注 digits 的末尾出现了多少个 9 即可。
如果不为9，直接加1即可，若末尾有n个9，我们直接将第一个不为9的值加1，然后其他9置0即可，如果都是9，那么我们就构造一个比digits长度多1的新数组，将首元素置为1，其余元素为0即可。
有几种解法，哪种解法时间复杂度最低，哪种解法空间复杂度最低，最优解法是什么？其他人的题解是什么，谁的效率更好一些？用不同语言实现的话，哪个语言速度最快？
按照常规的方式模拟两个数字进行加法，给定数组内的数字和1进行加法，然后记录下进位。
func plusOne(digits []int) []int {
// 初始进位1
add:=1
for i:=len(digits)-1;i>=0;i-- {
curr:= digits[i] +add
// 如果等于10说明要进位
if curr ==10 {
// 当前位位0
digits[i]=0
//进位1
add =1
}else{
// 无需进位
digits[i]=curr
add =0
}
// 等于0说明了加法完毕
if add ==0 {
break
}
}
// 如果进位仍然大于0 ,说明要在数组的开头补充1
if add >0 {
return append([]int{1},digits...)
}
return digits
}
作者：gopher666
链接：https://leetcode.cn/problems/plus-one/solution/by-gopher666-svmp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。三、AC 代码：
func plusOne(digits []int) []int {
n := len(digits)
for i := n - 1; i >= 0; i-- {
if digits[i] != 9 {
digits[i]++
for j := i + 1; j < n; j++ {
digits[j] = 0
}
return digits
}
}
digits = make([]int, n+1)
digits[0] = 1
return digits
}四、总结：
这是一道比较考验技巧的题目，需要根据题意摸清楚题目的规律，比如根据9的个数来对症下药！