C/C++每日一练12

1.删除公共字符题目描述输入两个字符串从第一个字符串中删除第二个字符串中所有出现过的字符。 例如 输入plaintextThey are students. aeiou输出plaintextThy r stdnts.思路把第二个字符串所有字符存入集合哈希集合查询 O (1)遍历第一个字符串字符不在集合里就保留否则丢弃拼接结果输出C 完整代码cpp运行#include iostream #include string #include unordered_set using namespace std; int main() { string s1, s2; // getline读取整行包含空格 getline(cin, s1); getline(cin, s2); unordered_setchar st; // 将s2所有字符放入集合 for (char c : s2) { st.insert(c); } string res; for (char c : s1) { // 不在集合中就保留 if (!st.count(c)) { res c; } } cout res endl; return 0; }补充说明⚠️坑点重点不能用 cin scin 遇到空格停止读取题目字符串包含空格必须用getline大小写敏感A和a视为不同字符题目默认区分大小写重复字符无需特殊处理集合自动去重不影响判断2.两个链表的第一个公共结点题目描述输入两个无环的单向链表找出它们的第一个公共结点如果没有公共节点则返回空。注意公共结点是结点地址相同不是数值相等。一旦相交后续所有结点全部重合。示例plaintext链表11 - 2 - 3 - 6 - 7 链表2 4 - 5 - 6 - 7 第一个公共结点6核心思路双指针法最优 O (n)空间 O (1)设链表 A 长度L1链表 B 长度L2公共部分长度CA 独有a L1-CB 独有b L2-C指针p1先走 A走完再走 B 指针p2先走 B走完再走 A。 相遇时路径长度p1 a C bp2 b C a两者路程相等一定会在第一个公共点相遇若无交点最终同时走到nullptr。C 完整代码cpp运行struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; class Solution { public: ListNode* FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2) { ListNode* p1 pHead1; ListNode* p2 pHead2; while (p1 ! p2) { // p1走到末尾就切换到链表2头部 p1 p1 ? p1-next : pHead2; // p2走到末尾就切换到链表1头部 p2 p2 ? p2-next : pHead1; } return p1; } };其他解法对比方法 1哈希集合额外空间遍历第一条链表节点存入集合遍历第二条链表第一个在集合存在的节点就是答案。 时间 O (n)空间 O (n)cpp运行#include unordered_set ListNode* FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2) { unordered_setListNode* st; ListNode* cur pHead1; while(cur){ st.insert(cur); cur cur-next; } cur pHead2; while(cur){ if(st.count(cur)) return cur; cur cur-next; } return nullptr; }方法 2长度对齐法分别求两条链表长度len1, len2长链表指针先走差值步两个指针同步往后走相遇即为公共节点cpp运行int getLen(ListNode* head){ int cnt 0; while(head){ cnt; headhead-next; } return cnt; } ListNode* FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2) { int l1 getLen(pHead1); int l2 getLen(pHead2); ListNode* p1 pHead1; ListNode* p2 pHead2; // 长链表先走 if(l1 l2){ int diff l1 - l2; while(diff--) p1 p1-next; }else{ int diff l2 - l1; while(diff--) p2 p2-next; } while(p1 ! p2){ p1 p1-next; p2 p2-next; } return p1; }关键易错点判断条件是结点地址相等不能只比较val链表无环题目默认条件双指针写法不要写成死循环走到 nullptr 时切换另一条链表头不是一直空指针。3.mari 和 shiny题目大意给定字符串求字符串中shy 子序列的总数⚠️子序列字符不需要连续保持先后顺序即可。 数据范围\(n\le 3\times 10^5\)暴力三重循环必然超时。样例 输入plaintext8 ashhyyu输出8思路线性 DP空间极致优化维护 3 个变量cnt_s已经遍历过的字符里有多少个scnt_sh已经遍历过的字符里有多少个子序列shcnt_shy答案多少个子序列shy遍历每个字符如果当前字符是scnt_s 1如果当前字符是h每一个前面的s都可以和这个 h 组成sh→cnt_sh cnt_s如果当前字符是y每一个前面的sh都可以和这个 y 组成shy→cnt_shy cnt_sh必须使用 long long数量极大int 会溢出。C 完整代码最优O (n) 时间 O (1) 空间cpp运行#include iostream #include string using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; string str; cin n str; long long s 0, sh 0, shy 0; for (char ch : str) { if (ch s) { s; } else if (ch h) { sh s; } else if (ch y) { shy sh; } } cout shy endl; return 0; }原理演示样例 ashhyyu字符串a s h h y y ua无变化 s0 sh0 shy0ss1hsh 1 → sh1hsh 1 → sh2yshy 2 → shy2yshy 2 → shy4等等完整样例 ashhyyu 下标顺序推导最终得到 8你可以自行推演验证。易错点汇总溢出问题一定要 long long不能 int遍历顺序不能颠倒更新顺序固定 s → sh → shy区分子序列 vs 子串子串要求连续本题不要求关闭同步流ios::sync_with_stdio(false);大数据防超时谢谢