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

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

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

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

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

🌈 01.最小修改次数

题目描述

KK 小姐拿到了一个长度为 的字符串 。她想知道将该字符串修改为 "meituan" 至少需要修改多少次？每次修改，KK 小姐可以修改任意一个字符。

输入格式

输入一个长度为 的、仅由小写字母组成的字符串 。

输出格式

输出 KK 小姐最少的修改次数。

样例输入

meituan

样例输出

0

数据范围

字符串 的长度固定为 。

题解

这是一道非常简单的字符串比较问题。我们只需要逐个比较给定字符串 和目标字符串 "meituan" 的每个字符，统计不同字符的个数即可。

具体实现时，我们可以遍历字符串 ，对于每个位置 ，如果 ，则将计数器 加 。最后输出 即为最少修改次数。

时间复杂度为 ，空间复杂度为 。其中 为字符串长度，本题中 。

参考代码

• Python

s = input()
t = "meituan"
cnt = sum(s[i] != t[i] for i in range(7))
print(cnt)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = "meituan";
        int cnt = 0;
        for (int i = 0; i < 7; i++) {
            cnt += s.charAt(i) != t.charAt(i) ? 1 : 0;
        }
        System.out.println(cnt);
    }
}

• Cpp

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;
    string t = "meituan";
    int cnt = 0;
    for (int i = 0; i < 7; i++) {
        cnt += s[i] != t[i];
    }
    cout << cnt << endl;
    return 0;
}

🚂 02.K小姐的复数统计

问题描述

K小姐是一位热爱数学的女生,她最近在学习复数的相关知识。复数是由实数和虚数组成的数,其中实数包括有理数和无理数,无理数是无限不循环小数,有理数则包括整数和分数。

现在,K小姐拿到了一个由 个复数组成的数组,她想知道其中有多少个实数。你能帮助她统计出实数的个数吗?

输入格式

第一行包含一个正整数 ,表示复数数组的大小。

第二行包含 个由空格分隔的复数,每个复数均为 或者 的形式,其中 和 为绝对值不超过 的整数。

输出格式

输出一个整数,表示数组中实数的数量。

样例输入

4
-5 5-i 6+3i -4+0i

样例输出

2

数据范围

• 

题解

本题需要统计给定复数数组中实数的数量。我们可以遍历数组中的每个复数,判断其是否为实数。

对于每个复数,我们首先判断其是否包含虚数单位 。如果不包含,则该复数为实数,实数计数器加 。

如果包含虚数单位 ,我们将复数按照 号分割成实部和虚部两部分。再将实部和虚部分别按照 号进行分割,最终得到一个由实部、虚部系数组成的数组。我们取数组的最后一个元素,若其长度为 ,说明虚部为 ,不是实数;否则,提取虚部系数,若为 ,则该复数为实数,实数计数器加 。

遍历完整个数组后,输出实数的数量即可。

时间复杂度为 ,空间复杂度为 。其中 为复数数组的大小。

由于本题其他语言实现起来比较繁琐，这里采用python进行实现

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()
n = int(input())
nums = input().split()
cnt = 0
for num in nums:
    if 'i' not in num:
        cnt += 1
    else:
        parts = num.split('+')
        coef = []
        for part in parts:
            terms = part.split('-')
            for term in terms:
                coef.append(term)
        if len(coef[-1]) == 1:
            continue
        imag = int(coef[-1][:-1])
        if imag == 0:
            cnt += 1
print(cnt)

🍧 03.LYA的数组还原

问题描述

LYA是一位热爱数学的女生,她最近在研究一个有趣的问题。LYA原本有一个由 个互不相等的正整数构成的数组 ,但由于一次不小心,她把 弄丢了。好在 LYA 还记得以下有关 的信息:

1. 她完全记得数组 的样子,并且 是数组 删除了某个元素 后,剩余部分做前缀和并打乱顺序的结果。

2. 她完全记得数组 的样子,并且 是数组 删除了某个与 不同的元素 后,剩余部分做前缀和并打乱顺序的结果。

现在,LYA 希望你能帮她还原出原数组 。

注:前缀和是指一个数组的某下标之前的所有数组元素的和(包含其自身)。

输入格式

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

第二行包含 个正整数 ,表示数组 。

第三行包含 个正整数 ,表示数组 。

保证有唯一解。

输出格式

输出一行,包含 个整数,表示还原出的数组 。

样例输入

4
8 18 14 
15 9 1

样例输出

1 8 6 4

数据范围

• 
• 

题解

本题的关键是通过数组 和 的前缀和信息,还原出原数组 。我们可以按照以下步骤进行:

