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

相关文章

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

顺序表之创建,判满,插入,输出

文章目录 🍊自我介绍🍊创建一个空的顺序表,为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了,满了返回值1,否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~ 🍊自我介绍   Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾”

AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出

AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出 在数字化时代,文本到语音(Text-to-Speech, TTS)技术已成为人机交互的关键桥梁,无论是为视障人士提供辅助阅读,还是为智能助手注入声音的灵魂,TTS 技术都扮演着至关重要的角色。从最初的拼接式方法到参数化技术,再到现今的深度学习解决方案,TTS 技术经历了一段长足的进步。这篇文章将带您穿越时

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G,设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断,有两种做法:(本文的实现均基于邻接矩阵存储方式的图) 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历,遍历过程中遇到结点i就表示存在路径start->i,故只需判断每个结点i是否就是stop