打卡力扣题目三

这篇具有很好参考价值的文章主要介绍了打卡力扣题目三。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 #左耳听风 ARST 打卡活动重启#

目录

 一、题目

 二、解题方法一

三、解题方法二 


关于 ARTS 的释义 —— 每周完成一个 ARTS:
● Algorithm: 每周至少做一个 LeetCode 的算法题
● Review: 阅读并点评至少一篇英文技术文章
● Tips: 学习至少一个技术技巧
● Share: 分享一篇有观点和思考的技术文章

希望通过此次活动能聚集一波热爱技术的人,延续好奇、探索、实践、分享的精神。
 


 一、题目

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。 请你将两个数相加,并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

 二、解题方法一

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1, l2):
    carry = 0
    p1 = l1
    p2 = l2
    ans = None
    while p1 or p2 or carry:
        v1 = p1.val if p1 else 0
        v2 = p2.val if p2 else 0
        total = v1 + v2 + carry
        if total >= 10:
            carry = 1
            total %= 10
        else:
            carry = 0
        node = ListNode(total)
        node.next = ans
        ans = node
        if p1: p1 = p1.next
        if p2: p2 = p2.next
    return ans

其中,`ListNode` 是链表节点的类定义,包含一个值 `val` 和一个指向下一个节点的指针 `next`。`addTwoNumbers()` 函数接受两个链表 `l1` 和 `l2`,并返回它们的和表示的链表。在函数中,我们使用三个指针 `p1`、`p2` 和 `carry` 分别指向两个链表的当前节点和进位值。然后,我们循环遍历两个链表,每次将当前节点的值相加再加上进位值,得到一个新的总和。如果总和大于等于 10,则需要进位;否则不需要进位。最后,我们将新的总和封装成一个节点,并将其插入到结果链表的最前面。当遍历完两个链表后,返回结果链表即可。

 具体实现过程如下:

  1. 定义一个链表节点类 ListNode,包含一个值 val 和一个指向下一个节点的指针 next
  2. 定义函数 addTwoNumbers(l1, l2),其中 l1 和 l2 分别表示两个链表。
  3. 在函数中定义三个指针变量 p1p2 和 carry,分别指向两个链表的当前节点和进位值。初始时,p1 和 p2 分别指向两个链表的头节点,carry 初始化为 0。
  4. 进入循环,每次循环处理两个链表中的一个节点和一个进位值:
    • 首先,获取当前节点的值 v1 和进位值 v2,如果当前节点为空,则将其值设为 0。
    • 然后,计算新的总和 total,即 v1 + v2 + carry。如果总和大于等于 10,则需要进位;否则不需要进位。
    • 如果需要进位,则将 carry 置为 1,并将总和对 10 取余数,以保证结果不超过 9。
    • 否则,将 carry 置为 0。
    • 然后,创建一个新的节点 node,其值为 total,并将其插入到结果链表的最前面。同时更新指针变量 p1p2 和 ans,使其分别指向新插入的节点、原链表的下一个节点和当前节点所指向的节点。
  5. 当遍历完两个链表后,返回结果链表即可。

需要注意的是,这个算法的时间复杂度为 O(max(m, n)),其中 m 和 n 分别表示两个链表的长度。因为在最坏情况下,我们需要遍历较长的链表才能得到最终结果。

三、解题方法二 

除了使用哈希表来存储已经遍历过的元素及其对应的下标的方法,还可以使用迭代的方式来实现。

具体实现过程如下:

1. 定义一个函数 `addTwoNumbers(l1, l2)`,其中 `l1` 和 `l2` 分别表示两个链表。
2. 在函数中定义两个变量 `num1` 和 `num2`,分别表示第一个链表的当前节点所指向的数字和第二个链表的当前节点所指向的数字。初始时,`num1` 和 `num2` 都为 0。
3. 定义一个变量 `carry`,用于记录进位值。初始时,`carry` 为 0。
4. 进入循环,每次循环处理两个链表中的一个节点:
   * 首先,获取当前节点所指向的数字 `val`,如果当前节点为空,则将其值设为 0。
   * 然后,将 `num1` 加上 `val`,并将结果与 `num2` 相加,同时加上进位值 `carry`。如果相加的结果大于等于 10,则需要进位;否则不需要进位。
   * 如果需要进位,则将 `carry` 置为 1,并更新 `num1` 的值为相加结果对 10 取余数。
   * 否则,将 `carry` 置为 0,并更新 `num1` 的值为相加结果。
5. 当遍历完两个链表后,返回一个新的链表,其头节点为 `num1`,尾节点为空。

需要注意的是,这个算法的时间复杂度为 O(max(m, n)),其中 m 和 n 分别表示两个链表的长度。因为在最坏情况下,我们需要遍历较长的链表才能得到最终结果。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1, l2):
    num1, num2, carry = 0, 0, 0
    res = ListNode()
    p1 = l1
    p2 = l2
    while p1 or p2 or carry:
        val1 = p1.val if p1 else 0
        val2 = p2.val if p2 else 0
        total = val1 + val2 + carry
        if total >= 10:
            carry = 1
            total %= 10
        else:
            carry = 0
        node = ListNode(total)
        node.next = res.next
        res.next = node
        num1 = val1
        num2 = val2
        p1 = p1.next if p1 else None
        p2 = p2.next if p2 else None
    return res.next

