​​​​​48days强训——day12

第一题：删除公共字符

链接：

描述 输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入”They are students.”和”aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.” 输入描述： 每个测试输入包含2个字符串 输出描述： 输出删除后的字符串 示例1 输入： They are students. aeiou 输出： Thy r stdnts.

题解：用一个哈希存储第二个字符串的所有字符，遍历第一个字符串的所有字符，哈希表中有的则删除。

代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s, sub,ret;
    getline(cin, s);  
    getline(cin, sub); 
    
    unordered_map<char, int> hash;
    for(auto& x : sub) hash[x]++;
    for(auto& x : s )
    {
        if(hash[x]==0)ret+=x;
    }
    cout << ret << endl;
    return 0;
}

第二题：两个链表的第⼀个公共结点

链接：两个链表的第一个公共结点_牛客题霸_牛客网

描述 输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的） 数据范围： n≤1000n≤1000 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n) 例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：

​ 可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。 输入描述： 输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。 返回值描述： 返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。 示例1 输入： {1,2,3},{4,5},{6,7} 返回值： {6,7} 说明： 第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分 这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的 示例2 输入： {1},{2,3},{} 返回值： {} 说明： 2个链表没有公共节点 ,返回null，后台打印{}

题解一：模拟，先让长的链表走到短链表相应的位置，之后再走。

题解二：两个指针分别遍历两个链表，当到达末尾时切换到另一链表头部继续遍历。如果两链表相交，指针会在公共节点相遇；否则同时到达NULL结束循环。

代码一：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) 
	{
		if(pHead1==nullptr || pHead2 == nullptr) return nullptr;

        ListNode* cur1 = pHead1, *cur2 = pHead2;
		int count1 = 1,count2 = 1;
		while (cur1->next) 
		{
			cur1 = cur1->next;
			count1++;
		}
		while (cur2->next) 
		{
			cur2 = cur2->next;
			count2++;
		}

		int len = abs(count1-count2);
		//默认1>2;
		ListNode* longlist = pHead1,*shortlist = pHead2;
		if(count2 > count1)
		{
			shortlist = pHead1;
			longlist = pHead2;
		}

		while(len--)
		{
			longlist = longlist->next;
		}
		while(longlist != shortlist)
		{
			longlist = longlist->next;
        	shortlist = shortlist->next;
		}

		return longlist;
    }
};

代码二：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) 
	{
         ListNode* cur1 = pHead1, *cur2 = pHead2;
                while(cur1 != cur2)
                {
                        cur1 = cur1 != NULL ? cur1->next : pHead2;
                        cur2 = cur2 != NULL ? cur2->next : pHead1;
                }
                return cur1;
    }
};

第三题：mari和shin

题目描述 mari每天都非常shiny。她的目标是把正能量传达到世界的每个角落！ 有一天，她得到了一个仅由小写字母组成的字符串。 她想知道，这个字符串有多少个"shy"的子序列？ （所谓子序列的含义见样例说明） 输入描述: 第一行一个正整数n，代表字符串的长度。（1≤n≤300000） 第二行为一个长度为n，仅由小写字母组成的字符串。 输出描述: 一个正整数，代表子序列"shy"的数量。 示例1 输入 8 sshhyyau 输出 8 说明 假设字符串下标从1到8。共有（135）（136）（145）（146）（235）（236）（245）（246）八个"shy"子序列。 备注: mari大喊道：“是shiny不是shy！！！”

题解：维护i位置之前，⼀共有多少个"s""sh"，然后更新"shy"的个数。

代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    string str;
    cin >> n >> str;

    long long s = 0, h = 0, y = 0;
    for(int i = 0; i < n; i++)
    {
        char ch = str[i];
        if(ch == 's') s++;
        else if(ch == 'h') h += s;
        else if(ch == 'y') y += h;
    }
    
    cout << y << endl;
    
    return 0;
 }