n*n矩阵，输出矩阵中任意两点之间所有路径

题目1：给你一个正整数n， 构造一个n*n的四项链表矩阵。

要求： 1.使用四项链表

            2.矩阵从左到右，从上到下值依次为1,2,3,4,......n*n

题目2：基于题目1， 在n*n链表矩阵中，输出矩阵中任意两点之间所有路径。

要求： 1.不能使用全局变量

            2.方法只接收两个参数，分别为起始节点

            3.不能重复遍历

构造一个n*n的四项链表矩阵

思路： 要构建一个n*n的矩阵，有这个一个简单思路：

  1. 初始化i=0
  2. 先构建第i行，第i列链表
  3. 再构建(n-1)*(n-1)矩阵
  4. 将第二步链表与第三步矩阵连接起来
  5. i=i+1
  6. 重复第二步

/*** @param k 当前要构造K*K矩阵* @param n* @return*/
public Node<E> build(int k, int n) {if (k <= 0) {return null;}Node<E> head = new Node();// 右侧Node<E> r = head;int i = k - 1;while (i > 0) {Node<E> right = new Node();r.right = right;right.left = r;r = right;i--;}// 下面i = k - 1;Node<E> d = head;while (i > 0) {Node<E> down = new Node();d.down = down;down.up = d;d = down;i--;}// n-1矩阵  subHead n-1矩阵头节点Node<E> subHead = build(k - 1, n);// 先连接顶部Node<E> h = head.right;Node<E> subH = subHead;while (null != h) {h.down = subH;subH.up = h;h = h.right;subH = subH.right;}// 再连接左侧Node<E> down = head.down;Node<E> subDown = subHead;while (null != down) {down.right = subDown;subDown.left = down;down = down.down;subDown = subDown.down;}return head;
}

 输出矩阵中任意两点之间所有路径

思路： 深度优先搜索(DFS) + 回溯

  1. 如果起始节点相等，直接输出，结束
  2. 起两个栈， 一个主栈，一个副栈
    1. 主栈：存放线路上的节点，用于符合条件时直接输出
    2. 副栈：存放主栈节点的邻接节点集合，需考虑边界与重复遍历问题
  3. 起始节点入主栈，起始节点的邻接节点入副站
  4. 副栈弹出节点集合
    1. 弹出集合中第一个节点node(集合长度-1)
    2. 集合重新入副栈
  5. 如果node=null, 主栈、副栈执行pop()操作，表示需要回溯到上一步(可以理解为，当前无路可走，需要从上一个节点试图走其他方向), 跳转并重复第4步
  6. 如果node!=null, 将node节点压入主栈
  7. 此时如果node==终止节点，则输出主站所有节点，弹出主栈节点(此时==终止节点)，跳转并重复第4步
  8. 将node邻接节点压入副栈

如下图5 * 5矩阵， 起始节点7 ，终止节点19

第一次                                                                       

第二次 

第三次

第四次                                     

第五次                                   

第六次

 第**次

  • 此时主栈栈顶元素为19，等于终止节点，则输出主占所有节点值
  • 弹出主栈栈顶节点19，从新取副栈栈顶节点
  • 当前主栈栈顶为18，试图从18开始再向其他方向寻找
  • 18邻接节点取出13，压住主栈

这样，不断压入弹出最终可遍历出所有路线

核心代码

public void search(Node<E> startNode, Node<E> endNode) {if (startNode == endNode) {System.out.println(startNode.v + " ");return;}// 主栈Stack<Node<E>> stack = new Stack<>();// 副栈Stack<Queue<Node<E>>> adjoinStack = new Stack<>();// 将开始节点入主栈stack.push(startNode);// 将起始节点邻接节点集合如副栈this.pushAdjoinStack(stack, startNode, adjoinStack);while (!stack.empty()) {Queue<Node<E>> queue = adjoinStack.pop();Node<E> node = queue.poll();adjoinStack.push(queue);// 如果到无路可走if (null == node) {adjoinStack.pop();stack.pop();continue;}stack.push(node);// 找到一个路径if (node == endNode) {this.printResult(stack);// 弹出主栈栈顶元素stack.pop();continue;}pushAdjoinStack(stack, node, adjoinStack);}
}/*** 将node节点的邻接几点入副站* 1. 边界问题* 2. 避免重复入副站** @param stack* @param node* @param adjoinStack*/
public void pushAdjoinStack(Stack<Node<E>> stack, Node<E> node, Stack<Queue<Node<E>>> adjoinStack) {Queue<Node<E>> nodeList = new LinkedList<>();if (node.up != null && !stack.contains(node.up)) {nodeList.offer(node.up);}if (node.down != null && !stack.contains(node.down)) {nodeList.offer(node.down);}if (node.left != null && !stack.contains(node.left)) {nodeList.offer(node.left);}if (node.right != null && !stack.contains(node.right)) {nodeList.offer(node.right);}adjoinStack.push(nodeList);
}

