admin管理员组文章数量:1029900
48days强训——day12
第一题：删除公共字符
链接：
描述 输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入”They are students.”和”aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.” 输入描述： 每个测试输入包含2个字符串 输出描述： 输出删除后的字符串 示例1 输入： They are students. aeiou 输出： Thy r stdnts.
题解：用一个哈希存储第二个字符串的所有字符，遍历第一个字符串的所有字符，哈希表中有的则删除。
代码：
代码语言：javascript代码运行次数：0运行复制#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结束循环。
代码一：
代码语言：javascript代码运行次数：0运行复制/*
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;
}
};代码二：
代码语言：javascript代码运行次数：0运行复制/*
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"的个数。
代码：
代码语言：javascript代码运行次数：0运行复制#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;
}48days强训——day12
第一题：删除公共字符
链接：
描述 输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入”They are students.”和”aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.” 输入描述： 每个测试输入包含2个字符串 输出描述： 输出删除后的字符串 示例1 输入： They are students. aeiou 输出： Thy r stdnts.
题解：用一个哈希存储第二个字符串的所有字符，遍历第一个字符串的所有字符，哈希表中有的则删除。
代码：
代码语言：javascript代码运行次数：0运行复制#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结束循环。
代码一：
代码语言：javascript代码运行次数：0运行复制/*
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;
}
};代码二：
代码语言：javascript代码运行次数：0运行复制/*
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"的个数。
代码：
代码语言：javascript代码运行次数：0运行复制#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;
}本文标签： 48days强训day12
版权声明：本文标题：48days强训——day12 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1747616727a2193854.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论