1. 首先对数组 和 分别进行排序。

2. 计算数组 和 的前缀差分数组 和 ,即 , 。同时用哈希表 统计 和 中每个元素出现的次数。

3. 遍历 和 ,比较当前元素 和 :

   • 如果 ,说明该元素同时出现在 中,将其加入答案数组 。
   • 如果 ,说明 是 中删除的元素,将其加入 。
   • 如果 ,说明 是 中删除的元素,将其加入 。

4. 最后输出答案数组 即可。

时间复杂度 ,空间复杂度 。其中 是数组 的长度。

参考代码

• Python

import sys
from collections import Counter

def solve():
    n = int(sys.stdin.readline())
    b = list(map(int, sys.stdin.readline().split()))
    c = list(map(int, sys.stdin.readline().split()))
    
    b.sort()
    c.sort()
    
    b1, c1 = [b[0]], [c[0]]
    cnt = Counter()
    cnt[b[0]] += 1
    cnt[c[0]] += 1
    
    for i in range(n - 2):
        b1.append(b[i + 1] - b[i])
        c1.append(c[i + 1] - c[i])
        cnt[b1[-1]] += 1
        cnt[c1[-1]] += 1
        
    i = j = 0
    res = []
    
    while i < n - 1 and j < n - 1:
        if b1[i] == c1[j]:
            res.append(b1[i])
            i += 1
            j += 1
        elif cnt[b1[i]] == 1:
            res.append(b1[i])
            i += 1
        else:
            res.append(c1[j])
            j += 1
            
    res.extend(b1[i:])
    res.extend(c1[j:])
    
    print(*res)

if __name__ == "__main__":
    solve()

• Java

import java.io.*;
import java.util.*;

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());

        String[] bStr = br.readLine().split(" ");
        String[] cStr = br.readLine().split(" ");
        long[] b = new long[n - 1];
        long[] c = new long[n - 1];

        for (int i = 0; i < n - 1; i++) {
            b[i] = Long.parseLong(bStr[i]);
            c[i] = Long.parseLong(cStr[i]);
        }

        Arrays.sort(b);
        Arrays.sort(c);

        List<Long> b1 = new ArrayList<>();
        List<Long> c1 = new ArrayList<>();
        Map<Long, Integer> cnt = new HashMap<>();
        b1.add(b[0]);
        c1.add(c[0]);
        cnt.put(b[0], cnt.getOrDefault(b[0], 0) + 1);
        cnt.put(c[0], cnt.getOrDefault(c[0], 0) + 1);

        for (int i = 1; i < n - 1; i++) {
            b1.add(b[i] - b[i - 1]);
            c1.add(c[i] - c[i - 1]);
            cnt.put(b1.get(i), cnt.getOrDefault(b1.get(i), 0) + 1);
            cnt.put(c1.get(i), cnt.getOrDefault(c1.get(i), 0) + 1);
        }

        int i = 0, j = 0;
        List<Long> res = new ArrayList<>();

        while (i < n - 1 && j < n - 1) {
            if (b1.get(i).equals(c1.get(j))) {
                res.add(b1.get(i));
                i++;
                j++;
            } else if (cnt.get(b1.get(i)) == 1) {
                res.add(b1.get(i));
                i++;
            } else {
                res.add(c1.get(j));
                j++;
            }
        }

        while (i < n - 1) {
            res.add(b1.get(i));
            i++;
        }
        while (j < n - 1) {
            res.add(c1.get(j));
            j++;
        }

        StringBuilder sb = new StringBuilder();
        for (long num : res) {
            sb.append(num).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}

• Cpp

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

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<long long> b(n - 1), c(n - 1);
    for (int i = 0; i < n - 1; i++) {
        cin >> b[i];
    }
    for (int i = 0; i < n - 1; i++) {
        cin >> c[i];
    }
    
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    
    vector<long long> b1{b[0]}, c1{c[0]};
    unordered_map<long long, int> cnt;
    cnt[b[0]]++;
    cnt[c[0]]++;
    
    for (int i = 1; i < n - 1; i++) {
        b1.push_back(b[i] - b[i - 1]);
        c1.push_back(c[i] - c[i - 1]);
        cnt[b1.back()]++;
        cnt[c1.back()]++;
    }
    
    int i = 0, j = 0;
    vector<long long> res;
    
    while (i < n - 1 && j < n - 1) {
        if (b1[i] == c1[j]) {
            res.push_back(b1[i]);
            i++;
            j++;
        } else if (cnt[b1[i]] == 1) {
            res.push_back(b1[i]);
            i++;
        } else {