完整代码：

/*** 节点类** @author ywl* @version 1.0* @date 2024/8/21 20:01*/public class Node<E> {E v;Node<E> up;Node<E> down;Node<E> left;Node<E> right;// 省略 getter setter
}

import java.util.*;/*** 题目1：给你一个正整数n， 构造一个n*n的四项链表矩阵。* 题目2：基于题目1， 在n*n链表矩阵中，输出矩阵中任意两点之间所有路径。** @author ywl* @version 1.0* @date 2024/8/21 20:01*/
public class StLink<E> {public Node<E> build(int k, int n) {if (k <= 0) {return null;}Node<E> head = new Node();// 右侧Node<E> r = head;int i = k - 1;while (i > 0) {Node<E> right = new Node();r.right = right;right.left = r;r = right;i--;}// 下面i = k - 1;Node<E> d = head;while (i > 0) {Node<E> down = new Node();d.down = down;down.up = d;d = down;i--;}// n-1矩阵  subHead n-1矩阵头节点Node<E> subHead = build(k - 1, n);// 先连接顶部Node<E> h = head.right;Node<E> subH = subHead;while (null != h) {h.down = subH;subH.up = h;h = h.right;subH = subH.right;}// 再连接左侧Node<E> down = head.down;Node<E> subDown = subHead;while (null != down) {down.right = subDown;subDown.left = down;down = down.down;subDown = subDown.down;}return head;}public static void main(String[] args) {int n = 4;StLink<Integer> sl = new StLink<>();Node<Integer> head = sl.build(n, n);// 循环赋值Node<Integer> down = head;int c = 1;while (null != down) {Node<Integer> right = down;while (null != right) {right.setV(c++);right = right.right;}down = down.down;}/*** 1  2  3  4* 5  6  7  8* 9  10 11 12* 13 14 15 16*/sl.search(head.right, head.right.right.down.down);}public void search(Node<E> startNode, Node<E> endNode) {if (startNode == endNode) {System.out.println(startNode.v + " ");return;}// 主栈Stack<Node<E>> stack = new Stack<>();// 副栈Stack<Queue<Node<E>>> adjoinStack = new Stack<>();// 将开始节点入主栈stack.push(startNode);// 将起始节点邻接节点集合如副栈this.pushAdjoinStack(stack, startNode, adjoinStack);int maxLen = Integer.MAX_VALUE;List<List<E>> result = new ArrayList<>();while (!stack.empty()) {Queue<Node<E>> queue = adjoinStack.pop();Node<E> node = queue.poll();adjoinStack.push(queue);// 如果无路可走if (null == node) {adjoinStack.pop();stack.pop();continue;}stack.push(node);// 找到一个路径if (node == endNode) {List<E> es = this.printResult(stack);if(es.size() == maxLen) {result.add(es);} else if(es.size() < maxLen) {maxLen = es.size();result = new ArrayList<>();result.add(es);}// 弹出主栈栈顶元素stack.pop();continue;}pushAdjoinStack(stack, node, adjoinStack);}System.out.println("最小路径:");for(List<E> r : result) {for(int i = 0; i < r.size(); i++) {System.out.print(r.get(i)+" ");}System.out.println();}}/*** 将node节点的邻接几点入副站* 1. 边界问题* 2. 避免重复入副站** @param stack* @param node* @param adjoinStack*/public void pushAdjoinStack(Stack<Node<E>> stack, Node<E> node, Stack<Queue<Node<E>>> adjoinStack) {Queue<Node<E>> nodeList = new LinkedList<>();if (node.up != null && !stack.contains(node.up)) {nodeList.offer(node.up);}if (node.down != null && !stack.contains(node.down)) {nodeList.offer(node.down);}if (node.left != null && !stack.contains(node.left)) {nodeList.offer(node.left);}if (node.right != null && !stack.contains(node.right)) {nodeList.offer(node.right);}adjoinStack.push(nodeList);}private List<E> printResult(Stack<Node<E>> stack) {List<E> r = new ArrayList<>();Iterator<Node<E>> iterator = stack.iterator();while (iterator.hasNext()) {Node<E> next = iterator.next();r.add(next.v);System.out.print(next.v + " ");}System.out.println();return r;}}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/415801.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

VK11之BADI增强SD_COND_SAVE_A

VK11之BADI增强SD_COND_SAVE_A

T-code se19 例如ZSD_COND_SAVE_A 若不知道增强位置&#xff0c;可以再CLASS CL_EXITHANDLER 的方法GET_INSTANCE设置外部断点&#xff0c;来查看Exit的位置。 此需求是当用户用VK11新增时&#xff0c;检查不能出现在process的值来进行错误反馈 UPDKZ ‘I’ 指新增 METHOD …
阅读更多...
《黑神话：悟空》与游戏经济学的深度剖析

《黑神话：悟空》与游戏经济学的深度剖析

《黑神话&#xff1a;悟空》作为近年来备受瞩目的国产3A游戏大作&#xff0c;自其发布以来&#xff0c;不仅在游戏界内引起了轰动&#xff0c;更在多个消费领域产生了深远的影响。这款游戏不仅以其卓越的品质和深刻的文化内涵吸引了大量玩家的关注&#xff0c;还通过一系列连锁…
阅读更多...
7-8月月报 | Apache SeaTunnel社区进展一览

7-8月月报 | Apache SeaTunnel社区进展一览

各位热爱 Apache SeaTunnel 的小伙伴们&#xff0c;社区 7-8 月份月报来啦&#xff01;这两个月项目有了哪些进展&#xff1f;又有谁登上了我们社区的贡献者榜单呢&#xff1f;快来一睹为快吧。 Merge Stars 感谢以下小伙伴上两个月为 Apache SeaTunnel 项目和社区发展所做的…
阅读更多...
在window环境下编译和安装DeepSpeed

在window环境下编译和安装DeepSpeed

DeepSpeed 是一个由 Microsoft 开发的深度学习优化库&#xff0c;旨在提高大规模深度学习模型的训练速度和效率。本文将介绍如何下载、安装和使用 DeepSpeed。 环境准备 需要安装 Git 以便从 GitHub 下载 DeepSpeed 源代码。可以从 Git 官方网站 下载并安装最新版本的 Git。 …
阅读更多...
毕业设计选题系统

毕业设计选题系统

一、项目概述 Hi&#xff0c;大家好&#xff0c;今天分享的项目是《毕业设计选题系统》。 毕业论文选题是大学教学管理中的重要环节&#xff0c;关系到高校的教学质量。传统的手工管理方式工作效率低下、管理繁琐&#xff0c;浪费教师和学生的时间与精力的问题。本系统以提高…
阅读更多...
c++内存管理和模板

c++内存管理和模板

C语言malloc calloc和realloc的弊端 C语言的这三个函数对于内置类型的处理是还可以的&#xff0c;但是对自定义类型就无法处理了&#xff0c;因为c自定义类型在初始化的时候是自动调用构造函数的&#xff0c;而C语言的这三个函数是无法初始化内置类型的&#xff0c;于是我们下…
阅读更多...
JetBrains`s IntelliJ IDEA springboot项目 gradle-bin安装 国内加速

JetBrains`s IntelliJ IDEA springboot项目 gradle-bin安装 国内加速

gradle wapper加速 可以看到&#xff0c;一般我们直接init的springboot项目会默认使用wapper来安装不同版本的gradle&#xff0c;但services.gradle.org网速过慢&#xff0c;我们选择切换为国内源 发现一篇同样的文档,并在此补充多个源 源名urlgradle(原本)https\://service…
阅读更多...
网站如何针对不同的DDOS进行防御？

网站如何针对不同的DDOS进行防御？

建设网站租用服务器是多数企业及个人的选择&#xff0c;一个安全稳定的服务器对网站的重要性无需再赘述。要保证服务器租用的安全和稳定&#xff0c;除了需要服务器自身有强大的硬、软件基础之外&#xff0c;还需要防范外部的一些因素&#xff0c;常见的就是各种网络攻击&#…
阅读更多...
接口测试 —— 如何设计高效的测试用例！

接口测试 —— 如何设计高效的测试用例！

摘要&#xff1a; 随着互联网应用的日益复杂化&#xff0c;接口测试已成为保证软件质量不可或缺的一部分。本文将探讨如何有效地设计接口测试用例&#xff0c;并提供实用的建议和示例。 一、引言 接口测试&#xff08;API测试&#xff09;是确保系统各部分之间交互正确性的关键…
阅读更多...
信息安全--（四）网络安全体系与安全模型（二）

信息安全--（四）网络安全体系与安全模型（二）

其他安全模型 ■纵深防御模型&#xff1a;①安全保护②安全监测③实时响应④恢复 ■分层防护模型&#xff1a;参考OSI模型&#xff0c;对保护对象进行层次化保护。 ■等级保护模型&#xff1a;将信息系统划分成不同安全保护等级&#xff0c;采取相 应的保护措施。 ■网络生…
阅读更多...
【MySQL-24】万字全面解析＜索引＞——【介绍＆语法＆性能分析＆使用规则】

【MySQL-24】万字全面解析＜索引＞——【介绍＆语法＆性能分析＆使用规则】

前言 大家好吖&#xff0c;欢迎来到 YY 滴MySQL系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过C的老铁 主要内容含&#xff1a; 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; YY的《C》专栏YY的《C11》专栏YY的《Lin…
阅读更多...
视频智能分析打手机检测算法安防监控打手机检测算法应用场景、算法源码、算法模型介绍

视频智能分析打手机检测算法安防监控打手机检测算法应用场景、算法源码、算法模型介绍

随着智能手机的普及&#xff0c;手机已成为人们生活中不可或缺的一部分。然而&#xff0c;在某些场合&#xff0c;如驾驶、会议、学校课堂等&#xff0c;不当使用手机可能会导致安全隐患或干扰他人。因此&#xff0c;开发出一种能够准确识别并阻止不当使用手机的行为检测算法显…
阅读更多...
网吧业务安全对抗(有源码)

网吧业务安全对抗(有源码)

网吧业务竞争激烈&#xff0c;网吧都会有以下系统软件。 无盘: 无盘是指没有硬盘。好处是统一维护管理和节约成本。本人研究无盘好几年&#xff0c;后面会专门发帖介绍。 计费: 是指收费系统。 营销软件: 包括销售饮品、‌零食和向客户发送电子邮件营销和短信营销等。产品如…
阅读更多...
springboot，maven多模块开发，子模块获取不到父模块添加的依赖，有多个root模块问题解决

springboot，maven多模块开发，子模块获取不到父模块添加的依赖，有多个root模块问题解决

错误示范 我以为放进去然后重载一下就是子模块了 导致后续在外层加的依赖&#xff0c;其article都接收不到 解决方案 需要在父模块的modules注册子模块 修改前后对比 此时子模块也能获取父模块的依赖
阅读更多...
在Ubuntu/Linux下重温FC游戏——超级玛丽奥

在Ubuntu/Linux下重温FC游戏——超级玛丽奥

文章目录 在Ubuntu/Linux下重温FC游戏——超级玛丽奥1 概述2 安装 FCEUX 模拟器3 下载 FC ROMS4 重温时光 在Ubuntu/Linux下重温FC游戏——超级玛丽奥 1 概述 FC 游戏机&#xff0c;是任天堂生产、发行和销售的 8 位第三世代家用游戏机&#xff0c;日本版官方名称为家庭电脑&…
阅读更多...
Java源码学习之高并发编程基础——AQS源码剖析之线程间通信之条件等待队列

Java源码学习之高并发编程基础——AQS源码剖析之线程间通信之条件等待队列

1.前言&目录 前言&#xff1a; 在Java中&#xff0c;使用synchronized关键字构建的锁&#xff0c;线程间通信可以使用某对象实例的wait/notify机制完成。AQS同样也提供了一套线程间通信的解决方案——条件等待队列。 在AQS源码分析的两篇文章AQS源码分析&#xff08;上&am…
阅读更多...
逻辑器件输出高阻态时，输出端口的电平是什么状态呢？

逻辑器件输出高阻态时，输出端口的电平是什么状态呢？

高阻态是逻辑器件输出端口的一种状态&#xff0c;当端口处于高阻态时&#xff0c;输入端口的电平变化不会引起输出端口变化&#xff0c;不会对与之相连的后级输入端口或总线产生影响&#xff0c;对于总线架构的电路极为重要。   输出端口处于高阻态时&#xff0c;输出端口处于…
阅读更多...
优秀软件工程师的工作思维

优秀软件工程师的工作思维

引言 在快速迭代的软件开发领域&#xff0c;软件工程师不仅需要精通编程技术&#xff0c;还需要具备产品思维、技术思维和工程思维&#xff0c;这三种思维相辅相成&#xff0c;共同推动产品的成功。本文将借鉴陈春花等管理学者的思考方式&#xff0c;深入剖析软件工程师如何在…
阅读更多...
数据恢复工具，电脑+手机双端，十分好用！

数据恢复工具，电脑+手机双端，十分好用！

哈喽&#xff0c;各位小伙伴们好&#xff0c;我是给大家带来各类黑科技与前沿资讯的小武。 今天给大家安利两款数据恢复工具&#xff0c;分别为电脑手机双端&#xff0c;无论是因为格式化误操作、设备损坏还是其他意外情况&#xff0c;都能轻松找回重要的文件、照片、视频等数…
阅读更多...
什么是串口服务器？

什么是串口服务器？

1.什么是串口服务器&#xff1f; 了解串口服务器之前&#xff0c;我们需要先了解什么串口。 串口&#xff1a;又叫串行数据接口&#xff0c;主要是用来表示传递各种的数据的通信接口&#xff0c;通常指COM口。一般分为RS232、RS422、与RS485三种。RS232接口&#xff1a;采用全…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023