Loading [MathJax]/jax/input/TeX/jax.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >米哈游(原神)最简单的算法原题

米哈游(原神)最简单的算法原题

作者头像
宫水三叶的刷题日记
发布于 2024-06-26 01:35:27
发布于 2024-06-26 01:35:27
22400
代码可运行
举报
运行总次数:0
代码可运行

来一道和「米哈游(原神)」相关的面试题(应该是米哈游出过最简单的了)。

题目描述

平台:LeetCode

题号:剑指 Offer 35. 复杂链表的复制

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random,该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。

深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。

新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态,复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 XY 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 xy ,同样有 x.random --> y

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。

每个节点用一个 [val, random_index] 表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从
0

n1

);如果不指向任何节点,则为 null

你的代码只接受原链表的头节点 head 作为传入参数。

示例 1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:head = [[1,1],[2,1]]

输出:[[1,1],[2,1]]

示例 3:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:head = [[3,null],[3,0],[3,null]]

输出:[[3,null],[3,0],[3,null]]

示例 4:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:head = []

输出:[]

解释:给定的链表为空(空指针),因此返回 null

提示:

0<=n<=1000
10000<=Node.val<=10000

模拟 + 哈希表

如果不考虑 random 指针的话,对一条链表进行拷贝,我们只需要使用两个指针:一个用于遍历原链表,一个用于构造新链表(始终指向新链表的尾部)即可。这一步操作可看做是「创建节点 + 构建 next 指针关系」。

现在在此基础上增加一个 random 指针,我们可以将 next 指针和 random 指针关系的构建拆开进行:

  1. 先不考虑 random 指针,和原本的链表复制一样,创建新新节点,并构造 next 指针关系,同时使用「哈希表」记录原节点和新节点的映射关系;
  2. 对原链表和新链表进行同时遍历,对于原链表的每个节点上的 random 都通过「哈希表」找到对应的新 random 节点,并在新链表上构造 random 关系。

Java 代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    public Node copyRandomList(Node head) {
        Node t = head;
        Node dummy = new Node(-10010), cur = dummy;
        Map<Node, Node> map = new HashMap<>();
        while (head != null) {
            Node node = new Node(head.val);
            map.put(head, node);
            cur.next = node;
            cur = cur.next; head = head.next;
        }
        cur = dummy.next; head = t;
        while (head != null) {
            cur.random = map.get(head.random);
            cur = cur.next; head = head.next;
        }
        return dummy.next;
    }
}

C++ 代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node* t = head;
        Node* dummy = new Node(-10010), *cur = dummy;
        unordered_map<Node*, Node*> map;
        while (head != nullptr) {
            Node* node = new Node(head->val);
            map[head] = node;
            cur->next = node;
            cur = cur->next; head = head->next;
        }
        cur = dummy->next; head = t;
        while (head != nullptr) {
            cur->random = map[head->random];
            cur = cur->next; head = head->next;
        }
        return dummy->next;
    }
};

Python 代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        t = head
        dummy = Node(-10010)
        cur = dummy
        mapping = {}
        while head:
            node = Node(head.val)
            mapping[head] = node
            cur.next = node
            cur, head = cur.next, head.next
        cur, head = dummy.next, t
        while head:
            if head.random in mapping:
                cur.random = mapping[head.random]
            cur, head = cur.next, head.next
        return dummy.next
  • 时间复杂度:
O(n)
  • 空间复杂度:
O(n)

模拟(原地算法)

显然时间复杂度上无法优化,考虑如何降低空间(不使用「哈希表」)。

我们使用「哈希表」的目的为了实现原节点和新节点的映射关系,更进一步的是为了快速找到某个节点 random 在新链表的位置。

那么我们可以利用原链表的 next 做一个临时中转,从而实现映射。

具体的,我们可以按照如下流程进行:

  1. 对原链表的每个节点节点进行复制,并追加到原节点的后面;
  2. 完成
1

操作之后,链表的奇数位置代表了原链表节点,链表的偶数位置代表了新链表节点,且每个原节点的 next 指针执行了对应的新节点。这时候,我们需要构造新链表的 random 指针关系,可以利用 link[i + 1].random = link[i].random.next

i

为奇数下标,含义为 「新链表节点的 random 指针指向旧链表对应节点的 random 指针的下一个值」

  1. 对链表进行拆分操作。

Java 代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return head;
        Node t = head;
        while (head != null) {
            Node node = new Node(head.val);
            node.next = head.next;
            head.next = node;
            head = node.next;
        }
        head = t;
        while (head != null) {
            if (head.random != null) head.next.random = head.random.next;
            head = head.next.next;
        }
        head = t;
        Node ans = head.next;
        while (head != null) {
            Node ne = head.next;
            if (ne != null) head.next = ne.next;
            head = ne;
        }
        return ans;
    }
}

C++ 代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return head;
        Node* t = head;
        while (head) {
            Node* node = new Node(head->val);
            node->next = head->next;
            head->next = node;
            head = node->next;
        }
        head = t;
        while (head) {
            if (head->random) head->next->random = head->random->next;
            head = head->next->next;
        }
        head = t;
        Node* ans = head->next;
        while (head) {
            Node* ne = head->next;
            if (ne) head->next = ne->next;
            head = ne;
        }
        return ans;
    }
};

