字节青训-小M的多任务下载器挑战、版本号比较
目录
一、小M的多任务下载器挑战
题目背景
题目内容
数据输入
数据输出
数据与约定
示例1
示例2
解题思路：
问题理解
数据结构选择
算法步骤
最终代码：
运行结果：
二、版本号比较
问题描述
样例
示例 1:
示例 2:
示例 3:
示例 4：
解题思路：
最终代码：
运行结果：
一、小M的多任务下载器挑战
题目背景
小M的程序设计大作业是编写一个多任务下载器，在做到计算任务并发数的时候遇到了困难。
题目内容
在一次下载中，总共包含N个任务，每个任务会在第x秒开始、并持续y秒。
小M想要知道，在一次下载中，同时最多会有多少个任务正在下载。
数据输入
第一行输入一个正整数N，代表总共有N个任务。
之后共N行，每行包含两个正整数x、y，x代表任务的开始时间，y代表任务的持续时间。
数据输出
输出包含一个整数，代表最高的任务并发数。
数据与约定
对于30%的数据，1 ≤ N ≤ 1,000，1 ≤ x, y ≤ 1,000。
对于50%的数据，1 ≤ N ≤ 1,000,000，1 ≤ x, y ≤ 1,000,000。
对于100%的数据，1 ≤ N ≤ 1,000,000，1 ≤ x, y ≤ 1,000,000,000。
示例1
输入
2
1 2
2 3
输出
2
说明
第一个任务在第一秒开始，持续两秒；第二个任务在第二秒开始，持续三秒。故在第二秒时有两个任务同时在进行，最大并发数为2。
示例2
输入
4
1 2
2 3
3 5
4 3
输出
3
说明
4个任务的时间区间分别为[1,2], [2,4], [3,7], [4,6]。
故在第4秒的时候，第2、3、4号任务正在进行。
解题思路：
问题理解
我们需要计算在一次下载中，同时最多会有多少个任务正在下载。每个任务有一个开始时间和持续时间，这意味着每个任务有一个开始时间和结束时间。
数据结构选择
为了有效地计算并发任务数，我们可以使用以下数据结构：
- 事件列表：记录每个任务的开始和结束时间。
- 时间线扫描：通过扫描时间线来计算每个时间点的并发任务数。
算法步骤
-
事件记录：
- 对于每个任务，记录其开始时间和结束时间。
- 将开始时间视为“+1”事件，结束时间视为“-1”事件。
-
时间线扫描：
- 将所有事件（开始和结束）按时间顺序排序。
- 遍历排序后的事件列表，维护一个计数器来记录当前并发任务数。
- 每当遇到一个开始事件，计数器加1；每当遇到一个结束事件，计数器减1。
- 在遍历过程中，记录计数器的最大值，即为最高的任务并发数。
最终代码：
#include <iostream>
#include <vector>
#include <algorithm>
int solution(int n, std::vector<std::vector<int>> array) {
std::vector<std::pair<int, int>> events;
// 记录每个任务的开始和结束事件
for (auto& task : array) {
int start = task[0];
int end = task[0] + task[1];
events.push_back({start, 1}); // 开始事件
events.push_back({end, -1}); // 结束事件
}
// 按时间顺序排序事件
std::sort(events.begin(), events.end());
int max_concurrent = 0;
int current_concurrent = 0;
// 遍历事件列表，计算并发任务数
for (auto& event : events) {
current_concurrent += event.second;
max_concurrent = std::max(max_concurrent, current_concurrent);
}
return max_concurrent;
}
int main() {
// Add your test cases here
std::cout << (solution(2, {{1,2}, {2,3}}) == 2) << std::endl;
std::cout << (solution(4, {{1,2}, {2,3}, {3,5}, {4,3}}) == 3) << std::endl;
return 0;
}运行结果：
二、版本号比较
问题描述
给你两个版本号 version1 和 version2，请你比较它们。
版本号由一个或多个修订号组成，各修订号由一个 . 连接。每个修订号由多位数字组成，可能包含前导零。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0，下一个修订号下标为 1，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。
比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值。也就是说，修订号 1 和修订号 001 相等。如果版本号没有指定某个下标处的修订号，则该修订号视为 0。例如，版本 1.0 小于版本 1.1，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1，0 < 1。
返回规则如下：
- 如果
version1 > version2返回1， - 如果
version1 < version2返回-1， - 除此之外返回
0。
样例
示例 1:
输入:
version1 = "0.1"
version2 = "1.1"
输出:
-1
示例 2:
输入:
version1 = "1.0.1"
version2 = "1"
输出:
1
示例 3:
输入:
version1 = "7.5.2.4"
version2 = "7.5.3"
输出:
-1
示例 4：
输入：
version1 = "1.0"
version2 = "1.0.0"
输出：
0
解释：version1 没有第三级修订号，这意味着它的第三级修订号默认为 0。
解题思路：
-
理解版本号的结构：
- 版本号由多个修订号组成，修订号之间用
.分隔。 - 每个修订号是一个整数，可能包含前导零。
- 版本号由多个修订号组成，修订号之间用
-
比较版本号：
- 从左到右依次比较每个修订号。
- 如果某个版本号缺少修订号，则视为
0。 - 比较修订号时，忽略前导零。
-
算法步骤：
- 将版本号字符串按
.分割成修订号数组。 - 逐个比较修订号数组中的元素。
- 如果某个修订号数组较短，则在其后补
0进行比较。 - 根据比较结果返回
1、-1或0。
- 将版本号字符串按
最终代码：
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
// 辅助函数：将版本号字符串分割并转换为整数数组
std::vector<int> splitAndConvert(std::string version) {
std::vector<int> result;
std::stringstream ss(version);
std::string token;
while (std::getline(ss, token, '.')) {
result.push_back(std::stoi(token));
}
return result;
}
int solution(std::string version1, std::string version2) {
// 将版本号按 `.` 分割成修订号数组
std::vector<int> v1 = splitAndConvert(version1);
std::vector<int> v2 = splitAndConvert(version2);
// 逐个比较修订号
int n = std::max(v1.size(), v2.size());
for (int i = 0; i < n; ++i) {
int num1 = (i < v1.size()) ? v1[i] : 0;
int num2 = (i < v2.size()) ? v2[i] : 0;
if (num1 > num2) return 1;
if (num1 < num2) return -1;
}
return 0;
}
int main() {
// Add your test cases here
std::cout << (solution("0.1", "1.1") == -1) << std::endl;
std::cout << (solution("1.0.1", "1") == 1) << std::endl;
std::cout << (solution("7.5.2.4", "7.5.3") == -1) << std::endl;
std::cout << (solution("1.0", "1.0.0") == 0) << std::endl;
return 0;
}运行结果：
