LeetCode 题目 65：有效数字（Valid Number）【python】

本文主要是介绍LeetCode 题目 65：有效数字（Valid Number）【python】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在列表的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

输入格式

digits：一个整数数组。

输出格式

返回一个数组，表示加一后的结果。

示例

示例 1

输入: digits = [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

示例 2

输入: digits = [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

示例 3

输入: digits = [9]
输出: [1,0]
解释: 输入数组表示数字 9。

方法一：模拟进位

解题步骤

从最低位开始遍历：遍历数组的最后一个元素，即数字的最低位。
处理进位：如果当前位加一后等于10，则设置当前位为0，并将进位带到下一位。
终止条件：如果没有进位发生，直接返回数组。如果遍历完所有元素仍有进位，需要在数组最前面添加一个元素1。

完整的规范代码

def plusOne(digits):"""使用模拟进位法对数组表示的数字进行加一操作:param digits: List[int], 代表数字的数组:return: List[int], 加一后的数组"""n = len(digits)for i in range(n-1, -1, -1):if digits[i] < 9:digits[i] += 1return digitsdigits[i] = 0return [1] + digits  # 处理全部为9的情况# 示例调用
print(plusOne([1,2,3]))  # 输出: [1,2,4]
print(plusOne([4,3,2,1]))  # 输出: [4,3,2,2]
print(plusOne([9]))  # 输出: [1,0]

算法分析

时间复杂度：(O(n))，在最坏的情况下需要遍历整个数组。
空间复杂度：(O(1))，除了输出数组外，额外使用的空间是常数级别的。

方法二：转换为数字

解题步骤

数组转换为数字：将数组转换为整数。
加一操作：对该数字加一。
数字转回数组：将结果数字转换回数组形式。

完整的规范代码

def plusOne(digits):"""将数组转换为数字进行加一，然后再转换回数组:param digits: List[int], 代表数字的数组:return: List[int], 加一后的数组"""num = 0for digit in digits:num = num * 10 + digitnum += 1return [int(i) for i in str(num)]# 示例调用
print(plusOne([1,2,3]))  # 输出: [1,2,4]
print(plusOne([4,3,2,1]))  # 输出: [4,3,2,2]
print(plusOne([9]))  # 输出: [1,0]

算法分析

时间复杂度：(O(n))，转换过程中涉及到线性时间的操作。
空间复杂度：(O(n))，需要存储转换后的数字和结果数组。

方法三：字符串处理

解题步骤

数组转字符串：将数组中的数字转换成字符串并连接。
字符串转数字加一：将字符串转换为数字进行加一操作。
数字转字符串再转数组：将加一后的数字转换为字符串，然后将每个字符转换为整数数组。

完整的规范代码

def plusOne(digits):"""使用字符串处理的方法进行加一操作:param digits: List[int], 代表数字的数组:return: List[int], 加一后的数组"""s = ''.join(map(str, digits))num = int(s) + 1return [int(x) for x in str(num)]# 示例调用
print(plusOne([1,2,3]))  # 输出: [1,2,4]
print(plusOne([4,3,2,1]))  # 输出: [4,3,2,2]
print(plusOne([9]))  # 输出: [1,0]

算法分析

时间复杂度：(O(n))，涉及字符串和数字的转换。
空间复杂度：(O(n))，需要额外的空间来存储字符串和结果数组。

方法四：递归处理

解题步骤

定义递归函数：递归处理加一和进位。
边界条件：当处理到第一个数字且需要进位时，在数组前添加一个1。
递归逻辑：从后向前处理每个数字，处理进位。

完整的规范代码

def plusOne(digits):"""使用递归处理数组加一的操作:param digits: List[int], 代表数字的数组:return: List[int], 加一后的数组"""def helper(index):if index < 0:digits.insert(0, 1)returnif digits[index] == 9:digits[index] = 0helper(index - 1)else:digits[index] += 1helper(len(digits) - 1)return digits# 示例调用
print(plusOne([1,2,3]))  # 输出: [1,2,4]
print(plusOne([4,3,2,1]))  # 输出: [4,3,2,2]
print(plusOne([9]))  # 输出: [1,0]

算法分析

时间复杂度：(O(n))，最坏情况下需要递归遍历整个数组。
空间复杂度：(O(n))，递归深度可能达到数组长度。

方法五：迭代优化

解题步骤

从最后一个元素开始迭代：处理每个元素的加一和进位。
处理进位：如果当前位置变为10，则设置为0并继续处理前一位。
处理全部为9的特殊情况：如果首位也进位，则数组前添加1。

完整的规范代码

def plusOne(digits):"""使用迭代优化的方法处理加一操作:param digits: List[int], 代表数字的数组:return: List[int], 加一后的数组"""for i in range(len(digits) - 1, -1, -1):if digits[i] == 9:digits[i] = 0else:digits[i] += 1return digitsdigits.insert(0, 1)return digits# 示例调用
print(plusOne([1,2,3]))  # 输出: [1,2,4]
print(plusOne([4,3,2,1]))  # 输出: [4,3,2,2]
print(plusOne([9]))  # 输出: [1,0]

算法分析

时间复杂度：(O(n))，遍历数组进行处理。
空间复杂度：(O(1))，除了结果外，几乎不使用额外空间。

不同算法的优劣势对比

特征	方法一: 模拟进位	方法二: 转数字	方法三: 字符串处理	方法四: 递归	方法五: 迭代优化
时间复杂度	(O(n))	(O(n))	(O(n))	(O(n))	(O(n))
空间复杂度	(O(1))	(O(n))	(O(n))	(O(n))	(O(1))
优势	直接明了，逻辑简单	数字操作直观	代码简洁，易理解	自然的递归逻辑	极简实现，高效处理
劣势	处理9的进位较多	处理大数可能溢出	大数转换成本高	栈溢出风险	特殊情况多一个步骤