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

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

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

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

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

🍥 本次T3难度较大

1️⃣ 贪心，最近笔试很多这种题

2️⃣ 找规律，如果能猜到和奇偶性相关，这题也就能出了

3️⃣ 博弈论DP，边界比较难调，难度不小

🌲 01.字母串进化

问题描述

LYA 是一位热爱密码学的大学生。她最近在研究一种特殊的字母串加密方法。这种方法需要不断生成下一个字典序的字母串。然而，手动计算下一个字母串既耗时又容易出错。因此，LYA 希望开发一个程序来自动化这个过程。

你的任务是帮助 LYA 编写一个程序，该程序能够接收一个小写字母组成的字符串，并生成按字典序排列的下一个相同长度的字符串。

输入格式

输入包含一行，给出一个字符串 ： 字符串 仅由小写字母组成。

输出格式

输出一行，包含与输入字符串长度相同的下一个字典序字母串。 如果不存在这样的字母串，则输出 -1。

样例输入

zz

样例输出

-1

样例输入

aa

样例输出

ab

数据范围

• 
• 字符串 中的字符均为小写字母。

题解

贪心

1. 从字符串的末尾开始向左遍历。
2. 找到第一个可以增加的字符（即不是 'z' 的字符）。
3. 将该字符增加 1。
4. 将该字符右侧的所有字符重置为 'a'。
5. 如果整个字符串都是 'z'，则返回 -1，表示没有下一个字符串。

参考代码

• Python

def next_string(s):
    # 将字符串转换为列表，便于修改
    chars = list(s)
    n = len(chars)
    
    # 从右向左查找第一个可以增加的字符
    for i in range(n - 1, -1, -1):
        if chars[i] != 'z':
            # 找到可以增加的字符，将其增加1
            chars[i] = chr(ord(chars[i]) + 1)
            
            # 将右侧的所有字符重置为'a'
            for j in range(i + 1, n):
                chars[j] = 'a'
            
            return ''.join(chars)
    
    # 如果所有字符都是'z'，则没有下一个字符串
    return '-1'

# 读取输入
s = input().strip()

# 计算并输出结果
result = next_string(s)
print(result)

• Java

import java.util.Scanner;

public class Main {
    public static String nextString(String s) {
        // 将字符串转换为字符数组，便于修改
        char[] chars = s.toCharArray();
        int n = chars.length;
        
        // 从右向左查找第一个可以增加的字符
        for (int i = n - 1; i >= 0; i--) {
            if (chars[i] != 'z') {
                // 找到可以增加的字符，将其增加1
                chars[i]++;
                
                // 将右侧的所有字符重置为'a'
                for (int j = i + 1; j < n; j++) {
                    chars[j] = 'a';
                }
                
                return new String(chars);
            }
        }
        
        // 如果所有字符都是'z'，则没有下一个字符串
        return "-1";
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine().trim();
        
        String result = nextString(s);
        System.out.println(result);
        
        scanner.close();
    }
}

• Cpp

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

string nextString(string s) {
    int n = s.length();
    
    // 从右向左查找第一个可以增加的字符
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] != 'z') {
            // 找到可以增加的字符，将其增加1
            s[i]++;
            
            // 将右侧的所有字符重置为'a'
            for (int j = i + 1; j < n; j++) {
                s[j] = 'a';
            }
            
            return s;
        }
    }
    
    // 如果所有字符都是'z'，则没有下一个字符串
    return "-1";
}

int main() {
    string s;
    cin >> s;
    
    string result = nextString(s);
    cout << result << endl;
    
    return 0;
}

📚 02.LYA的图书馆整理

问题描述

LYA是一位图书馆管理员，她负责整理一排书架上的图书。书架上有 本互不相同的书，每本书都有一个唯一的编号。LYA希望将这些书按照编号从小到大排列，但她只能使用两种整理方法：

1. 选择相邻的两本书，交换它们的位置。
2. 选择相邻的三本书，将它们的顺序完全颠倒。

