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

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

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

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


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

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

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

默默祈祷不要考算法。

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

题目:

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

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

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


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

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

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

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

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

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

怎么练?刷题。

哪里刷?力扣。

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

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

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

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

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

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

例如:


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

指针指向的 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. 字符串相加

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/2662.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • acwing-395. 冗余路径(Tarjan双连通分量)

    acwing-395. 冗余路径(Tarjan双连通分量)为了从 F 个草场中的一个走到另一个,奶牛们有时不得不路过一些她们讨厌的可怕的树。奶牛们已经厌倦了被迫走某一条路,所以她们想建一些新路,使每一对草场之间都会至少有两条相互分离的路径,这样她们就有多一些选择。每对草场之间已经有至少一条路径。给出所有 R 条双向路的描述,每条路连接了两个不同的草场,请计算最少的新建道路的数量,路径由若干道路首尾相连而成。两条路径相互分离,是指两条路径没有一条重合的道路。但是,两条分离的路径上可以有一些相同的草场。对于同一对草场之间,可能已经有两条不同的道路,你也可以

  • 手把手实现Java图书管理系统(附源码)_图书管理系统项目背景

    手把手实现Java图书管理系统(附源码)_图书管理系统项目背景基于JavaWeb开发的图书管理系统实现功能数据库运行环境图书馆作为一种信息资源的集散地,图书和用户借阅资料繁多,包含很多的信息数据的管理,现今,有很多的图书馆都是初步开始使用,甚至尚未使用计算机进行信息管理。图书馆信息管理作为计算机应用的一个分支,有着手工管理无法比拟的优点,如检索迅速、查找方便、可靠性高、存储量大、保密性好、寿命长、成本低等。这些优点很大程度的提高了管理图书馆信息的工作效率,节省了大量资金,方便了师生对图书的借阅和归还。图书馆管理系统代表了图书馆管理的信息化,不仅是体现图书馆现代化形

  • Mac下利用Anaconda安装Opencv「建议收藏」

    Mac下利用Anaconda安装Opencv「建议收藏」打开Anaconda,选择Environments,打开需要安装环境的终端输入以下代码sudopipinstallopencv-python-ihttps://pypi.tuna.tsinghua.edu.cn/simple记住命令前加sudo,否则会报错填写密码后即可安装验证安装是否成功方法1importcv2没错报错就表明安装成功方法2condalist找到opencv库则表明安装成功!!Reference添加链接描述添加链接描述…

  • CentOS7在线安装gcc及使用

    CentOS7在线安装gcc及使用CentOS7在线安装gcc及使用一.在线安装gcc(需要配置网络)在虚拟机VMwareWorkstation安装CentOS7后,系统是没有gcc的。进入系统根目录[root@localhost~],输入命令:[root@localhost~]yum-yinstallgccgcc-c++autoconfmake就会自动进行在线安装。完成后输入命令:[root…

  • php 一句话木马简介

    php 一句话木马简介一句话木马就是一段简单的代码,就这短短的一行代码,就能做到和大马相当的功能。一句话木马短小精悍,而且功能强大,隐蔽性非常好,在入侵中始终扮演着强大的作用。一句话木马工作原理<?php@eval($_POST[‘shell’]);?>这是php的一句话后门中最普遍的一种。它的工作原理是:首先存在一个名为shell的变量,shell的取值为HTTP的POST方式。Web服务器对shell取值以后,然后通过eval()函数执行shell里面的内容。实例:<?php@ev

  • LSD_SLAM编译之一气呵成法

    LSD_SLAM编译之一气呵成法LSD_SLAM编译之平台信息本LSD_SLAM编译平台信息:ubuntu16.04LSopencv3.XROS—kinetic其他的都不重要…ROS_kinetic的安装参考点击此处准备及安装注意:一定要下载此处的LSD_SLAM官方的lsd_slam一直没有编译成功,此LSD_SLAM已经被该作者fixedbugs.所以我们直接下载该git。…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号