奇安信服务端开发Java8.23笔试编程题记录
写完交卷,到牛客一看,暴力可解,懵了,小难受,还想了大半天
public int[] getFraction(float a) { // write code here int[][] b = new int[200][2]; double d = 1.0f; int index = 0; for (int i = 0; i < 200; i++) { b[i][0] = (int) ((i + 1) * a + 0.5); b[i][1] = i + 1; if (Math.abs(b[i][0] * 1.0 / b[i][1] - a) < d) { d = Math.abs(b[i][0] * 1.0 / b[i][1] - a); index = i; } } return new int[]{b[index][0], b[index][1]}; }
int[][] d = new int[][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; public int getMinLength(int[][] pearls) { // write code here int r = 0, c = 0; for (int[] pearl : pearls) { r = Math.max(r, pearl[0]); c = Math.max(c, pearl[1]); } int[][] a = new int[r + 1][c + 1]; for (int[] pearl : pearls) { a[pearl[0]][pearl[1]] = 1; } int mn = Integer.MAX_VALUE; for (int i = 0; i <= r; i++) { for (int j = 0; j <= c; j++) { int t = 0; int[][] l = new int[3][2]; if (a[i][j] == 1) { Queue<int[]> queue = new LinkedList<>(); boolean[][] b = new boolean[r + 1][c + 1]; queue.offer(new int[]{i, j}); b[i][j] = true; while (!queue.isEmpty() && t < 3) { int[] poll = queue.poll(); int x = poll[0], y = poll[1]; if (a[x][y] == 1) { l[t][0] = x; l[t][1] = y; t++; } if (t == 3) { break; } for (int k = 0; k < 4; k++) { int nx = x + d[k][0], ny = y + d[k][1]; if (nx >= 0 && nx <= r && ny >= 0 && ny <= c && !b[nx][ny]) { b[nx][ny] = true; queue.offer(new int[]{nx, ny}); } } } } if (t == 3) { mn = Math.min(mn, getLength(l)); } } } return mn; } public int getLength(int[][] l) { int x1 = l[0][0], y1 = l[0][1]; int x2 = l[1][0], y2 = l[1][1]; int x3 = l[2][0], y3 = l[2][1]; int d1 = Math.abs(x1 - x2) + Math.abs(y1 - y2); int d2 = Math.abs(x2 - x3) + Math.abs(y2 - y3); int d3 = Math.abs(x1 - x3) + Math.abs(y1 - y3); return Math.min(Math.min(d1 + d2, d2 + d3), d1 + d3); }想想自己的解法就有点气