LYA发现，无论书架上的书如何排列，总是可以通过有限次上述操作将所有书排列成升序。然而，她注意到如果只使用第一种方法，整理过程会变得非常繁琐，就像冒泡排序一样低效。

为了提高效率，LYA决定尽可能多地使用第二种方法，只在必要时才使用第一种方法。现在，她想知道在将所有书排列成升序的前提下，最少需要使用多少次第一种方法。

输入格式

第一行输入一个正整数 ，表示书架上书的数量。

接下来 行，每行一个整数 ，表示每本书的编号。保证这些编号互不相同。

输出格式

输出一个整数，表示LYA最少需要使用的第一种方法的次数。

样例输入

4
2
4
3
1

样例输出

1

数据范围

题解

贪心+找规律

这个问题的关键在于观察每本书的当前位置与其最终位置之间的关系。

1. 首先，我们需要知道每本书的最终位置。这可以通过对输入的编号进行排序来确定。

2. 然后，我们比较每本书的当前位置与其最终位置。如果一本书需要移动奇数个位置才能到达其最终位置，那么它必然需要使用一次第一种操作（两本书交换）。

3. 对于需要移动偶数个位置的书，我们可以只使用第二种操作（三本书颠倒）来完成移动。

4. 最后，我们统计需要奇数次移动的书的数量，这个数量除以2就是最少需要的第一种操作次数。

这个解法的时间复杂度是 ，主要来自于对书籍编号的排序。空间复杂度是 ，用于存储排序后的编号和位置映射。

参考代码

• Python

def min_swap_operations(n, books):
    # 创建书籍编号的有序列表和位置映射
    sorted_books = sorted(books)
    position_map = {num: i for i, num in enumerate(sorted_books)}
    
    # 统计需要奇数次移动的书的数量
    odd_moves = sum(1 for i, book in enumerate(books) if abs(i - position_map[book]) % 2 == 1)
    
    # 返回最少需要的第一种操作次数
    return odd_moves // 2

# 读取输入
n = int(input())
books = [int(input()) for _ in range(n)]

# 计算并输出结果
result = min_swap_operations(n, books)
print(result)

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] books = new int[n];
        
        // 读取书籍编号
        for (int i = 0; i < n; i++) {
            books[i] = scanner.nextInt();
        }
        
        System.out.println(minSwapOperations(n, books));
    }
    
    public static int minSwapOperations(int n, int[] books) {
        int[] sortedBooks = books.clone();
        Arrays.sort(sortedBooks);
        Map<Integer, Integer> positionMap = new HashMap<>();
        
        // 创建书籍编号到最终位置的映射
        for (int i = 0; i < n; i++) {
            positionMap.put(sortedBooks[i], i);
        }
        
        int oddMoves = 0;
        // 统计需要奇数次移动的书的数量
        for (int i = 0; i < n; i++) {
            if (Math.abs(i - positionMap.get(books[i])) % 2 == 1) {
                oddMoves++;
            }
        }
        
        // 返回最少需要的第一种操作次数
        return oddMoves / 2;
    }
}

• Cpp

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

using namespace std;

int minSwapOperations(int n, vector<int>& books) {
    // 创建书籍编号的有序副本
    vector<int> sortedBooks = books;
    sort(sortedBooks.begin(), sortedBooks.end());
    
    // 创建书籍编号到最终位置的映射
    unordered_map<int, int> positionMap;
    for (int i = 0; i < n; i++) {
        positionMap[sortedBooks[i]] = i;
    }
    
    int oddMoves = 0;
    // 统计需要奇数次移动的书的数量
    for (int i = 0; i < n; i++) {
        if (abs(i - positionMap[books[i]]) % 2 == 1) {
            oddMoves++;
        }
    }
    
    // 返回最少需要的第一种操作次数
    return oddMoves / 2;
}

int main() {
    int n;
    cin >> n;
    vector<int> books(n);
    
    // 读取书籍编号
    for (int i = 0; i < n; i++) {
        cin >> books[i];
    }
    
    cout << minSwapOperations(n, books) << endl;
    return 0;
}

🍿 03.魔法森林的最优路径

问题描述

在一片神秘的魔法森