专栏首页dongfanger我倒在了美团面试算法题:字符串大数相加

我倒在了美团面试算法题:字符串大数相加

话说之前换工作的时候,我经历了一次美团的视频面试。

不像腾讯面试有自家软件,美团面试是在第三方网页上进行的,长这样:

看见中间的代码编辑区,我笑了,难道?真的?算法?

我的算法,有点差呀。而且没怎么刷过题。

默默祈祷不要考算法。

可就在我以为面试要结束的时候,该来的还是来了。

题目:

给定两个字符串形式的非负整数 num1 和 num2,计算它们的和。
注意,不能把 string 转换为 int 后直接相加。

面试官笑了,我也笑了,好,我写一下。

我隐约记得是模拟人工手算:

一位一位来加,有进位就在左边那位加个 1。

因为没有刷过题,只能按我自己的思路去写,越写越乱,最后还是没能写出来。

面完后,我不禁陷入了沉思。

测试需要学算法?部分需要。

哪些需要?大厂、高级职位、测试开发。

怎么练?刷题。

哪里刷?力扣。

本文就跟大家讲一下字符串大数相加的算法。希望在面试时被问到了,能自信的写出来。

对这个算法,首先要考虑的是,怎么来遍历这 2 个数,可以用 2 个指针,分别指向这 2 个数的尾部,边计算边向左移动。

数的长度可能会不一样,短的那个数的指针就会先到达最左边的头部,为了能够继续计算,可以给缺失的位补 0。

加数长度不一致的问题就解决了。

指针的数相加后,可以通过除以 10 的余数,来算出当前位的结果。

进位,则可以通过对 10 的整除数,来算。

例如:

指针指向的 2 个数是 5 和 6。

5 + 6 = 11,用 tmp 变量来存,tmp = n1 + n2 + carry,因为有可能右边有进位,需要加上。

11 对 10 的整除数是 1,用 carry 来存进位。

11 除以 10 的余数是 1,用 res 来存结果,需要在 res 最左边添加 "1",把 “9084” 变为 “19084”。

最后分析代码:

class Solution:
    # 加法函数,入参num1和num2,返回计算结果,str类型
    def addStrings(self, num1: str, num2: str) -> str:
        res = ""
        # 定义i,j两个指针,分别指向两个数的尾部
        # 定义进位,默认0
        i, j, carry = len(num1) - 1, len(num2) - 1, 0
        # 循环,直到2个指针都到达头部
        while i >= 0 or j >= 0:
            # 如果没有到达头部,就通过-'0'转为int
            # 如果到达头部了,就补0
            n1 = num1[i] - '0' if i >= 0 else 0
            n2 = num2[j] - '0' if j >= 0 else 0
            # n1 + n2 + carry
            tmp = n1 + n2 + carry
            # 进位 = 对10的整除数
            carry = tmp // 10
            # 结果左边添加除以10的余数
            res = str(tmp % 10) + res
            # 每次计算后向左移动1位
            i, j = i - 1, j - 1
        # 2个指针都到达了头部,如果还有进位,就在res左边添加"1"
        # 否则直接返回res
        return "1" + res if carry else res

参考资料:力扣 415. 字符串相加

最后的最后,希望大家都能找到满意的工作,拿到超高的薪资。我也会继续向大厂努力。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • pytest封神之路第二步 132个命令行参数用法

    在Shell执行pytest -h可以看到pytest的命令行参数有这10大类,共132个

    dongfanger
  • DRF终极封装ViewSet和Router附教程PDF源码

    在DRF官方教程的学习过程中,一个很明显的感受是框架在不断地进行封装,我们自己写框架/工具/脚本/平台也可以模仿模仿,先完成底层代码,再做多层封装,让使用者很容...

    dongfanger
  • 字符集其实很简单

    工作中遇到的“词汇”,主要是ASCII、GB2312、GBK、Unicode、UTF-8,还有URL Encode、URL Escape。

    dongfanger
  • 前端基础-正则表达式(环视)

    (?!B)[A-Z]这种写法,其实它是[A-Z]范围里,排除B的意思,前置的(?!B)只是对后面数据的一个限定,从而达到过滤匹配的效果。

    cwl_java
  • 软件评测师笔记(五)—— 计算题

    DABFFH-B3000H+1=27C00H = 10 0111 1100 0000 0000 = 10 0111 11K = 159K

    小菠萝测试笔记
  • js 闭包

    看js闭包,有人出了这个问题, http://www.jb5...

    Dylan Liu
  • PowerShell静态分析(Part I)

    本文分为三个部分,主要介绍了一种实用的powershell脚本静态分析方法,并基于独立于平台python脚本来执行此任务。

    FB客服
  • 华为路由交换技术 | 华为命令行简介

    [ ]undo info-center enable 关闭信息中心 ,防止弹出日志

    网络技术联盟站
  • 8 张图,看你是否理解 Java

    一图胜千言,下面图解均来自Program Creek 网站的Java教程,目前它们拥有最多的票选。如果图解没有阐明问题,那么你可以借助它的标题来一窥究竟。

    芋道源码
  • 一文彻底搞清楚 Material Design

    Material Design 是 Google 在 2014 年 I/O 大会上发布的一种新的设计规范。这种设计风格给 Android UI 设计带来了很多...

    开发者

扫码关注云+社区

领取腾讯云代金券