华为笔试题！再次拿下！（0821秋招笔试真题解析，超详细、多语言）

大家好，我是吴师兄。

继续每天陪大家练习一场大厂算法题，拿下秋招！

今天练习的是 华为秋招笔试题 。

关注吴师兄，算法学习好轻松

1、小U的数据重删

题目介绍

小U正在进行数据存储优化。她发现存储池内有许多重复的数据块。数据重删的目标是将这些重复的数据块合并，保留一个副本，并在第一个出现的数据块后面增加重复次数。现在，她有一串数据，需要判断每个数据块是否与之前的数据块重复。如果重复，则删除该块，并在第一个出现的数据块后面增加重复计数。最终输出经过重删处理的数据内容。

输入

第一行输入两个整数 和 ，分别表示数据块的总个数和每个数据块的大小。

第二行输入 个正整数，表示存储的数据块。数据块按顺序排列，大小为 的数据块依次从这些数据中提取。

输出

输出去除重复数据后的结果，结果中最后没有空格，以数字结尾。输出内容的顺序和输入数据块的顺序保持一致。

样例

输入：
8 2
1 2 3 4 1 2 3 4

输出：
1 2 2 3 4 2

输入：
8 3
3 4 5 3 4 5 5 4

输出：
3 4 5 2 5 4 1

题目解析

本题主要考察如何处理数据的重复，并以数据块为单位进行去重和计数。根据输入的 和 ，我们可以按照固定大小 对数据进行切片，每个切片看作是一个数据块。如果某个数据块已经出现过，我们就增加它的计数并将其从输出列表中去除。

本题涉及的关键步骤包括：

1. 数据的切片和存储，使用字典来保存每个数据块及其出现的次数。
2. 遍历整个数据数组，每次取出一个 大小的数据块，将其转化为元组进行唯一性判断。
3. 输出时，按照每个数据块的原顺序，附加其出现的次数。

题目思路

解决这个问题的关键是如何高效地进行数据去重和计数。我们可以利用哈希表来存储数据块的唯一性及其出现的次数。每当我们发现一个新数据块时，将其存入哈希表并记录出现次数。当我们遇到重复数据块时，更新哈希表中的计数值。

步骤：

1. 首先从输入中读取数据，并根据 将数据分割成 大小的数据块。
2. 使用一个哈希表（字典）来存储每个数据块及其对应的第一次出现位置和出现次数。
3. 遍历整个数据列表，每次取出一个数据块并将其作为一个元组检查是否已经出现。
4. 如果已经存在于哈希表中，则增加其计数，否则将其添加到哈希表中。
5. 最后，按照数据块的顺序输出，并附加重复次数。

通过这种方式，我们可以保持数据块的顺序不变，同时去除重复数据并计数。

涉及的算法知识点

本题包含的算法知识点和数据结构包括：

• 哈希表 ：用于存储数据块的唯一性及出现次数。
• 排序 ：为了按照数据块的出现顺序输出，我们需要对哈希表中的数据进行排序。

本题与 LeetCode 中的一些去重类问题类似，例如：

• LeetCode 217. 存在重复元素 ：该题考察数组中是否存在重复元素，可以通过哈希表判断唯一性。
• LeetCode 1. 两数之和 ：该题使用哈希表来进行快速查找，与本题中通过哈希表查找数据块的唯一性相似。

遇到类似的题目时，可以使用哈希表来记录数据的唯一性或出现次数。通过哈希表的快速查找功能，我们可以在 时间内判断一个数据是否已经出现。

参考代码

Python 参考代码

# 关注吴师兄，算法好轻松
n = int(input())  # 读取总数据块数量
k = int(input())  # 读取每个数据块的大小
a = list(map(int, input().split()))  # 读取所有数据
mp = {}  # 创建一个字典用于存储数据块及其出现次数

for i in range(0, n, k):  # 按照数据块大小遍历整个数据
    t = tuple(a[i:i + k])  # 将数据块转化为元组，保证唯一性
    if t in mp.keys():  # 如果该数据块已经出现过
        mp[t][1] += 1  # 增加该数据块的出现次数
    else:
        mp[t] = [i, 1]  # 第一次出现时，记录其索引和出现次数

val = sorted(mp.items(), key=lambda v: v[1])  # 按照第一次出现的顺序排序
ans = []  # 创建结果数组
for k, v in val:  # 遍历每个数据块和其计数值
    ans += list(k) + [v[1]]  # 将数据块和计数添加到结果中

print(*ans)  # 输出最终结果

Java 参考代码

// 关注吴师兄，算法好轻松
import java.util.*;

