66. 加一
66. 加一
思路分析:
此题不难,其实就是让我们模拟竖式计算进位,然只需要加1即可。对此,我们将问题分成以下3类:
给定整数中最后一位不是数字9(如1234);
给定整数中最后一位是数字9,但不全是数字9(如1099);
给定整数所有位全是数字9(如99)。
算法思路:
对于上述情况1,直接在最后一位加11即可。
对于上述情况2,只需从后向前遍历数组,逢9进1,直至非9结束。
对于上述情况3,我们在最开始不需要与情况2区分,只需要在按照情况2遍历结束后判断首位,若首位为0,则代表情况3出现,此时直接在vector末尾添加1个0,再将首位由0变为1即可。
复杂度分析:
时间复杂度:O(n)O(n)
空间复杂度:O(1)O(1)