首页 > 编程语言 >LeetCode算法笔记2

LeetCode算法笔记2

时间：2024-07-15 22:26:24浏览次数：13  
标签：node head temp self 笔记 next current 算法 LeetCode

题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

知识储备:链表

在 Python 中，链表（Linked List）是一种数据结构，其中每个元素（称为节点）包含数据和一个指向下一个节点的引用（或指针）。链表的主要类型包括单链表、双链表和循环链表。下面详细介绍单链表，并附上示例代码。

单链表

特点
  • 每个节点包含数据和一个指向下一个节点的引用。
  • 第一个节点称为头节点（head），最后一个节点的指针指向 None 表示链表结束。
基本操作
  1. 创建节点类：每个节点存储数据和指向下一个节点的引用。
  2. 创建链表类：管理节点的插入、删除和遍历等操作。
示例代码(单链表)
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def insert_at_position(self, data, position):
        if position < 0:
            raise ValueError("Position must be non-negative")
        new_node = Node(data)
        if position == 0:
            new_node.next = self.head
            self.head = new_node
            return
        current = self.head
        prev = None
        count = 0
        while current and count < position:
            prev = current
            current = current.next
            count += 1
        if count == position:
            new_node.next = current
            prev.next = new_node
        else:
            raise IndexError("Position out of bounds")

    def delete_node(self, key):
        temp = self.head
        if temp and temp.data == key:
            self.head = temp.next
            temp = None
            return
        prev = None
        while temp and temp.data != key:
            prev = temp
            temp = temp.next
        if temp is None:
            raise ValueError("Node with data {} not found".format(key))
        prev.next = temp.next
        temp = None

    def delete_at_position(self, position):
        if position < 0:
            raise ValueError("Position must be non-negative")
        temp = self.head
        if temp is None:
            raise IndexError("List is empty")
        if position == 0:
            self.head = temp.next
            temp = None
            return
        prev = None
        count = 0
        while temp and count < position:
            prev = temp
            temp = temp.next
            count += 1
        if temp is None:
            raise IndexError("Position out of bounds")
        prev.next = temp.next
        temp = None

    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

    def display(self):
        elems = []
        current = self.head
        while current:
            elems.append(current.data)
            current = current.next
        print(elems)

