LeetCode – 445 – 两数相加|| – java – 细喔

云惠网小编 2021年12月30日17:26:59
评论
1860字阅读6分12秒
摘要

文章目录前身题目题目解析解题过程首先我们为 题目的两个链表,各自创建一个栈。然后便是将 ListNode l1 和 ListNode l2 两个节点的val值,分别存入两个“栈”。接下来,就是出栈,将两个链表对应val值相加,加上 上一个节点的 进位数 carry(逢十进一),得到sum和,再来求 sum 的个位数(sum%10),因为每个节点只能存储一位数。再根据这个值(sum%10),去new一个节点。顺便在讲carry值,更新(sum/10)。代码如下代码细节(不多,只有一个)前身 LeetCo

广告也精彩

代码细节(不多,只有一个)

首先我们为 题目的两个链表,各自创建一个栈。


然后便是将 ListNode l1 和 ListNode l2 两个节点的val值,分别存入两个“栈”。

如果 当两个“栈”里数据拿完后,最后两个数据的和sum>10,即:carry 不为 0,,那么意味着需要为其在创造一个节点来存放carry的数据。这点跟它的前身题是一样的,
在这里插入图片描述

题目

在这里插入图片描述

代码如下


解题过程

细节部分: 因为我们现在是逆序相加,所以我们carry进位数,一开始是 0 。而且需要定义在外面,不然每次循环都需要创建一个 carry 浪费时间和空间。(至于为什么需要循环,你可以想想,光是把两个栈里的数据拿出来,是不是就需要一个循环,你要一个个写,那当我没说。)。另外,我们需要new 一个新的头节点head,并初始化为null,用它来进行逆序链接链表的节点,并且最终作为新链表的头节点。最后返回这个head。我们这题就算完成了!
在这里插入图片描述

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<Integer> stack1 = new LinkedList<>();
Deque<Integer> stack2 = new LinkedList<>();
while(l1 != null){
stack1.push(l1.val);
l1 = l1.next;
}
while(l2 != null){
stack2.push(l2.val);
l2 = l2.next;
}
int carry = 0;// 进位数
ListNode head = null;// 头节点
while(!stack1.isEmpty() || !stack2.isEmpty() || carry > 0){
int val1 = stack1.isEmpty() ? 0 : stack1.pop();
int val2 = stack2.isEmpty() ? 0 : stack2.pop();
int sum = val1 + val2 + carry;
carry = sum/10;
ListNode node = new ListNode(sum%10);
node.next = head;
head = node;
}
return head;
}
}

接下来,就是出栈,将两个链表对应val值相加,加上 上一个节点的 进位数 carry(逢十进一),得到sum和,再来求 sum 的个位数(sum%10),因为每个节点只能存储一位数。再根据这个值(sum%10),去new一个节点。顺便在讲carry值,更新(sum/10)。

题目解析

前身

就是说 从两个链表尾结点的val开始相加,且一个节点的val域,只能存储一位数。也就是说十进制:逢十进一。与前身题,不同在就于逆序。难点就在这里。
这里我们的解题思维是利用栈的特性:先入后出,后入先出。

在这里插入图片描述


LeetCode – 445 – 两数相加|| – java – 细喔
我之所以使用 deque(双向队列)是因为,是因为我们想提升效率。(我也试了一下,如果是new了两个栈Stack【Stack stack = new Stack()】,空间效率大,占用空间比较大)。而使用双向队列的目标就是提升空间效率(效果跟栈是一样的)。至于后面new了个 LinkedList 链表,你们应该看得懂,我们这题是链表题,操作的是链表数据。
而且,你看看下标图, deque 是 LinkedList 的父类。父类引用子类对象,也可以!(向上提升)
在这里插入图片描述

LeetCode - 2 - 相加

在这里插入图片描述


文章目录

  • 前身
  • 题目
  • 题目解析
  • 解题过程
    • 首先我们为 题目的两个链表,各自创建一个栈。
    • 然后便是将 ListNode l1 和 ListNode l2 两个节点的val值,分别存入两个“栈”。
    • 接下来,就是出栈,将两个链表对应val值相加,加上 上一个节点的 进位数 carry(逢十进一),得到sum和,再来求 sum 的个位数(sum%10),因为每个节点只能存储一位数。再根据这个值(sum%10),去new一个节点。顺便在讲carry值,更新(sum/10)。
  • 代码如下
    • 代码细节(不多,只有一个)

本文转自 https://blog.csdn.net/DarkAndGrey/article/details/122221804

腾讯云618
未分类
云惠网小编
SpringCloud -- Config、Bus解析

SpringCloud — Config、Bus解析

1、Config1.1、概述简介1. 分布式面临的问题微服务意味着要将单体应用中的业务拆分成一个个子服务,每个服务的粒度相对较小,因此系统中会出现大量的服务。由于每个服务都需要必要...
Java数据结构-了解复杂度

Java数据结构-了解复杂度

2.实例分析与计算  四.写在最后  // 计算斐波那契递归fibonacci的时间复杂度 int fibonacci(int N) { return N < 2 ? N : fibonacci...
[深度解剖C语言] --关键字 static

[深度解剖C语言] –关键字 static

static ---最名不副实的关键字目录1.static修饰全局变量2.static修饰函数3.static修饰局部变量static的作用:1.static修饰全局变量我们创建两...
Java数据结构-认识顺序表

Java数据结构-认识顺序表

目录二.顺序表1.概念及结构2.顺序表的实现打印顺序表获取顺序表的有效长度在pos位置新增元素判断是否包含某个元素查找某个元素对应的位置获取/查找pos位置的元素给pos位置的元素...
腾讯云618

发表评论