💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🎊 01.最短等价子串

问题描述

K 小姐接到了一个字符串处理的任务。给定一个长度为 的小写字母字符串 ，定义字符串的权值为相邻两个字符相同的对数。例如，字符串 aaabbc 的权值为 3。

现在，K 小姐需要在字符串 中找到一个长度最短的子串，使得该子串的权值恰好等于 。你能帮助她完成这个任务吗？

输入格式

第一行包含两个正整数 和 ，分别表示字符串 的长度和目标权值。

第二行包含一个长度为 的字符串 ，仅由小写字母组成。

输出格式

输出一个整数，表示满足条件的最短子串的长度。如果不存在这样的子串，则输出 -1。

样例输入

6 2
aaabbc

样例输出

3

数据范围

题解

本题可以使用双指针算法求解。我们用两个指针 和 分别表示当前子串的起点和终点。初始时，两个指针都指向字符串的起点。

我们不断地向右移动指针 ，直到当前子串的权值大于等于 。此时，我们尝试向右移动指针 ，缩小当前子串的长度，直到子串的权值恰好等于 。在这个过程中，我们记录下满足条件的最短子串长度。

重复这个过程，直到指针 到达字符串的末尾。最终得到的最短子串长度即为答案。

参考代码

• Python

n, k = map(int, input().split())
s = input()

res = 0
ans = n + 1
i = 0
j = 1

while i < n:
    if i > 0 and s[i] == s[i - 1]:
        res -= 1
    
    while j < n and res < k:
        if s[j] == s[j - 1]:
            res += 1
        j += 1
    
    if res == k:
        ans = min(ans, j - i)
    
    i += 1

print(ans if ans != n + 1 else -1)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        String s = sc.next();
        
        int res = 0;
        int ans = n + 1;
        int i = 0;
        int j = 1;
        
        while (i < n) {
            if (i > 0 && s.charAt(i) == s.charAt(i - 1)) {
                res--;
            }
            
            while (j < n && res < k) {
                if (s.charAt(j) == s.charAt(j - 1)) {
                    res++;
                }
                j++;
            }
            
            if (res == k) {
                ans = Math.min(ans, j - i);
            }
            
            i++;
        }
        
        System.out.println(ans == n + 1 ? -1 : ans);
    }
}

• Cpp

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    
    int res = 0;
    int ans = n + 1;
    int i = 0;
    int j = 1;
    
    while (i < n) {
        if (i > 0 && s[i] == s[i - 1]) {
            res--;
        }
        
        while (j < n && res < k) {
            if (s[j] == s[j - 1]) {
                res++;
            }
            j++;
        }
        
        if (res == k) {
            ans = min(ans, j - i);
        }
        
        i++;
    }
    
    cout << (ans == n + 1 ? -1 : ans) << endl;
    
    return 0;
}

🎀 02.完美排列对

问题描述

K 小姐是一位数学爱好者，她正在研究排列的性质。给定一个长度为 的整数数组 ，K 小姐希望构造两个长度为 的排列 和 ，满足以下条件：

1. 对于任意 ，都有 。
2. 对于任意 ，都有 。

你能帮助 K 小姐找到这样的排列对吗？

注：排列是指一个长度为 的数组，其中 到 每个元素恰好出现一次。

输入格式

第一行包含一个正整数 ，表示数组 的长度。

第二行包含 个整数，表示数组 的元素，相邻两个整数之间用单个空格隔开。

输出格式

如果不存在满足条件的排列对，则输出一行，包含一个整数 。

否则输出两行，第一行包含 个整数，表示排列 ；第二行包含 个整数，表示排列 。相邻两个整数之间用单个空格隔开。如果存在多组解，输出任意一组即可。

样例输入

3
2 2 0

样例输出

1 3 2
3 1 2

数据范围

题解

根据题目条件，可以得到 和 的关系：

由条件 1 可知， 和 的和是固定的，都等于 。因此，可以预处理出所有可能的 对，并按照 的值进行分组。

接下来，将输入的数组 排序，然后与预处理得到的 的值进行比较。如果两个数组排序后不相同，说明无解，直接输出 。

如果两个数组排序后相同，则按照 数组的顺序，依次从对应的 分组中取出一对值，即可得到满足条件的排列 和 。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
b = a[:]
c = [abs(i - (n - 1 - i)) for i in range(n)]
mp = defaultdict(list)
for i in range(n):
    mp[c[i]].append((i, n - 1 - i))

b.sort()
c.sort()

if b != c:
    print(-1)
else:
    p = [0] * n
    q = [0] * n
    for i in range(n):
        x, y = mp[a[i]].pop()
        p[i] = x + 1
        q[i] = y + 1
    print(*p)
    print(*q)

• Java

import java.util.*;

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