布吉网站建设哪家好,wordpress做查询系统,凡科是免费做网站吗,做网站用什么语言和工具有一个环形的公路#xff0c;上面共有n站#xff0c;现在给定了顺时针第i站到第i1站之间的距离#xff08;特殊的#xff0c;也给出了第n站到第1站的距离#xff09;#xff0c;小*想着沿着公路第x站走到第y站#xff0c;她想知道最短的距离是多少#xff1f; 输入描述… 有一个环形的公路上面共有n站现在给定了顺时针第i站到第i1站之间的距离特殊的也给出了第n站到第1站的距离小*想着沿着公路第x站走到第y站她想知道最短的距离是多少 输入描述 第一行输入一个正整数n代表站的数量。第二行输入n个正整数ai前 n-1个数代表顺时针沿看公路走i站到第i1站之间的距离:最后一个正整数代表顺时针沿着公路走第n站到第1 站的距离 第三行输入两个正整数x和y代表小美的出发地和目的地。 1 n 10^5 1ai 10^9 1x,yn 输入 3 1 2 2 2 3 输出 2 大厂的笔试永远这么晦涩难懂刚看到题的时候只能知道它是一道图论问题题目描述的确实有一点绕现在让我们来分析一波题的含义 假如你现在在车站1假如你的目的地是车站3你选择哪条路路径最短毫无疑问肯定是由车站1直接到车站3路径是最短的我们可以用眼睛直接观察出来可是计算机可不能直接得出正确答案如果你做图论的相关题较多的话其实你刚看到这道题心里便会想到这道题和这题类似的leetcode原题K 站中转内最便宜的航班我们今天以讲解leetcode为例这道题知识稍微在那道题中做了变形就出来了 有 n 个城市通过一些航班连接。给你一个数组 flights 其中 flights[i] [fromi, toi, pricei] 表示该航班都从城市 fromi 开始以价格 pricei 抵达 toi。 现在给定所有的城市和航班以及出发城市 src 和目的地 dst你的任务是找到出一条最多经过 k 站中转的路线使得从 src 到 dst 的 价格最便宜 并返回该价格。 如果不存在这样的路线则输出 -1。 n 3, edges [[0,1,100],[1,2,100],[0,2,500]]
src 0, dst 2, k 1
输出: 200
解释:
城市航班图如下其实K站中转内最便宜的航班其实约束条件更多一点其要找到一条最多经过k站中转的路线
我们这次使用递归来解决这个问题 由于题目中给出我们这些信息所以我们就可以根据这些信息去构建邻接表 因为我们函数在递归的时候函数中的参数是我们的起点位置所以我们因为构造一个to-[from,price]的邻接矩阵
//邻接表的数据结构
MapInteger,ListInteger[] mapnew HashMap();//遍历每一个数组取出对应的元素for(int[] f:flights){//起点int fromf[0];//终点int tof[1];//两点之间的距离int pricef[2];//如果不包含if(!map.containsKey(to)){map.put(to,new LinkedList());}//构建邻接表map.get(to).add(new Integer[]{from,price});}
接下来就是我们寻找起点和终点的最短路径的最短距离
函数标签
//dst指的是当前点 k指的是剩下可以步数
private int dfs(int dst, int k) {}
如果我们的起点正好等于我们的终点直接返回0说明已经找到了一条可以到达目的地的路线 if(dstsrc){return 0;}
如果k0说明当前已经不满足题目的要求没到终点且步数为0直接返回-1 if(k0){return -1;} 如果当前节点合法那么就遍历与它直接相邻的节点 if(map.containsKey(dst)){//遍历邻接表for(Integer[] v:map.get(dst)){//起点int fromv[0];//所需要的花费int pricev[1];//递归下一个节点int subdfs(from,k-1);//如果sub不是-1就说明该路线是合法的if(sub!-1){//当前节点距离终点的路径下一个节点距离终点的路径当前节点距离下一个节点的距离resMath.min(res,subprice);}}return res;} 这种递归的方法肯定是超时所以我们使用记忆化搜索的方式去进行优化 int[][]memo;memonew int[n][k1];
//如果曾经已经计算过直接返回答案
if(memo[dst][k]!-88)return memo[dst][k]; res resInteger.MAX_VALUE?-1:res;memo[dst][k]res; 动态规划方式就先不做介绍了大家下去可以自行试一试
源码如下 MapInteger,ListInteger[] mapnew HashMap();//记忆化数组int[][]memo;//起点int src;//终点int dst;public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {this.dstdst;this.srcsrc;//k表示的节点我们将结点转换成步数更利于计算k;memonew int[n][k1];//对记忆化数组进行初始化for(int[] row:memo){Arrays.fill(row,-88);}//构造邻接表for(int[] f:flights){int fromf[0];int tof[1];int pricef[2];if(!map.containsKey(to)){map.put(to,new LinkedList());}map.get(to).add(new Integer[]{from,price});}return dfs(dst,k);}//表示从dst的走k步的最小价格private int dfs(int dst, int k) {if(dstsrc){return 0;}if(k0){return -1;}if(memo[dst][k]!-88)return memo[dst][k];int resInteger.MAX_VALUE;if(map.containsKey(dst)){for(Integer[] v:map.get(dst)){int fromv[0];int pricev[1];int subdfs(from,k-1);if(sub!-1){resMath.min(res,subprice);}}}res resInteger.MAX_VALUE?-1:res;memo[dst][k]res;return memo[dst][k];} 我们再来看这道所谓大厂的笔试题这道题过程跟这个题一模一样我们只需要将上面这个题中的k这个约束给省略掉这道题也就出来了
代码如下 MapInteger,ListInteger[] mapnew HashMap();int[]memo;int src;int dst;public int findCheapestPrice(int n, int[][] flights, int src, int dst) {this.dstdst;this.srcsrc;memonew int[n];Arrays.fill(memo,-88);for(int[] f:flights){int fromf[0];int tof[1];int pricef[2];if(!map.containsKey(to)){map.put(to,new LinkedList());}map.get(to).add(new Integer[]{from,price});}return dfs(dst);}private int dfs(int dst) {if(dstsrc){return 0;}if(memo[dst]!-88)return memo[dst];int resInteger.MAX_VALUE;if(map.containsKey(dst)){for(Integer[] v:map.get(dst)){int fromv[0];int pricev[1];int subdfs(from);if(sub!-1){resMath.min(res,subprice);}}}res resInteger.MAX_VALUE?-1:res;memo[dst]res;return memo[dst];}知识ACM模式下我们的所有参数都需要我们手动的去输入这点也是比较关键点的因素
起先我是这样写的
Scanner scannernew Scanner(System.in);int nscanner.nextInt();int[][] numsnew int[n][3];int index0;//遍历每个数组for(int[] num:nums){while(scanner.hasNextInt()){//给每个数组进行赋值for(int i0;inum.length;i) {if(in-1){num[0]i;num[1]0;num[2]scanner.nextInt();}else{num[0]i;num[1]i1;num[2]scanner.nextInt();}}break;}}int startscanner.nextInt();int endscanner.nextInt(); 最后半天一直在死循环后来发现每个数组就3个元素我这个for循环加的位置明显就有问题所以一直在死循环所以果断换了一种方式及时止损 Scanner scanner new Scanner(System.in);System.out.print(输入行数:);int n scanner.nextInt();int m 3;int[][] nums new int[n][m];System.out.println(输入二维数组中的值:);//利用双层for循环进行定点输入for (int i 0; i n; i) {for (int j 0; j m; j) {nums[i][j] scanner.nextInt();}}System.out.println(输入的二维数组为:);for (int i 0; i n; i) {for (int j 0; j m; j) {System.out.print(nums[i][j] );}System.out.println();}int start scanner.nextInt();int end scanner.nextInt();
我们将测试案例试一试 这样很明显示我们手动的输入了数组中的元素这样很显然是不符合题意的那么我们这么样输入[1 2 2] 会自动生成[[0,1,1],[1,2,2],[2,0,3]]这个数组呢我们先来说明它这个数组是是怎么生成的 因为我们的数组是从0开始计数的所以我们应该写成这样 我们开始ACM输入 System.out.println(输入二维数组中的值:);//输入一行时ACM输入while(scanner.hasNextInt()){for(int i0;in;i){int distscanner.nextInt();//如果是最后一个直接指向第一个节点if(in-1){int[] numnums[i];num[0]i;num[1]0;num[2]dist;//不是第一个直接指向后一个节点}else{int[] numnums[i];num[0]i;num[1]i1;num[2]dist;}}//这个break记得加要不就会死循环break;}System.out.println(输入的二维数组为:);for (int i 0; i n; i) {for (int j 0; j m; j) {System.out.print(nums[i][j] );}System.out.println();} 最后我们这道题也就讲解完了ACM输入的时候对于很多笔试经验少的同学确实是一个挑战希望大家刷题的过程中多使用ACM刷题leetcode的话尽量脱离有提示的工具最好在网页上进行写
ACM源代码输入 Scanner scanner new Scanner(System.in);System.out.print(输入行数:);int n scanner.nextInt();int m 3;int[][] nums new int[n][m];System.out.println(输入二维数组中的值:);while(scanner.hasNextInt()){for(int i0;in;i){int distscanner.nextInt();if(in-1){int[] numnums[i];num[0]i;num[1]0;num[2]dist;}else{int[] numnums[i];num[0]i;num[1]i1;num[2]dist;}}break;}System.out.println(输入的二维数组为:);for (int i 0; i n; i) {for (int j 0; j m; j) {System.out.print(nums[i][j] );}System.out.println();}int start scanner.nextInt();//输入的是起点为1数组的起点为0所以需要减1startstart-1;int end scanner.nextInt();endend-1; 如果有更高的ACM输入的方式或者是解题更妙的技巧欢迎大家来评论区进行评论
