c/c++每日一练1

1.数字统计题目描述输入一个整数 n统计这个数字中每一个数字0~9分别出现多少次依次输出 0、1、2……9 的出现次数。输入示例plaintext123321输出示例plaintext0:0 1:2 2:2 3:2 4:0 5:0 6:0 7:0 8:0 9:0思路创建长度为 10 的数组cnt[0~9]初始全 0记录每个数字出现次数循环取数字最后一位n%10对应计数 1去掉最后一位n n//10直到n0停止循环从 0 到 9 依次输出数字和对应次数#include iostream using namespace std; int main() { int n; cin n; int cnt[10] {0}; // 处理每一位数字 while (n ! 0) { int d n % 10; cnt[d]; n n / 10; } // 按顺序输出0~9 for (int i 0; i 10; i) { cout i : cnt[i] endl; } return 0; }2.两个数组的交集题目描述给定两个整数数组求它们的交集。 要求交集中每个元素只出现一次去重最终输出结果从小到大升序排列输入格式先输入第一个数组长度 n再输入 n 个整数再输入第二个数组长度 m再输入 m 个整数。输入样例plaintext4 1 2 2 1 3 2 2 3输出样例plaintext2输入样例 2plaintext5 4 9 5 4 9 4 9 8 4输出样例 2plaintext4 9写法 1unordered_set 存交集自动去重最后要排序#include iostream #include vector #include unordered_set #include algorithm using namespace std; int main() { int n, x; unordered_setint s1, inter; // 读第一个数组 cin n; for (int i 0; i n; i) { cin x; s1.insert(x); } // 读第二个数组存入交集集合自动去重 cin n; for (int i 0; i n; i) { cin x; if (s1.count(x)) { inter.insert(x); } } // unordered_set无序必须转vector排序才能按要求输出 vectorint ans(inter.begin(), inter.end()); sort(ans.begin(), ans.end()); // 打印 for (int i 0; i ans.size(); i) { if (i 0) cout ; cout ans[i]; } return 0; }写法 2set 存交集自带去重 升序无需排序#include iostream #include set using namespace std; int main() { int n, x; setint s1, inter; cin n; for (int i 0; i n; i) { cin x; s1.insert(x); } cin n; for (int i 0; i n; i) { cin x; if (s1.count(x)) { inter.insert(x); } } // set内部红黑树从小到大有序直接输出不用排序 bool first true; for (int num : inter) { if (!first) cout ; first false; cout num; } return 0; }3.unordered_set 比 set 更快核心原因是底层数据结构不同1. 底层实现差异unordered_set哈希表插入、查找、删除平均时间复杂度\(O(1)\)set红黑树平衡二叉搜索树插入、查找、删除稳定时间复杂度\(O(logn)\)数据量越大两者速度差距越明显。举个直观例子 数组长度 100000unordered_set 查询一次 ≈ 1 次计算set 查询一次 ≈ 约 17 次对比跳转2. 做题场景优势牛客刷题优点 1大数据不超时牛客部分测试用例数组长度开到 1e5、1e6用 set 容易时间超限 TLEunordered_set哈希查找速度快基本不会超时。优点 2只需要 “去重、判断存在” 时哈希性价比极高求交集只需要两件事存第一组数字快速判断某个数是否存在自动去重 哈希完美适配这个需求。3. unordered_set 唯一缺点 解决方案缺点无序输出要求升序时要额外排序。 但排序只做一次代价很低把交集全部倒进 vector一次 sort \(O(klogk)\)k 是交集元素个数远小于原数组长度 这点开销完全抵消不了哈希查找带来的速度优势。4. 对比完整时间开销假设原数组长度 n,m交集数量 kunordered_set 方案总复杂度\(O(nm klogk)\)set 方案总复杂度\(O(nlogn mlogm)\)n、m 很大时nlogn 远大于 \(nmklogk\)哈希更快。5. 什么时候选 set只有一种情况适合 set 数据量很小且不想写排序代码追求代码简短省事。 正常刷题、大数据场景一律优先unordered_set。总结刷题优先 unordered_set 的核心理由查找插入平均 \(O(1)\)速度碾压 set海量数据不会超时仅需末尾一次轻量排序开销可以忽略自动去重功能完全满足求交集需求。3.点击消除一、题目完整描述牛牛拿到一个小写字母字符串每次操作可以消除一对相邻相同字符消除后两边字符会贴在一起可能产生新的相邻相同字符重复消除直到无法消除。 求最终剩下的字符串如果全部消空输出0。输入一行小写字母长度 ≤ 300000大数据不能暴力循环删除输出消除后的字符串空串输出0样例输入abbc过程bb 消除 →ac无相邻相同 输出ac输入abba过程先消 bb →aa再消 aa → 空串 输出0输入bbbbb过程bb 消剩 bbb → bb 消剩 b 输出b二、核心思路栈模拟用字符串 /vector 充当栈规则遍历每个字符 c如果栈不为空且栈顶字符 当前 c出栈消除一对否则当前字符入栈 遍历结束后栈内就是最终结果。优势一次遍历 O (n)处理 3e5 长度不超时暴力 erase 会超时。三、C 标准可提交代码cpp运行模拟栈#include iostream #include string using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 加速输入适配超长字符串 string s, st; cin s; for (char c : s) { if (!st.empty() st.back() c) { st.pop_back(); // 相同消除栈顶 } else { st.push_back(c); // 不同入栈 } } if (st.empty()) cout 0\n; else cout st \n; return 0; }栈#include iostream #include stack #include string #include algorithm using namespace std; int main() { string s; stackchar st; cin s; for (char c : s) { if (!st.empty() st.top() c) st.pop(); else st.push(c); } string ans; while (!st.empty()) { ans.push_back(st.top()); st.pop(); } reverse(ans.begin(), ans.end()); cout ans.empty() ? 0 : ans; return 0; }关键细节说明为什么不用循环 erasestring.erase删除中间字符会移动后面所有元素多次循环时间复杂度 \(O(n^2)\)3e5 长度直接超时。栈只遍历一次最优。自动处理连锁消除例abbaa 入栈 → [a]b 入栈 → [a,b]下一个 b栈顶相等弹出 → [a]下一个 a栈顶相等弹出 → []最后输出 0输入加速 ios::sync_with_stdio (false)字符串很长时不加会读入超时刷题必加。谢谢