专栏首页机器视觉CV数据结构与算法-

数据结构与算法-

大整数相加

给两个很大很大的整数(可能有几百位),求出他们的和

  • 思路

因为很大的数已经超过了计算机可以存储,虽然 Python3 中的整型是没有限制内存大小的,但是不代表其他语言没有内存限制,所以一般将两个整数直接相加并不现实

在 Python3 中,一个长度为 36 的整数占 48 字节,一个长度为 1 的数占的字节数 28 字节,整数长度长和短在内存中差别并不明显。

既然没办法直接进行相加,想想小学的时候,老师是怎么教我们的,是不是从个位相加,超过 10 就进位。那么这么大的数字该用什么存储呢?有两种方法,一种是用数组存储,一种是用字符串存储

  • 代码

边界条件与测试案例

  1. 边界条件:输入非数值
  2. 正常大的整数
  3. 小的数值(0 )与大的数值

def big_num_sum(num1: str, num2: str) -> str:
    """
    边界条件:输入非数值
    测试案例:
    1. 包含有非数值的字符串
    2. 正常大的整数
    """
    assert num1.isdigit() == True
    assert num2.isdigit() == True
    long_num, short_num = (num1, num2) if (len(num1) > len(num2)) else (num2, num1)  # c

    long_num = long_num[::-1] # 倒序
    short_num = short_num[::-1] 

    long_len = len(long_num)  # 字符的长度
    short_len = len(short_num)

    for i in range(long_len - short_len):  # 将较短的数值后面补 0 补到和较长的数一样的长度
        short_num += "0"
    result = ""  # 用来保存结果
    flag = 0  # 进位标志位
    for i in range(long_len):
        temp = int(long_num[i]) + int(short_num[i]) + flag
        if temp >= 10:
            result += str(temp-10)
            flag = 1 # 
        else:
            result += str(temp)
            flag = 0
    return int(result[::-1])

if __name__ == "__main__":
    assert (big_num_sum("1234533333133333336", "88888888888888") == 1234533333133333336+88888888888888) == True
    assert (big_num_sum("0", "1") == 0+1) == True
    assert (big_num_sum("0", "d"))  # 非数值输入会报错,用来测试边界条件

当然,这个程序还可以换成用数组的形式写,这里就不在给出,同时还可对以上代码进行优化,如:只需要遍历最短的那个即可,这样对于很大整数加上一个小的整数来说,效率会更高,占据的内存也会更小

本代码的时间复杂度是 O (n)

参考:《漫画算法》 作者:魏梦舒

本文分享自微信公众号 - 机器视觉CV(Unfinished_coder)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 爬虫篇 | 高级爬虫(一):Scrapy爬虫框架的安装

    Scrapy是一个爬虫框架,通过这个爬虫框架,我们能很快的构建出一个强大的爬虫工具! 一般大型爬虫服务都会使用Scrapy 进行爬虫,我们甚至在这个框架基础上...

    叫我龙总
  • Python 63个内置函数,你都ok吗?

    判断对象是否可以被调用,能被调用的对象就是一个callable 对象,比如函数 str, int 等都是可被调用的,但是例子4 中xiaoming这个实例是不可...

    double
  • 推荐一款神器:在浏览器中运行 vscode,随时随地写代码

    最近整理一个爬虫系列方面的文章,不管大家的基础如何,我从头开始整一个爬虫系列方面的文章,让大家循序渐进的学习爬虫,小白也没有学习障碍 有兴趣移步次条

    叫我龙总
  • pytest框架从入门到精通

    unittest是python自带的单元测试框架,它封装好了一些校验返回的结果方法和一些用例执行前的初始化操作,使得单元测试易于开展,因为它的易用性,很多同学也...

    iTesting
  • Python列表生成式12个小功能,你常用哪几个?

    我正在梳理一个系列:Python在工作中被频繁用到的那些操作,直击重点,无半句废话,欢迎学习!目前已推送:

    double
  • 有趣的字符串面试题 --再探

    上次分享了一道有趣的字符串面试题,今天我们再重新审视下这道题,并借此机会了解下python库的强大。

    iTesting
  • 分享7个数据分析的有用工具

    该工具效果明显。下图展示了调用 df.profile_report() 这一简单方法的结果:

    double
  • 闲鱼上哪些商品抢手?Python 分析后告诉你

    经常看到有朋友在闲鱼卖些小东西又或是自己擅长的一些技能,都能为他们带来不错的 睡后收入。

    叫我龙总
  • 爬虫篇 | 高级爬虫( 二):Scrapy爬虫框架初探

    先确保你已经在电脑上安装好了Scrapy模块,说一下Scrapy安装的问题,网上大部分安装办法已经失效了,主要是因为 网站:https://www.lfd.uc...

    叫我龙总
  • 爬虫篇 | 高级爬虫(三):使用Scrapy爬取拉勾网数据并写入数据库

    之前我们讲到了使用Scrapy,今天我们使用Scrapy来作一个项目实战。Scrapy详细教程可以看前面两篇:

    叫我龙总

扫码关注云+社区

领取腾讯云代金券