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

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

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

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

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

🌲 01.K小姐的字符串问题

问题描述

K小姐最近在研究一个有趣的字符串问题。给定两个仅由小写字母组成的字符串 和 ，K小姐想知道在 中最多有多少个 不重叠 的子串，使得每个子串都是 的 异位词。这里两个字符串是 异位词 当且仅当两个字符串长度相同且每个字母出现的次数都相同。

例如，当 = "abcbac"， = "abc" 时，在 中最多有 2 个不重叠的子串 "abc" 和 "bac"，它们都是 的异位词。

输入格式

第一行包含一个字符串 。

第二行包含一个字符串 。

输出格式

输出一个整数，表示在 中最多有多少个不重叠的 的异位词子串。

样例输入

abcbac
abc

样例输出

1

数据范围

题解

本题可以用滑动窗口的思想来解决。我们可以维护一个长度为 的滑动窗口，统计窗口内每个字母出现的次数，并与 中每个字母出现的次数进行比较。如果窗口内的字母出现次数与 完全相同，则找到了一个异位词子串，答案加 1，并将窗口向右移动 个位置，继续查找下一个异位词子串。如果字母出现次数不同，就将窗口向右移动一个位置，继续进行比较。

具体实现时，我们可以用两个数组 和 分别存储窗口内和 中每个字母出现的次数。初始时，将 中每个字母出现的次数记录在 中。然后枚举滑动窗口的起始位置 ，统计窗口内每个字母出现的次数，存入 中。如果 和 完全相同，就将答案加 1，并将窗口向右移动 个位置；否则将窗口向右移动一个位置。

时间复杂度 ，空间复杂度 ，其中 为字符集大小。

参考代码

• Python

def count_anagrams(s: str, t: str) -> int:
    n, m = len(s), len(t)
    if n < m:
        return 0
    
    cnt_t = [0] * 26
    for c in t:
        cnt_t[ord(c) - ord('a')] += 1
    
    cnt_s = [0] * 26
    ans = 0
    for i in range(n):
        cnt_s[ord(s[i]) - ord('a')] += 1
        if i >= m:
            cnt_s[ord(s[i - m]) - ord('a')] -= 1
        if cnt_s == cnt_t:
            ans += 1
            for j in range(m):
                cnt_s[ord(s[i - j]) - ord('a')] -= 1
    
    return ans

s = input()
t = input()
print(count_anagrams(s, t))

• Java

import java.util.Scanner;

public class Solution {
    public static int countAnagrams(String s, String t) {
        int n = s.length(), m = t.length();
        if (n < m) {
            return 0;
        }
        
        int[] cntT = new int[26];
        for (char c : t.toCharArray()) {
            cntT[c - 'a']++;
        }
        
        int[] cntS = new int[26];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            cntS[s.charAt(i) - 'a']++;
            if (i >= m) {
                cntS[s.charAt(i - m) - 'a']--;
            }
            if (Arrays.equals(cntS, cntT)) {
                ans++;
                for (int j = 0; j < m; j++) {
                    cntS[s.charAt(i - j) - 'a']--;
                }
            }
        }
        
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String t = sc.nextLine();
        System.out.println(countAnagrams(s, t));
    }
}

• Cpp

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int countAnagrams(string s, string t) {
    int n = s.size(), m = t.size();
    if (n < m) {
        return 0;
    }
    
    vector<int> cntT(26, 0);
    for (char c : t) {
        cntT[c - 'a']++;
    }
    
    vector<int> cntS(26, 0);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        cntS[s[i] - 'a']++;
        if (i >= m) {
            cntS[s[i - m] - 'a']--;
        }
        if (cntS == cntT) {
            ans++;
            for (int j = 0; j < m; j++) {
                cntS[s[i - j] - 'a']--;
            }
        }
    }
    
    return ans;
}

int main() {
    string s, t;
    getline(cin, s);
    getline(cin, t);
    cout << countAnagrams(s, t) << endl;
    return 0;
}

🍄 02.珍惜美食

问题描述

K小姐是一位美食家，她最近来到了一个美食之都。这个城市以街边小吃和特色餐厅闻名于世，每条街道上都有许多独特的美食店铺。

共有 家店铺坐落在同一条街道上，第 家店铺提供 份第 种美食。K小姐希望品尝尽可能多的美食，但由于时间和胃容量有限，她最多只能光顾 次店铺。每次光顾可以选择一段连续的店铺，并品尝这些店铺提供的所有美食。

为了不错过任何一种美味，K小姐希望在光顾店铺后，剩下的美食种类数量仍然大于 ，并且剩余美食中数量最少的那一种尽可能多。

请问，K小姐最多能让剩余美食中数量最少的那一种有多少份呢？

输入格式

第一行包含两个正整数 和 ，分别表示店铺数量和最多光顾次数。

第二行包含 个正整数，其中第 个数为 ，表示第 种美食的份数。

输出格式

输出一个整数，表示剩余美食中数量最少的那一种的最大可能份数。

样例输入

5 1
45 39 90 65 15

样例输出

45

数据范围

题解

这道题可以使用贪心的思想来解决。我们可以分情况讨论：

1. 当 时，不能光顾任何店铺，因此剩余美食中数量最少的就是所有美食中最少的那一种。
2. 当 时，可以选择光顾街道的左端或右端，剩余美食中数量最少的就是左右两端美食数量的较大值。
3. 当 时，可以先光顾左右两端，然后剩下的美食可以任意选择。此时剩余美食中数量最少的就是所有美食中最多的那一种。

因此，我们可以根据 的值，直接求出答案。

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

参考代码

• Python

n, k = map(int, input().split())
a = list(map(int, input().split()))

def solve(n, k, a):
    if k == 0:
        return min(a)
    if k == 1:
        return max(a[0], a[-1])
    return max(a)

res = solve(n, k, a)
print(res)

• 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();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        int res = solve(n, k, a);
        System.out.println(res);
    }
    
    public static int solve(int n, int k, int[] a) {
        if (k == 0) {
            return min(a);
        }
        if (k == 1) {
            return Math.ma