Loading [MathJax]/jax/output/CommonHTML/config.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

n-1

);如果不指向任何节点,则为 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 删除。

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
管脚约束问题导致生成bit时报错 如何在不重新Implentation情况下生成bit?
  像上面这个图中,由于在约束中忘记指定mdc和mdio的电平,再经过了长时间的综合和实现后,最后的Generate Bitstream报错了。
猫叔Rex
2021/11/25
4330
管脚约束问题导致生成bit时报错 如何在不重新Implentation情况下生成bit?
FPGA时序约束理论篇之IO约束
  管脚约束就是指管脚分配,我们要指定管脚的PACKAGE_PIN和IOSTANDARD两个属性的值,前者指定了管脚的位置,后者指定了管脚对应的电平标准。
猫叔Rex
2020/06/30
2.1K0
FPGA时序约束理论篇之IO约束
蜂鸟E203系列——FPGA硬件环境
make执行GUI 加载编译加入源文件综合出错实现出错生成bitstream出错烧录 flash
瓜大三哥
2020/07/09
1.7K0
Vivado2015.4使用教程(一个完成工程的建立)
NingHeChuan
2018/01/05
9440
Vivado2015.4使用教程(一个完成工程的建立)
多平台FPGA工程快速移植与构建
作为一名FPGA工程师,经常需要在多个FPGA设备之间移植项目,核心的问题是IP的管理和移植,今天通过安装和使用 FuseSoC 在多个 AMD FPGA 之间移植一个简单的项目。从 AMD Spartan™ 7 更改为 AMD Artix™ 7 设备,然后是 AMD Kintex™ UltraSacle™。
FPGA技术江湖
2024/12/11
1470
多平台FPGA工程快速移植与构建
Vivado初体验LED工程
本节我们要做的是熟练使用 Vivado 创建工程并实现对 LED 灯控制,每秒钟控制开发板上的 LED 灯翻转一次,实现亮、灭、亮、灭的控制。会控制 LED 灯,其它外设也慢慢就会了。
Gnep@97
2023/09/19
8860
Vivado初体验LED工程
FPGA片内ROM读写测试实验
FPGA 本身是 SRAM 架构的,断电之后程序就会消失,那么如何利用 FPGA 实现一个 ROM 呢,我们可以利用 FPGA 内部的 RAM 资源实现 ROM,但这不是真正意义上的 ROM,而是每次上电都会把初始化的值先写入 RAM。Vivado 软件中提供了 ROM 的 IP 核 , 我们只需通过 IP 核例化一个 ROM,根据 ROM 的读时序来读取 ROM 中存储的数据。本节将介绍如何使用 FPGA 内部的 ROM 以及程序对该 ROM 的数据读操作。该实验与 FPGA 片内 RAM 读写测试实验操作类似,可以参考一下。
Gnep@97
2023/10/02
9250
FPGA片内ROM读写测试实验
PYNQ上手笔记 | ⑥HDL设计IP核
然后在文件最后,找到Add user logic here,然后在其后添加逻辑功能代码:
Mculover666
2020/07/15
1K0
ZC706评估板IBERT误码率测试和眼图扫描【GT高速串行收发器】【IBERT】【FPGA】【眼图】【FPGA探索者】
IBERT(Integrated Bit ErrorRatio Tester,集成误比特率测试工具),是Xilinx提供用于调试FPGA高速串行接口比特误码率性能的工具,最常用在GT高速串行收发器测试:
FPGA探索者
2021/03/15
4.9K0
FPGA片内RAM读写测试实验
本节讲述一下 FPGA 片内 RAM 的仿真与测试,我们也知道 RAM 是随机存储器,顾名思义是一种存储数据的一种模块,说到随机呢,也就是我们可以任意的访问它里面的一些地址空间里面的数据。
Gnep@97
2023/09/24
1.2K0
FPGA片内RAM读写测试实验
强大的JTAG边界扫描1-基本原理
听卖家介绍说,这是之前挖矿盛行时,定制矿机中的一块HASH算力卡,主要功能是通过串口接收数据,FPGA计算出HASH值,再通过串口输出,由于工作频率较高,还外加了散热器,后来由于矿难,就把矿机中的板卡都处理掉了,遗憾的是没有留下任何软硬件资料。
单片机点灯小能手
2023/09/18
9120
强大的JTAG边界扫描1-基本原理
【分享】升级Vivado工程脚本
Vivado可以导出脚本,保存创建工程的相关命令和配置,并可以在需要的时候使用脚本重建Vivado工程。脚本通常只有KB级别大小,远远小于工程打包文件的大小,因此便于备份和版本管理。 脚本里指定了Vivado的版本、器件的型号,IP的版本。如果导出脚本时的相关版本,和恢复工程时的相关版本不一样,会导致创建工程失败。可以通过手工检查和修改相关版本信息,升级Vivado工程脚本,使新的Vivado也能恢复出对应的工程。 目前我电脑中只有Vivado 2020.2。但是得到了一份Vivado 2020.1为开发板vck190 es的创建的工程脚本。下面以把前述脚本升级到Vivado 2020.2为例,讨论如何升级Vivado工程脚本。
hankfu
2021/03/03
2.2K0
平头哥开源项目wujian100_open | 基于synplify+vivado生成bitfile
Use the sdc2fdc Tcl shell command to convert the timing constraints.
数字芯片社区
2022/04/06
2.1K0
平头哥开源项目wujian100_open | 基于synplify+vivado生成bitfile
Vivado下PLL实验
本节介绍一下赛灵思锁相环的一个使用方法,我手头的 AC7020 fpga 开发板上面有一个 50MHz 的晶振连接在 PL 端,晶振输出链接到 FPGA 的全局时钟(MRCC),这个 CLK 可以用来驱动 FPGA 内的用户逻辑电路,该时钟源的原理图如图所示:
Gnep@97
2023/09/21
7370
Vivado下PLL实验
Vivado Tcl 脚本编译工程
工具命令语言(Tcl--Tool Command Language)是Vivado®工具环境中集成的脚本语言。Tcl是半导体行业中用于应用程序编程接口的标准语言,并由Synopsys®设计约束(SDC)使用。
FPGA开源工作室
2020/02/14
2.5K0
Vivado Tcl 脚本编译工程
利用 IBERT 进行 GTX 信号眼图测试
Vivado中提供了1种IBERT工具用于对Xilinx FPGA芯片的高速串行收发器进行板级硬件测试。通过IBERT我们可以获取误码率,观察眼图,调节串行收发器的参数,从而有助于判断可能存在的问题,便于验证硬件的稳定性和信号完整性。
碎碎思
2020/06/30
6.8K3
单周期CPU
1、理解 MIPS 常用的指令系统并掌握单周期 CPU 的工作原理与逻辑功能实现。
ttony0
2022/12/26
2.5K0
单周期CPU
时序分析笔记系列(五)、IO约束与时钟约束
管脚约束就是指管脚分配,指定管脚的PACKAKE_PIN(管脚位置)和PACKAGE_IOSTARD(电平标准)两个属性的值。
根究FPGA
2020/06/29
2.7K0
Vivado Non-Project模式
read_verilog [ glob ./sources_1/imports/new/*.v ]
瓜大三哥
2018/07/30
1.7K0
Vivado Non-Project模式
wujian100——FPGA综合实现
最后就可以生成 bit 流文件。而且小编还看到 Slack 恰好为 0 ,的确是 ”绝了“。
瓜大三哥
2020/11/10
2.1K1
wujian100——FPGA综合实现
推荐阅读
相关推荐
管脚约束问题导致生成bit时报错 如何在不重新Implentation情况下生成bit?
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验