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

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

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

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

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

🌈 毒秋招笔试，来啦！！！

🍥 本次很多粉丝反馈只做出来第一题，是的这次后面两题都不好做，T2的贪心容易想歪，T3也需要一些思维+图论的知识，总体难度不低

1️⃣ 这题比较打卡，但要对于剩余次数的处理

2️⃣ 贪心，考虑每个点最多被换两次，所以直接对其下标的位置进行贪心

3️⃣ 图论+最短路+思维题，先dijkstra跑一遍最短路后，然后判断新的边是否必须加即可

🫚 01.字符串大小写转换 评测链接🔗

问题描述

K小姐拿到了一个由大小写字母构成的字符串，长度为 。她想通过 次操作，将字符串中尽可能多的字母转换为大写字母。每次操作，她可以选择字符串中的任意一个字母，将其从小写转换为大写，或从大写转换为小写。

请你帮助K小姐计算，经过 次操作后，字符串中最多能有多少个大写字母？

输入格式

第一行包含两个正整数 和 ，分别表示字符串的长度和操作次数，两个数之间用空格隔开。

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

输出格式

输出一个整数，表示经过 次操作后，字符串中最多能有的大写字母数量。

样例输入

1 3
A

样例输出

0

样例解释

对于样例，字符串只有一个字母。无论操作多少次，最终的字符串要么是 "A"，要么是 "a"。因此，最多只能有 0 个大写字母。

数据范围

题解

这道题可以这样考虑：先统计字符串中原本有多少个小写字母和大写字母。

• 如果操作次数 足够多，那么可以先把所有小写字母都转换成大写字母。
• 如果 还有剩余，再考虑是否需要把一些大写字母转换回小写字母。

统计字符串中小写字母的数量 和大写字母的数量 。

1. 如果 ，说明操作次数足够将所有小写字母转换为大写字母。此时我们先把所有小写字母转换为大写字母，剩余的操作次数为 。
   • 如果 是偶数，那么我们不需要再进行转换，因为偶数次的转换会让字母的大小写状态回到原点。此时大写字母的数量就是字符串的总长度 。
   • 如果 是奇数，那么我们需要再将一个大写字母转换为小写字母。此时大写字母的数量就是 。
2. 如果 ，说明操作次数不足以将所有小写字母转换为大写字母。此时我们只需要将 个小写字母转换为大写字母即可。最终的大写字母数量为 。

参考代码

• Python

def solve(n, k, s):
    # 统计小写字母和大写字母的数量
    lower = sum(c.islower() for c in s)
    upper = n - lower
    
    if k >= lower:
        # 操作次数足够将所有小写字母转换为大写字母
        extra = k - lower
        if extra % 2 == 0:
            return n
        else:
            return n - 1
    else:
        # 操作次数不足以将所有小写字母转换为大写字母
        return upper + k

# 读取输入
n, k = map(int, input().split())
s = input().strip()

# 调用函数并输出结果
print(solve(n, k, s))

• 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();
        
        System.out.println(solve(n, k, s));
    }
    
    public static int solve(int n, int k, String s) {
        // 统计小写字母和大写字母的数量
        int lower = 0;
        for (char c : s.toCharArray()) {
            if (Character.isLowerCase(c)) {
                lower++;
            }
        }
        int upper = n - lower;
        
        if (k >= lower) {
            // 操作次数足够将所有小写字母转换为大写字母
            int extra = k - lower;
            if (extra % 2 == 0) {
                return n;
            } else {
                return n - 1;
            }
        } else {
            // 操作次数不足以将所有小写字母转换为大写字母
            return upper + k;
        }
    }
}

• Cpp

#include <iostream>
#include <string>
using namespace std;

int solve(int n, int k, string s) {
    // 统计小写字母和大写字母的数量
    int lower = 0;
    for (char c : s) {
        if (islower(c)) {
            lower++;
        }
    }
    int upper = n - lower;
    
    if (k >= lower) {
        // 操作次数足够将所有小写字母转换为大写字母
        int extra = k - lower;
        if (extra % 2 == 0) {
            return n;
        } else {
            return n - 1;
        }
    } else {
        // 操作次数不足以将所有小写字母转换为大写字母
        return upper + k;
    }
}

int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    
    cout << solve(n, k, s) << endl;
    
    return 0;
}

🎀 02.K小姐的珠宝交换评测链接🔗

问题描述

K小姐是一位珠宝设计师,她有一串由 颗宝石组成的项链。这些宝石分别由 到 标号,且没有重复的宝石。