# 示例使用
ll = LinkedList()
ll.insert_at_end(1)
ll.insert_at_end(2)
ll.insert_at_end(3)
ll.insert_at_beginning(0)
ll.insert_at_position(1.5, 2)  # 插入 1.5 到索引 2 的位置
ll.display()  # 输出: [0, 1, 1.5, 2, 3]
print(ll.search(2))  # 输出: True
ll.delete_node(1.5)
ll.display()  # 输出: [0, 1, 2, 3]
ll.delete_at_position(1)
ll.display()  # 输出: [0, 2, 3]
示例代码(双链表)
class DNode:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def insert_at_end(self, data):
        new_node = DNode(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def insert_at_beginning(self, data):
        new_node = DNode(data)
        if self.head is None:
            self.head = new_node
            return
        self.head.prev = new_node
        new_node.next = self.head
        self.head = new_node

    def insert_at_position(self, data, position):
        if position < 0:
            raise ValueError("Position must be non-negative")
        new_node = DNode(data)
        if position == 0:
            new_node.next = self.head
            if self.head:
                self.head.prev = new_node
            self.head = new_node
            return
        current = self.head
        count = 0
        while current and count < position:
            prev = current
            current = current.next
            count += 1
        if count == position:
            new_node.next = current
            new_node.prev = prev
            if current:
                current.prev = new_node
            if prev:
                prev.next = new_node
        else:
            raise IndexError("Position out of bounds")

    def delete_node(self, key):
        temp = self.head
        if temp and temp.data == key:
            self.head = temp.next
            if self.head:
                self.head.prev = None
            temp = None
            return
        while temp and temp.data != key:
            temp = temp.next
        if temp is None:
            raise ValueError("Node with data {} not found".format(key))
        if temp.next:
            temp.next.prev = temp.prev
        if temp.prev:
            temp.prev.next = temp.next
        temp = None

    def delete_at_position(self, position):
        if position < 0:
            raise ValueError("Position must be non-negative")
        temp = self.head
        if temp is None:
            raise IndexError("List is empty")
        if position == 0:
            self.head = temp.next
            if self.head:
                self.head.prev = None
            temp = None
            return
        count = 0
        while temp and count < position:
            temp = temp.next
            count += 1
        if temp is None:
            raise IndexError("Position out of bounds")
        if temp.next:
            temp.next.prev = temp.prev
        if temp.prev:
            temp.prev.next = temp.next
        temp = None

    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

    def display_forward(self):
        elems = []
        current = self.head
        while current:
            elems.append(current.data)
            current = current.next
        print(elems)

    def display_backward(self):
        elems = []
        current = self.head
        while current and current.next:
            current = current.next
        while current:
            elems.append(current.data)
            current = current.prev
        print(elems)

# 示例使用
dll = DoublyLinkedList()
dll.insert_at_end(1)
dll.insert_at_end(2)
dll.insert_at_end(3)
dll.insert_at_beginning(0)
dll.insert_at_position(1.5, 2)  # 插入 1.5 到索引 2 的位置
dll.display_forward()  # 输出: [0, 1, 1.5, 2, 3]
dll.display_backward()  # 输出: [3, 2, 1.5, 1, 0]
dll.delete_node(1.5)
dll.display_forward()  # 输出: [0, 1, 2, 3]
dll.delete_at_position(1)
dll.display_forward()  # 输出: [0, 2, 3]

解法(最佳)

完整代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        dummy_head = ListNode(0)
        current = dummy_head  # 指针,指向当前节点
        carry = 0  # 进位初始化为0
        while l1 or l2 or carry:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0

            # 当前位的和
            total = x + y + carry

            # 更新进位
            carry = total // 10

            # 当前位的值(去掉进位的部分)
            current.next = ListNode(total % 10)
            current = current.next

            #移动到新节点
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next

        return dummy_head.next

详细思路讲解

这个函数的目的是将两个用链表表示的逆序非负整数相加，结果也用链表表示。链表节点的值为0到9之间的一个数字。

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:

这是函数的定义，其中 l1 和 l2 是两个链表的头节点，返回值是表示相加结果的链表头节点。

初始化

        dummy_head = ListNode(0)
        current = dummy_head
        carry = 0  # 进位初始化为0
  • dummy_head 是一个哑结点（dummy node），它的作用是简化链表操作。最后返回结果时，返回的是 dummy_head.next。
  • current 是一个指针，指向我们构建的结果链表的当前节点。
  • carry 是进位初始化为0。进位是指两个数字相加时超过10的部分。

遍历链表

        while l1 or l2 or carry:
  • 使用 while 循环，条件是 l1、l2 或 carry 任何一个不为零时继续循环。这样确保我们处理完所有的节点以及可能的最后一个进位。

获取当前节点值

            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
  • x 是当前节点 l1 的值，如果 l1 已经遍历完了就取0。
  • y 是当前节点 l2 的值，如果 l2 已经遍历完了就取0。

计算当前位的总和

            total = carry + x + y
  • total 是当前位的总和，等于 carry 加上 x 和 y。

更新进位

            carry = total // 10
  • 更新进位 carry 为 total 除以10的整数部分（地板除）。如果 total 小于10，则 carry 为0；如果 total 大于等于10，则 carry 为1。

生成新节点

            current.next = ListNode(total % 10)
            current = current.next
  • 创建一个新节点，其值为 total 模10的结果（即去掉进位的部分）。
  • 更新 current 指针到新节点。

移动到下一个节点

            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
  • 移动 l1 和 l2 指针到它们的下一个节点。如果链表已经遍历完毕，这些指针将变为 None。

返回结果

        return dummy_head.next
  • 返回 dummy_head.next，因为 dummy_head 是哑结点，真正的结果链表从 dummy_head.next 开始。

代码整体思路

  1. 初始化哑结点 dummy_head 和当前节点 current 以及进位 carry。
  2. 遍历 l1 和 l2 直到它们和 carry 都为零。
  3. 在每次循环中，获取当前节点的值并计算总和，然后更新进位，创建新节点并更新 current。
  4. 最后返回 dummy_head.next，即结果链表的头节点。

这种方式确保了代码的简洁和高效，同时处理了链表长度不同和最终进位的情况。

标签：node,head,temp,self,笔记,next,current,算法,LeetCode
From： https://blog.csdn.net/m0_73192625/article/details/140331255

相关文章

  • 长链剖分笔记
    与轻重链剖分相似.dfs1：高度\(h\)、\(son\)；dfs2：\(top\).性质1：到根最多\(O(\sqrtn)\)条轻边.（证明：长链长度最坏情况：1,2,3...）性质2：\(x\)的\(k\)级祖先\(y\)所在的长链长度\(\gek\).（证明：若非，则\(y-x\)是一条更长的链，矛盾.）树上\(k\)级祖先\(O(n\logn)-O(1)\)：......
  • 【matlab】智能优化算法优化BP神经网络
    目录引言一、BP神经网络简介二、智能优化算法概述三、智能优化算法优化BP神经网络的方法四、蜣螂优化算法案例1、算法来源2、算法描述3、算法性能结果仿真代码实现引言智能优化算法优化BP神经网络是一个重要的研究领域，旨在通过智能算法提高BP神经网络的性能和......
  • 最爽手撕算法个人笔记【第一周-数组】
    27.移除元素给你一个数组nums和一个值val，你需要原地移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回nums中与val不同的元素的数量。假设nums中不等于val的元素数量为k，要通过此题，您需要执行以下操作：更改nums数组，使nums的前k个元素包含不......
  • 网络安全相关的一些学习笔记
    网络安全？本文主要为《计算机网络》网络安全章节的学习笔记，也包括部分来自其他博客与网站的段落。1.一些名词解释密码编码学（cryptography）：密码体制的设计学密码分析学（cryptanalysis）：在未知密钥的情况下从密文推演出明文或密钥的技术上述二者合称密码学（cryptology）无条件安全（理......
  • 基于改进K-means的网络数据聚类算法matlab仿真
    1.程序功能描述       K-means属于聚类分析中一种基本的划分方法，常采用误差平方和准则函数作为聚类准则。主要优点是算法简单、快速而且能有效地处理大数据集。研究和分析了聚类算法中的经典K-均值聚类算法，总结出其优点和不足。重点分析了K-均值聚类算法对初始值的依赖性......
  • AcWing 2074：倒计数 ← 双指针算法
    【题目来源】https://www.acwing.com/problem/content/2076/【题目描述】艾弗里有一个由N个正整数构成的数组。数组中的第i个整数是Ai。如果一个连续的子数组的长度为m，并且按顺序包含整数m,m−1,m−2,…,2,1，则称它为m倒计数。例如，[3,2,1]是3倒计数。请帮助艾......
  • 设计模式之装饰模式（学习笔记）
    定义装饰模式（DecoratorPattern），又称为包装模式，是一种结构型设计模式。它允许在不改变现有对象结构的情况下，动态地添加新的功能。通过将每个功能封装在单独的装饰器类中，并且这些装饰器类通过引用原始对象来实现功能的组合，从而提供了灵活性和可扩展性的优势。装饰模式避免了通过继......
  • 矩阵优化 DP 以及全局平衡二叉树实现的动态 DP 学习笔记
    矩阵乘法求斐波那契数列的第\(n\)项，其中\(n\le10^{18}\)，对数\(m\)取模。写出转移方程，\(f_i=f_{i-1}+f_{i-2}\)，直接算是\(O(n)\)的，似乎没什么办法优化。定义大小分别为\(n\timesp\)和\(p\timesm\)的矩阵（分别为\(a\)和\(b\)）相乘的结果（矩阵\(c\)）是一个大小为\(......
  • Leetcode.20 有效括号
    题目描述给定一个只包括'('，')'，'{'，'}'，'['，']' 的字符串s，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。示例输入：s="()"输出：true输入：s="()[]{}"输出：true输入：s=......
  • LeetCode - #96 不同的二叉搜索树（Top 100）
    文章目录前言1.描述2.示例3.答案关于我们前言本题为LeetCode前100高频题我们社区陆续会将顾毅（Netflix增长黑客，《iOS面试之道》作者，ACE职业健身教练。）的Swift算法题题解整理为文字版以方便大家学习与阅读。LeetCode算法到目前我们已经更新到94期，......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99