1.删除公共字符
思路：
无
代码：
#define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> #include<unordered_map> using namespace std; int main() { string str1, str2; getline(cin, str1); getline(cin, str2); unordered_map<char, int> mp; // cout<<str1<<" "<<str2<<endl; for (int i = 0; i < str2.size(); i++) { mp[str2[i]]++; } string ans = ""; for (int i = 0; i < str1.size(); i++) { if (mp.count(str1[i]))continue; ans += str1[i]; } cout << ans << endl; return 0; } // 64 位输出请用 printf("%lld")
2.两个链表的第一个公共节点
思路：
先计算每个链表的长度，长的那一条就先走，走到剩下的节点数量和另一条相等。然后两个链表再一起走，直到找到相同节点为止。
这个思路在LCA求最近公共祖先的算法里也有用到。
代码：
#define _CRT_SECURE_NO_WARNINGS 1 class Solution { public: ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) { if (!pHead1 || !pHead2)return nullptr; ListNode* cur1 = pHead1; ListNode* cur2 = pHead2; int n1 = 0; int n2 = 0; while (cur1) { cur1 = cur1->next; n1++; } while (cur2) { cur2 = cur2->next; n2++; } cur1 = pHead1; cur2 = pHead2; if (n1 > n2) { while (n1 > n2) { cur1 = cur1->next; n1--; } } else { while (n1 < n2) { cur2 = cur2->next; n2--; } } while (cur1 && cur2 && cur1 != cur2) { cur1 = cur1->next; cur2 = cur2->next; } return cur1; } };
3.mari和shiny
思路：
求子序列的数量。子序列的相对位置是固定的。于是可以想到，对于每一个’y‘,前面能组成多少个”sh“。要想算出”sh“的数量，也可以用类似的思路。对于每一个’h‘,前面有多少个’s'就表示以当前‘h’结尾的”sh“序列有多少个。于是我们只需要遍历一遍数组，遇到‘s'就记录一下，遇到’h'就结算一下sh,遇到y,就结算一下‘shy'。
代码：
#include <iostream> using namespace std; int main() { string str; int n; cin>>n; cin>>str; long long a=0,b=0; long long ans=0; long long k=0;//记录每一个’y‘前面的”sh"的数量 for(int i=0;i<n;i++){ if(str[i]=='s')a++; else if(str[i]=='h')b=a,k+=b; else if(str[i]=='y'){ ans+=k; } } cout<<ans<<endl; return 0; }
