博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
李洪强iOS经典面试题34-求两个链表表示的数的和
阅读量:5855 次
发布时间:2019-06-19

本文共 2171 字,大约阅读时间需要 7 分钟。

李洪强iOS经典面试题34-求两个链表表示的数的和

问题

给你两个链表,分别表示两个非负的整数。每个链表的节点表示一个整数位。

为了方便计算,整数的低位在链表头,例如:123 在链表中的表示方式是:

3 -> 2 -> 1

现在给你两个这样结构的链表,请输出它们求和之后的结果。例如:

输入: (2 -> 4 -> 1) + (5 -> 6 -> 1)

输出: 7 -> 0 -> 3

代码模版

本题的 Swift 代码模版如下:

private class ListNode {    public var val: Int    public var next: ListNode?    public init(_ val: Int) {        self.val = val        self.next = nil    }}class Solution {    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?)          -> ListNode? {    }}

考查点

本题出自 LeetCode 上的第 2 题。

这是我高中学习编程时最早接触的一类题目,我们把这类题目叫做「高精度计算」,其实就是在计算机计算精度不够时,模拟我们在纸上演算的方式来计算答案,然后获得足够精度的解。

我还记得我 7 年前第一次去网易有道面试的时候,就考查的是一道类似的高精度计算题目,比这道题复杂得多,我当时用了一个比较笨的办法,加上当时还是用 C++ 写的,内存分配和释放写起来也比较麻烦,最后写了两页 A4 纸才写完。

这道题其实完全不考查什么「算法」,人人都知道怎么计算,但是它考察了「将想法转换成代码」的能力,新手通常犯的毛病就是:意思都明白,但是写不出来代码。所以,这类题目用来过滤菜鸟确实是挺有效的办法。

答案

本题的做法其实没什么特别,就是直接计算。计算的时候需要考虑到以下这些情况:

  1. 两个整数长度不一致的情况。

  2. 进位的情况。当进位产生时,我们需要保存一个标志位,以便在计算下一位的和的时候,加上进位。

  3. 当计算完后,如果还有进位,需要处理最后结果加一位的情况。

以下是完整的代码,我使用了一些 Swift 语言的特性,比如用 flatMap 来减少对于 Optional类型值为 nil 的判断。

private class ListNode {    public var val: Int    public var next: ListNode?    public init(_ val: Int) {        self.val = val        self.next = nil    }}private class Solution {    private func getNodeValue(_ node: ListNode?) -> Int {        return node.flatMap { $0.val } ?? 0    }    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?)              -> ListNode? {        if l1 == nil || l2 == nil {            return l1 ?? l2        }        var p1 = l1        var p2 = l2        let result: ListNode? = ListNode(0)        var current = result        var extra = 0        while p1 != nil || p2 != nil || extra != 0 {            var tot = getNodeValue(p1) +                      getNodeValue(p2) + extra            extra = tot / 10            tot = tot % 10            let sum:ListNode? = ListNode(tot)            current!.next = sum            current = sum            p1 = p1.flatMap { $0.next }            p2 = p2.flatMap { $0.next }        }        return result!.next    }}

以上代码也可以从我的 Gist 中找到:https://gist.github.com/tangqiaoboy/af0dc9a45dd309e91436b44b76eab5f1

偷偷告诉你一个小秘密,Gist 里面的代码我稍微修改了两行,最终性能就从打败 LeetCode 10% 的提交变成了打败 LeetCode 50% 的提交,如果你感兴趣,可以自己仔细对比一下。

愿大家玩得开心~

转载地址:http://vnojx.baihongyu.com/

你可能感兴趣的文章
零星笔记
查看>>
mysql中INSERT INTO… ON DUPLICATE KEY UPDATE用法
查看>>
一例所有文件都打不开的数据恢复过程
查看>>
alibench交互 获取测试链接全国打开情况
查看>>
性能测试培训:sql server性能测试分析局部变量的性能影响1
查看>>
Vector图层使用SelectFeature控件后,鼠标无法拖动地图的解决方法
查看>>
ie8,9无法获取到绝对定位的元素的left的值
查看>>
蓝牙几个基础常识
查看>>
WINDOWS8.1远程桌面设置与无法连接解决办法
查看>>
linux授权执行权限
查看>>
springboot的PathVariable接收参数值带点号问题
查看>>
spring security oauth2 allowFormAuthenticationForClients原理解析
查看>>
树的创建和遍历
查看>>
flask+datatables服务器分页
查看>>
Linux 之 特殊字符理解
查看>>
dell emc isilon修改丢失的root密码
查看>>
ThinkPHP 3.2.3响应微信发送的Token验证失败
查看>>
Win7+Ubuntu11
查看>>
Java如何获取系统cpu、内存、硬盘信息
查看>>
PMP每日一题
查看>>