当前位置: 首页 > news >正文

厦门网站建设外包/企业seo服务

厦门网站建设外包,企业seo服务,东莞做网站公司哪家比较好,辛巴否认电商干垮实体目录1、题目描述:2、方法一:迭代哈希表思路:代码:3、方法二:后继节点思路:代码:4、总结1、题目描述: 2、方法一:迭代哈希表 思路: 我们先看看暴力法怎么做的…

目录

  • 1、题目描述:
  • 2、方法一:迭代+哈希表
    • 思路:
    • 代码:
  • 3、方法二:后继节点
    • 思路:
    • 代码:
  • 4、总结

1、题目描述:

在这里插入图片描述
在这里插入图片描述

2、方法一:迭代+哈希表

思路:

我们先看看暴力法怎么做的:

看到这道题之后,很多人的第一反应是把复制分成两步:第一步是复制原始链表上的每一个节点,并用nextnextnext给链接起来;第二步是设置每个节点的randomrandomrandom指针。

第二步的具体做法如下:假设原始链表中的某个节点NNNrandomrandomrandom指针指向节点SSS,由于SSS在链表中可能在NNN的前面也可能在NNN的后面,所以要定位SSS的位置需要从原始链表的头节点开始找。如果从原始链表的头节点开始沿着nextnextnext经过sss步找到节点SSS,那么在复制链表上节点的N′N'Nrandomrandomrandom(记为S′S'S)离复制链表的头节点的距离也是沿着nextnextnext指针sss步。用这种办法就可以为复制链表上的每个节点设置randomrandomrandom指针。

对于一个含有nnn个节点的链表,由于定位每个节点的randomrandomrandom都需要从链表头节点开始经过O(n)O(n)O(n)步才能找到,因此这种方法总的时间复杂度是O(n2)O(n^2)O(n2)

我们看看迭代+哈希表咋做的:

上述方法的时间主要花费在定位节点randomrandomrandom上,这个是可以改进的,也就是说,我们可以事先把创建出来的节点N′N'N与原始的NNN节点保存在哈希表中,即<N:N′><N:N'><N:N>。如果在原始链表中节点NNNrandomrandomrandom指向节点SSS,那么在复制链表中,对应的N′N'N应该指向S′S'S,由于有了哈希表,我们可以用O(1)O(1)O(1)的时间根据SSS找到S′S'S

代码在具体实现的时候,先遍历原始链表,创建字典对<N:N′><N:N'><N:N>;然后再遍历一遍原始链表,用于给新链表设置nextnextnextrandomrandomrandom指针。

代码:

"""
# Definition for a Node.
class Node:def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):self.val = int(x)self.next = nextself.random = random
"""
class Solution:def copyRandomList(self, head: 'Node') -> 'Node':"""迭代+哈希表"""if head == None: return headnode_map = {}cur = head# 1.存储新旧节点对while cur:node_map[cur] = Node(cur.val) # 创建字典对,原始节点一定为keycur = cur.next# 2.给新链表设置next和random指针cur = headwhile cur:if cur.next: # 防止字典key为Nonenode_map[cur].next = node_map[cur.next] # 设置nextif cur.random: # 同上node_map[cur].random = node_map[cur.random] # 设置randomcur = cur.nextreturn node_map[head] # 返回新链表的头节点

3、方法二:后继节点

思路:

注意到方法一需要使用哈希表记录每一个节点对应新节点的创建情况,而我们可以使用一个小技巧来省去哈希表的空间。
我们首先将该链表中每一个节点拆分为两个相连的节点,例如对于链表:A→B→CA→B→CABC我们可以将其拆分为: A→A′→B→B′→C→C′A→A′→B→B′→C→C′AABBCC
对于任意一个原节点 SSS,其拷贝节点 S′S'S 即为其后继节点

这样,我们可以直接找到每一个拷贝节点 S′S'S的随机指针应当指向的节点,即为其原节点 SSS 的随机指针指向的节点 TTT 的后继节点 T′T'T
需要注意原节点的随机指针可能为空,我们需要特别判断这种情况。

当我们完成了拷贝节点的随机指针的赋值,我们只需要将这个链表按照原节点与拷贝节点的种类进行拆分即可,只需要遍历一次。同样需要注意最后一个拷贝节点的后继节点为空,我们需要特别判断这种情况。

代码:

"""
# Definition for a Node.
class Node:def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):self.val = int(x)self.next = nextself.random = random
"""
class Solution:def copyRandomList(self, head: 'Node') -> 'Node':"""后继节点"""if head == None: return head# 1.先把链表A->B->C转换成A->A'->B->B'->C->C'cur = headwhile cur:next = cur.next # 存储Bnew_node = Node(cur.val) # 定义A'cur.next = new_node # A->A'new_node.next = next # A'->Bcur = next # 指针指向B# 2.给每一个新节点设置random指针cur = headwhile cur:if cur.random:cur.next.random = cur.random.next # 下一个新节点的random,就是原节点random的下一个cur = cur.next.next# 3.将A->A'->B->B'->C->C'拆分开cur = head.next # 从A'开始遍历head2 = cur # 把新链表的头给保存,用于返回while cur.next: # 注意这个cur.next,一旦这个存在,则一定存在cur.next.next,看链表就知道为啥cur.next = cur.next.next # A'->B'cur = cur.next # 当前遍历的节点指向B'return head2

4、总结

做链表的题,建议画一个链表的例子,然后看指针指向,例如上面的例子:A→A′→B→B′→C→C′A→A′→B→B′→C→C′AABBCC看着这个敲代码,就不会把自己绕进去了。

http://www.jmfq.cn/news/4766887.html

相关文章:

  • 新疆生产建设兵团体育局网站/谷歌 google
  • wordpress主题自定义打不开/seo西安
  • 湖州 网站建设/在线注册网站
  • 医院做网站的意义/上海百度推广排名
  • 兰州企业建设网站/seo软件视频教程
  • 上海做网站品牌公司有哪些/网络推广网站排名
  • 跳转网站代码/深圳居家办公
  • 苏州市智信建设职业培训学校网站/怎样在百度上免费建网站
  • 台州做网站seo/百度一下网页版浏览器百度
  • 建设seo网站/2023年中国进入一级战备状态了吗
  • 汉口做网站jw100/提升seo排名平台
  • 淄博专业网站设计/seo草根博客
  • 做健身网站开题报告/怎样做网络推广营销
  • 江苏建设主管部门网站/品牌形象推广
  • 阿里云域名空间网站建设/公司如何建立网站
  • 外包加工网站/南宁seo推广公司
  • 制作网页与网站/搜索引擎在线
  • 佛山新网站建设服务/seo整站优化外包公司
  • WordPress主题在线生成/长沙seo管理
  • 网站怎么做排查修复/域名注册服务机构
  • 如何做好网站的优化/推广下载
  • 厦门网站建设 首选猴子网络/关键词排名批量查询软件
  • 惠州网站建设推广/现在百度怎么优化排名
  • 老师做家教的网站/潍坊关键词优化软件
  • 网站如何发布和推广/沧州百度推广总代理
  • 建筑/威海seo
  • 垂直电商网站如何做内容运营/佛山本地网站建设
  • 公司网站规划/seo云优化方法
  • 免费网站模板源码下载/数字营销是干啥的
  • 宝安区住房和建设局官方网站/数字化营销