leetcode66---数组加一

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了leetcode66---数组加一，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1932字，纯文字阅读大概需要3分钟。

内容图文

leetcode66—数组加一：

关键字：数组，字符串转换

---

题目：

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 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]

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2cv1c/

---

方法 ：

1.数组操作

末尾元素进行加1操作，不进位一般情况直接计算即可，考虑进位的特殊情况。

1. 部分进位的情况，对进位的部分序列进行操作，当不再出现进位即可退出，返回结果。
2. 数组全部发生进位，因为是加1操作，所以最多结果是10，进位后该位置元素为0。当所有位置发生进位时，所有位置元素都会为0，数组长度会加1，且增加的第一位元素为1。比如[9,9,9]类型的全为9元素的数组会全部进位，此时只需生成一个长度为4，第一位为1，其余位为0的数组即可满足条件。即[1,0,0,0]。

代码如下：

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)
        for i in range(n-1, -1, -1):
            k = digits[i] + 1
            if k >= 10:
                digits[i] = k-10
            else:
                digits[i] = k
                return digits
        digits = [0]*(n+1)
        digits[0] = 1
        return digits

复杂度分析：

• 时间复杂度： O ( n ) O(n) O(n)，数组进位情况未知，当遍历所有元素时为n。
• 空间复杂度： O ( 1 ) O(1) O(1)，无额外空间，覆盖原有数组。

---

2.字符串转换：

将数组中数组转为字符串进行拼接，再转换为整数进行加1运算后，再转换为列表。
代码如下：

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        result = int(''.join([str(num) for num in digits]))+1
        return [int(j) for j in str(result)]

str()转换为字符串元素，通过join函数进行拼接，int()整数化后，再str()回字符串，用列表生成式生成列表存储。

复杂度分析：

• 时间复杂度： O ( n ) O(n) O(n)，遍历所有元素进行操作。
• 空间复杂度： O ( n ) O(n) O(n)，新生成了一个列表，占用额外空间。

---

总结

这道题第一种方法很巧妙，利用了这个进位运算的小规律，处理非常简洁。
第二种方法转换为字符串进行操作也是一种思路。

内容总结

以上是互联网集市为您收集整理的leetcode66---数组加一全部内容，希望文章能够帮你解决leetcode66---数组加一所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---