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

2024-08-28 17:04
文章标签 输出 路径 所有 矩阵 之间 任意 两点

本文主要是介绍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;}}

这篇关于n*n矩阵，输出矩阵中任意两点之间所有路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1115358。

相关文章

Python pip下载包及所有依赖到指定文件夹的步骤说明

Python pip下载包及所有依赖到指定文件夹的步骤说明

《Pythonpip下载包及所有依赖到指定文件夹的步骤说明》为了方便开发和部署,我们常常需要将Python项目所依赖的第三方包导出到本地文件夹中,：本文主要介绍Pythonpip下载包及所有依... 目录步骤说明命令格式示例参数说明离线安装方法注意事项总结要使用pip下载包及其所有依赖到指定文件夹，请按照以
阅读更多...
SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

《SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志》在SpringBoot项目中,使用logback-spring.xml配置屏蔽特定路径的日志有两种常用方式,文中的... 目录方案一：基础配置（直接关闭目标路径日志）方案二：结合 Spring Profile 按环境屏蔽关
阅读更多...
java Long 与long之间的转换流程

java Long 与long之间的转换流程

《javaLong与long之间的转换流程》Long类提供了一些方法,用于在long和其他数据类型（如String）之间进行转换,本文将详细介绍如何在Java中实现Long和long之间的转换,感... 目录概述流程步骤1：将long转换为Long对象步骤2：将Longhttp://www.cppcns.c
阅读更多...
VSCode设置python SDK路径的实现步骤

VSCode设置python SDK路径的实现步骤

《VSCode设置pythonSDK路径的实现步骤》本文主要介绍了VSCode设置pythonSDK路径的实现步骤,包括命令面板切换、settings.json配置、环境变量及虚拟环境处理,具有一定... 目录一、通过命令面板快速切换（推荐方法）二、通过 settings.json 配置（项目级/全局）三、
阅读更多...
使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

《使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)》字体设计和矢量图形处理是编程中一个有趣且实用的领域,通过Python的matplotlib库,我们可以轻松将字体轮廓... 目录背景知识字体轮廓的表示实现步骤1. 安装依赖库2. 准备数据3. 解析路径指令4. 绘制图形关键
阅读更多...
C/C++中OpenCV 矩阵运算的实现

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算（标量与矩阵）、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元
阅读更多...
如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)

如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)

《如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)》：本文主要介绍如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)问题,具有很好的参考价值,希望对大家有所帮助,如有... 目录先在你打算存放的地方建四个文件夹更改这四个路径就可以修改默认虚拟内存分页js文件的位置接下来从高级-
阅读更多...
使用Java将实体类转换为JSON并输出到控制台的完整过程

使用Java将实体类转换为JSON并输出到控制台的完整过程

《使用Java将实体类转换为JSON并输出到控制台的完整过程》在软件开发的过程中,Java是一种广泛使用的编程语言,而在众多应用中,数据的传输和存储经常需要使用JSON格式,用Java将实体类转换为J... 在软件开发的过程中，Java是一种广泛使用的编程语言，而在众多应用中，数据的传输和存储经常需要使用j
阅读更多...
一文详解如何查看本地MySQL的安装路径

一文详解如何查看本地MySQL的安装路径

《一文详解如何查看本地MySQL的安装路径》本地安装MySQL对于初学者或者开发人员来说是一项基础技能,但在安装过程中可能会遇到各种问题,：本文主要介绍如何查看本地MySQL安装路径的相关资料,需... 目录1. 如何查看本地mysql的安装路径1.1. 方法1：通过查询本地服务1.2. 方法2：通过MyS
阅读更多...
Python如何调用指定路径的模块

Python如何调用指定路径的模块

《Python如何调用指定路径的模块》要在Python中调用指定路径的模块,可以使用sys.path.append,importlib.util.spec_from_file_location和exe... 目录一、sys.path.append() 方法1. 方法简介2. 使用示例3. 注意事项二、imp
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2