【牛客网】迷宫问题与年终奖

一、编程题

1.迷宫问题

2.年终奖

二、选择题

1、将N条长度均为M的有序链表进行合并，合并以后的链表也保持有序，时间复杂度为()?

2、大小为MAX的循环队列中，f为当前对头元素位置，r为当前队尾元素位置(最后一个元素的位置)，则任意时刻，队列中的元素个数为

一、编程题

1.迷宫问题

链接：迷宫问题_牛客题霸_牛客网 (nowcoder.com)

描述：定义一个二维数组 N*M ，如 5 × 5 数组下所示：

int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。

数据范围： 2≤n,m≤10 ，输入的内容只包含 0≤val≤1

输入描述：输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述：左上角到右下角的最短路径，格式如样例所示。

示例1

输入：

5 5

0 1 0 0 0

0 1 1 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

输出：

(0,0)

(1,0)

(2,0)

(2,1)

(2,2)

(2,3)

(2,4)

(3,4)

(4,4)

说明：注意不能斜着走！！！

🔎做题思路：

import java.util.ArrayList;
import java.util.Scanner;
class Node {int x;int y;public Node(int x, int y) {this.x = x;this.y = y;}
}public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()) {String str = scanner.nextLine();String[] arr = str.split(" ");int row = Integer.parseInt(arr[0]);int col = Integer.parseInt(arr[1]);//创建迷宫矩阵int[][] mat = new int[row][col];//读入迷宫数据for (int i = 0; i < row; i++) {str = scanner.nextLine();arr = str.split(" ");for (int j = 0; j < col; j++) {mat[i][j] = Integer.parseInt(arr[j]);}}//搜索最短路径ArrayList<Node> path = new ArrayList<>();ArrayList<Node> minPath = new ArrayList<>();int[][] book = new int[row][col];getMinPath(mat, row, col, 0, 0, book, path, minPath);//打印最短路径for (Node n : minPath) {System.out.println("(" + n.x + "," + n.y + ")");}}}//mat:迷宫矩阵  row，col//x,y：当前位置//book：标记矩阵，标记当前位置是否走过//path：保存当前路径的每一个位置//minPath：保存最短路径public static void getMinPath(int[][] mat, int row, int col, int x, int y, int[][] book, ArrayList<Node> path, ArrayList<Node> minPath) {//判断（x，y）是否越界，是否走过，是否有障碍if (x < 0 || x >= row || y < 0 || y >= col || book[x][y] == 1 || mat[x][y] == 1) {return;}//把当前位置存入路径中path.add(new Node(x, y));//标记当前位置book[x][y] = 1;//判断当前位置是否为出口if (x == row -1 && y == col - 1) {//一条新的路径产生//判断是否为更短路径if (minPath.isEmpty() || path.size() < minPath.size()) {//更新更短路径minPath.clear();for (Node n: path) {minPath.add(n);}}}//如果不是出口：继续搜索（x,y）的上下左右四个方向getMinPath(mat, row, col, x + 1, y, book, path, minPath);//上getMinPath(mat, row, col, x - 1, y, book, path, minPath);//下getMinPath(mat, row, col, x, y - 1, book, path, minPath);//左getMinPath(mat, row, col, x, y + 1, book, path, minPath);//右//把当前位置从路径中删除，寻找新的路径path.remove(path.size() - 1);book[x][y] = 0;}
}

2.年终奖

链接：年终奖_牛客题霸_牛客网 (nowcoder.com)

描述：

小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个6*6的棋盘上进行，上面放着36个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，请设计一个算法使小东拿到价值最高的礼物。

给定一个6*6的矩阵board，其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值，保证每个礼物价值大于100小于1000。

🔎解题思路：

    public static int getMost(int[][] board) {int row = board.length;int col = board.length;//处理第一行for (int i = 1; i < col; i++) {board[0][i] += board[0][i - 1];}//处理第一列for (int i = 1; i < row; i++) {board[i][0] += board[i - 1][0];}//处理剩余位置for (int i = 1; i < row; i++) {for (int j = 1; j < col; j++) {//F(i,j) = max (F(i-1,j),F(i,j-1)) + board[i][j]board[i][j] += Math.max(board[i - 1][j], board[i][j - 1]);}}return  board[row - 1][col - 1];}