[笔试训练](十二)

目录

034:删除公共字符串

035:两个链表的第一个公共节点

036:mari和shiny

034:删除公共字符串

删除公共字符_牛客题霸_牛客网 (nowcoder.com)

题解:

用哈希记录好第二个字符串中的字符，再遍历一遍第一个字符串，只将没有记录的字符加在结果字符串上。

#include <iostream>
#include<string>
using namespace std;

int main() 
{
    string s;
    string t;
    getline(cin,s);
    getline(cin,t);

    bool hash[300]={0};
    for(auto ch:t) hash[ch]=true;

    string ret;
    for(auto ch:s)
    {
        if(hash[ch]==false)
        {
            ret+=ch;
        }
    }

    cout<<ret<<endl;
    return 0;

}

035:两个链表的第一个公共节点

 两个链表的第一个公共结点_牛客题霸_牛客网 (nowcoder.com)

题目: 

题解：

1.计数:从两个头节点遍历一遍计算长度差，长的链表先走len步再同时向后遍历当两节点相同时，到达第一个公共节点。

2.等量关系:两个头节点遍历双头链表的全部节点是等价的，所以两个头节点同时开始向后遍历到结尾后，到另一个头节点继续遍历，最终会在公共相交节点相遇（此时刚好均遍历完全部节点）。

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) 
	{
		//计数
		ListNode* cur1=pHead1,* cur2=pHead2;
		
		int count1=0,count2=0;
		while(cur1 || cur2)
		{
			if(cur1)
			{
				count1++;
				cur1=cur1->next;
			}
			if(cur2)
			{
				count2++;
				cur2=cur2->next;
			}
		}

		int len=0;
		ListNode* longList;
		ListNode* shortList;
		if(count1>count2)
		{
			longList=pHead1;
			shortList=pHead2;
			len=count1-count2;
		}
		else
		{
			longList=pHead2;
			shortList=pHead1;
			len=count2-count1;
		}
		cur1=longList;
		cur2=shortList;
		
		for(int i=0;i<len;i++)
		{
			cur1=cur1->next;
		}
		while(cur1 && cur2)
		{
			if(cur1==cur2) return cur1;
			cur1=cur1->next;
			cur2=cur2->next;
		}
		return 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;
    }
};

036:mari和shiny

mari和shiny (nowcoder.com)

题目:

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

#include<iostream>
#include<string>
using namespace std;
int main()
{
    string S;
    int n=0;
    cin>>n;
    cin>>S;
    
    long long s=0,h=0,y=0;
    for(auto ch : S)
    {
        if(ch=='s') s++;
        else if(ch=='h') h+=s;
        else if(ch=='y') y+=h;
    }
    cout<<y<<endl;
    return 0;
}