阿里4.13笔试
第一题:选动物老大,n个小动物,编号1-n,代表武力值,值越小,武力值越高,每个小动物都有一票投票权,可以投给自己或者自己崇拜的动物,或者和自己崇拜的动物跟票。只能崇拜武力值比自己厉害的动物。
输入样例:第一行动物个数, 第二行崇拜对象。
4
0 1 1 1
输出
4
1
1
1
这道题笔试的时候我AC了。
我的解题思路:因为动物只会崇拜能力值比自己高的动物,所以从后向前依次统计每个动物受了多少个其他动物的崇拜,所以每个动物的得票数为崇拜对象数+1(自己给自己投).
public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] an = new int[n]; int[] pow = new int[n + 1]; for(int i = 0; i < n; i++){ an[i] = scanner.nextInt(); } for (int i = an.length - 1; i >= 0; i--) { if(an[i] == 0){ continue; } pow[an[i]] = pow[an[i]] + pow[i + 1] + 1; } for (int i = 1; i < pow.length; i++) { System.out.println(pow[i] + 1); } }
第二题:n个城市n个人,每个城市一个人,选择一个城市x,所有人去那聚会,聚合结束所有人返回各自城市。
有m条单向路径,保证每个人可以到达城市x,一个人所消耗时间为往返时间和,每个人选择自己的最短路径,问最长的时间是多少
输入样例:第一行n,m,x
,第二行路径
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
输出
10
能不能AC不清楚,测试用例是可以过的
这道题由于时间不足(可能是我太菜),当时写的时候比较慌,出了蛮多问题,14号中午又接到面试,就搁置了。
今天仔细思考了下,还是用暴力方法解决了。我用的是dfs,直接找每个城市到达目的城市的最短路径的最长时间。最后后比较每个城市的时间。
static int[] mark;//标记数组防止重复访问 static int step;//记录步数 public static int minPath(int[][] map, int start, int end, int nowStep){ int res = 0; mark[start] = 1; int tmp = Integer.MAX_VALUE; for (int i = 1; i < map[start].length; i++) { if(map[start][i] == 0 || mark[i] != 0){ continue; } if(i == end){ res = map[start][i]; break; }else{ step++; int tmpRes = minPath(map, i, end, nowStep+1); if(tmp > step){ res = tmpRes; tmp = step; step = nowStep; } else if(tmp == step){ res = Math.max(tmpRes, res); } } } mark[start] = 0; return res; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int k = scanner.nextInt(); int[][] map = new int[n+1][n+1]; mark = new int[n+1]; int[] path = new int[n+1]; for(int i = 1; i <=m; i++){ int x = scanner.nextInt(); int y = scanner.nextInt(); map[x][y] = scanner.nextInt(); } for (int i = 1; i < path.length; i++) { if(i == k){ continue; } step = 0; path[i] = minPath(map, i, k, 0) + minPath(map, k, i, 0); } int max = 0; for (int i : path) { max = Math.max(max, i); } System.out.println(max); }#阿里笔试2020##笔试题目##阿里巴巴#