Python 代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return head
        t = head
        while head:
            node = Node(head.val)
            node.next = head.next
            head.next = node
            head = node.next
        head = t
        while head:
            if head.random:
                head.next.random = head.random.next
            head = head.next.next
        head = t
        ans = head.next
        while head:
            ne = head.next
            if ne:
                head.next = ne.next
            head = ne
        return ans
  • 时间复杂度:
O(n)
  • 空间复杂度:
O(1)
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2024-06-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 宫水三叶的刷题日记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
【面试高频题】可逐步优化的链表高频题
题目描述 这是 LeetCode 上的 138. 复制带随机指针的链表 ,难度为 中等。 Tag : 「哈希表」、「链表」 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random,该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。 返回复制链表的头节点。 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:
PHP开发工程师
2022/08/09
2440
【面试高频题】可逐步优化的链表高频题
【面试高频题】可逐步优化的链表高频题
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random,该指针可以指向链表中的任何节点或空节点。
宫水三叶的刷题日记
2022/10/30
3470
【面试高频题】可逐步优化的链表高频题
【算法题解】 Day18 链表
假设链表为 1 → 2 → 3 → ∅,我们想要把它改成 ∅ ← 1 ← 2 ← 3。
sidiot
2023/08/31
1620
【算法题解】 Day18 链表
算法细节系列(31):链表
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/72902779
用户1147447
2019/05/26
4260
LeetCode 138:复制带随机指针的链表 Copy List with Random Pointer
给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。
爱写bug
2019/07/29
4030
剑指offer | 面试题28:复制链表的复制
题目描述 :请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
千羽
2021/12/29
2340
剑指offer | 面试题28:复制链表的复制
阿里巴巴的算法面试题JAVA,python,go,rust ,js,C++,Swift,Kotlin,Scala解法大全
算法思路相同,都是使用dummy节点和cur指针,两两交换链表节点,并返回dummy.next作为结果。
疯狂的KK
2023/05/16
1K0
阿里巴巴的算法面试题JAVA,python,go,rust ,js,C++,Swift,Kotlin,Scala解法大全
搞定大厂算法面试之leetcode精讲15.链表
搞定大厂算法面试之leetcode精讲15.链表 视频讲解(高效学习):点击学习 目录: 1.开篇介绍 2.时间空间复杂度 3.动态规划 4.贪心 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.单调栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其他类型题 链表操作如下图: 动画过大,点击查看 时间复杂度: prepend: O(1
全栈潇晨
2021/12/02
4570
链表常见操作总结及C++实现
给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字
evenleo
2020/08/21
5530
复制带随机指针的链表( LeetCode 138 )
请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
五分钟学算法
2021/12/21
6630
复制带随机指针的链表( LeetCode 138 )
【算法题解】 Day3 链表
给你一个字符串形式的电话号码 number。number 由数字、空格 ' '、和破折号 '-' 组成。
sidiot
2023/08/31
1740
【算法题解】 Day3 链表
面试必备 LeetCode 链表算法题汇总,全程干货!
搜集题目的难度是在简单级别和中级级别,也是面试常考的题目。题目的题解,使用的开发语言是Swift。
Wu_Candy
2022/07/04
3670
剑指Offer题解 - Day3
请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
chuckQu
2022/08/19
1520
【算法/学习】:搞懂链表题型,这一篇就够了
链表(Linked List) 是一种线性数据结构,由一系列节点组成。每个节点包含两个部分:
IsLand1314
2025/02/25
1220
【算法/学习】:搞懂链表题型,这一篇就够了
为什么链表算法题如此亲睐虚拟节点..........
相信大家在做算法题的时候,会经常用到虚拟节点这个技巧。但是却不明白它会给我们带来多大的便利,今天我们利用几道算法题来分析一下。
破晓的历程
2024/10/12
1100
☆打卡算法☆LeetCode 138. 复制带随机指针的链表 算法解析
“给定一个长度为n的链表,每个节点包含随机指针,随机指针可以指向链表中任何节点或空节点,构造这个链表的深拷贝,返回复制链表的头结点。”
恬静的小魔龙
2022/08/07
1860
☆打卡算法☆LeetCode 138. 复制带随机指针的链表  算法解析
2023年前端面试题汇总-数据结构(链表)
在计算机里,不保存在连续存储空间中,而每一个元素里都保存了到下一个元素的地址的数据结构,我们称之为链表(Linked List)。链表上的每一个元素又可以称它为节点(Node),而链表中第一个元素,称它为头节点(Head Node),最后一个元素称它为尾节点(Tail Node)。
越陌度阡
2023/06/10
1.2K0
2023年前端面试题汇总-数据结构(链表)
算法练习(9)-复杂带随机指针的单链表
除next外,还有一个随机指针random,随机指向链表中的某个元素(当然 :random也可能为null). 复制的难度在于, 新节点刚new出来时,其random指向的另外1个“新”节点,可能还没复制出来(即:首次无法确定新节点的random该指向谁,除非所有老节点全复制完)
菩提树下的杨过
2021/10/26
3370
【面试高频题】难度 1/5,经典树的搜索(多语言)
给定一个单链表的头节点 head,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。
宫水三叶的刷题日记
2023/10/20
3170
【面试高频题】难度 1/5,经典树的搜索(多语言)
听说用虚拟头节点会方便很多?
https://leetcode-cn.com/problems/remove-linked-list-elements/
代码随想录
2021/05/11
5400
听说用虚拟头节点会方便很多?
相关推荐
【面试高频题】可逐步优化的链表高频题
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档