华为编程题目（实时更新）

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 overflowif (input < -2147483648LL || input >= 4294967296LL) {return "overflow";}// Convert input to unsigned intunsigned int value = static_cast<unsigned int>(input);// Convert unsigned int to big endian and little endian stringsstringstream 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 stringsstring 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;
}

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;
}

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>> &regCallForwardNums){unordered_map<int, string> callForwards;// 初始化呼叫状态映射unordered_map<string, int> statusMap = {{"idle", -1}, {"busy", 1}, {"no-response", 2}, {"unreachable", 3}};// 存储用户设置的呼叫转移for (auto &reg : regCallForwardNums) {callForwards[reg.first] = reg.second;}if (status == "idle" && callForwards.count(0) == 0) {// 用户状态为idle，且无无条件转移type=0return "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;
}

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 onevector<string> combined(arrayA);combined.insert(combined.end(), arrayB.begin(), arrayB.end());// Remove duplicatessort(combined.begin(), combined.end());combined.erase(unique(combined.begin(), combined.end()), combined.end());// Convert hex strings to integers for sortingvector<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 valuesort(converted.begin(), converted.end());// Extract the sorted strings back into the resultvector<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;
}

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;
}

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;
}

心得：

核心就是利用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;
}

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); // 初始化每个字符的最后位置为-1long 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;
}

代码解读：

代码中使用了滑动窗口技术结合数组来追踪字符的最后出现位置，有效解决了要求无重复字符的子串计数问题。下面我将逐步详解这段代码的实现和逻辑：

初始化：

数组 lastPos：这个数组用于存储每个英文字母最后一次出现在字符串中的位置。因为字符串仅包含小写字母，所以数组大小为26。初始化为-1，表示开始时，没有任何字母被访问过。

int lastPos[26];
std::fill_n(lastPos, 26, -1);

变量定义：

变量 totalCount：用于累计满足条件的子串数量。由于字符串长度可能非常大（最大100万），所以使用 long long 类型以避免整数溢出。
窗口的指针 start 和 end：start 是当前无重复子串的起始索引，end 是当前正在处理的字符的索引。

主逻辑循环：

对字符串 input 进行遍历。

扩展窗口： 每次循环体内，end 指针每次都会向右移动一位（扩展窗口的右边界）。

for (int end = 0; end < n; ++end) {}

检查并更新 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);
}

计算子串数量：
- 窗口内的字符都是不重复的，且以 end 指向的字符结尾的子串数量等于窗口长度。end - start + 1 表示从 start 到 end（包括end）字符的数量。

totalCount += (end - start + 1);

更新处理中的字符的最后出现位置：

lastPos[charIndex] = end;

返回结果：

循环结束后，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;
}

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);// 一个哈希表记录每天成功登录的不同IPunordered_map<int, set<unsigned int>> daily_ips;// 一个集合记录整个月成功登录的不同IPset<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;
}

其中，将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;}
};

这段函数standardize_ip是一个私有成员函数，它的目的是将IP地址字符串转换为无符号整数，以便于后续的比较和存储操作。下面是对这段函数的详细分析：

函数签名

private:  
unsigned int standardize_ip(const string &ip)

private:：表明这个函数是类的私有成员函数，只能被该类的其他成员函数或友元函数访问。
unsigned int：函数的返回类型是无符号整数。
standardize_ip：函数名称。
const string &ip：函数接收一个常量字符串引用作为参数，这个字符串代表一个IP地址。

函数体

变量声明

cpp复制代码int a, b, c, d; // 四个部分的整数值

这里声明了四个整型变量a、b、c和d，它们将用于存储IP地址的各个部分。

使用sscanf函数解析IP地址

cpp复制代码sscanf(ip.c_str(), "%d.%d.%d.%d", &a, &b, &c, &d);

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;

这里使用了位操作来将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 IPunordered_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 orderunordered_map<string, bool> ipUsed; // Track whether IP has been used ever for re-allocationpublic: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;
}

可能要考虑下原因？

参考别人代码：


/** 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已释放的ipfor(int i = 0; i < 256; ++i) {if(ip2mac[i].empty()) {free.push_back(i);}}}if(free.empty()) { // 如果还是没有可分配ip，返回NAreturn "NA";}else { // 如果有可分配ip，更新ip2mac和lastUsedip = 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()) { // 如果是曾经分配过的macint lu = lastUsed[mac];if(ip2mac[lu] == mac) { // 重复申请return prefix + to_string(lu);} else if(ip2mac[lu].empty()) { // 是已被释放尚未分配的ipfree.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;
}

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

复制输出：

解释：

最少需三次，第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

复制输出：

解释：

第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;
}

心得：采用贪心算法，将问题向量化，并对连续行之间所需的缩进差异进行操作，非常之巧妙！！！

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;
}

对于识别字符串中的数字，有两种方式：

                    j = i + 1;while (j < expression.size() && isdigit(expression[j])) {j++;}myStack.push(stoi(expression.substr(i, j - i)));

                        while (i < expression.size() && isdigit(expression[i])) {value = value * 10 + (expression[i] - '0');i++;}myStack.push(value);value = 0;

利用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;
}

若针对复杂的带有括号的表达式时，可以利用双栈来求解

#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;elsecout << "error" << endl;}catch(const char* error){cout << error << endl;}return 0;
}

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

复制输出：

解释：

三个订单都是同一秒（年-月-日小时:分:秒）内下单，毫秒时间第一个订单最早，可以免单。

样例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 个订单可以免单。

样例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

复制输出：

解释：

前两个订单是同一秒内同一时刻（也是最早）下单，第三第四个订单不是当前秒内最早下单，不可免单，第五个订单可以免单。

提示

您编写的代码需要符合可信的要求（包括通用编码规范、安全编码规范和圈复杂度）

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;
}

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

复制输入：

复制输出：

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

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

复制输出：

解释：

满足条件的最长元音字符子串有两个，分别为uio和auu，长度为3。

样例2

复制输入：

2 aeueo

复制输出：

解释：

没有满足条件的元音字符子串，输出0

样例3

复制输入：

1 aabeebuu

复制输出：

解释：

满足条件的最长元音字符子串有两个，分别为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;  // 最大长度初始化为0int 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;
}

心得：

碰见子串问题，就要想到用滑动窗口，核心就是要想滑动窗口的两个左右指针在什么条件下移动，以及边界条件的设置！

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，上报失败批次numsif (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;
}

18.二进制转十进制

输入一个二进制字符串，请处理转换成十进制整数

解答要求

时间限制: C/C++ 1000ms, 其他语言：2000ms

内存限制: C/C++ 64MB, 其他语言：128MB

输入

二进制字符串（仅含 0 和 1 ），用例保证转换结果范围在 32 位有符号整型范围以内。

输出

十进制整数

样例1

复制输入：

00011

复制输出：

解释：

样例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;
}

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

复制输出：

解释：

试卷一共有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;}}// 如果循环结束后，没有覆盖到所有的题目，返回 -1return -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;
}

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

复制输出：

解释：

由于只有两个VM，优先级为1的两个任务先被执行，优先级为2的两个任务等待。其中VM1执行完时长为1的任务后，这时可以执行优先级为2、时长为3的任务；接着等VM2空闲时，再执行时长为2的任务。这样可以得到执行完所有任务的总时间为4。

样例2

复制输入：

4 3 3 1 1 1 2 2

复制输出：

解释：

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

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;  }

最小堆（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;  }

在上面的代码中，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); // 返回处理完所有任务的总时间取模
}

};

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


##### 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;  }

最小堆（Min Heap）

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;  }