奇安信服务端开发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);
}