其中,ListNode 是链表节点的类定义,包含一个值 val 和一个指向下一个节点的指针 nextaddTwoNumbers() 函数接受两个链表 l1l2,并返回它们的和表示的链表。在函数中,我们使用三个变量 num1num2carry 分别表示第一个链表的当前节点所指向的数字、第二个链表的当前节点所指向的数字和进位值。初始时,num1num2carry 都为 0。然后,我们进入循环,每次循环处理两个链表中的一个节点和一个进位值:首先获取当前节点所指向的数字 val,如果当前节点为空,则将其值设为 0;然后将 num1 加上 val,并将结果与 num2 相加,同时加上进位值 carry;如果相加的结果大于等于 10,则需要进位;否则不需要进位;如果需要进位,则将 carry 置为 1,并更新 num1 的值为相加结果对 10 取余数;否则,将 carry 置为 0,并更新 num1 的值为相加结果。最后,将新节点插入到结果链表的最前面,并返回结果链表即可。文章来源地址https://www.toymoban.com/news/detail-620985.html

到了这里,关于打卡力扣题目三的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 打卡力扣题目九

    #左耳听风 ARST 打卡活动重启# 目录  一、问题  二、解题方法一  三、解题方法二 四、两种方法的区别 关于 ARTS 的释义 —— 每周完成一个 ARTS: ● Algorithm: 每周至少做一个 LeetCode 的算法题 ● Review: 阅读并点评至少一篇英文技术文章 ● Tips: 学习至少一个技术技巧 ● Share

    2024年02月14日
    浏览(38)
  • 打卡力扣题目十一

    #左耳听风 ARST 打卡活动重启# 目录  一、问题 二、解题方法一  三、解题方法二  四、区别  关于 ARTS 的释义 —— 每周完成一个 ARTS: ● Algorithm: 每周至少做一个 LeetCode 的算法题 ● Review: 阅读并点评至少一篇英文技术文章 ● Tips: 学习至少一个技术技巧 ● Share: 分享一篇有

    2024年02月14日
    浏览(31)
  • 【leetcode 力扣刷题】回文串相关题目(KMP、动态规划)

    题目链接:5. 最长回文子串 题目内容: 题目就是要我们找s中的回文子串,还要是最长的。其实想想,暴力求解也行……就是遍历所有的子串,同时判断是不是回文串,是的话再和记录的最大长度maxlen比较,如果更长就更新。时间复杂度直接变成O(n^3)。 优化的点在于,假设子

    2024年02月09日
    浏览(48)
  • 算法打卡day32|贪心算法篇06|Leetcode 738.单调递增的数字、968.监控二叉树

    Leetcode 738.单调递增的数字 题目链接:738.单调递增的数字  大佬视频讲解:单调递增的数字视频讲解  个人思路 这个题目就是从例子中找规律,例如 332,从后往前遍历,32不是单调递增将2变为9,3减1,变成了329,遍历到2,32不是递增,将2变为9,3减1,变成299,符合题目条件,打印

    2024年04月16日
    浏览(46)
  • [职场] 会计学专业学什么 #其他#知识分享#职场发展

    会计学专业学什么 会计学专业属于工商管理学科下的一个二级学科,本专业培养具备财务、管理、经济、法律等方面的知识和能力,具有分析和解决财务、金融问题的基本能力,能在企、事业单位及政府部门从事会计实务以及教学、科研方面工作的工商管理学科高级专门人才

    2024年02月20日
    浏览(49)
  • 算法打卡day49|动态规划篇17| Leetcode 647. 回文子串、516.最长回文子序列

    Leetcode 647. 回文子串 题目链接:647. 回文子串 大佬视频讲解:647. 回文子串视频讲解  个人思路  这道题的dp数组有点难找到关联,以至于递归关系也不好找,所以看题解吧... 解法 动态规划 动规五部曲: 1.确定dp数组(dp table)以及下标的含义 一般在定义dp数组的时候 会根据题

    2024年04月22日
    浏览(50)
  • 学习平台助力职场发展与提升

    近年来,随着互联网技术的发展, 学习平台 逐渐成为了职场发展和提升的必备工具。学习平台通过提供丰富的课程内容、灵活的学习时间和个性化的学习路径,帮助职场人士更好地提升自己的技能和知识储备,为职场发展打下坚实的基础。 学习平台的优势在于提供了丰富多

    2024年02月11日
    浏览(51)
  • 算法打卡day39|动态规划篇07| Leetcode 70. 爬楼梯(进阶版)、322. 零钱兑换、279.完全平方数

    Leetcode 70. 爬楼梯(进阶版) 题目: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 = m n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 输入描述:输入共一行,包含两个正整数,分别表示n, m 输出描述:输出一个整数,

    2024年04月14日
    浏览(65)
  • 力扣(LeetCode)算法_C++—— 快乐数

    编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1,那么这个数就是快乐数。 如果 n 是

    2024年02月09日
    浏览(40)
  • 算法学习——LeetCode力扣回溯篇2

    40. 组合总和 II - 力扣(LeetCode) 描述 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意:解集不能包含重复的组合。 示例 示例 1: 输入: candidates = [10,1,2,7

    2024年02月20日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包