- 1前端面试必考题：介绍项目和项目难点
- 2【STM32学习】HAL库点灯学习
- 3探索LTP Python Interface：高效处理自然语言的利器
- 4做什么样的软件才能赚钱？学什么样的知识才能赚钱？_什么软件能学习又能赚钱
- 5达梦数据库——学习笔记四（达梦数据库自增列的实现）_达梦 identity
- 6自动驾驶感知——多传感器融合技术_汽车多传感器融合
- 7微信小程序开发中的图像处理和海报生成_微信小程序生成海报
- 8tensorflow+小白入门笔记︱基本张量tensor理解与tensorflow运行结构_local tetra pattern
- 9git统计代码总行数
- 10git教程（基于vscoede）_vscode git版本回退
华为编程题目（实时更新）_c++假设在平面直角坐标系(上北-y轴正方向,下南-y轴负方向,左西-x轴负方向,右东-x
赞
踩
1.大小端整数
计算机中对整型数据的表示有两种方式：大端序和小端序，大端序的高位字节在低地址，小端序的高位字节在高地址。例如：对数字 65538，其4字节表示的大端序内容为00 01 00 02，小端序内容为02 00 01 00。
现输入一个字符串表示的十进制整数（含负数），请分别输出以4字节表示的大端序和小端序：
- 负数以补码形式表示。
- 如果输入的整数的值超出 [-2^31, 2^32) 范围，则输出字符串
overflow。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 64MB, 其他语言：128MB
输入
十进制整数，以负号-开头表示负数，其它为正整数；数字长度范围：[1,32]。
输入数字不含前导零。
输出
大端序 + \n + 小端序；或字符串overflow。
大端序和小端序的输出格式：每个字节以两位16进制数字表示（16进制数中A-F要大写），字节之间以单空格分隔。
样例1
复制输入：
-10
复制输出：
FF FF FF F6 F6 FF FF FF
解释：
含负号表示为负整数。
该负整数的补码表示为 FF FF FF F6，其对应大端序和小端序内容分别为FF FF FF F6和F6 FF FF FF。
按输出格式要求输出其大端序和小端序内容，中间加换行符。
样例2
复制输入：
4027691818
复制输出：
F0 11 B3 2A 2A B3 11 F0
解释：
输入 4027691818 为正整数，按输出格式要求输出其大端序和小端序内容，中间加换行符。
样例3
复制输入：
1234567890123456789012345678900
复制输出：
overflow
解释：
输入数字超过[-2^31, 2^32) 范围，因此输出 overflow 。
C++代码：
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <sstream>
#include <iomanip>
using namespace std;
class Solution {
public:
// 待实现函数，在此函数中填入答题代码;
string GetHexString(long long input)
{
// Check for overflow
if (input < -2147483648LL || input >= 4294967296LL) {
return "overflow";
}
// Convert input to unsigned int
unsigned int value = static_cast<unsigned int>(input);
// Convert unsigned int to big endian and little endian strings
stringstream bigEndianStream;
bigEndianStream << uppercase << setfill('0') << setw(2) << hex << ((value >> 24) & 0xFF);
bigEndianStream << " " << uppercase << setfill('0') << setw(2) << hex << ((value >> 16) & 0xFF);
bigEndianStream << " " << uppercase << setfill('0') << setw(2) << hex << ((value >> 8) & 0xFF);
bigEndianStream << " " << uppercase << setfill('0') << setw(2) << hex << (value & 0xFF);
stringstream littleEndianStream;
littleEndianStream << uppercase << setfill('0') << setw(2) << hex << (value & 0xFF);
littleEndianStream << " " << uppercase << setfill('0') << setw(2) << hex << ((value >> 8) & 0xFF);
littleEndianStream << " " << uppercase << setfill('0') << setw(2) << hex << ((value >> 16) & 0xFF);
littleEndianStream << " " << uppercase << setfill('0') << setw(2) << hex << ((value >> 24) & 0xFF);
// Concatenate big endian and little endian strings
string bigEndianStr = bigEndianStream.str();
string littleEndianStr = littleEndianStream.str();
return bigEndianStr + "\n" + littleEndianStr;
}
};
int main()
{
long long input;
cin >> input;
Solution solu;
string result = solu.GetHexString(input);
cout << result;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
2.公共字符
公共字符
给定 m 个字符串，请计算有哪些字符在所有字符串中都出现过 n 次及以上。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 64MB, 其他语言：128MB
输入
首行是整数 n ，取值范围 [1,100]
第二行是整数 m ，表示字符串的个数，取值范围 [1,100]
接下来 m 行，每行一个仅由英文字母和数字组成的字符串，长度范围 [1,1000)
输出
按ASCII码升序输出所有符合要求的字符序列； 如果没有符合要求的字符，则输出空序列[]。
样例1
复制输入：
2 3 aabbccFFFFx2x2 aaccddFFFFx2x2 aabcdFFFFx2x2
复制输出：
[2 F a x]
解释：
字符 a 在三个字符串中都出现 2次，符合要求；
字符 b 在第二三个字符串中分别出现 0次、1次，不符合要求；
字符 c 在第三个字符串中出现 1次，不符合要求；
字符 d 在第三个字符串中出现 1次，不符合要求；
字符 F 在三个字符串中都出现了 4 次，符合要求；
字符 x 在三个字符串中都出现了 2 次，符合要求；
字符 2 在三个字符串中都出现了 2 次，符合要求；因此字符 a、F、x、2符合要求，按ASCII码升序输出为 [2 F a x]
样例2
复制输入：
2 3 aa bb cc
复制输出：
[]
C++代码：
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
using namespace std;
class Solution {
public:
// 待实现函数，在此函数中填入答题代码;
vector<char> GetNTimesCharacter(int n, const vector<string> &strings)
{
// 存储所有字符串中字符出现至少n次的结果
map<char, int> globalCharFreq;
vector<char> result;
for (int i = 0; i < strings.size(); ++i) {
map<char, int> localCharFreq;
for (char ch : strings[i]) {
localCharFreq[ch]++;
}
for (auto &p : localCharFreq) {
if (p.second >= n) {
if (i == 0) {
// 第一个字符串初始化计数
globalCharFreq[p.first] = 1;
} else if (globalCharFreq.find(p.first) != globalCharFreq.end()) {
// 后续字符串累加计数
globalCharFreq[p.first]++;
}
}
}
}
// 遍历 globalCharFreq，将出现次数等于字符串数量的字符添加到结果中
for (auto &p : globalCharFreq) {
if (p.second == strings.size()) {
result.push_back(p.first);
}
}
// 按ASCII升序排列
sort(result.begin(), result.end());
return result;
}
};
inline int ReadInt()
{
int number;
cin >> number;
return number;
}
template<typename T>
inline vector<T> ReadVector(int size)
{
vector<T> objects(size);
for (int i = 0; i < size; ++i) {
cin >> objects[i];
}
return objects;
}
template<typename T>
inline void WriteVector(const vector<T>& objects, char delimeter = ' ')
{
auto it = objects.begin();
if (it == objects.end()) {
return;
}
cout << *it;
for (++it; it != objects.end(); ++it) {
cout << delimeter << *it;
}
}
int main()
{
int n = ReadInt();
int m = ReadInt();
vector<string> strings = ReadVector<string>(m);
Solution solu;
auto result = solu.GetNTimesCharacter(n, strings);
cout << "[";
WriteVector(result);
cout << "]" << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
3.呼叫转移
呼叫转移
呼叫转移是指您的电话无法接听或您不愿接电话，可以将来电转移到其它电话号码上。它是电信业一项传统通信业务，又称呼叫前转、呼入转移。
- 用户被呼叫时的状态有4种：
idle，busy，no-response，unreachable - 用户可登记的5种呼叫转移，格式为
type number，type代表转移种类， number代表转移号码：
type为 0：无条件转移，优先级最高，用户处于任何状态都触发此转移
type为 1：用户状态busy时触发此转移
type为 2：用户状态no-response时触发此转移
type为 3：用户状态unreachable时触发此转移
type为 4：默认转移，优先级最低，用户不是idle状态时，且无法触发上述四种转移，触发此转移
注：同一个状态可登记多次，以最后一次登记为准。
现给出某一用户当前的用户状态，以及其登记的若干个呼叫转移号码，请输出最终的呼叫结果：
- 若发生转移，则输出转移号码
- 若用户状态为idle，且未发生转移时，则呼叫本机成功，输出
success - 若呼叫失败：既没有发生转移，也没有呼叫本机成功，则输出
failure。例如，用户状态为 busy，但用户既未登记 type 为 0 或 1 或 4 的呼叫转移，则呼叫失败。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 256MB, 其他语言：512MB
输入
第一行是数字 num 和 字符串 status：num代表呼叫转移登记的次数（ 0 < N <= 20），status表示用户被呼叫时的状态。
接下来 num 行是用户的呼叫转移登记操作，转移号码长度 6-15位，用例保证输入合法。
输出
一个字符串，代表最终的呼叫结果
样例1
复制输入：
3 busy 2 18912345678 4 18912345678 4 13312345567
复制输出：
13312345567
解释：
用户busy，且没有登记 busy 转移，但登记默认转移，呼叫转移到默认转移号码。
默认转移号码已最后一次登记为准
样例2
复制输入：
1 no-response 3 075587678100
复制输出：
failure
解释：
用户no-response，没有登记no-response转移，也没有登记默认转移，呼叫失败。
样例3
复制输入：
1 idle 3 075587678100
复制输出：
success
解释：
用户idle，且没有登记无条件转移，呼叫成功
C++代码：
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
using namespace std;
class Solution {
public:
string Calling(const string &status, const vector<pair<int, string>> ®CallForwardNums)
{
unordered_map<int, string> callForwards;
// 初始化呼叫状态映射
unordered_map<string, int> statusMap = {{"idle", -1}, {"busy", 1}, {"no-response", 2}, {"unreachable", 3}};
// 存储用户设置的呼叫转移
for (auto ® : regCallForwardNums) {
callForwards[reg.first] = reg.second;
}
if (status == "idle" && callForwards.count(0) == 0) {
// 用户状态为idle，且无无条件转移type=0
return "success";
}
if (callForwards.count(0)) {
// 检查是否有无条件转移
return callForwards[0];
} else if (statusMap.count(status) && callForwards.count(statusMap[status])) {
// 检查用户状态对应的转移
return callForwards[statusMap[status]];
} else if (callForwards.count(4)) {
// 检查默认转移
return callForwards[4];
}
// 没有匹配的转移则失败
return "failure";
}
};
// 以下为考题输入输出框架，此部分代码不建议改动
inline string ReadLine()
{
string line;
getline(cin, line);
return line;
}
inline vector<string> ReadLines(int size)
{
vector<string> lines(size);
for (int i = 0; i < size; ++i) {
lines[i] = ReadLine();
}
return lines;
}
inline pair<string, string> SplitPair(const string& word, char delimeter)
{
auto pos = word.find(delimeter);
return make_pair(word.substr(0, pos), word.substr(pos + 1));
}
int main()
{
pair<string, string> p = SplitPair(ReadLine(), ' ');
int n = stoi(p.first);
string status = p.second;
vector<string> lines = ReadLines(n);
vector<pair<int, string>> regCallForwardNums;
for (auto s : lines) {
p = SplitPair(s, ' ');
regCallForwardNums.push_back(make_pair(stoi(p.first), p.second));
}
Solution solu;
string out = solu.Calling(status, regCallForwardNums);
cout << out << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
4.单板告警统计
假设某系统中有两块单板，这两块单板上产生的告警ID（以十六进制字符串表示）分别存储在列表 arrayA 和列表arrayB 中。
请统计并输出系统中的所有告警ID（即arrayA和arrayB的并集）：
- 如果告警ID存在重复，先需去重。
- 然后以告警ID所表示值的升序排序输出
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 256MB, 其他语言：512MB
输入
第一行1个整数，表示告警列表arrayA的长度，取值范围为：[0,1000]
第二行表示告警列表arrayA的数据，告警ID以单空格分隔
第三行1个整数，表示告警列表arrayB的长度，取值范围为：[0,1000]
第四行表示告警列表arrayB的数据，告警ID以单空格分隔
告警ID为无符号整数，以十六进制字符串表示，由数字字符、大写字母A~F组成，固定为 8 个字符。
输出
按升序排序的告警ID，以单空格分隔
样例1
复制输入：
2 00001001 00ABCD00 3 FFFFFAAB FFFFFAAB 00ABCD00
复制输出：
[00001001 00ABCD00 FFFFFAAB]
解释：
系统中共有三个告警ID：
00ABCD00，去重后保留一个；
FFFFFAAB，去重后保留一个；
00001001，只有一个。
按所表示值的大小升序排列，输出这三个告警ID为 [00001001 00ABCD00 FFFFFAAB] 。
样例2
复制输入：
0 1 FFFFFAAB
复制输出：
[FFFFFAAB]
解释：
提示
答题要求：您编写的代码需要符合CleanCode的要求（包括通用编码规范、安全编码规范和圈复杂度）
C++代码：
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
class Solution {
public:
// 待实现函数，在此函数中填入答题代码;
vector<string> GetAllFault(const vector<string> &arrayA, const vector<string> &arrayB)
{
// Combine both arrays into one
vector<string> combined(arrayA);
combined.insert(combined.end(), arrayB.begin(), arrayB.end());
// Remove duplicates
sort(combined.begin(), combined.end());
combined.erase(unique(combined.begin(), combined.end()), combined.end());
// Convert hex strings to integers for sorting
vector<pair<unsigned int, string>> converted;
for (const string &hexStr : combined) {
unsigned int value = stoul(hexStr, nullptr, 16);
converted.push_back(make_pair(value, hexStr));
}
// Sort by integer value
sort(converted.begin(), converted.end());
// Extract the sorted strings back into the result
vector<string> result;
for (const auto &pair : converted) {
result.push_back(pair.second);
}
return result;
}
};
inline int ReadInt()
{
int number;
std::cin >> number;
return number;
}
template<typename T>
inline std::vector<T> ReadVector(int size)
{
std::vector<T> objects(size);
for (int i = 0; i < size; ++i) {
std::cin >> objects[i];
}
return objects;
}
template<typename T>
inline void WriteVector(const std::vector<T>& objects, char delimeter = ' ')
{
auto it = objects.begin();
if (it == objects.end()) {
return;
}
std::cout << *it;
for (++it; it != objects.end(); ++it) {
std::cout << delimeter << *it;
}
}
int main()
{
int arrayANum = ReadInt();
vector<string> arrayA = ReadVector<string>(arrayANum);
int arrayBNum = ReadInt();
vector<string> arrayB = ReadVector<string>(arrayBNum);
Solution solu;
auto result = solu.GetAllFault(arrayA, arrayB);
cout << "[";
WriteVector(result, ' ');
cout << "]" << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
5.表达式计算
现给你一个字符串，代表一个后序遍历形式的四则运算表达式，请计算出表达式的结果（只输出整数部分）。
注：
- 都是双目运算，不存在单目运算;
- 中间计算结果范围：[-2^31, 2^31)；
- 除法只需保留整数部分，比如:5/4=1, (-5)/3=-1, 5/(-3)=-1，无需考虑余数；无需考虑除数为0的情况，用例不存在除零。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 64MB, 其他语言：128MB
输入
一个字符串，代表一个四则运算表达式，由若干操作数和运算符组成，操作数、运算符之间都用一个逗号隔开。长度范围：[1,50000)。
注：用例保证输入合法：1）一定有计算结果； 2）操作数是合法的整数； 3）运算符只包含+，-，*，/四种。
输出
一个整数，表示表达式的计算结果，用例保证最终结果范围：-2,147,483,648 ~ 2,147,483,647。
样例1
复制输入：
9,3,5,-,2,*,+
复制输出：
5
样例2
复制输入：
3,-3,-,2,/,10,-
复制输出：
-7
C++：
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <utility>
#include <algorithm>
using namespace std;
class Solution {
public:
// 将字符串表达式分割成操作数和运算符的数组
vector<string> SplitExpression(const string& expression) {
vector<string> tokens;
string token;
for (char c : expression) {
if (c == ',') {
if (!token.empty()) {
tokens.push_back(token);
token.clear();
}
} else {
token += c;
}
}
if (!token.empty()) {
tokens.push_back(token);
}
return tokens;
}
// 计算后序表达式
int CalcExpression(const string &expression) {
stack<int> st;
vector<string> tokens = SplitExpression(expression);
for (const string& token : tokens) {
if (isdigit(token[0]) || token.size() > 1) { // 这个很关键！检查是否为操作数(可能是负数)
st.push(stoi(token));
} else {
int r = st.top(); st.pop();
int l = st.top(); st.pop();
switch (token[0]) {
case '+': st.push(l + r); break;
case '-': st.push(l - r); break;
case '*': st.push(l * r); break;
case '/': st.push(l / r); break;
}
}
}
return st.top();
}
};
inline string ReadLine()
{
string line;
getline(cin, line);
return line;
}
int main()
{
string expression = ReadLine();
Solution solu;
int result = solu.CalcExpression(expression);
cout << result << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
6.话单发送
某核心网设备向计费网关发送话单（一个话单指一条通话记录的信息），发送规则如下：
- 每个话单具有长度和优先级两个属性，优先级值越小表示优先级越高，高优先级的发送完，才能发送次优先级的。
- 设备有一个承载规格，表示发送话单总容量的阈值，发送话单的总长度不能超过承载规格。
现给定设备的承载规格和待发送话单（长度和优先级）列表，请计算最多可以发送多少个话单。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 256MB, 其他语言：512MB
输入
第一行是正整数 cap ，表示设备的承载规格，取值范围：[1,10000]
第二行是正整数 num ，表示待发送话单的数量，取值范围：[0,100]
第三行 num 个整数，依次表示每个待发送话单的长度，每个值的范围：[0, 1000]
第四行 num 个整数，依次表示每个待发送话单的优先级，每个值的范围：[0,30]
第三行和第四行的数据一一对应，表示同一个话单的长度和优先级。
输出
输出一个整数，表示最多能发送话单的个数。
样例1
复制输入：
110 5 50 20 30 10 50 2 2 1 3 1
复制输出：
3
解释：
- 首先尝试发送优先级为 1 的话单，长度分别是30和50，长度之和在承载规格范围内，优先级 1 的两个话单全部完成发送，剩余容量为30。
- 接着尝试发送优先级为 2 的话单，长度20的被发送，剩余容量为10，长度50的无法发送。
- 因优先级 2 的话单未发送完（仍剩余一条），优先级3的所有话单都无法发送。
所以，最多能发送的话单数为 3 。
C++代码：
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
class Solution {
public:
// 待实现函数，在此函数中填入答题代码
int GetMaxSendNum(int cap, const vector<int> &bill, const vector<int> &pri)
{
int num = bill.size();
vector<pair<int, int>> bills(num);
for (int i = 0; i < num; i++) {
bills[i] = {pri[i], bill[i]};
}
sort(bills.begin(), bills.end());
int res = 0;
int curCap = 0;
for (int i = 0; i < num; i++){
if (curCap + bills[i].second <= cap) {
res++;
curCap += bills[i].second;
}else {
break;
}
}
return res;
}
};
// 以下为考题输入输出框架，此部分代码不建议改动
inline int ReadInt()
{
int number;
std::cin >> number;
return number;
}
template<typename T>
inline std::vector<T> ReadVector(int size)
{
std::vector<T> objects(size);
for (int i = 0; i < size; ++i) {
std::cin >> objects[i];
}
return objects;
}
int main()
{
int cap = ReadInt();
int n = ReadInt();
vector<int> bill = ReadVector<int>(n);
vector<int> pri = ReadVector<int>(n);
Solution solu;
int res = solu.GetMaxSendNum(cap, bill, pri);
cout << res;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
心得：
- 核心就是利用hash结构的pair，将优先级和容量组成pair，然后利用优先级排序，最后在遍历即可！
7.字符排序
给定一个字符串，仅含英文字母和数字，请按如下规则对其进行排序：
- 排序后，原位置是数字的，排序后仍然是数字；原位置是字母的，排序后仍然是字母。
- 数字：按 0-9 升序。
- 英文字母：大写字母大于小写字母，小写字母按 a-z 升序，大写字母按 A-Z 升序。
输入
输入为一行字符串，长度范围 [1,1000)，字符串中不会出现除英文字母、数字以外的别的字符。
输出
输出排序后的字符串。
样例1
复制输入：
a2CB1c
复制输出：
a1cB2C
解释：
第二、五位置的数字分别为 2、1，排序后为1、2 ；
第一、三、四、六位置的字母分别为 a、C、B、c，小写字母a、c排在前；大写字母C、B排在后，并按 A-Z 升序为 B、C ；因此最终输出为 a1cB2C
样例2
复制输入：
ab12C4Ac3B
复制输出：
ab12c3AB4C
解释：
无
C++代码：
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
class Solution {
public:
// 待实现函数，在此函数中填入答题代码;
string CharacterSort(const string &inputStr)
{
string result;
vector<int> digits;
vector<char> lowercase;
vector<char> uppercase;
// 分离字母和数字，并放入对应的容器中
for (char c: inputStr) {
if (isdigit(c)) {
digits.push_back(c - '0'); // 将数字转为int是为了后面更好的排序！
}else if (islower(c)) {
lowercase.push_back(c);
}else if (isupper(c)) {
uppercase.push_back(c);
}
}
// 分别对数字和字母进行排序
sort(digits.begin(), digits.end());
sort(lowercase.begin(), lowercase.end());
sort(uppercase.begin(), uppercase.end());
// 分别追踪数字和字母的迭代位置
int digitsIndex = 0;
int lowerIndex = 0;
int upperIndex = 0;
// 遍历原字符串，根据字符类型，从已排序容器中获取对应的字符
for (int i = 0; i < inputStr.size(); ++i) {
if (isdigit(inputStr[i])) {
result += digits[digitsIndex++] + '0';
}else {
if (lowerIndex >= lowercase.size()) {
result += uppercase[upperIndex++];
}else {
result += lowercase[lowerIndex++];
}
}
}
return result;
}
};
inline string ReadLine()
{
string line;
getline(cin, line);
return line;
}
int main()
{
string inputStr = ReadLine();
Solution solu;
string result = solu.CharacterSort(inputStr);
cout << result;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
8.统计无重复字符字串
统计无重复字符子串
给定一字符串，请统计位置连续，且无重复字符出现的子串数量。例如abc是无重复字符的子串，abb不是。
注：内容一样但位置不一样的子串，按不同子串参与统计。
一个字符串中任意个连续的字符组成的子序列称为该字符串的子串。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 256MB, 其他语言：512MB
输入
一个字符串，仅由小写英文字母组成，其长度范围：[1, 1000000]
输出
一个整数，表示统计出的无重复字符的子串的数量。
样例1
复制输入：
abac
复制输出：
8
解释：
子串有 a、b、a、c、ab、ba、ac、aba、bac、abac, 无重复字符的子串为 a、b、a、c、ab、ba、ac、bac，因此统计结果为8。
样例2
复制输入：
xbmxbnh
复制输出：
21
解释：
无重复字符的子串为 x、b、m、x、b、n、h、xb、bm、mx、xb、bn、nh、xbm、bmx、mxb、xbn、bnh、mxbn、xbnh、mxbnh，因此统计结果为21。
C++代码：
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
// 待实现函数，在此函数中填入答题代码;
int GetCountOfSubString(const string &input)
{
if (input.empty())
{
return 0;
}
int n = input.size();
int lastPos[26];
fill_n(lastPos, 26, -1); // 初始化每个字符的最后位置为-1
long long totalCount = 0; // 结果可能很大，使用更大的存储类型
int start = 0; // 窗口的起始位置
for (int end = 0; end < n; ++end) {
char charIndex = input[end] - 'a';
// 更新窗口的起始位置，确保窗口内没有重复字符
if (lastPos[charIndex] != -1) {
start = max(start, lastPos[charIndex] + 1);
}
// 以当前字符结尾的无重复字符子串的数量是窗口的长度
totalCount += (end - start + 1);
// 更新当前字符的最后出现位置
lastPos[charIndex] = end;
}
return totalCount;
}
};
int main()
{
string input;
cin >> input;
Solution solu;
cout << solu.GetCountOfSubString(input) << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
代码解读：
代码中使用了滑动窗口技术结合数组来追踪字符的最后出现位置，有效解决了要求无重复字符的子串计数问题。下面我将逐步详解这段代码的实现和逻辑：
初始化：
- 数组
lastPos：这个数组用于存储每个英文字母最后一次出现在字符串中的位置。因为字符串仅包含小写字母，所以数组大小为26。初始化为-1，表示开始时，没有任何字母被访问过。
int lastPos[26];
std::fill_n(lastPos, 26, -1);
- 1
- 2
变量定义：
- 变量
totalCount：用于累计满足条件的子串数量。由于字符串长度可能非常大（最大100万），所以使用long long类型以避免整数溢出。 - 窗口的指针
start和end：start是当前无重复子串的起始索引，end是当前正在处理的字符的索引。
主逻辑循环：
对字符串 input 进行遍历。
- 扩展窗口： 每次循环体内，
end指针每次都会向右移动一位（扩展窗口的右边界）。
for (int end = 0; end < n; ++end) {}
- 1
- 检查并更新
start：- 通过当前字符计算其在
lastPos数组中的索引。 - 如果当前的字符之前出现过（即在
lastPos中的值不是-1），则可能需要调整窗口的起始位置start，确保窗口内无重复字符。窗口的起始位置应该是之前该字符出现的位置的下一个位置（lastPos[charIndex] + 1）与当前start的较大值。
- 通过当前字符计算其在
char charIndex = input[end] - 'a';
if (lastPos[charIndex] != -1) {
start = std::max(start, lastPos[charIndex] + 1);
}
- 1
- 2
- 3
- 4
- 计算子串数量：
- 窗口内的字符都是不重复的，且以
end指向的字符结尾的子串数量等于窗口长度。end - start + 1表示从start到end（包括end）字符的数量。
- 窗口内的字符都是不重复的，且以
totalCount += (end - start + 1);
- 1
- 更新处理中的字符的最后出现位置：
lastPos[charIndex] = end;
- 1
返回结果：
- 循环结束后，
totalCount存储了符合条件的所有子串的数量。
整体分析：
这段代码通过维护一个动态的滑动窗口来保持窗口内的字符唯一性，从而高效地统计所有可能的、不含重复字符的子串的数量。它的时间复杂度是线性的，也就是O(n)，空间复杂度由于使用了固定大小的数组，是O(1)。这使得解法非常高效而适用于处理大数据量的输入。
9.手机壳库存管理
库存管理对于手机壳销售是否达成盈利最大化至关重要。
仓库中有一批不同型号的手机壳，每种型号手机壳的库存数量存在数组inventory中、总售价存在数组price中。每种型号手机壳的 销售收益 = 销售数量 * (price[i] / inventory[i]) 。
现给定市场上手机壳的最大需求量demand，请制定最佳销售策略以获得最大的总销售收益，并返回该值。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 256MB, 其他语言：512MB
输入
首行两个正整数 M 和 N，M 表示手机壳种类的个数，取值范围：[1, 1000]； N 表示市场最大需求量，取值范围：[1, 500] （单位为千部）。
第2行 M 个数字，表示每种型号手机壳的数量（单位为千部），每个数字的取值范围：(0.0,1000.0]
第3行 M 个数字，表示每种手机壳的总售价（单位为万元），顺序与第2行一一对应，每个数字的取值范围：(0.0,10000.0]。
输出
浮点数形式的最大收益值（万元为单位）
系统进行浮点数结果判断，误差在0.01之内即认为正确。
样例1
复制输入：
3 20 18 15.0 10 75.0 72 45
复制输出：
94.50
解释：
最大收益策略是卖出全部 15 千部第 2 种型号手机壳、以及 5 千部第 3 种型号手机壳，获得 72 + 45/2 = 94.5（万元）。
C++代码：
/*
* Copyright (c) Huawei Technologies Co., Ltd. 2020-2020. All rights reserved.
* Description: 上机编程认证
* Note: 缺省代码仅供参考，可自行决定使用、修改或删除
*/
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <iomanip>
using namespace std;
class Solution {
public:
// 待实现函数，在此函数中填入答题代码;
float PhoneSellManage(float demand, const vector<float> &inventory, const vector<float> &price)
{
int len = inventory.size();
vector<pair<float, float>> profitPair(len);
// 计算每种手机壳的单位收益并存储
for (int i = 0; i < len; i++) {
if (inventory[i] > 0) {
profitPair[i] = {price[i] / inventory[i], inventory[i]};
}else {
profitPair[i] = {0.00, 0.00};
}
}
// 根据单位收益从高到底排序
sort(profitPair.rbegin(), profitPair.rend());
float remainingDemand = demand;
float salesSam = 0;
for (const auto & pair: profitPair) {
if (remainingDemand < 0) {
break;
}
float mount = min(pair.second, remainingDemand);
salesSam += pair.first * mount;
remainingDemand -= mount;
}
return salesSam;
}
};
inline int ReadInt()
{
int number;
std::cin >> number;
return number;
}
template<typename T>
inline std::vector<T> ReadVector(int size)
{
std::vector<T> objects(size);
for (int i = 0; i < size; ++i) {
std::cin >> objects[i];
}
return objects;
}
int main()
{
int num;
float demand;
cin >> num >> demand;
vector<float> inventory = ReadVector<float>(num);
vector<float> price = ReadVector<float>(num);
Solution solu;
float result = solu.PhoneSellManage(demand, inventory, price);
cout <<std::fixed << std::setprecision(2)<< result; //保留两位小数
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
10.日活月活统计
现有一份接口访问日志，每行日志格式如下，请统计日活数和月活数。
yyyy-mm-dd|client_ip|url|result
各字段说明：
yyyy-mm-dd：日志打印时间，一个日志文件中时间跨度保证都在同一个月内，但不保证每行是按日期有序的。
client_ip：为合法的点分十进制ipv4地址（1.1.1.1和1.01.001.1应视为同一个地址）。
url：访问的地址，格式如 /login.do，/query.html，仅包含字母、.、/和_。
result：接口访问结果，只有2种值：success 或 fail 。
日活数、月活数的统计规则：
- 日活数统计：统计当天有多少个不同的 client_ip 访问的地址是 /login.do，且结果为 success。
- 月活数统计：统计当月有多少个不同的 client_ip 访问的地址是 /login.do，且结果为 success。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 256MB, 其他语言：512MB
输入
首行一个正整数 num ，表示日志行数，范围为 [1,50000]。
接下来 num 行字符串，每行字符串表示一条日志内容，每行字符串长度不超过150。
输出
32个整数，以单空格分隔。第1个整数表示月活数，第 2-32 个整数分别表示当月1-31天的日活数。
样例1
复制输入：
5 2020-02-01|192.168.218.218|/login.do|success 2020-02-01|192.168.218.218|/login.do|success 2020-02-01|192.168.210.210|/login.do|fail 2020-02-02|192.168.210.210|/login.do|success 2020-02-02|192.168.218.218|/login.do|success
复制输出：
2 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
解释：
二月的第一天即2月1日，有两条日志访问/login.do的结果为success，但都来自同一个ip（192.168.218.218），因此当天的日活数统计为1。
第二天有两条访问成功，来自两个不同的ip，因此日活数为 2。
当月仅有2个ip访问成功，因此月活数为2。注意：月活数不是日活数的简单累加。
样例2
复制输入：
3 2020-12-01|192.168.218.001|/login.do|success 2020-12-01|192.168.218.1|/login.do|success 2020-12-01|192.168.218.2|/to_login.do|success
复制输出：
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
解释：
192.168.218.001和192.168.218.1视为同一个ip，/to_login.do 与 /login.do 不匹配，因此统计下来日活数为1，月活数为1。
要完成这个问题，关键在于解析日志并从中提取关心的数据：日期、客户端 IP 地址、URL 和结果。根据题意要求解析日志条目，只关注URL为/login.do且结果为success的日志条目。
详细步骤如下：
- 首先把每个客户端IP期望用
set来消除重复，并确保1.1.1.1和1.01.001.1是相同的IP，可以通过整数化处理。 - 用一个哈希表（键为日期，值为客户端 IP 的集合）来存储每天有效的客户端IP以统计日活数。
- 用一个集合存储整个文件中有效的客户端IP来统计月活数。
- 日期可能不连续出现，但保证日志是同一月份的，用数组储存结果，大小固定为32（第一个位置存储月活数）。
C++代码：（思路非常清晰，行云流水！）
/*
* Copyright (c) Huawei Technologies Co., Ltd. 2019-2019. All rights reserved.
* Description: 上机编程认证
* Note: 缺省代码仅供参考，可自行决定使用、修改或删除
*/
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <sstream>
#include <set>
#include <unordered_map>
using namespace std;
class Solution {
public:
// 待实现函数，在此函数中填入答题代码;;
vector<int> GetActiveUserNum(const vector<string> &logs)
{
// 定义一个数组来统计每天的日活数，初始化31天，数组索引1-31对应于日期
vector<int> daily_active(32, 0);
// 一个哈希表记录每天成功登录的不同IP
unordered_map<int, set<unsigned int>> daily_ips;
// 一个集合记录整个月成功登录的不同IP
set<unsigned int> monthly_ips;
for (const string &log : logs) {
stringstream ss(log);
string date, ip, url, result;
// 按照 '|' 记号分解日志记录
getline(ss, date, '|');
getline(ss, ip, '|');
getline(ss, url, '|');
getline(ss, result, '|');
// 检查是否为成功登录
if (url == "/login.do" && result == "success") {
// 将日期字符串分解，获取日份
int day = stoi(date.substr(8, 2));
// 标准化IP地址
unsigned int ip_address = standardize_ip(ip);
// 将IP加入对应日期的set中
daily_ips[day].insert(ip_address);
// 将IP加入全月set中
monthly_ips.insert(ip_address);
}
}
// 计算日活数并填充答案
for (const auto &daily_set : daily_ips) {
int day = daily_set.first; // 当天日期
int count = daily_set.second.size(); // 当天的客户端数目
daily_active[day] = count; // 把计数写入结果数组对应元素
}
// 计算月活数
daily_active[0] = monthly_ips.size();
return daily_active;
}
private:
// 把IP地址字符串标准化为整数，以便进行比较和存储
unsigned int standardize_ip(const string &ip) {
int a, b, c, d; // 四个部分的整数值
sscanf(ip.c_str(), "%d.%d.%d.%d", &a, &b, &c, &d);
return (a << 24) | (b << 16) | (c << 8) | d;
}
};
inline int ReadInt()
{
int number;
cin >> number;
return number;
}
template<typename T>
inline vector<T> ReadVector(int size)
{
vector<T> objects(size);
for (int i = 0; i < size; ++i) {
cin >> objects[i];
}
return objects;
}
template<typename T>
inline void WriteVector(const vector<T>& objects, char delimeter = ' ')
{
auto it = objects.begin();
if (it == objects.end()) {
return;
}
cout << *it;
for (++it; it != objects.end(); ++it) {
cout << delimeter << *it;
}
cout << endl;
}
int main()
{
int n = ReadInt();
vector<string> logs = ReadVector<string>(n);
Solution solu;
vector<int> result = solu.GetActiveUserNum(logs);
WriteVector(result, ' ');
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
其中，将IP地址字符串转化为整数的代码如下：
private:
// 把IP地址字符串标准化为整数，以便进行比较和存储
unsigned int standardize_ip(const string &ip) {
int a, b, c, d; // 四个部分的整数值
sscanf(ip.c_str(), "%d.%d.%d.%d", &a, &b, &c, &d);
return (a << 24) | (b << 16) | (c << 8) | d;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
这段函数standardize_ip是一个私有成员函数，它的目的是将IP地址字符串转换为无符号整数，以便于后续的比较和存储操作。下面是对这段函数的详细分析：
函数签名
private:
unsigned int standardize_ip(const string &ip)
- 1
- 2
private:：表明这个函数是类的私有成员函数，只能被该类的其他成员函数或友元函数访问。unsigned int：函数的返回类型是无符号整数。standardize_ip：函数名称。const string &ip：函数接收一个常量字符串引用作为参数，这个字符串代表一个IP地址。
函数体
- 变量声明
cpp复制代码
int a, b, c, d; // 四个部分的整数值
- 1
- 2
- 3
这里声明了四个整型变量a、b、c和d，它们将用于存储IP地址的各个部分。
- 使用
sscanf函数解析IP地址
cpp复制代码
sscanf(ip.c_str(), "%d.%d.%d.%d", &a, &b, &c, &d);
- 1
- 2
- 3
sscanf是一个标准库函数，用于从字符串中读取格式化输入。这里，它将IP地址字符串ip（首先转换为C风格字符串ip.c_str()）解析为四个整数，并分别存储在变量a、b、c和d中。
IP地址格式通常为a.b.c.d，其中a、b、c和d都是0到255之间的整数。
- 将IP地址的各个部分组合成一个无符号整数–>(这里也相当关键）
cpp复制代码
return (a << 24) | (b << 16) | (c << 8) | d;
- 1
- 2
- 3
这里使用了位操作来将IP地址的各个部分组合成一个无符号整数。<<是左移操作符，用于将数值向左移动指定的位数。|是按位或操作符，用于将两个数值的对应位进行或运算。
a << 24：将a的值左移24位，这样a的值就位于结果整数的最高8位。b << 16：将b的值左移16位，这样b的值就位于结果整数的次高8位。c << 8：将c的值左移8位，这样c的值就位于结果整数的第三高8位。d：保持d的值不变，它将成为结果整数的最低8位。
最后，通过按位或操作符|将这些部分组合在一起，形成一个无符号整数，并作为函数的返回值。
总结
这个函数将IP地址字符串转换为无符号整数，以便于后续的比较和存储操作。它使用了sscanf函数来解析IP地址，并通过位操作将IP地址的各个部分组合成一个无符号整数。这种转换方式可以方便地比较两个IP地址是否相等，或者用于在数据结构中存储IP地址。
11.简易DHCP服务器
DHCP服务器的功能是为每一个MAC地址分配唯一的IP地址。现假设：分配的IP地址范围从 192.168.0.0 到 192.168.0.255 总共256个可用地址（以点分十进制表示）。请实现一个简易的DHCP服务器，功能如下：
-
分配Request
根据输入的MAC地址分配IP地址池中的IP地址：
- 如果对应的IP已分配并未释放，则为重复申请，直接返回对应已分配的IP地址。
- 如果一个MAC地址已申请过并已释放，即：当前未分配IP地址，则为再申请，优先分配最近一次曾经为其分配过的IP地址，请返回此地址。
- 按升序分配从未被分配过的IP地址；如果地址池中地址都已被分配过，则按升序分配已释放出来的IP地址；若可分配成功，则返回此IP地址。
- 若仍然无法分配成功，则返回
NA。
-
释放Release
根据输入的MAC地址释放已分配的IP地址：
- 如果申请释放的对应的IP地址已分配，则释放此IP地址；
- 如果申请释放的对应的IP地址不存在，则不作任何事情；
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 256MB, 其他语言：512MB
输入
首行为整数n, 表示其后输入的命令行数，范围[1,2000]。
之后每行为一条分配命令，格式为：命令=MAC地址
- 命令只有两种：
REQUEST和RELEASE，分别表示分配和释放； - MAC地址为：12个大写英文字母或数字，如：
AABBCCDDEEF1。
输出
1.REQUEST命令，输出分配结果(IP地址字符串或字符串NA)，均为字符串形式。
注意：IP地址的各区段不设置前置
0
2.RELEASE命令，不输出任何内容。
样例1
复制输入：
2 REQUEST=AABBCCDDEEF1 RELEASE=AABBCCDDEEF1
复制输出：
192.168.0.0
解释：
REQUEST=AABBCCDDEEF1 按升序分配从未使用过的IP地址，输出192.168.0.0
RELEASE=AABBCCDDEEF1 不输出
样例2
复制输入：
6 REQUEST=AABBCCDDEEF1 REQUEST=F2FBBCCDDEEF RELEASE=AABBCCDDEEF1 RELEASE=F2FBBCCDDEEF REQUEST=333333333333 REQUEST=F2FBBCCDDEEF
复制输出：
192.168.0.0 192.168.0.1 192.168.0.2 192.168.0.1
解释：
REQUEST=AABBCCDDEEF1 按升序分配从未使用过的IP，为192.168.0.0
REQUEST=F2FBBCCDDEEF 按升序分配从未使用过的IP，为192.168.0.1
RELEASE=AABBCCDDEEF1 释放IP 192.168.0.0。
RELEASE=F2FBBCCDDEEF 释放IP 192.168.0.1。
REQUEST=333333333333 按升序分配从未使用过的IP，为192.168.0.2
REQUEST=F2FBBCCDDEEF 该MAC地址再申请，优先分配最近一次曾经为其分配过的IP，为192.168.0.1
C++代码：（通过率95%）
/*
* Copyright (c) Huawei Technologies Co., Ltd. 2019-2020. All rights reserved.
* Description: 考生实现代码
* Note: 缺省代码仅供参考，可自行决定使用、修改或删除
*/
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
class MiniDhcpServer {
private:
unordered_map<string, string> macToIP; // Maps MAC addresses to their currently assigned IP
unordered_map<string, string> previousAllocation; // Maps MAC addresses to their last IP (for re-allocation)
queue<string> availableIPs; // Queue for available IPs to ease allocation in ascending order
unordered_map<string, bool> ipUsed; // Track whether IP has been used ever for re-allocation
public:
MiniDhcpServer() {
for (int i = 0; i < 256; ++i) {
string ip = "192.168.0." + to_string(i);
availableIPs.push(ip);
ipUsed[ip] = false;
}
}
string Request(const string &mac) {
// If this MAC is currently linked to an IP address, return it.
if (macToIP.find(mac) != macToIP.end()) {
return macToIP[mac];
}
// If this MAC had an IP address previously, assign it the same IP if available.
if (previousAllocation.find(mac) != previousAllocation.end() && !ipUsed[previousAllocation[mac]]) {
string ip = previousAllocation[mac];
macToIP[mac] = ip;
ipUsed[ip] = true;
return ip;
}
// Otherwise, assign a new IP address from the available IPs.
if (!availableIPs.empty()) {
string ip = availableIPs.front();
availableIPs.pop();
macToIP[mac] = ip;
ipUsed[ip] = true;
previousAllocation[mac] = ip;
return ip;
}
// If all IPs are in use and none are available, return "NA".
return "NA";
}
void Release(const string &mac) {
// If the MAC address has a currently assigned IP, release it.
if (macToIP.find(mac) != macToIP.end()) {
string ip = macToIP[mac];
macToIP.erase(mac);
availableIPs.push(ip);
ipUsed[ip] = false; // This line isn't absolutely necessary but maintains consistency.
}
}
};
int main()
{
int line;
cin >> line;
MiniDhcpServer dhcp;
for (int loop = 0; loop < line; loop++) {
string str;
cin >> str;
string opration = str.substr(0, str.find_first_of("="));
string mac = str.substr(str.find_first_of("=") + 1);
if (opration == "REQUEST") {
cout << dhcp.Request(mac) << endl;
} else if (opration == "RELEASE") {
dhcp.Release(mac);
}
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
可能要考虑下原因？
参考别人代码：
/*
* Copyright (c) Huawei Technologies Co., Ltd. 2019-2020. All rights reserved.
* Description: 考生实现代码
* Note: 缺省代码仅供参考，可自行决定使用、修改或删除
*/
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <array>
#include <unordered_map>
#include <queue>
#include <list>
using namespace std;
// DHCP服务器的功能是为每一个MAC地址分配唯一的IP地址。现假设：分配的IP地址范围从 192.168.0.0 到 192.168.0.255 总共256个可用地址（以点分十进制表示）。请实现一个简易的DHCP服务器，功能如下：
// 分配Request：根据输入的MAC地址分配IP地址池中的IP地址：
// 如果对应的IP已分配并未释放，则为重复申请，直接返回对应已分配的IP地址。
// 如果一个MAC地址已申请过并已释放，即：当前未分配IP地址，则为再申请，优先分配最近一次曾经为其分配过的IP地址，请返回此地址。
// 按升序分配从未被分配过的IP地址；如果地址池中地址都已被分配过，则按升序分配已释放出来的IP地址；若可分配成功，则返回此IP地址。
// 若仍然无法分配成功，则返回NA。
// 释放Release：根据输入的MAC地址释放已分配的IP地址：
// 如果申请释放的对应的IP地址已分配，则释放此IP地址；
// 如果申请释放的对应的IP地址不存在，则不作任何事情；
class MiniDhcpServer {
public:
MiniDhcpServer() {
for(int i = 0; i < 256; ++i) {
free.push_back(i);
}
prefix = "192.168.0.";
}
string AllocateIP(const string& mac) {
int ip = -1;
if (free.empty()) { // 如果没有可分配的ip，升序push_back已释放的ip
for(int i = 0; i < 256; ++i) {
if(ip2mac[i].empty()) {
free.push_back(i);
}
}
}
if(free.empty()) { // 如果还是没有可分配ip，返回NA
return "NA";
}
else { // 如果有可分配ip，更新ip2mac和lastUsed
ip = free.front();
free.pop_front();
ip2mac[ip] = mac;
lastUsed[mac] = ip;
return prefix + to_string(ip);
}
}
string Request(const string &mac)
{
if(lastUsed.find(mac) != lastUsed.end()) { // 如果是曾经分配过的mac
int lu = lastUsed[mac];
if(ip2mac[lu] == mac) { // 重复申请
return prefix + to_string(lu);
}
else if(ip2mac[lu].empty()) { // 是已被释放尚未分配的ip
free.remove(lu);
ip2mac[lu] = mac;
return prefix + to_string(lu);
}
else { // 上一次分配的ip被分配了，正常分配
return AllocateIP(mac);
}
}
else { // 如果是新mac，正常分配
return AllocateIP(mac);
}
}
void Release(const string &mac)
{
for(string& mac_: ip2mac) {
if(mac_ == mac) {
mac_.clear();
break;
}
}
}
private:
list<int> free;
array<string, 256> ip2mac;
int idx = 0;
string prefix;
unordered_map<string, int> lastUsed;
};
int main()
{
int line;
cin >> line;
MiniDhcpServer dhcp;
for (int loop = 0; loop < line; loop++) {
string str;
cin >> str;
string opration = str.substr(0, str.find_first_of("="));
string mac = str.substr(str.find_first_of("=") + 1);
if (opration == "REQUEST") {
cout << dhcp.Request(mac) << endl;
} else if (opration == "RELEASE") {
dhcp.Release(mac);
}
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
12.代码缩进
缩进**的代码，通过多次操作，最终实现对每一行的缩进长度要求。
一次操作指：
- 一次操作是缩进一个TAB长度（如样例1图所示）。注：这里缩进仅指从左往右，不能回退。
- 一次操作可选择一行或连续多行同时缩进。
现给出一段代码的每行缩进长度要求，用一个数字序列表示，请计算至少需要多少次操作才能实现。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 256MB, 其他语言：512MB
输入
一个整数 n ，表示代码总行数，取值范围：[1, 65535]。
接下来一行有 n 个整数，依次表示第 1~n 行的最终缩进长度要求，取值范围：[0, 1000000]。
输出
一个整数，表示所需的最少操作次数。
样例1
复制输入：
5 1 2 3 2 1
复制输出：
3
解释：
最少需三次，第1次操作全选所有行，缩进1个TAB；第2次操作选择2、3、4行，再缩进1个TAB；第3次操作，选择第3行，再缩进1个TAB。 初始5行都未缩进，每次操作后的缩进变化情况如下图所示：
样例2
复制输入：
9 0 1 2 0 2 4 2 1 0
复制输出：
6
解释：
第1次操作选择第2、3行，缩进1个TAB；第2次选择第3行缩进1个TAB；第3次选择第5、6、7、8行，缩进1个TAB；第4次选择第5、6、7行，缩进1个TAB；第5次和第6次操作都选择第6行，分别缩进1个TAB。通过6次操作达成目标，因此输出6
提示
答题要求：结果可信和过程可信同样重要，您编写的代码需要符合可信的要求（包括通用编码规范、安全编码规范和圈复杂度）
C++代码：
/*
* Copyright (c) Huawei Technologies Co., Ltd. 2019-2020. All rights reserved.
* Description: 考生实现代码
* Note: 缺省代码仅供参考，可自行决定使用、修改或删除
*/
#include <iostream>
#include <vector>
using namespace std;
int GetMinStep(const std::vector<int> &steps) {
int n = steps.size();
if (n == 0) return 0;
// 计算所需操作数
int operations = steps[0]; // 对于第一行，你至少需要这么多操作。
// 遍历后续每一行，以确定所需的额外操作
for (int i = 1; i < n; i++) {
// 由于缩进只能增加，因此只将正向增加视为操作。
if (steps[i] > steps[i-1]) {
operations += (steps[i] - steps[i-1]);
}
}
return operations;
}
int main()
{
int num;
cin >> num;
vector<int> steps;
for (int i = 0; i < num; i++) {
int step;
cin >> step;
steps.push_back(step);
}
cout << GetMinStep(steps) << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
心得：采用贪心算法，将问题向量化，并对连续行之间所需的缩进差异进行操作，非常之巧妙！！！
13.四则表达式运算
给定一个字符串形式的计算表达式，其中只包含数字和加+、减-、乘*、除/四种运算符，乘除计算优先级高于加减。
请对该计算表达式求值，并返回计算结果。如果在计算过程中遇到除零，则返回字符串error。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 64MB, 其他语言：128MB
输入
一个字符串形式的计算表达式，长度范围：[1,100]
用例保证，输入数字和中间及最终计算结果的值都是整数，且在int型范围内。
输出
一个10进制整数； 或字符串error
样例1
复制输入：
3/0
复制输出：
error
心得：
这种表达式是无括号的，所以利用单栈就可以解决
- 遇到’+'，直接跳过
- 遇到’-'，连带负号和后面数字
num一起压栈 - 遇到’*'，将栈顶元素和乘号后面数字
num相乘，并将得到的结果再压栈 - 遇到’/'，判定’/‘后面的数字
num是否为零，为零返回false，不为零则栈顶元素和num相除，然后将结果压栈 - 最终将栈中元素全部相加，得到的结果即为所求
C++代码：(通过率100%–>第一版代码比较粗糙）
/*
* Copyright (c) Huawei Technologies Co., Ltd. 2020-2020. All rights reserved.
* Description: 上机编程认证
* Note: 缺省代码仅供参考，可自行决定使用、修改或删除
*/
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <stack>
using namespace std;
class Solution {
public:
// 待实现函数，在此函数中填入答题代码;
bool Calculate(const string &expression, int& result)
{
int i = 0, j = 0; // i用来遍历字符串表达式，j的作用是确定数字最终位置
stack<int> myStack; // 用栈来存储结果
int value = 0;
while (i < expression.size()) {
if (isdigit(expression[i])) { // 遇到了数字，直接将数字转化为整型后压栈
while (i < expression.size() && isdigit(expression[i])) {
value = (value * 10) + (expression[i] - '0');
i++;
}
myStack.push(value);
value = 0;
}else if (expression[i] == '+'){ // 遇到+，则跳过
i++;
}else if (expression[i] == '-') { // 遇到-，则连带负号和后面数字转为整型后一起压栈
j = i + 1;
while (j < expression.size() && isdigit(expression[j])) {
j++;
}
myStack.push(stoi(expression.substr(i, j - i)));
i = j;
}else if (expression[i] == '*') {
// 遇到*，将栈顶元素和乘号后面数字相乘，并将得到的结果转为整型后一起压栈
int num1 = myStack.top();
myStack.pop();
j = i + 1;
while (j < expression.size() && isdigit(expression[j])) {
j++;
}
int num2 = stoi(expression.substr(i + 1, j - i - 1));
int res = num1 * num2;
myStack.push(res);
i = j;
}else if (expression[i] == '/') {
// 遇到/，先判定后面的数字num2是否为零，为零返回false；不为零则栈顶元素和num2相除，然后将结果压栈
int num1 = myStack.top();
myStack.pop();
j = i + 1;
while (j < expression.size() && isdigit(expression[j])) {
j++;
}
int num2 = stoi(expression.substr(i + 1, j - i - 1));
if (num2 == 0) {
return false;
}else {
int res = num1 / num2;
myStack.push(res);
i = j;
}
}
}
while (!myStack.empty()) {
result += myStack.top();
myStack.pop();
}
bool isOk = true;
return isOk;
}
};
inline string ReadLine()
{
string line;
getline(cin, line);
return line;
}
int main()
{
string expr = ReadLine();
Solution solu;
int result = 0;
bool isOk = solu.Calculate(expr, result);
if (isOk) {
cout << result;
} else {
cout << "error";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
对于识别字符串中的数字，有两种方式：
j = i + 1;
while (j < expression.size() && isdigit(expression[j])) {
j++;
}
myStack.push(stoi(expression.substr(i, j - i)));
- 1
- 2
- 3
- 4
- 5
while (i < expression.size() && isdigit(expression[i])) {
value = value * 10 + (expression[i] - '0');
i++;
}
myStack.push(value);
value = 0;
- 1
- 2
- 3
- 4
- 5
- 6
利用switch-case语句优化：
/*
* Copyright (c) Huawei Technologies Co., Ltd. 2020-2020. All rights reserved.
* Description: 上机编程认证
* Note: 缺省代码仅供参考，可自行决定使用、修改或删除
*/
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <stack>
using namespace std;
class Solution {
public:
// 待实现函数，在此函数中填入答题代码;
bool Calculate(const string &expression, int& result)
{
int i = 0, j = 0; // i用来遍历字符串表达式，j的作用是确定数字最终位置
stack<int> myStack; // 用栈来存储结果
int num1, num2, value = 0;
while (i < expression.size()) {
switch (expression[i]) {
case '+': // 遇到+，则跳过
i++;
break;
case '-': // 遇到-，则连带负号和后面数字转为整型后一起压栈
j = i + 1;
while (j < expression.size() && isdigit(expression[j])) {
j++;
}
myStack.push(stoi(expression.substr(i, j - i)));
i = j;
break;
case '*': // 遇到*，将栈顶元素和乘号后面数字相乘，并将得到的结果转为整型后一起压栈
num1 = myStack.top();
myStack.pop();
j = i + 1;
while (j < expression.size() && isdigit(expression[j])) {
j++;
}
num2 = stoi(expression.substr(i + 1, j - i - 1));
myStack.push(num1 * num2);
i = j;
break;
case '/':
// 遇到/，先判定后面的数字num2是否为零，为零返回false；不为零则栈顶元素和num2相除，然后将结果压栈
num1 = myStack.top();
myStack.pop();
j = i + 1;
while (j < expression.size() && isdigit(expression[j])) {
j++;
}
num2 = stoi(expression.substr(i + 1, j - i - 1));
if (num2 == 0) {
return false;
} else {
myStack.push(num1 / num2);
i = j;
}
break;
default: // 否则就证明遇到了数字，直接将数字转化为整型后压栈
if (isdigit(expression[i])) {
while (i < expression.size() && isdigit(expression[i])) {
value = (value * 10) + (expression[i] - '0');
i++;
}
myStack.push(value);
value = 0;
}
break;
}
}
while (!myStack.empty()) {
result += myStack.top();
myStack.pop();
}
bool isOk = true;
return isOk;
}
};
inline string ReadLine()
{
string line;
getline(cin, line);
return line;
}
int main()
{
string expr = ReadLine();
Solution solu;
int result = 0;
bool isOk = solu.Calculate(expr, result);
if (isOk) {
cout << result;
} else {
cout << "error";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
若针对复杂的带有括号的表达式时，可以利用双栈来求解
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int performOperation(int a, int b, char op)
{
switch(op)
{
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': if (b == 0) throw "error"; return a / b;
}
return 0;
}
int getPriority(char ch)
{
if (ch == '*' || ch == '/') return 2;
if (ch == '+' || ch == '-') return 1;
return 0;
}
bool Calculate(const string &expression, int& result)
{
bool isOk = true;
stack<int> values;
stack<char> operators;
for(int i = 0; i < expression.length(); i++)
{
if(expression[i] == ' ') continue;
if(isdigit(expression[i]))
{
int value = 0;
while(i < expression.length() && isdigit(expression[i]))
{
value = (value*10) + (expression[i]-'0');
i++;
}
values.push(value);
i--;
}
else if(expression[i] == '(')
{
operators.push(expression[i]);
}
else if(expression[i] == ')')
{
while(!operators.empty() && operators.top() != '(')
{
int val2 = values.top(); values.pop();
int val1 = values.top(); values.pop();
char op = operators.top(); operators.pop();
values.push(performOperation(val1, val2, op));
}
if(!operators.empty()) operators.pop();
}
else
{
while(!operators.empty() && getPriority(operators.top()) >= getPriority(expression[i]))
{
int val2 = values.top(); values.pop();
int val1 = values.top(); values.pop();
char op = operators.top(); operators.pop();
values.push(performOperation(val1, val2, op));
}
operators.push(expression[i]);
}
}
while(!operators.empty())
{
int val2 = values.top(); values.pop();
int val1 = values.top(); values.pop();
char op = operators.top(); operators.pop();
values.push(performOperation(val1, val2, op));
}
if(!values.empty())
{
result = values.top();
}
else
{
isOk = false;
}
return isOk;
}
int main()
{
string expression;
int result;
cout << "Enter the expression: ";
getline(cin, expression);
try
{
if(Calculate(expression, result))
cout << "Result: " << result << endl;
else
cout << "error" << endl;
}
catch(const char* error)
{
cout << error << endl;
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
14.促销活动
华为商城举办了一个促销活动，某一秒内最早的订单（可能多个）可以获取免单。
现给定一批订单记录，请计算有多少个订单可以获取免单。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 256MB, 其他语言：512MB
输入
第一行一个整数 size, 表示顾客下单数量，其值范围：[1, 50000)
随后为 size 行字符串，每行表示一个订单的下单时间，格式为：
YYYY-MM-DD hh:mm:ss.fff
其中 YYYY-MM-DD hh:mm:ss 表示下单时间的 年-月-日 小时:分:秒，皆为合法范围。
fff 表示下单时间的毫秒值，值的范围为 [0, 999]
输出
一个整数，表示有多少个订单可以获取免单。
样例1
复制输入：
3
2019-01-01 00:00:00.001
2019-01-01 00:00:00.002
2019-01-01 00:00:00.003
复制输出：
1
解释：
三个订单都是同一秒（年-月-日 小时:分:秒）内下单，毫秒时间第一个订单最早，可以免单。
样例2
复制输入：
6
2019-01-01 00:00:00.001
2019-01-01 00:00:00.002
2019-01-01 00:00:00.003
2019-01-01 08:59:00.123
2019-01-01 08:59:00.123
2018-12-28 13:08:00.999
复制输出：
4
解释：
- 前三个订单是同一秒（年-月-日 小时:分:秒 都相同）内下单，第一个订单的毫秒时间最早、可以免单； 第二、三个订单不是该秒内的最早时间、不可免单。
- 第四、五个订单是另外的同一秒内下单，且毫秒时间也完全相同，因此同为最早时间、都可以免单。
- 最后一个订单是该秒内唯一的一个订单，也是最早、可以免单。
因此共有 4 个订单可以免单。
样例3
复制输入：
5
2019-01-01 00:00:00.004
2019-01-01 00:00:00.004
2019-01-01 00:00:01.006
2019-01-01 00:00:01.006
2019-01-01 00:00:01.005
复制输出：
3
解释：
前两个订单是同一秒内同一时刻（也是最早）下单，第三第四个订单不是当前秒内最早下单，不可免单，第五个订单可以免单。
提示
您编写的代码需要符合可信的要求（包括通用编码规范、安全编码规范和圈复杂度）
C++代码：
/*
* Copyright (c) Huawei Technologies Co., Ltd. 2020-2020. All rights reserved.
* Description: 上机编程认证
* Note: 缺省代码仅供参考，可自行决定使用、修改或删除
*/
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;
class Solution {
public:
int FreeOrder(const vector<string> &orderTime) {
// 这里用一个map来存储每一秒对应的最早订单时间
map<string, string> earliestTimes;
// 遍历所有订单，记录每秒的最早订单
for (const string &time : orderTime) {
string secondKey = time.substr(0, 19); // YYYY-MM-DD hh:mm:ss 部分
string millis = time.substr(20); // fff 部分
// 如果当前秒还没有记录，或者新的订单时间更早，则更新记录
if (earliestTimes.find(secondKey) == earliestTimes.end() || millis < earliestTimes[secondKey]) {
earliestTimes[secondKey] = millis;
}
}
// 现在earliestTimes中存储了每秒的最早时间，我们需要去统计这些最早时间的订单数量
int count = 0;
for (const string &time : orderTime) {
string secondKey = time.substr(0, 19);
string millis = time.substr(20);
// 只有当时间完全符合该秒内记录的最早时间时，才算是免单
if (millis == earliestTimes[secondKey]) {
count++;
}
}
return count;
}
};
inline int ReadInt()
{
int number;
cin >> number;
return number;
}
inline string ReadLine()
{
string line;
getline(cin, line);
return line;
}
int main()
{
int m = ReadInt();
cin.ignore();
vector<string> orderTime;
for (int i = 0; i < m; i++) {
string oneRow = ReadLine();
orderTime.push_back(oneRow);
}
Solution solu;
int result = solu.FreeOrder(orderTime);
cout << result << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
15.遥控小车
假设在平面直角坐标系（上北-Y轴正方向，下南-Y轴负方向，左西-X轴负方向，右东-X轴正方向）上，一个遥控小车最初位于原点 (0, 0) 处，且面朝北方。
遥控小车可以接受下列三条指令之一：
“G”：直走 1 个单位
“L”：左转 90 度
“R”：右转 90 度
给定一批指令，遥控小车按顺序执行每个指令后，请计算遥控小车最终所处的位置。
用例保证整个过程中坐标(x,y)的值都在 int (32 位系统)范围内
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 64MB, 其他语言：128MB
输入
字符串表示的一批遥控指令，仅由字符 G、L、R组成，长度范围[1,100]
输出
小车最终所处位置的坐标
样例1
复制输入：
GG
复制输出：
(0,2)
解释：
提示
答题要求：结果可信和过程可信同样重要，您编写的代码需要符合可信的要求（包括通用编码规范、安全编码规范和圈复杂度）。
解答：
要完成这个问题，我们首先需要理解整个遥控小车的移动和旋转机制。
小车的方向使用一个点 (dir_x, dir_y) 来代表，对于面向北方，我们可以使用 (0, 1)表示。当小车左转或右转时，方向会相应改变。下面是四个基本方向与对应符号的关系：
- 北
(0, 1) - 东
(1, 0) - 南
(0, -1) - 西
(-1, 0)
左转使用 (dir_x, dir_y) 转变为 (-dir_y, dir_x)，而右转用 (dir_x, dir_y) 转变为 (dir_y, -dir_x)。这两个变换来自于线性代数中的旋转矩阵。
接下来就是按照输入命令来改变小车的位置和当前方向。这里使用一个函数实现，命名为 ExecCommand 来代表执行这些命令。
根据整体逻辑编写代码如下:
/*
* Copyright (c) Huawei Technologies Co., Ltd. 2020-2020. All rights reserved.
* Description: 上机编程认证
* Note: 缺省代码仅供参考，可自行决定使用、修改或删除
*/
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
string ExecCommand(const string &commands) {
// 初始化位置和方向
int x = 0, y = 0;
// 方向表示为二维数组，依次代表北、东、南、西的方向变化
vector<pair<int, int>> directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
int curDir = 0; // 0 表示北
// 遍历命令执行
for (char command : commands) {
if (command == 'G') {
// 根据当前方向移动
x += directions[curDir].first;
y += directions[curDir].second;
} else if (command == 'L') {
// 左转，顺时针旋转至前一个方向
curDir = (curDir + 3) % 4;
} else if (command == 'R') {
// 右转，顺时针旋转至下一个方向
curDir = (curDir + 1) % 4;
}
}
// 形成结果字符串
return "(" + to_string(x) + "," + to_string(y) + ")";
}
};
inline string ReadLine()
{
string line;
getline(cin, line);
return line;
}
int main()
{
string commands = ReadLine();
Solution solu;
string result = solu.ExecCommand(commands);
cout << result;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
16.最长的指定瑕疵度的元音子串
定义：开头和结尾都是元音字母（aeiouAEIOU）的字符串为 元音字符串 ，其中混杂的非元音字母数量为其 瑕疵度 。比如:
- “a” 、 "aa"是元音字符串，其瑕疵度都为0
- "aiur"不是元音字符串（结尾不是元音字符）
- "abira"是元音字符串，其瑕疵度为2
给定一个字符串，请找出指定瑕疵度的最长元音字符子串，并输出其长度，如果找不到满足条件的元音字符子串，输出0。
子串：字符串中任意个连续的字符组成的子序列称为该字符串的子串。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 256MB, 其他语言：512MB
输入
首行输入是一个整数，表示预期的瑕疵度flaw，取值范围 [0, 65535]。
接下来一行是一个仅由字符a-z和A-Z组成的字符串，字符串长度 (0, 65535]。
输出
输出一个整数，代表满足条件的元音字符子串的长度。
样例1
复制输入：
0 asdbuiodevauufgh
复制输出：
3
解释：
满足条件的最长元音字符子串有两个，分别为uio和auu，长度为3。
样例2
复制输入：
2 aeueo
复制输出：
0
解释：
没有满足条件的元音字符子串，输出0
样例3
复制输入：
1 aabeebuu
复制输出：
5
解释：
满足条件的最长元音字符子串有两个，分别为aabee和eebuu，长度为5
/*
* Copyright (c) Huawei Technologies Co., Ltd. 2019-2020. All rights reserved.
* Description: 上机编程认证
* Note: 缺省代码仅供参考，可自行决定使用、修改或删除
*/
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <climits>
using namespace std;
bool isVowel(char c) {
static const unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
return vowels.find(c) != vowels.end();
}
int GetLongestFlawedVowelSubstrLen(int flaw, const string& input) {
if (input.empty()) return 0;
int maxLen = 0; // 最大长度初始化为0
int numFlaws = 0; // 当前瑕疵数
int left = 0, right = 0;
while (right < input.length()) {
while (right < input.length() && (!isVowel(input[left]) || !isVowel(input[right]))) {
if (isVowel(input[right])) {
right++; // 右指针往右扩展
} else {
numFlaws++;
right++; // 右指针往右扩展
}
while (numFlaws > flaw) {
if (!isVowel(input[left])) {
numFlaws--;
}
left++; // 左指针往右扩展
}
}
if (numFlaws == flaw && isVowel(input[left]) && isVowel(input[right])) {
maxLen = max(maxLen, right - left + 1);
}
right++; // 有可能第一个条件已经满足，左指针没有移动，所以右指针要往右移动
}
return maxLen;
}
int main()
{
size_t flaw;
cin >> flaw;
string input;
cin >> input;
cout << GetLongestFlawedVowelSubstrLen(flaw, input) << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
心得：
- 碰见子串问题，就要想到用滑动窗口，核心就是要想滑动窗口的两个左右指针在什么条件下移动，以及边界条件的设置！
17.批次计算任务
某业务需要连续上报 10000 批的数据（批次从1到10000），可能会存在数据上报失败（某一批次数据上报失败后不影响后续数据上报）。假设已知 nCount 批上报失败的批次，现给你 mCount 次机会纠错，每次机会只能纠错一个批次，并保证成功。
请计算纠错后（不一定需要用完所有机会），最大的连续上报成功的数据批数是多少。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 256MB, 其他语言：512MB
输入
第一行两个整数 nCount mCount，分别表示上报失败的批数和纠错的机会，取值范围都为 [0,10000]
第二行 nCount 个整数，表示上报失败的批次序列，且为升序，值的范围 [1,10000]
输出
一个整数，表示最大的连续上报成功的数据批数
样例1
复制输入：
2 1 83 800
复制输出：
9917
解释：
纠错前，连续上报成功的区间为[1,82]、[84,799]和[801,10000]，批数分别为82、716、9200。 选择对第800批纠错，纠错后[84,10000]连续上报成功的批数最大，为9917
样例2
复制输入：
2 2 12 34
复制输出：
10000
解释：
对两批都纠错，则10000批数据全部连续上报成功
样例3
复制输入：
5 1 2 3000 5000 8000 9990
复制输出：
4999
解释：
选择对第5000批纠错，则[3001,7999]连续上报成功，批数为4999
C++代码：
/*
* Copyright (c) Huawei Technologies Co., Ltd. 2020-2020. All rights reserved.
* Description: 上机编程认证
* Note: 缺省代码仅供参考，可自行决定使用、修改或删除
*/
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
class Solution {
public:
// 待实现函数，在此函数中填入答题代码;
int BatchCalculation(int mCount, vector<int>& nums) {
int nCount = nums.size();
// 最大的连续上报成功的数据批数，数据批次为：[1,10000],上报失败n，纠错次数m，上报失败批次nums
if (mCount >= nCount || nCount < 1) {
return 10000;
}
vector<int> successBatchNum(nCount + 1);
successBatchNum[0] = nums[0] - 1;
for (int i = 1; i < nums.size(); i++) {
successBatchNum[i] = nums[i] - nums[i - 1] - 1;
}
successBatchNum[nCount] = 10000 - nums[nums.size() - 1];
int maxNum = 0;
//利用滑动窗口计算出最大的连续上报成功批数:先将前mCount+1个值相加求和
for (int i = 0; i <= mCount; i++) {
maxNum += successBatchNum[i];
}
// 之后遍历剩余的元素，通过前mCount+1个值的和，减一个successBatchNum[i-(mCount+1)]，
// 加一个successBatchNum[i]求出滑动窗口为mCount+1个值的和。
// 这种方式的滑动窗口很巧妙，抓住批次必须是“
int sum = maxNum;
for (int i = mCount + 1; i < successBatchNum.size(); i++) {
sum = sum - successBatchNum[i - mCount - 1] + successBatchNum[i];
if (sum > maxNum) {
maxNum = sum;
}
}
maxNum += mCount;
return maxNum;
}
};
inline int ReadInt()
{
int number;
cin >> number;
return number;
}
template<typename T>
inline vector<T> ReadVector(int size)
{
vector<T> objects(size);
for (int i = 0; i < size; ++i) {
cin >> objects[i];
}
return objects;
}
int main()
{
int n = ReadInt();
int m = ReadInt();
auto numbers = ReadVector<int>(n);
Solution solu;
int result = solu.BatchCalculation(m, numbers);
cout << result << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
18.二进制转十进制
输入一个二进制字符串，请处理转换成十进制整数
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 64MB, 其他语言：128MB
输入
二进制字符串（仅含 0 和 1 ），用例保证转换结果范围在 32 位有符号整型范围以内。
输出
十进制整数
样例1
复制输入：
00011
复制输出：
3
解释：
样例2
复制输入：
11111111111111111111111111111111
复制输出：
-1
解释：
注：二进制字符串表示的是整数的补码形式，从右向左第32位1表示此数为负数。
提示
答题要求：结果可信和过程可信同样重要，您编写的代码需要符合可信的要求（包括通用编码规范、安全编码规范和圈复杂度）。
C++代码：
/*
* Copyright (c) Huawei Technologies Co., Ltd. 2020-2020. All rights reserved.
* Description: 上机编程认证
* Note: 缺省代码仅供参考，可自行决定使用、修改或删除
*/
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
class Solution {
public:
int BinaryToDecimal(const std::string &binaryString) const
{
int result = 0;
for(char digit : binaryString) {
result = result * 2 + (digit - '0');
}
return result;
}
};
inline string ReadLine()
{
string line;
getline(cin, line);
return line;
}
int main()
{
string binaryString = ReadLine();
Solution solu;
int result = solu.BinaryToDecimal(binaryString);
cout << result << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
19.完美答案收集
考生在在线平台考试结束后，可以查看自己每道题的结果（包括题干、选项、答案、回答正确或错误），针对回答错误的题目并没有给出正确答案。这时需要综合多个考生的正确答案才能得到一份该试卷的完美答案（即包含所有题目的正确答案）。
假设共有 questionsCount 道题，题目编号从 1 到 questionsCount。现给出每个考生的答对题目的编号，格式如1 3，表示答对第1到3题；9 9表示答对第9题。
说明：
- 考生答对的题目是连续的。
- 每个考生至少答对1道题。
请计算至少需综合多少个考生的正确答案才能得到完美答案，如果无法综合到完美答案，则输出-1。
解答要求
时间限制: C/C++ 3000ms, 其他语言：6000ms
内存限制: C/C++ 256MB, 其他语言：512MB
输入
第一行一个整数，表示题目的总数量questionsCount，范围 [1, 1024]
第二行一个整数，表示考生人数peopleCount，范围 [1, 1024]
接下来peopleCount行，每行两个整数start end， 1 <= start <=end <= questionsCount
输出
一个整数，表示可以综合到完美答案的最少人数；如果无法综合到完美答案，则输出-1 。
样例1
复制输入：
10 6 1 3 4 6 1 6 6 10 5 8 10 10
复制输出：
2
解释：
试卷一共有10道题；
第一位同学答对了1~3题；
第二位同学答对了4~6题；
第三位同学答对了1~6题；
第四位同学答对了6~10题；
第五位同学答对了5~8题；
第六位同学只答对了第10题一个题。要综合到所有题的正确答案，可以有多种方法，例如：综合第一、二、四这3位考生的答案，或者综合第三、四这2位考生的答案。 至少需要综合2位考生的答案。
C++代码：
/*
* Copyright (c) Huawei Technologies Co., Ltd. 2019-2020. All rights reserved.
* Description: 完美答案收集
* Note: 缺省代码仅供参考，可自行决定使用、修改或删除
*/
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
int GetMinPeople(int questionsCount, int peopleCount, const vector<pair<int, int>>& correctRanges) {
// 对区间按照起始点进行排序，如果起始点相同，则按终点递减排序
vector<pair<int, int>> ranges = correctRanges;
sort(ranges.begin(), ranges.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
return a.first < b.first || (a.first == b.first && a.second > b.second);
});
int needed = 0; // 统计需要的最少考生数
int currentEnd = 0; // 当前覆盖的最远位置
int i = 0; // 遍历每个考生的答对区间
int maxEnd = 0; // 可达到的最远区间的终点
while (currentEnd < questionsCount) {
// 尽量扩展当前的区间范围
bool found = false;
while (i < peopleCount && ranges[i].first <= currentEnd + 1) {
found = true;
maxEnd = max(maxEnd, ranges[i].second);
i++;
}
if (!found) break; // 如果没有找到合适的考生，直接退出
// 更新当前覆盖的最远位置，并增加考生计数
currentEnd = maxEnd;
needed++;
//如果已经覆盖了所有题目
if (currentEnd >= questionsCount) {
return needed;
}
}
// 如果循环结束后，没有覆盖到所有的题目，返回 -1
return -1;
}
int main()
{
int questionsCount;
cin >> questionsCount;
int peopleCount;
cin >> peopleCount;
vector<pair<int, int>> correctRanges(peopleCount);
for (int i = 0; i < peopleCount; ++i) {
cin >> correctRanges[i].first >> correctRanges[i].second;
}
cout << GetMinPeople(questionsCount, peopleCount, correctRanges);
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
20.CI任务调度
CI任务调度
持续集成 CI 系统需要调度多台虚拟机资源 VM ，用于并发执行多个任务（每个任务有两个属性，执行时间T和优先级P），调度规则如下：
- 一个VM同一时间只能执行一个任务。
- 当VM不足时，优先级高的任务优先被执行，数字越小优先级越高；优先级相同的任务，执行时间长的先被执行。
- 当资源充足时，不同优先级的任务可以同时被执行。
现给定一次构建的N个任务，VM数量为M，请计算执行完所有任务的总时间。 结果需要取模 1e9+7（1000000007），如计算初始值为：1000000008，则返回 1。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 256MB, 其他语言：512MB
输入
第一行一个整数 M，表示空闲资源VM的数量，取值范围 [1,10000]。
第二行一个整数 N，表示该次构建的任务数量，取值范围[1,20000]。
接下来 N行，每行两个整数 T 和 P，分别表示一个任务的执行时间和优先级，取值范围：1 <= T <= 10^9， 1 <= P <= 10 。
输出
一个整数，表示执行完所有任务的总时间。
样例1
复制输入：
2 4 1 1 2 1 3 2 2 2
复制输出：
4
解释：
由于只有两个VM，优先级为1的两个任务先被执行，优先级为2的两个任务等待。其中VM1执行完时长为1的任务后，这时可以执行优先级为2、时长为3的任务；接着等VM2空闲时，再执行时长为2的任务。 这样可以得到执行完所有任务的总时间为4。
样例2
复制输入：
4 3 3 1 1 1 2 2
复制输出：
3
解释：
4个VM，3个任务。由于资源充足，3个任务虽然优先级不一样，但仍可全部并发执行，执行完所有任务的总时间为3 。
C++代码：
// we have defined the necessary header files here for this problem.
// If additional header files are needed in your program, please import here.
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MOD = 1e9 + 7;
struct Attrib {
int time;
int priority;
};
class Solution {
public:
int TaskScheduler(int resourcesNum, const vector<Attrib> &taskAttributes) {
vector<Attrib> tasks(taskAttributes);
// 优先级高的先，同优先级执行时间长的先
sort(tasks.begin(), tasks.end(), [](const Attrib& a, const Attrib& b) {
if (a.priority == b.priority) {
return a.time > b.time; // 时长长的先
}
return a.priority < b.priority; // 优先级小的优先
});
priority_queue<long long, vector<long long>, greater<long long>> pq;
// 初始化资源
for (int i = 0; i < resourcesNum; ++i) {
pq.push(0); // 所有VM初始时刻为空闲
}
for (const auto& task : tasks) {
long long earliestAvailable = pq.top();
pq.pop();
pq.push(earliestAvailable + task.time); // 更新该VM的忙碌截止时间
}
long long maxTime = 0;
while (!pq.empty()) {
maxTime = pq.top();
pq.pop();
}
return (int)(maxTime % MOD); // 返回处理完所有任务的总时间取模
}
};
inline int ReadInt()
{
int number;
cin >> number;
return number;
}
template<typename T>
inline vector<T> ReadVector(int size)
{
vector<T> objects(size);
for (int i = 0; i < size; ++i) {
cin >> objects[i];
}
return objects;
}
int main()
{
int resourcesNum = ReadInt();
int n = ReadInt();
vector<Attrib> taskAttributes;
for (int i = 0; i < n; ++i) {
Attrib obj;
cin >> obj.time >> obj.priority;
taskAttributes.push_back(obj);
}
Solution solu;
int result = solu.TaskScheduler(resourcesNum, taskAtt
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
C++中priority_queue用法：
在C++中，我们通常使用标准库中的std::priority_queue来模拟堆（heap）的行为，但std::priority_queue默认实现的是最大堆（max heap）。不过，通过提供自定义的比较器（comparator），我们可以实现最小堆（min heap）。
最大堆（Max Heap）
最大堆是一个完全二叉树，其中每个父节点的值都大于或等于其子节点的值。在C++中，使用std::priority_queue默认就是最大堆，因为std::priority_queue默认会将元素按照从大到小的顺序排列。
cpp复制代码
#include <queue>
#include <functional> // 引入 std::greater 用于最小堆
int main() {
std::priority_queue<int> maxHeap; // 默认是最大堆
maxHeap.push(3);
maxHeap.push(1);
maxHeap.push(4);
// 顶部元素是 4（最大的）
// 访问顶部元素（但不删除）
int top = maxHeap.top();
// 删除顶部元素
maxHeap.pop();
// ...
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
最小堆（Min Heap）
最小堆是一个完全二叉树，其中每个父节点的值都小于或等于其子节点的值。为了在C++中实现最小堆，我们需要为std::priority_queue提供一个自定义的比较器，通常使用std::greater。
cpp复制代码
#include <queue>
#include <functional> // 引入 std::greater 用于最小堆
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // 最小堆
minHeap.push(3);
minHeap.push(1);
minHeap.push(4);
// 顶部元素是 1（最小的）
// 访问顶部元素（但不删除）
int top = minHeap.top();
// 删除顶部元素
minHeap.pop();
// ...
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
在上面的代码中，std::priority_queue<int, std::vector, std::greater>定义了一个最小堆，其中std::vector是底层容器（尽管通常不需要明确指定，除非有特殊需求），而std::greater是比较器，它确保堆按照从小到大的顺序排列。
f additional header files are needed in your program, please import here.
#include
#include
#include
#include
#include
using namespace std;
const int MOD = 1e9 + 7;
struct Attrib {
int time;
int priority;
};
class Solution {
public:
int TaskScheduler(int resourcesNum, const vector &taskAttributes) {
vector tasks(taskAttributes);
// 优先级高的先，同优先级执行时间长的先
sort(tasks.begin(), tasks.end(), [](const Attrib& a, const Attrib& b) {
if (a.priority == b.priority) {
return a.time > b.time; // 时长长的先
}
return a.priority < b.priority; // 优先级小的优先
});
priority_queue<long long, vector<long long>, greater<long long>> pq;
// 初始化资源
for (int i = 0; i < resourcesNum; ++i) {
pq.push(0); // 所有VM初始时刻为空闲
}
for (const auto& task : tasks) {
long long earliestAvailable = pq.top();
pq.pop();
pq.push(earliestAvailable + task.time); // 更新该VM的忙碌截止时间
}
long long maxTime = 0;
while (!pq.empty()) {
maxTime = pq.top();
pq.pop();
}
return (int)(maxTime % MOD); // 返回处理完所有任务的总时间取模
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
};
inline int ReadInt()
{
int number;
cin >> number;
return number;
}
template
inline vector ReadVector(int size)
{
vector objects(size);
for (int i = 0; i < size; ++i) {
cin >> objects[i];
}
return objects;
}
int main()
{
int resourcesNum = ReadInt();
int n = ReadInt();
vector taskAttributes;
for (int i = 0; i < n; ++i) {
Attrib obj;
cin >> obj.time >> obj.priority;
taskAttributes.push_back(obj);
}
Solution solu;
int result = solu.TaskScheduler(resourcesNum, taskAtt
- 1
- 2
##### C++中`priority_queue`用法：
在C++中，我们通常使用标准库中的std::priority_queue来模拟堆（heap）的行为，但std::priority_queue默认实现的是最大堆（max heap）。不过，通过提供自定义的比较器（comparator），我们可以实现最小堆（min heap）。
##### 最大堆（Max Heap）
最大堆是一个完全二叉树，其中每个父节点的值都大于或等于其子节点的值。在C++中，使用std::priority_queue默认就是最大堆，因为std::priority_queue默认会将元素按照从大到小的顺序排列。
```cpp
cpp复制代码
#include <queue>
#include <functional> // 引入 std::greater 用于最小堆
int main() {
std::priority_queue<int> maxHeap; // 默认是最大堆
maxHeap.push(3);
maxHeap.push(1);
maxHeap.push(4);
// 顶部元素是 4（最大的）
// 访问顶部元素（但不删除）
int top = maxHeap.top();
// 删除顶部元素
maxHeap.pop();
// ...
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
最小堆（Min Heap）
最小堆是一个完全二叉树，其中每个父节点的值都小于或等于其子节点的值。为了在C++中实现最小堆，我们需要为std::priority_queue提供一个自定义的比较器，通常使用std::greater。
cpp复制代码
#include <queue>
#include <functional> // 引入 std::greater 用于最小堆
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // 最小堆
minHeap.push(3);
minHeap.push(1);
minHeap.push(4);
// 顶部元素是 1（最小的）
// 访问顶部元素（但不删除）
int top = minHeap.top();
// 删除顶部元素
minHeap.pop();
// ...
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
在上面的代码中，std::priority_queue<int, std::vector, std::greater>定义了一个最小堆，其中std::vector是底层容器（尽管通常不需要明确指定，除非有特殊需求），而std::greater是比较器，它确保堆按照从小到大的顺序排列。
