9.7-携程-笔试

心态爆炸，我真是废物，只做出一道完整的，其他拼凑起来总共不足两道，看了看不少佬都AK了，跟着他们的思路重新整理回顾一下吧。

第一题：排列统计

相邻两数和不为素数的序列个数 类似排列问题，用回溯算法

import java.util.Scanner;

public class Main {
    static int[] prime = new int[50];
    static int ans;
    static int[] val = new int[50];
    static int[] a = new int[50];
    //打表 生成素数序列 1是素数
    public static void generateP(){
        prime[1] = 1;
        prime[2] = 1;
        prime[3] = 1;
        for (int i = 4; i <= 40; i++) {
            int flag = 1;
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    flag = 0;
                    break;
                }
            }
            prime[i] = flag;
        }
    }
    // 回溯
    public static void getAns(int k, int n) {
        if (k == n) {
            ans++;
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (val[i] != 0){
                continue;
            }
            if (k != 0 && prime[a[k - 1] + i] != 0) {
                continue;
            }
            val[i] = 1;
            a[k] = i;
            getAns(k + 1, n);
            val[i] = 0;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        generateP();
        getAns(0, n);
        System.out.println(ans);
    }
}

第二题：you矩阵

给出n*m的字符矩阵，求三点分别为y o u的直角三角形个数，数据范围n,m≤1000行列统计，相乘，注意开long

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int[][] a = new int[1010][1010];
        // 5种状态 0-初始化、1-y、2-0、3-u、4-其他
        int[][] row = new int[1010][5];
        int[][] col = new int[1010][5];

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        // 标记 y、o、u位置
        for (int i = 0; i < n; i++) {
            String t = scanner.next();
            for (int j = 0; j < t.length(); j++) {
                if (t.charAt(j) == 'y')
                    a[i][j] = 1;
                else if (t.charAt(j) == 'o')
                    a[i][j] = 2;
                else if (t.charAt(j) == 'u')
                    a[i][j] = 3;
                else
                    a[i][j] = 4;
            }
        }
        // 标记每行 每列中 y o u出现的次数
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                row[i][a[i][j]]++;
                col[j][a[i][j]]++;
            }
        }

        long ans = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(a[i][j] == 1) {
                    //定位在y点，所在行的o或u数量 * 所在列的u或o数量
                    ans += row[i][2] * col[j][3];
                    ans += row[i][3] * col[j][2];
                }
                if(a[i][j] == 2) {
                    ans += row[i][1] * col[j][3];
                    ans += row[i][3] * col[j][1];
                }
                if(a[i][j] == 3) {
                    ans += row[i][2] * col[j][1];
                    ans += row[i][1] * col[j][2];
                }
            }
        }
        System.out.println(ans);
    }
}

第三题：元素修改

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

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long T = scanner.nextLong();
        while (T-- > 0) {
            long n = scanner.nextLong();
            long l = scanner.nextLong();
            long r = scanner.nextLong();
            long[] v = new long[(int) n];
            long sum = 0;
            long cnt1 =0;
            long cnt2 =0;
            for (int i = 0; i < n; i++) {
                v[i] = scanner.nextLong();
                sum += v[i];
                if(v[i]>r){
                    cnt1+=v[i]-r;
                }else if(v[i]<l){
                    cnt2+=l-v[i];
                }
            }
            // 边界判断
            if (sum < l*n || sum > r*n){
                System.out.println(-1);
            }else {
                System.out.println(Math.max(cnt1, cnt2));
            }
        }
        scanner.close();
    }
}

第四题：好串

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

参考这位大佬的代码:https://www.nowcoder.com/discuss/529398383690137600维护前缀和，遇到0加一，遇到1减一

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String a = scanner.next();
        long ans = 0;
        int t = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) == '0') {
                if (t < 0) {
                    t = 0;
                }
                t++;
                if (t > 0) {
                    ans += t;
                }
            } else if (a.charAt(i) == '1') {
                t--;
                if (t > 0) {
                    ans += t;
                }
            }
        }
        System.out.println(ans);
    }
}