2.1AC网易互娱笔试4.11
第一题0.3
直接暴力求解,失分点应该在于没有把方法抽象出来,这题感觉要抽象一个match方法,然后用递归。。但时间不够,来不及改,感觉暴力可以A
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][] news = new int[n + 1][n + 1]; for (int i = 0; i < n; i++) { for (int j = 0; j < n + 1; j++) { news[i][j] = sc.nextInt(); } } int[][] olds = new int[n + 1][n + 1]; for (int i = 0; i < n; i++) { for (int j = 0; j < n + 1; j++) { olds[i][j] = sc.nextInt(); } } sc.close(); HashMap<Integer, Integer> match = new HashMap<>(); for (int i = 0; i < n; i++) { int newN = news[i][0]; for (int j = 1; j < n + 1; j++) { if(!match.containsKey(news[i][j])){ match.put(news[i][j], newN); break; }else { for (int k = 1; k < n + 1; k++) { int like = olds[news[i][j]][k]; if(like == newN){ int curr_new = match.get(news[i][j]); int curr_old = like; for (int m = 1; m < n + 1; m++) { if(news[curr_new][m] == curr_old){ curr_old = news[curr_new][m + 1]; break; } } match.put(like, newN); match.put(curr_old, curr_new); }else if(like == match.get(news[i][j])){ break; } } } } } TreeMap<Integer, Integer> res = new TreeMap<>(); for (Integer old : match.keySet()) { res.put(match.get(old), old); } for (Integer newNum : res.keySet()) { System.out.println(newNum + " " + res.get(newNum)); } }
第二题0.8
类似原题机器人可运动空间,简单的DFS,没超时没超空间,不知道哪里出错
private static int count = 0; private static boolean[][] visited = null; private static char[][] map = null; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); map = new char[n][n]; for (int i = 0; i < n; i++) { String curr = sc.next(); for (int j = 0; j < n; j++) { map[i][j] = curr.charAt(j); } } int x = sc.nextInt(); int y = sc.nextInt(); sc.close(); // System.out.println("success"); visited = new boolean[n + 1][n + 1]; mov(n, n, x, y); System.out.println(count); } private static void mov(int rows, int cols, int row, int col) { if(row >= rows || col >= cols || visited[row][col] || map[row][col] == '#') return; visited[row][col] = true; char curr = map[row][col]; if(curr >= '0' && curr <= '9') count += curr - '0'; if(row > 0) mov(rows, cols, row - 1, col); if(row < rows - 1) mov(rows, cols, row + 1, col); if(col > 0) mov(rows, cols, row, col - 1); if(col < cols - 1) mov(rows, cols, row, col + 1); }
第三题AC
sql语句的意思应该是找出username相同但tbaname不同的所有行,然后输出tbaname对应的“所有username分别反向对应的tbaname”数量大于2的所有不同的tbaname和对应值这里称为ABA集合
例如测试用例:
8
ddd Kate
ccc Kate
ccc Beal
eee Tom
ddd Beal
bbb Kate
ddd Tom
ccc Tom
这里面ccc对应的有Kate、Beal、Tom三个,这三个分别反向对应的为ddd ccc bbb和ccc ddd和eee ddd ccc,那么这里面数量大于2的是ccc3个,ddd3个,而不同的tbaname为ddd3个,也就是第一个输出ccc ddd 3
ddd Kate
ccc Kate
ccc Beal
eee Tom
ddd Beal
bbb Kate
ddd Tom
ccc Tom
这里面ccc对应的有Kate、Beal、Tom三个,这三个分别反向对应的为ddd ccc bbb和ccc ddd和eee ddd ccc,那么这里面数量大于2的是ccc3个,ddd3个,而不同的tbaname为ddd3个,也就是第一个输出ccc ddd 3
同理可以求得ddd ccc 3,而eee和bbb没有大于2的所以忽略。
这道题的难点在于集合来回遍历,中间步骤容易出错,不知道有没有大神有更好的方法。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
HashSet<String> tbas = new HashSet<>(); //存储所有tbaname
HashMap<String, HashSet<String>> use = new HashMap<>(); //存储username对应的所有tbaname
for (int i = 0; i < n; i++) {
String[] sqls = sc.nextLine().split(" ", -1);
tbas.add(sqls[0]);
if(use.containsKey(sqls[1])){
use.get(sqls[1]).add(sqls[0]);
}else {
HashSet<String> curr = new HashSet<>();
curr.add(sqls[0]);
use.put(sqls[1], curr);
}
}
sc.close();
HashMap<String, HashMap<String, HashSet<String>>> res = new HashMap<>(); //存储tbaname对应的“所有username分别反向对应的tbaname”的集合,也就是描述的ABA集合 for (String s : tbas) {
HashMap<String, HashSet<String>> curr = new HashMap<>();
for (String t : use.keySet()) {
if(use.get(t).contains(s)) curr.put(t, use.get(t));
}
res.put(s, curr);
}
TreeMap<String, TreeMap<String, Integer>> count = new TreeMap<>(); //存储结果集,最后输出结果集中,数量大于2的即可
for (String s : res.keySet()) {
HashMap<String, HashSet<String>> shsh = res.get(s);
TreeMap<String, Integer> curr = new TreeMap<>();
for (String t : shsh.keySet()) {
for (String str : shsh.get(t)) {
if(curr.containsKey(str)){
curr.put(str, curr.get(str) + 1);
}else {
curr.put(str, 1);
}
}
}
count.put(s, curr);
}
for (String s : count.keySet()) {
TreeMap<String, Integer> curr = count.get(s);
for (String str : curr.keySet()) {
if(curr.get(str) > 2 && !str.equals(s)) System.out.println(s + " " + str + " " + curr.get(str));
}
}
}