第一题
求最短路径
核心思想:DFS 以及用二维数组接收数据
核心思想:DFS 以及用二维数组接收数据
启发:https://blog.csdn.net/seagal890/article/details/96048023
package com.ljn.test; import java.util.Scanner; public class Test4 { //最短路径值 static int min = Integer.MAX_VALUE; //二维数组记录路径值。如:1到2路径3 就是int[1][2]=3 static int[][] edge = new int[100][100]; //普通数组记录该点是否已走过 0-未经过 1-已经过 static int[] vertex = new int[100]; //n-站点数 ,m-路线数 ,endPoint-终点编号 static int n, m,endPoint; static Scanner input = new Scanner(System.in); public static void main(String[] args) { //输入的第一行第一个数字-站点数 n = input.nextInt(); //输入的第一行第二个数字-路线数 m = input.nextInt(); //外层循环-站点数 for (int i = 0; i < n; i++) { //内层循环-线路数 for (int j = 1; j <= m; j++) { //如果相等就相当于 1站点到1站点,无意义 置为0 if (i == j) { edge[i][j] = 0; } else { //路径默认值设为最大值 edge[i][j] = Integer.MAX_VALUE; } } } //根据线路数m 循环遍历 把路径值赋给初始化好的二维数组 for (int i = 0; i < m; i++) { int a = input.nextInt(); int b = input.nextInt(); int c = input.nextInt(); edge[a][b] = c; } //输入的最后一行是 要计算的终点站 endPoint = input.nextInt(); dfs(0, 0); System.out.println(min); } /** * * @param cur 当前站点 * @param dis 目前走过的距离 */ public static void dfs(int cur, int dis) { /** * 如果当前路径大于之前找到的最小值,可直接返回 * */ if (dis > min) { return; } /** * 判断是否达到终点,更新最小值,返回 * */ if(cur == endPoint) { if (dis < min) { min = dis; return; } } /** * 当前点到其他各点之间可连通但是还未添加进来时,遍历执行 * */ for (int i = 1; i <= n; i++) { if (edge[cur][i] != Integer.MAX_VALUE && vertex[i] == 0) { vertex[i] = 1; dfs(i, dis+edge[cur][i]); /** * 回溯 **/ vertex[i] = 0; } } return; } }
第二题
游戏王
背包问题
核心思想:动态规划
参考:https://blog.csdn.net/Lin_Willen/article/details/105052124
package com.ljn.test; import java.util.Scanner; public class Test5 { public static void main(String[] args) { int numberGames,days; //每款游戏完成天数 数组 int[] dayArr = new int[10]; //每款游戏完成成就值 数组 int[] honorArr = new int[10]; Scanner scanner = new Scanner(System.in); //输入的第一行第一个数字-游戏数 numberGames = scanner.nextInt(); //输入的第一行第二个数字-总天数 days = scanner.nextInt(); //外层循环-根据游戏数量 for (int i = 0; i < numberGames; i++) { //当前行的的第一个数字-游戏的成就值 int a = scanner.nextInt(); honorArr[i]=a; //当前行的的第二个数字-游戏所需完成时间 int b = scanner.nextInt(); dayArr[i]=b; } biggestHonor(dayArr,honorArr,days,numberGames); } /** * * @param w 每款游戏完成天数 数组 * @param v 每款游戏完成成就值 数组 * @param m 输入的第一行第二个数字-总天数 * @param n 输入的第一行第一个数字-游戏数 */ public static void biggestHonor(int[] w ,int [] v,int m,int n){ int[][] val = new int[n+1][m+1];//表格中有一行一列为0,表示没有物品时价值为0,背包没有容量时价值为0 int[][] path = new int[n+1][m+1];//记录背包装物品的记录 //将val数组的第一行跟第一列置0 for (int i = 0; i < val.length; i++) { val[i][0] = 0;//将列置0 } for (int j = 0; j < val[0].length; j++) { val[0][j] = 0;//将行置0 } for (int i = 1; i < val.length; i++) { for (int j = 1; j < val[0].length; j++) { if(w[i-1] > j){ val[i][j]=val[i-1][j]; }else{ if(val[i-1][j] > v[i-1]+val[i-1][j-w[i-1]]){ val[i][j] = val[i-1][j]; }else{ val[i][j] = v[i-1]+val[i-1][j-w[i-1]]; path[i][j] = 1; } } } } System.out.println(val[val.length-1][val[0].length-1]); } }
第三题
数学题
贪心算法、栈
package com.janeroad; import java.util.LinkedList; /** * Created on 2020/8/16. * * [@author] LJN */ public class Test28 { public static void main(String[] args) { System.out.println(removeKdigits("71245323308", 4)); } public static String removeKdigits(String num, int k) { LinkedList<Character> stack = new LinkedList<Character>(); for(char digit : num.toCharArray()) { while(stack.size() > 0 && k > 0 && stack.peekLast() > digit) { stack.removeLast(); k -= 1; } stack.addLast(digit); } /* remove the remaining digits from the tail. */ for(int i=0; i<k; ++i) { stack.removeLast(); } // build the final string, while removing the leading zeros. StringBuilder ret = new StringBuilder(); boolean leadingZero = true; for(char digit: stack) { if(leadingZero && digit == '0') continue; leadingZero = false; ret.append(digit); } /* return the final string */ if (ret.length() == 0) return "0"; return ret.toString(); } }
重点:第一次参加笔试,不懂oj输入输出等判题要求,平时刷题都是只要写出算法就行了,很少用Scanner都忘光了,所以痛定思痛多联系输入输出+写算法
牛客网在线判题系统使用帮助:https://www.nowcoder.com/discuss/276
代码写的不好,纯属输出用于日后复习,勿喷
全部评论
(1) 回帖