为了让项链看起来更加美观,K小姐可以选择相邻的两颗宝石进行交换。不过,每颗宝石最多只能被交换两次。

经过若干次交换后,K小姐希望得到一串字典序最大的项链。所谓字典序,就是从项链的第一颗宝石开始,逐个比较对应位置宝石的标号大小,直到找到第一个不同的宝石,通过比较这两颗宝石的标号大小来决定两串项链的字典序大小。

现在,K小姐想知道,在满足每颗宝石最多被交换两次的前提下,她能得到的字典序最大的项链是什么样的?

输入格式

第一行包含一个正整数 ,表示项链的宝石数量。

第二行包含 个由空格分隔的正整数 ,表示初始时项链上每颗宝石的标号。

输出格式

输出一行,包含 个由空格分隔的正整数,表示字典序最大的项链中每颗宝石的标号。

样例输入

8
3 7 2 1 6 5 4 8

样例输出

7 3 6 5 2 1 8 4

数据范围

题解

贪心

假设当前正在考虑第 个位置的宝石。如果这颗宝石已经被交换过两次了,那我们就不能再移动它,只能考虑下一个位置。

如果这颗宝石还可以交换,我们就在它之后的宝石中(最多往后看两个位置),找到标号最大的那颗宝石,将它交换到第 个位置。

为什么最多只看后面两个位置呢?

• 因为每颗宝石最多只能交换两次，如果它后面的宝石要移动到第 个位置,就要交换至少 次。所以我们最多只能考虑 和 这两个位置。

参考代码

• Python

def rearrange_jewelry(N, jewelry):
    # 记录每颗宝石的交换次数
    swap_count = [2] * (N + 1)  
    
    for i in range(N):
        if swap_count[jewelry[i]] == 0:
            continue
        
        max_idx = i
        for j in range(i + 1, min(N, i + 3)):
            if swap_count[jewelry[j]] < (j - i):
                break
            if jewelry[j] > jewelry[max_idx]:
                max_idx = j
        
        if max_idx != i:
            max_val = jewelry[max_idx]
            for j in range(max_idx, i, -1):
                jewelry[j] = jewelry[j - 1]
                swap_count[jewelry[j]] -= 1
            jewelry[i] = max_val
            swap_count[jewelry[i]] -= (max_idx - i)
    
    return jewelry

# 读取输入
N = int(input())
jewelry = list(map(int, input().split()))

# 调用函数
result = rearrange_jewelry(N, jewelry)

# 输出结果
print(' '.join(map(str, result)))

• Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 读取宝石数量
        int N = Integer.parseInt(br.readLine());
        
        // 读取初始项链
        int[] jewelry = Arrays.stream(br.readLine().split(" "))
                             .mapToInt(Integer::parseInt)
                             .toArray();
        
        // 调用函数
        int[] result = rearrangeJewelry(N, jewelry);
        
        // 输出结果
        System.out.println(Arrays.toString(result).replaceAll("[\\[\\],]", ""));
    }
    
    private static int[] rearrangeJewelry(int N, int[] jewelry) {
        // 记录每颗宝石的交换次数
        int[] swapCount = new int[N + 1];
        Arrays.fill(swapCount, 2);
        
        for (int i = 0; i < N; i++) {
            if (swapCount[jewelry[i]] == 0) {
                continue;
            }
            
            int maxIdx = i;
            for (int j = i + 1; j < Math.min(N, i + 3); j++) {
                if (swapCount[jewelry[j]] < (j - i)) {
                    break;
                }
                if (jewelry[j] > jewelry[maxIdx]) {
                    maxIdx = j;
                }
            }
            
            if (maxIdx != i) {
                int maxVal = jewelry[maxIdx];
                System.arraycopy(jewelry, i, jewelry, i + 1, maxIdx - i);
                System.arraycopy(swapCount, jewelry[i], swapCount, jewelry[i + 1], maxIdx - i);
                jewelry[i] = maxVal;
                swapCount[jewelry[i]] -= (maxIdx - i);
                
                for (int j = i + 1; j <= maxIdx; j++) {
                    swapCount[jewelry[j]]--;
                }
            }
        }
        
        return jewelry;
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> rearrange_jewelry(int N, vector<int>& jewelry) {
    // 记录每颗宝石的交换次数
    vector<int> swap_count(N + 1, 2);
    
    for (int i = 0; i < N; i++) {
        if (swap