本文主要是介绍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的进位较多 | 处理大数可能溢出 | 大数转换成本高 | 栈溢出风险 | 特殊情况多一个步骤 |
应用示例
会计软件:
在处理财务数据时,经常需要对大量的数字序列进行加减操作。这些算法可用于实现一些基本的数字操作功能,如自动递增发票号或处理交易记录。特别是在需要快速响应和高效计算的场景中,选择合适的算法可以显著提高软件性能和用户满意度。
这篇关于LeetCode 题目 65:有效数字(Valid Number)【python】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!