一、路线规划

某公司有M个园区，从0到M-1编号，已知2个园区的距离，描述如下：0 1 3，表示从0号园区到1号园区的距离是3（1到0号园区也是3），已知N段距离，未给出距离的则为不可达，现在有一个员工想从A区出发，走遍所有的园区，同一园区只能够经过一次，请计算该员工的最短距离。

输入
第一行：园区个数M，起始园区编号，已知距离个数N
第二行到N行：第一个数字为起始园区，第二个数字为目的园区，第三个数字为距离，中间使用空格区分。
约束：

0 所有输入数据>=0，距离输入都为有效范围，不用考虑无效输入。距离范围为：[1,1000]
每个园区路径不超过3条
输出
最短距离，如无法完成题目条件，则输出-1

样例
4 0 4
0 1 1
1 2 1
2 3 1
1 3 2
1
2
3
4
5
输出3
解释：从园区0经过园区1，再从园区1到园区2，最后到达园区3，最短距离3

4 0 4
0 1 1
0 2 1
0 3 1
1 2 1
1
2
3
4
5
输出-1
无法从0到3，输出-1

参考代码
使用了DFS解，应该还有更好的解法。leetcode上有类似的题LCP 07. 传递信息
以下代码过了80%的测试用例

package zsh;
import java.util.Scanner;public class Park {static boolean flag = false;static int minDistance = Integer.MAX_VALUE;public static void main(String[] args){Scanner scanner = new Scanner(System.in);int parkNum = scanner.nextInt();int start = scanner.nextInt();int pathNum = scanner.nextInt();int[][] path = new int[parkNum][parkNum];for(int i = 0; i < pathNum; i++){int x = scanner.nextInt();int y = scanner.nextInt();int value = scanner.nextInt();path[x][y] = value;path[y][x] = value;}
//        int parkNum = 4;
//        int start = 0;
//        int pathNum = 4;
//        int[][] path = {
//                {0, 1, 0, 0},
//                {1, 0, 2, 1},
//                {0, 2, 0, 1},
//                {0, 1, 1, 0}
//        };boolean[] isVisit = new boolean[parkNum];isVisit[start] = true;int distance = 0;int visitNum = 1;dfs(start, path, distance, parkNum, visitNum, isVisit);if(flag){System.out.println(minDistance);}else{System.out.println(-1);}}public static void dfs(int cur, int[][] path, int distance, int parkNum, int visitNum, boolean[] isVisit){if(visitNum == parkNum){flag = true;minDistance = Math.min(minDistance, distance);return;}for(int i = 0; i < parkNum; i++) {  //for循环结束和isVisit同时确保不在一个点循环if (path[cur][i] == 0 || isVisit[i] == true) {continue;}isVisit[i] = true;distance += path[cur][i];visitNum++;dfs(i, path, distance, parkNum, visitNum, isVisit);isVisit[i] = false;distance -= path[cur][i];visitNum--;}}
}

1.2 上题的变种，注意区别

m个村庄，村庄之间n个公交车线路相连接，现给出所有村庄之间公交路线图及乘坐费用。 

小明希望花费最少的钱从村庄A最多经过K次中转到达村庄D。如果没有相关路线，程序返回-1.

输入：4 （村庄个数）

0        （起始地）

3        （目的地）

1        （中转次数）

[[0,1,2],[0,2,4],[1,3,6],[1,2,1],[2,3,2]]        (公交路线图及乘坐费用edge = [source, destination, price])

输出 6  从村庄0到村庄3最多经过1次中转，最少花费6

package zsh;
import java.util.Scanner;public class Park {static boolean flag = false;static int minDistance = Integer.MAX_VALUE;static int pathNum;public static void main(String[] args){
//        Scanner scanner = new Scanner(System.in);
//        int parkNum = scanner.nextInt();
//        int start = scanner.nextInt();
//        int end = scanner.nextInt();int pathNum = scanner.nextInt();
//        int maxNum = scanner.nextInt();
//        int[][] path = new int[parkNum][parkNum];
//        for(int i = 0; i < pathNum; i++){
//            int x = scanner.nextInt();
//            int y = scanner.nextInt();
//            int value = scanner.nextInt();
//            path[x][y] = value;
//            path[y][x] = value;
//        }int parkNum = 4;int start = 0;int end = 3;pathNum = 1;int[][] path = {{0, 2, 4, 0},{0, 0, 1, 6},{0, 0, 0, 2},{0, 0, 0, 0}};boolean[] isVisit = new boolean[parkNum];isVisit[start] = true;int distance = 0;int visitNum = 0;dfs(start, path, distance, parkNum, visitNum, isVisit, end);if(flag){System.out.println(minDistance);}else{System.out.println(-1);}}public static void dfs(int cur, int[][] path, int distance, int parkNum, int visitNum, boolean[] isVisit, int end){if(cur == end && visitNum <= pathNum+1){flag = true;minDistance = Math.min(minDistance, distance);return;}for(int i = 0; i < parkNum; i++) {  //for循环结束和isVisit同时确保不在一个点循环if (path[cur][i] == 0){ // || isVisit[i] == true) {continue;}
//            isVisit[i] = true;distance += path[cur][i];visitNum++;dfs(i, path, distance, parkNum, visitNum, isVisit, end);
//            isVisit[i] = false;distance -= path[cur][i];visitNum--;}}
}

二、逃出生天

在大小为row*col的方格区域地图上，处处暗藏杀机，地图上每一个格子均有一个倒计时转置，当时间变为0时会触发籍贯，使得该格子区域变为一处死地，该区域无法通过，英雄每移动一个格子消耗1s。英雄可以上下左右四个方向移动，请设置一条最佳路线，让英雄最短时间从[0,0]到达[row-1,col-1]离开。
注意：英雄在出生点和出口时，该区域不能为死地。

输入
首行输入单个空格分隔的两个正整数row和col，row代表行数（0 接下来row行，每一行包含col个以当个空格分隔的数字，代表对应时间的区域倒计时装置设定时间time，单位为秒（0<=time<=100）

输出
英雄从起点到终点的最短用时，若无法到达，则输出-1

样例
输入

3 3
2 3 2
5 1 1
4 5 5
1
2
3
4
输出
4

输入

5 5
3 5 4 2 3
4 5 3 4 3
4 3 5 3 2
2 5 3 3 5
5 3 4 4 3
1
2
3
4
5
6
输出
-1

参考代码
还是DFS问题，过了70%
 

package zsh;
import java.util.Scanner;
public class IslandTime {static int minTime = Integer.MAX_VALUE;static boolean flag = true;public static void main(String[] args){Scanner scanner = new Scanner(System.in);int row = scanner.nextInt();int col = scanner.nextInt();int[][] map = new int[row][col];for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){map[i][j] = scanner.nextInt();}}
//        int row = 5;
//        int col = 4;
//        int[][] map = {
//                {1, 2, 3, 4},
//                {1, 1, 1, 5},
//                {9, 8, 7, 6},
//                {10, 1, 1, 1},
//                {11, 12, 13, 14},
//        };int costTime = 0;boolean[][] isVisit = new boolean[row][col];dfs(0, 0, costTime, isVisit, row, col, map);if(flag){System.out.println(minTime);}else{System.out.println(-1);}}public static void dfs(int x, int y, int costTime, boolean[][] isVisit, int row, int col, int[][] map){if(x < 0 || y < 0 || x >= row || y >= col || isVisit[x][y] ==true || map[x][y] < costTime){return;}if(x == (row-1) && y == (col-1)){minTime = Math.min(costTime, minTime);flag = true;return;}isVisit[x][y] = true;dfs(x, y+1, costTime + 1, isVisit, row, col, map);dfs(x+1, y, costTime + 1, isVisit, row, col, map);dfs(x,y-1, costTime + 1, isVisit, row, col, map);dfs(x-1,y, costTime + 1, isVisit, row, col, map);}
}

package zsh;import java.util.Scanner;
public class LandMap {static int maxArea = 0;static boolean flag = true;public static void main(String[] args){
//        Scanner scanner = new Scanner(System.in);
//        int row = scanner.nextInt();
//        int col = scanner.nextInt();
//        int[][] map = new int[row][col];
//        for(int i = 0; i < row; i++){
//            for(int j = 0; j < col; j++){
//                map[i][j] = scanner.nextInt();
//            }
//        }int row = 6;int col = 6;int[][] map = {{1, 1, 1, 1, 2, 1},{0, 0, 0, 0, 1, 0},{0, 2, 5, 0, 0, 0},{0, 1, 2, 0, 0, 0},{0, 0, 1, 1, 0, 0},{0, 0, 0, 0, 0, 0},};int area = 0;boolean[][] isVisit = new boolean[row][col];for(int i = 0; i < row; i++) {for(int j = 0; j < col; j++) {if(map[i][j] > 0){area = dfs(i, j, isVisit, map);maxArea = Math.max(maxArea, area);}}}System.out.println(maxArea);}public static int  dfs(int x, int y, boolean[][] isVisit, int[][] map){if(x < 0 || y < 0 || x >= map.length || y >= map[0].length || isVisit[x][y] ==true || map[x][y] == 0 ){return 0;}isVisit[x][y] = true;return  map[x][y]+dfs(x, y+1, isVisit, map)+dfs(x+1, y, isVisit, map)+dfs(x,y-1, isVisit, map)+dfs(x-1,y, isVisit, map);//       area += map[x][y];maxArea = Math.max(maxArea, area);
//        isVisit[x][y] = true;
//        dfs(x, y+1,  isVisit, map, area);
//        dfs(x+1, y, isVisit, map, area);
//        dfs(x,y-1, isVisit, map, area);
//        dfs(x-1,y, isVisit, map, area);
//        return area;}
}

三、求海岛面积，不同于Leecode，每块面积不同

package zsh;public class LandMap {static int maxArea = 0;static boolean flag = true;public static void main(String[] args){
//        Scanner scanner = new Scanner(System.in);
//        int row = scanner.nextInt();
//        int col = scanner.nextInt();
//        int[][] map = new int[row][col];
//        for(int i = 0; i < row; i++){
//            for(int j = 0; j < col; j++){
//                map[i][j] = scanner.nextInt();
//            }
//        }int row = 3;int col = 3;
//        int[][] map = {
//                {1, 2, 3, 4, 5, 6},
//                {0, 0, 0, 8, 7, 0},
//                {0, 2, 0, 9, 0, 0},
//                {0, 1, 2, 0, 0, 0},
//                {0, 0, 1, 1, 0, 0},
//                {0, 0, 0, 0, 0, 0},
//        };int[][] map = {{1, 2, 3},{0, 4, 0},{0, 1, 0},};int area = 0;boolean[][] isVisit = new boolean[row][col];  //是否访问过for(int i = 0; i < row; i++) {for(int j = 0; j < col; j++) {if(map[i][j] > 0){area = dfs(i, j, isVisit, map);maxArea = Math.max(maxArea, area);}}}System.out.println(maxArea);}public static int  dfs(int x, int y, boolean[][] isVisit, int[][] map){if(x < 0 || y < 0 || x >= map.length || y >= map[0].length || isVisit[x][y] ==true || map[x][y] == 0 ){return 0;}int area =  map[x][y];isVisit[x][y] = true;area += dfs(x, y+1, isVisit, map);area += dfs(x+1, y, isVisit, map);area += dfs(x,y-1, isVisit, map);area += dfs(x-1,y, isVisit, map);return area;}
}

四、 字符串排列

力扣

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof

package zsh;import java.util.*;public class StringSort {static char[] charArr;static List list = new ArrayList<>();static int length = 0;static int sum = 0;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);charArr = scanner.nextLine().trim().toCharArray();length = charArr.length;dfs(0);System.out.println(sum);
//        for(String str : list){
//            System.out.println(str);
//        }}static void dfs(int k){if(k == length - 1){
//            list.add(charArr.toString());list.add(String.valueOf(charArr));sum++;return;}Set set = new HashSet<>();for(int i = k; i < length; i++){  //反向思维，第一遍过去顺序，递归回来才交换顺序if(set.contains(charArr[i])){continue;}set.add(charArr[i]);swap(i, k);dfs(k + 1);swap(k, i);}}static void swap(int x, int y){char temp = charArr[x];charArr[x] = charArr[y];charArr[y] = temp;}
}

五、出租车和步行

小美的最快到达时间

参考 2021-08-15_zzxhqzz的博客-CSDN博客

小美现在临时接到一个会议通知，需要立刻赶往对应地点开会。 不妨将小美所在的地点抽象成一个图。小美位于节点x的位置，将要赶往节点y开会。

小美启动了打车软件，该打车软件可以将起点定位在任何一个节点开始叫车。但是，叫车是需要时间的，不同位置叫车的等车时间不同。

这就意味着，考虑到叫车的时间，小美可以不选自己所在的节点叫车，而选择一个附近的点叫车，在等车时间内自行走路到对应的节点以缩短综合时间，更快地赶到目的地开会。

请注意：小美的叫车终点只能是开会处，即此题不考虑通过多次打车来缩短时间，只考虑更改起点带来的时间减少。

下面给出一个简单的例子来帮助你理解：

小美位于节点1，开会的地点位于节点3

节点1和节点2之间有一条汽车通行时长为1，步行通行时间为2的通路；

节点2和节点3之间有一条汽车通行时长为2，步行通行时间为5的道路；

节点1的打车等候时间为10，节点2的打车等候时间为1，节点3的打车等候时间为5

此时，显然小美有如下几种方案：

第一种方案：小美在节点1打车，此时小美需要先等时间10上车，之后花费3的时间抵达节点3，共计花费时长13；

第二种方案：小美在节点2打车，此时小美需要步行时长2抵达节点2，此时汽车司机已经等候在节点2，小美直接上车，通行时长2后抵达节点3。共计花费时长为4。

第三种方案：小美直接步行到节点3（因为节点3是开会地点，显然在节点3打车无意义），此时花费的时长为7。

以上三种方案中，应选第二种方案能最快抵达开会地点。共计花费时长为4。

注意：实际打车过程中，司机会存在客人太久没来上车自行取消的可能，这里为了简化问题，我们假设司机耐心是充分的，可以无限制等候乘客。

输入描述 第一行四个正整数n,m,x,y，空格隔开，其中 n 表示点的数量，点的序号依次表示为 1 到 n；m表示边的数量；x表示小美当前的节点位置，y表示小美开会的节点位置。

接下来 m 行，每行四个正整数，空格隔开，x, y, p, q，表示节点 x 和节点 y 之间有一条汽车通行时长 p，步行通行时长 q 的双向道路。

接下来一行 n 个空格隔开的正整数，第 i 个正整数表示在第i个节点打车所需要花费的等车时间。

输出描述 输出一行一个正整数表示小美最快抵达开会地点的时间。

样例输入

3 2 1 3
1 2 1 2
2 3 2 5
10 1 5

样例输出 4

提示 数据范围和说明

对于全体数据保证p和q（即汽车通行时间和步行时间）都是[1, 50]内的正整数，保证每个点打车的等候时间都是[1, 1000]内的正整数

对于n和m，对于60%的数据，保证 1<= n <= 10, 1 <= m <= 30, 对于100%的数据，保证 1<= n <= 50, 1 <= m <= 200，数据保证没有重复的边。

package zsh;import java.util.*;public class TaxiWalk {static List> list = new ArrayList<>();  //用来存储每个节点可以和哪些节点相连static int nodeNum;public static int[] bfs(int[] dis, int start, int[][] map){Queue queue = new LinkedList<>();queue.add(start);while(!queue.isEmpty()){int cur = queue.poll();int len = list.get(cur).size();for (int i = 0; i < len; i++) {int next = list.get(cur).get(i);if(dis[next] > (dis[cur] + map[cur][next])){dis[next] = dis[cur] + map[cur][next];queue.add(next);}}}return dis;}//递归遍历public static int[] dfs(int cur, int end, int[][] path, boolean[] isVisit, int[] dis){if(cur == end){return dis;}for(int i = 0; i < nodeNum; i++) {  //for循环结束和isVisit同时确保不在一个点循环if (path[cur][i] == 0 || isVisit[i] == true) {continue;}isVisit[i] = true;dis[i] = Math.min(dis[i], dis[cur] + path[cur][i]);dfs(i, end, path, isVisit, dis);isVisit[i] = false;}return dis;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);nodeNum = scanner.nextInt();int edge = scanner.nextInt();int start = scanner.nextInt()-1;int end = scanner.nextInt()-1;int[][] mapTaxi = new int[nodeNum][nodeNum];int[][] mapWalk = new int[nodeNum][nodeNum];for (int i = 0; i < nodeNum; i++) {list.add(new ArrayList<>());}for (int i = 0; i < edge; i++) {int x = scanner.nextInt() - 1;  //记得减1，题目从1开始int y = scanner.nextInt() - 1;list.get(x).add(y);list.get(y).add(x);mapTaxi[x][y] = mapTaxi[y][x] = scanner.nextInt();mapWalk[x][y] = mapWalk[y][x] = scanner.nextInt();}int[] wainextime = new int[nodeNum];for (int i = 0; i < nodeNum; i++) {wainextime[i] = scanner.nextInt();}int[] disTaxi = new int[nodeNum];int[] disWalk = new int[nodeNum];Arrays.fill(disTaxi, Integer.MAX_VALUE);Arrays.fill(disWalk, Integer.MAX_VALUE);disTaxi[end] = 0;  //倒着走disWalk[start] = 0;disTaxi = bfs(disTaxi, end, mapTaxi);  //从后往前，倒序打车的最短路，最后贪心判断disWalk = bfs(disWalk, start, mapWalk);  //正序 步行的最短路//递归
//        boolean[] isVisit = new boolean[nodeNum];
//        disTaxi = dfs(end, start, mapTaxi, isVisit, disTaxi);
//        disWalk = dfs(start, end, mapWalk, isVisit, disWalk);//贪心判断 等待时间 步行出租车混合 巧妙int minTime = Integer.MAX_VALUE;minTime = Math.min(minTime, disWalk[end]);  //最慢就是完全步行for(int i = 0; i < nodeNum; i++){disWalk[i] = Math.max(disWalk[i], wainextime[i]);  //在每个节点坐出租车，必须取 等待时间 和 步行到这个节点 的最大值minTime = Math.min(disWalk[i] + disTaxi[i], minTime);  //加上剩余路程的出租车时间（逆序才能这样加）}System.out.println(minTime);}
}
//3 2 1 3
//1 2 1 2
//2 3 2 5
//10 1 5

package zsh;public class ShortestPath {static int[] start;static int[] end;static int[][] arr;static boolean[][] isVisit;static int res = Integer.MAX_VALUE;static int row;static int col;static int line = 0;public static void main(String[] args) {row = 3;col = 5;arr = new int[][]{{1, 0, 2, 0, 3},{0, 2, 0, 1, 1},{0, 3, 0, 0, 0}};isVisit = new boolean[row][col];start = new int[]{0, 2};end = new int[]{1, 1};arr[start[0]][start[1]] = 0;dfs(start[0], start[1]);System.out.println(res);}public static void dfs(int x, int y){if(x == end[0] && y == end[1]){res = Math.min(res, line);line--;return;}if(x < 0 || y < 0 || x >= row || y >= col || isVisit[x][y] == true || arr[x][y] != 0){return;}isVisit[x][y] = true;dfs(x, y + 1);line++;dfs(x + 1, y);line++;dfs(x, y - 1);line++;dfs(x - 1, y);line++;
//        dfs(x + 1, y, line + 1);
//        dfs(x, y - 1, line + 1);
//        dfs(x - 1, y, line + 1);}
}

package zsh;import java.util.Scanner;public class QuShi1 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String p = scanner.next();String str = scanner.nextLine();String[] arr = str.trim().replace("[", "").replace("]", "").replace("\"","").replace(" ","").split(",");boolean flag = false;for (int i = 0; i < arr.length; i++) {if(isMatch(arr[i], p)){System.out.print(arr[i]+" ");flag = true;}}if(flag == false){System.out.println("Not Match");}}public static boolean isMatch(String s, String p) {int m = s.length();int n = p.length();boolean[][] dp = new boolean[m + 1][n + 1];dp[0][0] = true;for (int i = 1; i <= n; ++i) {if (p.charAt(i - 1) == '*') {dp[0][i] = true;} else {break;}}for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (p.charAt(j - 1) == '*') {dp[i][j] = dp[i][j - 1] || dp[i - 1][j];} else if ( s.charAt(i - 1) == p.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];}}}return dp[m][n];}
}
//a.*.com ["a.test.com","a.b.com","b.c.com"]
//a.*.com ["b.c.com","d.e.com"]

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！