秋招笔试不会的题汇总

本文最后更新于：2024年2月12日 晚上

8/27-360笔试

给一个没有重复数字的数组a，进行快排，但是每次根据划分点划分完后便会直接返回，不会递归的进行快排，现给定划分数组b（里边的数字代表a中的值），求根据b数组中的划分点进行快排划分后，输出最后的排序结果；

例子：
    a=[1,9,2,8,3,7,4,6,5]
    b=[3,7]
输出：
    1 2 3 4 6 5 7 9 8
```

### 8/27-京东笔试

给一个数n，求长度为n的漂亮数组有多少个？漂亮数组定义：必须至少包含两个`red`子串，例如`redred`,`redrred`是漂亮的，而`redder`不是。

每一个位置都可以是任意小写字母，结果对`1e9 + 7`取模

$1\le n \le 1e6$

```java
输入：
    6
输出：
    1
static int MOD = (int) 1e9 + 7;

public static int count(int n) {
    if (n < 6) return 0;
    long[] f = new long[n + 10]; // 长度为i且含有0个red子串的个数
    long[] g = new long[n + 10]; // 长度为i且含有1个red子串的个数
    long[] h = new long[n + 10]; // 长度i且至少含有2个red子串的个数
    for (int i = 1; i <= 3; i++) f[i] = pow(26, i);
    f[3]--;
    g[3] = 1;
    for (int i = 4; i <= n; i++) {
        f[i] = (f[i - 1] * 26 % MOD - f[i - 3] + MOD) % MOD;
        g[i] = (g[i - 1] * 26 % MOD - g[i - 3] + f[i - 3] + MOD) % MOD;
        h[i] = (pow(26, i) - f[i] - g[i] + 2L * MOD) % MOD;
    }
    return (int) (h[n]);
}

public static long pow(long a, long b) {
    long res = 1;
    while (b > 0) {
        if ((b & 1) == 1) res = (res * a) % MOD;
        b >>= 1;
        a = (a * a) % MOD;
    }
    return res;
}

8/28-小红书笔试

偶数n表示有n个人，编号为1-n，给一个长度为 n-1 的的数组a，表示编号为$a_{i}$和i+1的人是朋友，现在要将这些人两两分组，求最后分完组后，互为朋友的最大组数？

$2\le n \le 1000$

输入：
    6
    1 2 2 3 3
输出：
    2

二分图最大匹配问题，板子

static int n;
static void solve(){
    n = in.nextInt();
    int[][] adj = new int[n][n];
    for (int i = 0; i < n - 1; i++) {
        int x = in.nextInt() - 1;
        adj[x][i + 1] = 1;
        adj[i + 1][x] = 1;
    }
    out.println(getMax(adj) / 2);
}

static int getMax(int[][] adj) {
    int ans = 0;
    int[] linked = new int[n];
    Arrays.fill(linked, -1);
    for (int i = 0; i < n; i++) {
        boolean[] seen = new boolean[n];
        if (dfs(adj, seen, linked, i)) {
            ans++;
        }
    }
    return ans;
}

static boolean dfs(int[][] adj, boolean[] seen, int[] linked, int x) {
    for (int i = 0; i < n; i++) {
        if (!seen[i] && adj[x][i] == 1) {
            seen[i] = true;
            if (linked[i] == -1 || dfs(adj, seen, linked, linked[i])) {
                linked[i] = x;
                return true;
            }
        }
    }
    return false;
}

8/29-满帮笔试（这题不会纯属脑子抽了）

给一个长度为n的数组a，每一个数各不相同，x轴上从$[-210^9,210^9]$的每一个位置上都有一个空杯子，a中的数表示在$a_i$位置处的杯子里有水，每一次操作都可以将一杯水倒进任何一个空杯子里，求将这n杯水置为位置相邻时最小的操作次数？

$1\le n \le 10^5$

$-10^9 \le a_i \le 10^9$

输入：
    6
    -2 0 2 1 3 6
输出：
    1
解释：
    将位置6的水倒到位置-1即可，-2 -1 0 1 2 3
static void solve(){
    int n = in.nextInt();
    int[] arr = new int[n];
    for (int i = 0 ; i < n; i++) {
        arr[i] = in.nextInt();
    }
    Arrays.sort(arr);
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        // 以i为左端点，求可能的右端点，计算左右端点里的个数，剩余的就是要移动的
        int l = i, r = n - 1;
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (arr[mid] - arr[i] + 1 < n) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        if (arr[l] - arr[i] + 1 > n) l--;
        ans = Math.min(ans, n - (l - i + 1));
    }
    out.println(ans);
}

9/13-微众银行

https://atcoder.jp/contests/abc237/tasks/abc237_f

给定n、m，n表示序列的长度，m表示序列中每个数的大小在[1,m]之间，构建长度为n的序列，序列的最长上升子序列的长度为3，这样的序列有多少个？结果对$10^9+7$取模

$3\le n \le 500$

$1\le m \le 10$

9/14-蔚来

定义$f(i)$表示数字$i$截取二进制表示中的最低位1及其后面表示的表示的数字，例如$6=(110)b$,$f(6)=(10)_b=2$，给定一个数字n，求$\sum {i=1} ^n \frac{i}{f(i)}$

$1\le n \le 10^9$

input:
	5
output:
	11
// 根据周期性来计算

9/17-滴滴

给一个字符串s，里边又一些?可替换为[0,9]之间的任意数字，求s能表示的最小整数，需要满足下面三个条件：

1.数字各位数之和为3的倍数

2.任意相邻的两个数字不能相同

3.不能包含前导0

字符串长度小于等于100000

input:
	?9
output:
	39

input:
	????
output:
	1014
// 64%
static void solve(){
    String s = in.nextLine();
    char[] a = s.toCharArray();
    int tot = 0;
    int need = 0;
    for (int i = 0; i < s.length(); i++) {
        if (a[i] == '?') need++;
        else tot += a[i] - '0';
    }
    if (need == 0) {
        out.println(s);
        return;
    }
    if (s.length() == 1) {
        out.println("3");
        return;
    }
    for (int i = 0; i < s.length(); i++) {
        if (a[i] == '?') {
            if (i == 0) {
                a[i] = (a[i + 1] == '1' ? '2' : '1');
            } else if (i == s.length() - 1) {
                a[i] = (a[i - 1] == '0' ? '1' : '0');
            } else {
                if (a[i + 1] == '?') {
                    if (a[i - 1] == '0') a[i] = '1';
                    else a[i] = '0';
                } else {
                    for (char j = '0'; j <= '9'; j++) {
                        if (j != a[i - 1] && j != a[i + 1]) {
                            a[i] = j;
                            break;
                        }
                    }
                }
            }
            tot += a[i] - '0';
        }
    }
    int n = s.length();
    if (tot % 3 == 0) {
        out.println(new String(a));
    } else {
        int more = 3 - (tot % 3);
        if (a[n - 1] + more <= '9') {
            a[n - 1] += more;
        } else {
            int tmp = '9' + more - a[n - 1];
            a[n - 1] = '9';
            a[n - 2] += tmp;
        }
        if (a[n - 1] == a[n - 2]) {
            if (a[n - 1] + 3 <= '9') a[n - 1] += 3;
            else {
                int tmp = '9' - a[n - 1];
                a[n - 1] = '9';
                a[n - 2] += tmp;
            }
        }
        out.println(new String(a));
    }
}