LeetCode 题目 65:有效数字(Valid Number)【python】

简介: LeetCode 题目 65:有效数字(Valid Number)【python】

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

备注说明:方便大家阅读,统一使用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。

方法一:模拟进位

解题步骤
  1. 从最低位开始遍历:遍历数组的最后一个元素,即数字的最低位。
  2. 处理进位:如果当前位加一后等于10,则设置当前位为0,并将进位带到下一位。
  3. 终止条件:如果没有进位发生,直接返回数组。如果遍历完所有元素仍有进位,需要在数组最前面添加一个元素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] += 1
            return digits
        digits[i] = 0
    
    return [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)),除了输出数组外,额外使用的空间是常数级别的。

方法二:转换为数字

解题步骤
  1. 数组转换为数字:将数组转换为整数。
  2. 加一操作:对该数字加一。
  3. 数字转回数组:将结果数字转换回数组形式。
完整的规范代码
def plusOne(digits):
    """
    将数组转换为数字进行加一,然后再转换回数组
    :param digits: List[int], 代表数字的数组
    :return: List[int], 加一后的数组
    """
    num = 0
    for digit in digits:
        num = num * 10 + digit
    num += 1
    return [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)),需要存储转换后的数字和结果数组。

方法三:字符串处理

解题步骤
  1. 数组转字符串:将数组中的数字转换成字符串并连接。
  2. 字符串转数字加一:将字符串转换为数字进行加一操作。
  3. 数字转字符串再转数组:将加一后的数字转换为字符串,然后将每个字符转换为整数数组。
完整的规范代码
def plusOne(digits):
    """
    使用字符串处理的方法进行加一操作
    :param digits: List[int], 代表数字的数组
    :return: List[int], 加一后的数组
    """
    s = ''.join(map(str, digits))
    num = int(s) + 1
    return [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. 定义递归函数:递归处理加一和进位。
  2. 边界条件:当处理到第一个数字且需要进位时,在数组前添加一个1。
  3. 递归逻辑:从后向前处理每个数字,处理进位。
完整的规范代码
def plusOne(digits):
    """
    使用递归处理数组加一的操作
    :param digits: List[int], 代表数字的数组
    :return: List[int], 加一后的数组
    """
    def helper(index):
        if index < 0:
            digits.insert(0, 1)
            return
        if digits[index] == 9:
            digits[index] = 0
            helper(index - 1)
        else:
            digits[index] += 1
    
    helper(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)),递归深度可能达到数组长度。

方法五:迭代优化

解题步骤
  1. 从最后一个元素开始迭代:处理每个元素的加一和进位。
  2. 处理进位:如果当前位置变为10,则设置为0并继续处理前一位。
  3. 处理全部为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] = 0
        else:
            digits[i] += 1
            return digits
    digits.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的进位较多 处理大数可能溢出 大数转换成本高 栈溢出风险 特殊情况多一个步骤

应用示例

会计软件

在处理财务数据时,经常需要对大量的数字序列进行加减操作。这些算法可用于实现一些基本的数字操作功能,如自动递增发票号或处理交易记录。特别是在需要快速响应和高效计算的场景中,选择合适的算法可以显著提高软件性能和用户满意度。

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
22天前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
11 1
|
7天前
|
Python
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
|
7天前
|
存储 算法 索引
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
|
7天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
存储 算法 调度
力扣中级算法(Python)
力扣中级算法(Python)
|
1月前
|
算法 Python
力扣初级算法(Python)(二)
力扣初级算法(Python)(二)
|
1月前
|
算法 Python
力扣初级算法(Python)(一)
力扣初级算法(Python)(一)
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
1月前
|
容器
【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(4)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总

热门文章

最新文章

相关实验场景

更多