public class DataDeduplication {
    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             a[i] = sc.nextInt();  // 读取每个数据块
        }
        Map, int[]> mp = new HashMap<>();  // 哈希表存储数据块

        for (int i = 0; i // 遍历数据块
            List t = new ArrayList<>();  // 创建一个列表保存数据块
            for (int j = i; j                 t.add(a[j]);  // 将当前数据块加入列表
            }
            if (mp.containsKey(t)) {  // 如果数据块已经出现
                mp.get(t)[1]++;  // 增加其计数
            } else {
                mp.put(t, new int[]{i, 1});  // 否则记录出现位置和计数
            }
        }

        List, int[]>> val = new ArrayList<>(mp.entrySet());
        val.sort(Comparator.comparingInt(e -> e.getValue()[0]));  // 按照第一次出现位置排序
        List ans = new ArrayList<>();  // 结果数组

        for (Map.Entry, int[]> entry : val) {  // 遍历每个数据块
            ans.addAll(entry.getKey());  // 将数据块加入结果
            ans.add(entry.getValue()[1]);  // 将计数加入结果
        }

        for (int i = 0; i             if (i != 0) System.out.print(" ");
            System.out.print(ans.get(i));  // 输出结果
        }
    }
}

C++ 参考代码

// 关注吴师兄，算法好轻松
#include 
#include 
#include 
#include 

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;  // 读取总数据块数量和每个数据块的大小
    vector<int> a(n);  // 存储数据块
    for (int i = 0; i         cin >> a[i];  // 读取每个数据块
    }
    map<vector<int>, pair<int, int>> mp;  // 哈希表存储数据块及其出现次数

    for (int i = 0; i // 遍历数据块
        vector<int> t;  // 创建一个列表保存数据块
        for (int j = i; j             t.push_back(a[j]);  // 将当前数据块加入列表
        }
        if (mp.count(t)) {  // 如果数据块已经出现
            mp[t].second++;  // 增加其计数
        } else {
            mp[t] = {i, 1};  // 否则记录出现位置和计数
        }
    }

    vectorvector<int>, pair<int,

 int>>> val(mp.begin(), mp.end());
    sort(val.begin(), val.end(), [](const auto &lhs, const auto &rhs) {
        return lhs.second.first // 按照第一次出现位置排序
    });
    vector<int> ans;  // 结果数组

    for (const auto &kv : val) {  // 遍历每个数据块
        ans.insert(ans.end(), kv.first.begin(), kv.first.end());  // 将数据块加入结果
        ans.push_back(kv.second.second);  // 将计数加入结果
    }

    for (int i = 0; i         if (i != 0) cout <" ";
        cout     }
}

2、小C的任务调度系统

题目介绍

小C的任务调度系统需要匹配一批并发任务与执行机。任务和执行机都有不同的类型：CPU 型（用 表示）、IO 型（用 表示），以及通用型（用 表示）。任务和执行机的类型分别用数组 和 表示，其中 表示第 个任务的类型， 表示第 台执行机的类型。每台 CPU 型或 IO 型执行机只能执行一个对应类型的任务，而通用型执行机可以执行任意类型的任务。

任务需要按照优先级从高到低进行匹配，即优先匹配任务数组头部（优先级最高）的任务到空置执行机数组头部（优先级最高）的执行机。如果任务与执行机类型匹配，则该任务调度成功，将该执行机从空置执行机数组中移除。如果不匹配，则将该执行机放到执行机数组的尾部。这个过程会重复直到所有任务匹配成功或当前任务无法被所有剩余空置执行机匹配。

通用型执行机可以在任何时刻被使用，但一旦选择了某个任务类型匹配通用型执行机，则所有通用型执行机只能用于执行该类型的任务。为了避免任务排队阻塞，请返回在现有匹配策略下剩下的最小空置执行机数量。

输入

输入共 行：

• 第一行是一个正整数 ，表示任务数量和执行机数量。
• 第二行包含 个整数，以空格分隔，表示任务数组 。
• 第三行包含 个整数，以空格分隔，表示空置执行机数组 。

数据范围：

输出

输出一行一个整数，表示在当前匹配策略下剩下的最小空置执行机数量。

样例

输入：
3
1 0 1
1 2 0

输出：
0

输入：
4
1 0 1 1
1 0 2 0

输出：
1

题目解析

本题考察了贪心策略和任务调度的问题。每个任务只能由特定类型的执行机处理，而通用型执行机可以处理任何任务。但是，为了保证最小的执行机剩余数量，通用型执行机的使用需要非常慎重。

解决该问题的步骤如下：

1. 遍历任务数组，并尝试将任务匹配到空置执行机上。
2. 对于 CPU 型和 IO 型任务，优先匹配同类型的执行机。
3. 通用型执行机可以匹配任意任务，但一旦选择某个任务类型匹配通用型执行机，后续所有通用型执行机必须一致匹配该类型。
4. 如果当前任务无法匹配任何执行机，则将执行机移动到数组末尾，继续尝试匹配下一个任务。

最终输出剩余未被使用的执行机数量。

题目思路

我们可以使用双指针加队列来处理任务调度问题。具体思路如下：

1. 首先按照任务的优先级遍历任务数组，尝试将每个任务匹配到执行机。
2. 使用一个队列来存储执行机，队列中的第一个执行机会与任务数组的第一个任务尝试匹配。
3. 对于每个任务，优先匹配对应类型的执行机。如果匹配成功，则将执行机从队列中移除；否则将执行机移动到队列的末尾。
4. 如果当前任务匹配成功，继续匹配下一个任务；如果匹配不成功，则继续调整执行机的顺序。

涉及的算法知识点

本题包含的算法知识点和数据结构包括：

