专栏首页灰子学技术算法篇:链表之两数相加

算法篇:链表之两数相加

算法: 核心问题是进位的操作:

1)不要忘记进位之后的哪一个1;

2)不要忘记所有位都操作完了之后,最后的哪一个进位1

变形题目的话,需要想办法转换成 题目1这种原子操作的题目。

题目 1: 两数相加:

https://leetcode-cn.com/problems/add-two-numbers/

代码:

// 算法: 核心问题是:进位的操作,
// 1)不要忘记进位之后的哪一个1;
// 2)不要忘记所有位都操作完了之后,最后的哪一个进位1

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
  if l1 == nil {
    return l2
  }
  if l2 == nil {
    return l1
  }
  h := new(ListNode)
  pre,res := h,h
    m, n := l1, l2
  for  m != nil && n != nil {
    tmp := new(ListNode)
    sum := m.Val + n.Val + res.Val
    if sum >= 10 {
      tmp.Val = 1
    }
    pre = res
    res.Val = sum % 10
    res.Next = tmp
        res = res.Next
    m = m.Next
    n = n.Next
  }
    
  for m != nil {
    tmp := new(ListNode)
    s := m.Val + res.Val
    if s >= 10 {
      tmp.Val = 1
    }
    pre = res
    res.Val = s % 10
    res.Next = tmp
        res = res.Next
    m = m.Next
  }
  for n != nil {
    tmp := new(ListNode)
    s := n.Val + res.Val
    if s >= 10 {
      tmp.Val = 1
    }
    pre = res
    res.Val = s % 10
    res.Next = tmp
        res = res.Next
    n = n.Next
  }
  if res.Val == 0 {
        pre.Next = nil
    }
  return h
}

运行结果:

题目 2: 两数之和:

https://leetcode-cn.com/problems/sum-lists-lcci/

代码实现:

// 算法:实现方式与题目1一致,
// 本题代码相当于对题目1的解法做了一个代码层面的优化
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    res := new(ListNode)
    n := res
    r := 0
    // 相同位的计算
    for l1 != nil && l2 != nil {
        s:= r + l1.Val + l2.Val
        if s >= 10 {
            r = 1 
        } else {
            r = 0 
        }
        tmp := ListNode{Val:s%10}
        res.Next = &tmp
        l1 = l1.Next
        l2 = l2.Next
        res = res.Next
    }
    // 位数不同的两个数的,高位数计算
    var result *ListNode
    if l1 != nil {
        result = l1
    } else if l2 != nil {
        result = l2
    }
    for result != nil {
        s:= r + result.Val 
        if s >= 10 {
            r = 1 
        } else {
            r = 0 
        }
        tmp := ListNode{Val:s%10}
        res.Next = &tmp
        result = result.Next
        res = res.Next 
    }
    // 最后的进位
    if r  != 0 {
        tmp := ListNode{Val:r}
        res.Next = &tmp
    }
    return n.Next
}

执行结果:

题目 3 :两数相加

https://leetcode-cn.com/problems/add-two-numbers-ii/

// 算法:
// 核心点在于,链表的低位是数字的高位,只要能够将链表的高低位交换,就变成题目1.
// 采用数组顺序性去实现高低位的反转,从数组末尾遍历就可以了。
// 剩下的思路与题目1一致。
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    var a,b,c []*ListNode
    for l1 != nil {
        a = append(a,l1)
        l1 = l1.Next
    }
    for l2 != nil {
        b = append(b,l2)
        l2 = l2.Next
    }
    
    c = Sum(a,b)
    
    res := new(ListNode)
    n := res
    for i := len(c)-1;i>=0;i-- {
        res.Next = c[i]
        res = res.Next
    }
    return n.Next
}
func Sum(a,b []*ListNode) (c []*ListNode){
    r := 0
    i, j := len(a)-1,len(b)-1
    for i>=0 && j >=0 {
        s := r + a[i].Val+b[j].Val
        tmp := new(ListNode)
        tmp.Val = s%10
        c = append(c,tmp)
        if s >= 10 {
            r = 1
        } else {
            r = 0
        }
        i--
        j--
    }
    for i >= 0{
        s := r + a[i].Val
        tmp := new(ListNode)
        tmp.Val = s%10
        if s >= 10 {
            r = 1
        } else {
            r = 0
        }
        c = append(c,tmp)
        i--
    }
    for j >= 0{
        s := r + b[j].Val
        tmp := new(ListNode)
        tmp.Val = s%10
        if s >= 10 {
            r = 1
        } else {
            r = 0
        }
        c = append(c,tmp)
        j--
    }
    if r != 0 {
        c = append(c,&ListNode{Val:r})
    }
    return c
}

运行结果:

本文分享自微信公众号 - 灰子学技术(huizixueguoxue),作者:灰子学技术

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

原始发表时间:2020-07-26

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法篇:链表之排序

    https://leetcode-cn.com/problems/partition-list/submissions/

    灰子学技术
  • 算法篇:链表之删除链表中重复节点

    核心点在于如何找到重复节点,有序链表的话,只要下一个节点与当前节点数值一样就是重复节点,直接将当前节点指向下一个节点的下一个节点即可。

    灰子学技术
  • 算法篇:链表之倒数第k个节点

    该类型的题目,核心点在于如何找到倒数第k个节点的位置,典型的操作办法是,双指针的方法。

    灰子学技术
  • 蜂群衰竭,这架专为植物授粉的无人机应运而生

    近日,来自日本的科研人员制造出了一种跟昆虫差不多大小的无人机,未来它将能取代--或是至少能协助蜜蜂传播花粉。可以看到,这种无人机的底部粘有类似于蜜蜂腹毛的毛发,...

    机器人网
  • C++经典算法题-多维矩阵转一维矩阵

    有的时候,为了运算方便或资料储存的空间问题,使用一维阵列会比二维或多维阵列来得方便 , 例如上三角矩阵、下三角矩阵或对角矩阵,使用一维阵列会比使用二维阵列来得节...

    cwl_java
  • 在android中资源文件夹中添加一个新的图片资源

    刚刚看了一下一个帧布局的简单Android示例,纠结了半天不知道如何将图片加到resource中的drawable中去。     比如在一个TestDem...

    ccf19881030
  • 使用PowerShell 监控运行时间和连接情况

    概念 Powershell 是运行在windows机器上实现系统和应用程序管理自动化的命令行脚本环境。你可以把它看成是命令行提示符cmd.exe的扩充,不对,应...

    用户1217611
  • 微云携手Office在线编辑

    腾讯ISUX
  • crontab条目包含%号问题

    crontab条目中包含%号,最常见的取时间,如:date +%d, 对%需要使用\进行转义,否则不能按预期执行,正确做法为: * * * * * echo...

    一见
  • 12.18 ssl原理

    ssl原理 https的相关知识点 要配置nginx和https,就需要首先去了解https是什么? 在访问一些网站的时候,会自动加上了https前标 http...

    运维小白

扫码关注云+社区

领取腾讯云代金券