用php做电商网站有哪些,游戏开发物语完美搭配,diy在线定制网站系统,网站上做旅游卖家要学什么1.大小端整数
计算机中对整型数据的表示有两种方式#xff1a;大端序和小端序#xff0c;大端序的高位字节在低地址#xff0c;小端序的高位字节在高地址。例如#xff1a;对数字 65538#xff0c;其4字节表示的大端序内容为00 01 00 02#xff0c;小端序内容为02 00 01…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_castunsigned 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:// 待实现函数在此函数中填入答题代码;vectorchar GetNTimesCharacter(int n, const vectorstring strings){// 存储所有字符串中字符出现至少n次的结果mapchar, int globalCharFreq;vectorchar result;for (int i 0; i strings.size(); i) {mapchar, 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;
}templatetypename T
inline vectorT ReadVector(int size)
{vectorT objects(size);for (int i 0; i size; i) {cin objects[i];}return objects;
}templatetypename T
inline void WriteVector(const vectorT 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();vectorstring strings ReadVectorstring(m);Solution solu;auto result solu.GetNTimesCharacter(n, strings);cout [;WriteVector(result);cout ] endl;return 0;
}
3.呼叫转移
呼叫转移
呼叫转移是指您的电话无法接听或您不愿接电话可以将来电转移到其它电话号码上。它是电信业一项传统通信业务又称呼叫前转、呼入转移。
用户被呼叫时的状态有4种idlebusyno-responseunreachable用户可登记的5种呼叫转移格式为type numbertype代表转移种类 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 和 字符串 statusnum代表呼叫转移登记的次数 0 N 20status表示用户被呼叫时的状态。 接下来 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 vectorpairint, string regCallForwardNums){unordered_mapint, string callForwards;// 初始化呼叫状态映射unordered_mapstring, 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且无无条件转移type0return 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 vectorstring ReadLines(int size)
{vectorstring lines(size);for (int i 0; i size; i) {lines[i] ReadLine();}return lines;
}inline pairstring, 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()
{pairstring, string p SplitPair(ReadLine(), );int n stoi(p.first);string status p.second;vectorstring lines ReadLines(n);vectorpairint, 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:// 待实现函数在此函数中填入答题代码;vectorstring GetAllFault(const vectorstring arrayA, const vectorstring arrayB){// Combine both arrays into onevectorstring 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 sortingvectorpairunsigned 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 resultvectorstring result;for (const auto pair : converted) {result.push_back(pair.second);}return result;}
};inline int ReadInt()
{int number;std::cin number;return number;
}templatetypename T
inline std::vectorT ReadVector(int size)
{std::vectorT objects(size);for (int i 0; i size; i) {std::cin objects[i];}return objects;
}templatetypename T
inline void WriteVector(const std::vectorT 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();vectorstring arrayA ReadVectorstring(arrayANum);int arrayBNum ReadInt();vectorstring arrayB ReadVectorstring(arrayBNum);Solution solu;auto result solu.GetAllFault(arrayA, arrayB);cout [;WriteVector(result, );cout ] endl;return 0;
}
5.表达式计算
现给你一个字符串代表一个后序遍历形式的四则运算表达式请计算出表达式的结果只输出整数部分。 注 都是双目运算不存在单目运算;中间计算结果范围[-2^31, 2^31)除法只需保留整数部分比如:5/41, (-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:// 将字符串表达式分割成操作数和运算符的数组vectorstring SplitExpression(const string expression) {vectorstring 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) {stackint st;vectorstring 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 vectorint bill, const vectorint pri){int num bill.size();vectorpairint, 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;
}templatetypename T
inline std::vectorT ReadVector(int size)
{std::vectorT objects(size);for (int i 0; i size; i) {std::cin objects[i];}return objects;
}int main()
{int cap ReadInt();int n ReadInt();vectorint bill ReadVectorint(n);vectorint pri ReadVectorint(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;vectorint digits;vectorchar lowercase;vectorchar 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 和 endstart 是当前无重复子串的起始索引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 和 NM 表示手机壳种类的个数取值范围[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 vectorfloat inventory, const vectorfloat price){int len inventory.size();vectorpairfloat, 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;
}templatetypename T
inline std::vectorT ReadVector(int size)
{std::vectorT objects(size);for (int i 0; i size; i) {std::cin objects[i];}return objects;
}int main()
{ int num;float demand;cin num demand;vectorfloat inventory ReadVectorfloat(num);vectorfloat price ReadVectorfloat(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但都来自同一个ip192.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_mapusing namespace std;class Solution {
public:// 待实现函数在此函数中填入答题代码;;vectorint GetActiveUserNum(const vectorstring logs){// 定义一个数组来统计每天的日活数初始化31天数组索引1-31对应于日期vectorint daily_active(32, 0);// 一个哈希表记录每天成功登录的不同IPunordered_mapint, setunsigned int daily_ips;// 一个集合记录整个月成功登录的不同IPsetunsigned 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;
}templatetypename T
inline vectorT ReadVector(int size)
{vectorT objects(size);for (int i 0; i size; i) {cin objects[i];}return objects;
}templatetypename T
inline void WriteVector(const vectorT 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();vectorstring logs ReadVectorstring(n);Solution solu;vectorint 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 REQUESTAABBCCDDEEF1 RELEASEAABBCCDDEEF1 复制输出 192.168.0.0 解释 REQUESTAABBCCDDEEF1 按升序分配从未使用过的IP地址输出192.168.0.0 RELEASEAABBCCDDEEF1 不输出 样例2 复制输入 6 REQUESTAABBCCDDEEF1 REQUESTF2FBBCCDDEEF RELEASEAABBCCDDEEF1 RELEASEF2FBBCCDDEEF REQUEST333333333333 REQUESTF2FBBCCDDEEF 复制输出 192.168.0.0 192.168.0.1 192.168.0.2 192.168.0.1 解释 REQUESTAABBCCDDEEF1 按升序分配从未使用过的IP为192.168.0.0 REQUESTF2FBBCCDDEEF 按升序分配从未使用过的IP为192.168.0.1 RELEASEAABBCCDDEEF1 释放IP 192.168.0.0。 RELEASEF2FBBCCDDEEF 释放IP 192.168.0.1。 REQUEST333333333333 按升序分配从未使用过的IP为192.168.0.2 REQUESTF2FBBCCDDEEF 该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_mapstring, string macToIP; // Maps MAC addresses to their currently assigned IPunordered_mapstring, string previousAllocation; // Maps MAC addresses to their last IP (for re-allocation)queuestring availableIPs; // Queue for available IPs to ease allocation in ascending orderunordered_mapstring, 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 isnt 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:listint free;arraystring, 256 ip2mac;int idx 0;string prefix;unordered_mapstring, 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
复制输出
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 vectorusing namespace std;
int GetMinStep(const std::vectorint 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;vectorint 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的作用是确定数字最终位置stackint 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的作用是确定数字最终位置stackint 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;stackint values; stackchar 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 复制输出
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 vectorstring orderTime) {// 这里用一个map来存储每一秒对应的最早订单时间mapstring, 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();vectorstring 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
复制输入
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;// 方向表示为二维数组依次代表北、东、南、西的方向变化vectorpairint, 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是元音字符串其瑕疵度都为0aiur不是元音字符串结尾不是元音字符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 climitsusing namespace std;
bool isVowel(char c) {static const unordered_setchar 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, vectorint nums) {int nCount nums.size();// 最大的连续上报成功的数据批数数据批次为[1,10000],上报失败n纠错次数m上报失败批次numsif (mCount nCount || nCount 1) {return 10000;}vectorint 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;//利用滑动窗口计算出最大的连续上报成功批数:先将前mCount1个值相加求和for (int i 0; i mCount; i) {maxNum successBatchNum[i];}// 之后遍历剩余的元素通过前mCount1个值的和减一个successBatchNum[i-(mCount1)]// 加一个successBatchNum[i]求出滑动窗口为mCount1个值的和。// 这种方式的滑动窗口很巧妙抓住批次必须是“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;
}templatetypename T
inline vectorT ReadVector(int size)
{vectorT objects(size);for (int i 0; i size; i) {cin objects[i];}return objects;
}int main()
{int n ReadInt();int m ReadInt();auto numbers ReadVectorint(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
复制输出
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;
}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 vectorpairint, int correctRanges) {// 对区间按照起始点进行排序如果起始点相同则按终点递减排序vectorpairint, int ranges correctRanges;sort(ranges.begin(), ranges.end(), [](const pairint, int a, const pairint, 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;vectorpairint, 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请计算执行完所有任务的总时间。 结果需要取模 1e971000000007如计算初始值为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个VM3个任务。由于资源充足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 vectorAttrib taskAttributes) {vectorAttrib 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_queuelong long, vectorlong long, greaterlong 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;
}templatetypename T
inline vectorT ReadVector(int size)
{vectorT objects(size);for (int i 0; i size; i) {cin objects[i];}return objects;
}int main()
{int resourcesNum ReadInt();int n ReadInt();vectorAttrib 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, taskAttC中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_queueint 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_queueint, std::vectorint, std::greaterint minHeap; // 最小堆 minHeap.push(3); minHeap.push(1); minHeap.push(4); // 顶部元素是 1最小的 // 访问顶部元素但不删除 int top minHeap.top(); // 删除顶部元素 minHeap.pop(); // ... return 0; } 在上面的代码中std::priority_queueint, 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_queuelong long, vectorlong long, greaterlong 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_queueint 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_queueint, std::vectorint, std::greaterint minHeap; // 最小堆 minHeap.push(3); minHeap.push(1); minHeap.push(4); // 顶部元素是 1最小的 // 访问顶部元素但不删除 int top minHeap.top(); // 删除顶部元素 minHeap.pop(); // ... return 0; } 在上面的代码中std::priority_queueint, std::vector, std::greater定义了一个最小堆其中std::vector是底层容器尽管通常不需要明确指定除非有特殊需求而std::greater是比较器它确保堆按照从小到大的顺序排列。
