Java 笔试【xc-0907】

面试要线下参加，是为了检验我的诚心吗？

题目的内容参考：https://www.nowcoder.com/discuss/529638802495721472

T1：相邻的数不能是合数

不知道咋做，用的 dfs。

public static void main11(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int ans = 0;
            int[] arr = new int[n];
            boolean[ ] visited = new boolean[n];
            ans = dfs(0, visited, arr);
            System.out.println(ans);

        }
    }

    private static int dfs(int idx, boolean[] visited, int[] arr) {
        if (idx == visited.length) return 1;
        int ans = 0;
        for (int i = 0; i < visited.length; i++) {
            if (visited[i]) continue;
            if (idx > 0 && isP(arr[idx - 1] + 1 + i + 1)) continue;
            visited[i] = true;
            arr[idx] = i;
            ans += dfs(idx + 1, visited, arr);
            arr[idx] = 0;
            visited[i] = false;
        }
        return ans;
    }

    private static boolean isP(int num) {
        switch (num) {
            case 2:
            case 4:
            case 6:
            case 8:
            case 9:
            case 10:
            case 12:
            case 14:
            case 15:
            case 16:
            case 18:
            case 20:
                return false;
            default:
                return true;
        }
    }

T2：三角形

给出n*m的字符矩阵，求三点分别为y o u的直角三角形个数。只过了10%。

思路：记录 y 和 o 的位置，for 循环，获取合格的 u 的位置。时间复杂度 (n*m) * (n*m)。

这个思路错误的地方在于，我们其实只需要记录每行每列的 y 和 o，不需要记录每个 y 和 o。

public static void main22(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int row = in.nextInt();
            int col = in.nextInt();
            List<int[]> ys = new ArrayList<>();
            List<int[]> os = new ArrayList<>();

            Map<Integer, Integer> xCnts = new HashMap<>();
            Map<Integer, Integer> yCnts = new HashMap<>();
//            Map<Integer, Integer> cnts = new HashMap<>();
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < row; i++) {
                String str = in.next();
                char[] cs = str.toCharArray();
                for (int j = 0; j < col; j++) {
                    char c = cs[j];
                    switch (c) {
                        case 'y': ys.add(new int[]{i, j}); break;
                        case 'o': os.add(new int[]{i, j}); break;
                        case 'u':
                            add(xCnts, i);
                            add(yCnts, j);
                            set.add(i * col + j);
                            break;
                        default: break;
                    }
                }
            }
            int ans = 0;
            for (int[] y: ys) {
                int x1 = y[0];
                int y1 = y[1];
                for (int[] o: os) {
                    int x2 = o[0];
                    int y2 = o[1];

                    if (x1 == x2) {
                        // 已经有水平线
                        ans += yCnts.getOrDefault(y1, 0) + yCnts.getOrDefault(y2, 0);
                    } else if (y1 == y2) {
                        // 已经有竖直线
                        ans += xCnts.getOrDefault(x1, 0) + xCnts.getOrDefault(x2, 0);
                    } else {
                        // {x1, y2}
                        // {x2, y1}
                        ans += set.contains(x1 * col + y2) ? 1 : 0;
                        ans += set.contains(x2 * col + y1) ? 1 : 0;
                    }
                }
            }
            System.out.println(ans);
        }
    }

    public static void add(Map<Integer, Integer> map, int key) {
        if (map.containsKey(key)) {
            map.put(key, map.get(key) + 1);
        } else {
            map.put(key, 1);
        }
    }

T3：数组操作次数

给出n个整数，每次可以选两个分别+1-1，求使得n个数都位于[l, r]的最少操作次数，不存在则输出-1枚举每个数，对小于左边界的数用一个变量记录差值，大于有边界的变量用另一个数记录差值，最后输出两个变量中大的那个。

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int t = in.nextInt();

            for (int i = 0; i < t; i++) {
                int n = in.nextInt();
                int l = in.nextInt();
                int r = in.nextInt();
                int[] arr = new int[n];
                long sum = 0L;
                List<Integer> nums = new ArrayList<>();
                long lack = 0;
                long remain = 0;
                for (int j = 0; j < n; j++) {
                    int num = in.nextInt();
                    arr[j] = num;
                    sum += num;
                    if (num < l || num > r) nums.add(num);
                    if (num < l) lack += l - num;
                    if (num > r) remain += num - r;
                }
                if (sum < (long)l * n || sum > (long)r * n) {
                    System.out.println(-1);
                    continue;
                }
                System.out.println(Math.max(lack, remain));
            }
        }
    }

T4：好串

给一个0和1组成的字符串，求子串中有多少“好串”。对“好串”的定义是：所有的前缀子串中，0的数量全部严格大于1的数量。

思路：主要想法是用前缀和+单调栈。前缀和在遍历到 1 则加 1，遇到 0 则减 1。对于每一个左端点来说，合法的右端点是这个区间的前缀和值都大于等于左端点的前缀和值。因此考虑记录每一个位置的前缀和值，查询时用单调栈找到左端点的第一个小于左端点的前缀和值的位置，减一下就得到对应的区间对答案的贡献。时间复杂度O(nlogn)。

参考：https://www.nowcoder.com/feed/main/detail/17274cfeb3c143cdb4dc6e2bba0cd5df?sourceSSR=search