• 贪心算法 ：每次尽量选择最优的调度方案，以确保剩余执行机数量最少。
• 双指针和队列 ：用于循环匹配任务和执行机的顺序。

本题与 LeetCode 的一些任务调度类问题相似，例如：

• LeetCode 621. 任务调度器 ：这道题涉及到任务的执行顺序和最短冷却时间的计算，采用贪心策略来调度任务。
• LeetCode 134. 加油站 ：这道题涉及到循环遍历和贪心算法，类似于本题的循环匹配执行机和任务的思路。

下次遇到类似的题目，可以采用贪心策略和双指针技巧，逐步找到最优解。

参考代码

Python 参考代码

# 关注吴师兄，算法好轻松
from collections import deque

# 输入任务和执行机的数量
n = int(input())  
tasks = list(map(int, input().split()))  # 输入任务数组
machines = list(map(int, input().split()))  # 输入执行机数组

# 定义一个函数用于调度任务
def solve(machines):
    machines = deque(machines)  # 将执行机列表转化为双端队列
    for task in tasks:  # 遍历每个任务
        if task not in machines:  # 如果当前任务无法匹配任何执行机
            break  # 终止匹配过程
        while machines[0] != task:  # 调整队列顺序，找到匹配的执行机
            machines.rotate(-1)  # 将执行机移动到队尾
        machines.popleft()  # 成功匹配后移除执行机
    return len(machines)  # 返回剩余的执行机数量

# 计算匹配0型和1型任务的剩余执行机数量，并取最小值
print(min(solve([0 if x == 2 else x for x in machines]), solve([1 if x == 2 else x for x in machines])))

Java 参考代码

// 关注吴师兄，算法好轻松
import java.util.*;

public class TaskScheduler {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 输入任务和执行机数量
        int[] tasks = new int[n];  // 存储任务数组
        int[] machines = new int[n];  // 存储执行机数组
        
        for (int i = 0; i // 读取任务
        for (int i = 0; i // 读取执行机

        System.out.println(Math.min(solve(Arrays.copyOf(machines, n), tasks, 0), 
                                    solve(Arrays.copyOf(machines, n), tasks, 1)));
    }

    // 定义解决方案
    public static int solve(int[] machines, int[] tasks, int targetType) {
        LinkedList queue = new LinkedList<>();  // 使用链表作为队列
        for (int m : machines) queue.add(m == 2 ? targetType : m);  // 初始化队列

        for (int task : tasks) {
            if (!queue.contains(task)) break;  // 如果任务无法匹配任何执行机
            while (queue.getFirst() != task) {  // 调整队列顺序
                queue.addLast(queue.removeFirst());  // 将不匹配的执行机移到队尾
            }
            queue.removeFirst();  // 匹配成功后移除执行机
        }
        return queue.size();  // 返回剩余执行机数量
    }
}

C++ 参考代码

// 关注吴师兄，算法好轻松
#include 
#include 
#include 

using namespace std;

int solve(deque<int> machines, int tasks[], int n, int targetType) {
    for (int &m : machines) {
        if (m == 2) m = targetType;  // 将通用型执行机转化为指定类型
    }

    for (int i = 0; i // 遍历每个任务
        if (find(machines.begin(), machines.end(), tasks[i]) == machines.end()) break;  // 如果任务无法匹配任何执行机
        while (machines.front() != tasks[i]) {  // 调整队列顺序
            machines.push_back(machines.front());  // 将不匹配的执行机移到队尾
            machines.pop_front();  // 移除队首元素
        }
        machines.pop_front();  // 成功匹配后移除执行机
    }

    return machines.size();  // 返回剩余执行机数量
}

int main()




    
 {
    int n;
    cin >> n

;  // 输入任务和执行机数量
    int tasks[n], machines[n];

    for (int i = 0; i cin >> tasks[i];  // 读取任务
    for (int i = 0; i cin >> machines[i];  // 读取执行机

    deque<int> machineDeque(machines, machines + n);  // 将执行机数组转为双端队列
    cout <0), solve(machineDeque, tasks, n, 1)) // 输出最小剩余执行机数量

    return 0;
}

3、小C的任务调度问题

题目介绍

在小C的调度系统中，有一组待调度的任务（Job），其中部分任务之间存在亲和关系，需要优先将这些具有亲和关系的任务调度到同一个处理核上。对于不亲和的任务，它们不能运行在同一个处理核上。现在给定一组待调度的任务（包括任务编号和任务执行时间），同时提供任务之间不存在亲和关系的列表（未列出的任务对默认是亲和的）。请设计一个调度器，满足以下要求：

1. 找出一组包含亲和任务数量最多的亲和调度任务组。
2. 如果规则 1 有多个解，选择所有任务执行时间之和最小的组合。

并输出该亲和调度任务组所有任务的执行时间之和。

亲和调度任务组定义为：可以在同一核上面执行的亲和任务集合。

输入

第一行是一个整数 ，表示任务数量，任务编号为 ，取值范围为 。
第二行是 个整数，表示每个任务的执行时间。
第三行是一个整数 ，表示不存在亲和关系的任务对的数量。
接下来