9.7 携程笔试面经 - 编程题 & 题解

考试时间：2023-09-07（2小时）

考试平台： 牛客网

T1 游游的排列统计

​ 游游想知道，有多少个长度为n的排列满足任意两个相邻元素之和都不是素数。你能帮帮她吗?我们定义，长度为n的排列值一个长度为n的数组，其中1到n每个元素恰好出现了一次。

输入描述

一个正整数n。

2 ≤ n ≤10

输出描述

满足条件的排列数量。

示例1

输入：
5

输出：
4
说明：
共有以下 4 种合法排列:
[1,3,5,4,2]
[3,1,5,4,2]
[2,4,5,1,3]
[2,4,5,3,1]

题解

数量不大，简单回溯的方式暴力所有情况然后返回合法的排列数量。

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Solution solution = new Solution();
        System.out.println(solution.solve(n));
    }
}


class Solution {
    int cnt;

    // 素数列表
    static Set<Integer> primeSet = new HashSet<>(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19));

    public int solve(int n) {
        this.cnt = 0;
        boolean[] vis = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            vis[i] = true;
            dfs(n, vis, i, 1);
            vis[i] = false;
        }
        return this.cnt;
    }

    /**
     *
     * @param n     元素个数
     * @param vis   使用状态
     * @param pre   前一个数
     * @param idx   当前第 idx 个数
     */
    public void dfs(int n, boolean[] vis, int pre, int idx) {
        if (idx == n) {
            cnt++;
            return;
        }
        for (int i = 1; i <= n; i++) {
            int sum = pre + i;
            if (!vis[i] && !primeSet.contains(sum)) {
                vis[i] = true;
                dfs(n, vis, i, idx + 1);
                vis[i] = false;
            }
        }
    }
}

T2 游游的you矩阵

游游拿到了一个字符矩阵，她想知道有多少个三角形满足以下条件:

1. 三角形的三个顶点分别是 y、o、u 字符。

2. 三角形为直角三角形，且两个直角边一个为水平、另一个为垂直。

输入描述

第一行输入两个正整数n,m，用空格隔开，代表矩阵的行数和列数。

接下来的n行，每行输入一个长度为m的字符串，代表游游拿到的矩阵。

1 ≤ n, m ≤ 1000

输出描述

输出一个整数，代表满足条件的三角形个数。

示例1

输入：
2 3
you
our
输出：
3
说明： 如下图

题解

前缀和

以每个点作为直角的点，有 8 中可能的情况。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        String[] a = new String[n];
        for (int i = 0; i < n; i++) a[i] = scanner.next();

        // 【水平方向】前缀和
        int[][] y = new int[n][m + 1];
        int[][] o = new int[n][m + 1];
        int[][] u = new int[n][m + 1];
        for (int i = 0; i < n; i++) {
            char[] w = a[i].toCharArray();
            for (int j = 0; j < m; j++) {
                y[i][j + 1] = y[i][j] + (w[j] == 'y' ? 1 : 0);
                o[i][j + 1] = o[i][j] + (w[j] == 'o' ? 1 : 0);
                u[i][j + 1] = u[i][j] + (w[j] == 'u' ? 1 : 0);
            }
        }

        //【垂直方向】前缀和
        int[][] yColSum = new int[n + 1][m];
        int[][] oColSum = new int[n + 1][m];
        int[][] uColSum = new int[n + 1][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                yColSum[j + 1][i] = yColSum[j][i] + (a[j].charAt(i) == 'y' ? 1 : 0);
                oColSum[j + 1][i] = oColSum[j][i] + (a[j].charAt(i) == 'o' ? 1 : 0);
                uColSum[j + 1][i] = uColSum[j][i] + (a[j].charAt(i) == 'u' ? 1 : 0);
            }
        }

        long rs = 0;
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < m; col++) {
                final char C = a[row].charAt(col);
                // 下面变量的含义，参加上图, y1 表示字符ｙ在边 1 的数量
                int y1 = yColSum[row][col], o1 = oColSum[row][col], u1 = uColSum[row][col];
                int y2 = y[row][m] - y[row][col], o2 = o[row][m] - o[row][col], u2 = u[row][m] - u[row][col];
                int y3 = yColSum[n][col] - yColSum[row][col], o3 = oColSum[n][col] - oColSum[row][col], u3 = uColSum[n][col] - uColSum[row][col];
                int y4 = y[row][col], o4 = o[row][col], u4 = u[row][col];


                if (C == 'y') {