$$\color{Red}{加一【leetcode66 借高精度思想而优化(不开动态数组)】}$$
我的网站=> 分享了我关于前后端的各种知识和生活美食~
我于Acwing平台分享的零散刷的各种各样的题
题目介绍
给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 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
解析
这道题,如果本身直接使用高精度加法的思路做,其实是完全没问题的,倒序,然后计算是否有进位,然后遍历,如果最后到了最高位的下一位,还有进位,直接把进位加入高位下一位【其实肯定是1】。
但是这个思路其实对于这道题,需要开一个动态数组,要么是链表类型要么是扩容数组类型,其实时间复杂度,空间复杂度都扩大了,而且,每次扩容也浪费时间,最后还要求返回一个静态数组,岂不是还得类型转换。这对于JAVA
选手来说,无疑是很恶心的,明明方法摆在眼前,但是凭空多出的复杂度和各种转换操作,简直像吃屎一样难受。怒了。🤬
直接剖析原理,其实这道题,不同于高精度加法,高精度加法,肯定要依次判断完位数少的那个数字的每一位,进行相加,不断进行变化,维护进位。
但是这道题加一
=> 一旦进位相加当前位不为10
,直接可以跳出循环了!
所以没必要用高精度思想做,直接在原数组基础上维护进位就行,一旦出现当前位相加小于 10
的情况,直接返回原数组。为 10
就置 0
进位不变还是 1
。
一旦出现需要进位的情况,很显然,说明加了个1
导致低位全给进位了,那不就是 10000000....
0 的个数相当于之前原数组长度,我直接 new
一个长度比之前大一位的数组,直接把数组第一位置 1
,游戏结束。
又水一题。。。。【😋不是】
class Solution {
public int[] plusOne(int[] digits) {
int n = digits.length;
int k = 1;
for (int i = n - 1; i >= 0; i --) {
if (digits[i] + k >= 10) {
digits[i] = 0;
} else {
digits[i] += k;
return digits;
}
}
int [] ans = new int[n + 1];
ans[0] = 1;
return ans;
}
}