美文网首页
面试题:使用Java打印 M*N 矩阵从左上角(0,0)到右下角

面试题:使用Java打印 M*N 矩阵从左上角(0,0)到右下角

作者: Bury丶冬天 | 来源:发表于2021-07-05 21:43 被阅读0次

注:每次只能向右或向下运动一格。
直接看代码:

package com.kaibo.share;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author kaibo
 * @date 2021/7/4 13:27
 * @GitHub:https://github.com/yuxuelian
 * @email:kaibo1hao@gmail.com
 * @description:
 */

public class PrintMatrixPathTest {

    static class MatrixNode {
        private final int xIndex;
        private final int yIndex;
        private final MatrixNode parent;
        private MatrixNode right;
        private MatrixNode bottom;

        public MatrixNode(int xIndex, int yIndex, MatrixNode parent) {
            this.xIndex = xIndex;
            this.yIndex = yIndex;
            this.parent = parent;
        }
    }

    private void printSinglePath(Stack<MatrixNode> tmpPathStack) {
        StringBuilder resPath = new StringBuilder();
        while (!tmpPathStack.isEmpty()) {
            MatrixNode matrixNode = tmpPathStack.pop();
            resPath.append("->(").append(matrixNode.xIndex).append(", ").append(matrixNode.yIndex).append(")");
        }
        System.out.println(resPath.toString());
    }

    private void printPath(MatrixNode rootNode) {
        if (rootNode.right != null) {
            printPath(rootNode.right);
        }
        if (rootNode.bottom != null) {
            printPath(rootNode.bottom);
        }

        if (rootNode.right == null && rootNode.bottom == null) {
            // 是最后一个结点,开始反向遍历父节点
            // 使用栈将路径变为正向流程
            Stack<MatrixNode> tmpPathStack = new Stack<>();
            MatrixNode whileTmp = rootNode;
            while (whileTmp != null) {
                tmpPathStack.push(whileTmp);
                whileTmp = whileTmp.parent;
            }
            // 将栈变成路径输出
            printSinglePath(tmpPathStack);
        }
    }

    /**
     * 创建路径二叉树
     *
     * @param M
     * @param N
     * @return
     */
    private MatrixNode createPathTree(int M, int N) {
        Queue<MatrixNode> matrixNodes = new LinkedList<>();
        MatrixNode rootNode = new MatrixNode(0, 0, null);
        matrixNodes.offer(rootNode);
        while (!matrixNodes.isEmpty()) {
            MatrixNode tmpParent = matrixNodes.poll();
            if (tmpParent.xIndex < M - 1) {
                MatrixNode right = new MatrixNode(tmpParent.xIndex + 1, tmpParent.yIndex, tmpParent);
                // 将自己赋值给父节点的 right 表示父节点能向右运动
                tmpParent.right = right;
                matrixNodes.offer(right);
            }

            if (tmpParent.yIndex < N - 1) {
                MatrixNode bottom = new MatrixNode(tmpParent.xIndex, tmpParent.yIndex + 1, tmpParent);
                // 将自己赋值给父节点的 bottom 表示父节点能向下运动
                tmpParent.bottom = bottom;
                matrixNodes.offer(bottom);
            }
        }
        return rootNode;
    }

    private void printMatrix(int M, int N) {
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print("(" + i + ", " + j + ") ");
            }
            System.out.println();
        }
    }

    @Test
    public void test() {
        int M = 2;
        int N = 2;

        System.out.println("---------------打印矩阵--------------");
        printMatrix(M, N);
        System.out.println("---------------输出路径--------------");

        // 创建路径树
        MatrixNode rootNode = createPathTree(M, N);
        // 输出路径
        printPath(rootNode);
    }

}

运行结果:
二阶矩阵:


image.png

三阶矩阵:


image.png
3*2阶矩阵:
image.png

相关文章

  • 面试题:使用Java打印 M*N 矩阵从左上角(0,0)到右下角

    注:每次只能向右或向下运动一格。直接看代码: 运行结果:二阶矩阵: 三阶矩阵: 3*2阶矩阵:

  • 蛇形矩阵

    java实现“之“字型矩阵 思路: 分为左上角、右下角、中间三部分,其中左上角和右下角和为N*N + 1,中间一部...

  • 机器人的运动范围

    《剑指offer》面试题13:矩阵中的路径 题目:地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动...

  • 1600 - Patrol Robot

    大致题意:机器人要从一个m*n(m和n的范围都在1到20的闭区间内)的网格的左上角(1,1)走到右下角(m,n)。...

  • B1050 螺旋矩阵 (25分)

    /*题意:1、给出N个数,按非递增序列组成螺旋矩阵,左上角第一个格子,顺时针,m*n = N,m>=n,而且m-n...

  • 算法 25 Minimum Path Sum

    题目:给出一个 m × n 的栅格,里面填着非负的数字。找到从左上角到右下角的最短(经过格子的数字之和最短)路径。...

  • 64. Minimum Path Sum

    题目 给定一个由非负数i填充的 m*n 网格,找到一条从左上角到右下角的路径,使得所有数字和最小。 解析 要求到 ...

  • codeforces-2B The least round wa

    题意:给定n*n的矩阵,矩阵左上角为起点,右下角为终点,选择一条路线,使得走过路线中乘积中的0最少。思路:避免质因...

  • 矩阵游戏(杨辉三角的应用)

    题意为:一个n✲n的矩阵,从左上角开始,只能向下或向右移动,求解到达右下角有几种运动方案。运动的过程假设可以把每停...

  • 100天代码挑战:DAY8

    LeetCode 64. 最小路径和 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,...

网友评论

      本文标题:面试题:使用Java打印 M*N 矩阵从左上角(0,0)到右下角

      本文链接:https://www.haomeiwen.com/subject/rcaiultx.html