[已解决]用双指针怎么写

lsmCC

题目链接：https://codeforces.com/problemset/problem/978/B

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int n,sum=0;//表示操作数
   
4. string s;
   
5. int main()
   
6. {
   
7.     cin>>n;
   
8.     cin>>s;
   
9.     vector<int>a;
   
10.     for(int i=0,j=0;i<s.size();i++)
    
11.     {
    
12.         while(j<s.size()&&s[j]=='x')j++;
    
13.         a.push_back(j-i-1);
    
14.         i=j-1;
    
15.     }
    
16.     for(auto i:a)
    
17.     {
    
18.         if(i>3)sum+=i-2;
    
19.         else if(i==3)sum+=1;
    
20.         
    
21.     }
    
22.     cout<<sum<<endl;
    
23.    
    
24.         
    
25.    
    
26. 
    
27. }

复制代码

我双指针写的不对

最佳答案

月排行榜 / 总排行榜

tommyyu

2023-11-24 19:41:30

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int n,sum=0;//表示操作数
   
4. string s;
   
5. int main()
   
6. {
   
7.     cin>>n;
   
8.     cin>>s;
   
9.     vector<int>a;
   
10.     for(int i=0,j=0;i<s.size();i++, j++)
    
11.     {
    
12.         while(j<s.size()&&s[j]=='x')j++; // 这个循环结束后，a[j]的值将不是'x'
    
13.         a.push_back(j-i);                // 好比 "xxxiii"，上一条语句执行后 i 的值是 0，j 的值是 3，很明显要添加的是 j-i
    
14.         i=j;                             // 此时 i 与 j 直接到了同一位置，开启下一轮循环
    
15.     }
    
16.     for(int i=0; i<a.size(); ++i) //我的编译器不支持 auto ，抱歉暂时改了
    
17.     {
    
18.         //if(a[i]>3)sum+=a[i]-2;
    
19.         //else if(a[i]==3)sum+=1;  //可以合并
    
20.                 if(a[i]>=3) sum += (a[i]-2);
    
21.         }
    
22.     cout<<sum<<endl;
    
23. }

复制代码

跳转到最佳答案楼层

Mike_python小

你好！对于你提供的代码段，我注意到你想使用双指针来解决问题。根据给定的题目链接，这个问题涉及对字符串进行操作并计数。

在你提供的代码中，使用了两个指针变量i和j，其中i用于迭代字符串中的每个字符，而j用于跳过连续的字符。

然而，根据题目的要求，在统计特定字符序列长度时，我们需要注意一些细节。下面是对你提供的代码进行修改的版本：

1. ++
2. #include <iostream>
3. #include <vector>
4. using namespace std;
6. int main() {
7.     int n;
8.     cin >> n;
9.    
10.     string s;
11.     cin >> s;
12.    
13.     int i = 0, j = 0; // 双指针
14.    
15.     int count = 0; // 连续字符计数
16.     long long sum = 0; // 计算结果
17.    
18.     while (j < n) {
19.         if (s[j] == 'x') {
20.             count++;
21.         } else {
22.             if (count >= 3) {
23.                 sum += count - 2;
24.             }
25.             count = 0;
26.         }
27.         j++;
28.     }
29.    
30.     // 处理末尾字符序列
31.     if (count >= 3) {
32.         sum += count - 2;
33.     }
34.    
35.     cout << sum << endl;
36.    
37.     return 0;
38. }

复制代码

在这个修改后的代码中，我们使用了两个指针i和j，其中i指向当前字符，而j用于寻找连续字符序列的结束位置。我们采用了一种更简洁的方式来统计连续字符的长度，并根据规则进行计数。

希望这次的回答能够解决你的问题！如果你还有其他疑问，请随时提问。

回复来自于CHAT-GPT。回复仅供参考，如有人工回答，最佳答案请优先选择人工

FishC_GPT

双指针是一种常用的算法技巧，在解决某些问题时非常有效。在给定的问题中，我们需要统计字符串中连续出现的"xxx"子串的个数。

以下是使用双指针的代码实现：

1. #include <iostream>
2. #include <string>
3. using namespace std;
5. int main() {
6.     int n;
7.     cin >> n;
8.     string s;
9.     cin >> s;
10.    
11.     int count = 0; // 统计子串个数
12.    
13.     for (int i = 0; i < n-2; ) {
14.         // 如果当前字符和下两个字符都为'x'，说明找到了一个子串
15.         if (s[i] == 'x' && s[i+1] == 'x' && s[i+2] == 'x') {
16.             count++;
17.             // 将指针移动到下一个位置
18.             i += 3;
19.         } else {
20.             // 否则，将指针向后移动一位
21.             i++;
22.         }
23.     }
24.    
25.     cout << count << endl;
27.     return 0;
28. }

复制代码

在这段代码中，我们使用单个循环来遍历整个字符串。我们设定一个指针i，初始值为0。如果当前字符和下两个字符都为'x'，说明找到了一个"xxx"子串，我们将子串个数count加一，并将指针移动到下一个位置（即i += 3）。如果不满足上述条件，我们将指针向后移动一位（即i++）。

最后，输出统计的子串个数即可。

希望对你有所帮助！
以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

tommyyu

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int n,sum=0;//表示操作数
   
4. string s;
   
5. int main()
   
6. {
   
7.     cin>>n;
   
8.     cin>>s;
   
9.     vector<int>a;
   
10.     for(int i=0,j=0;i<s.size();i++, j++)
    
11.     {
    
12.         while(j<s.size()&&s[j]=='x')j++; // 这个循环结束后，a[j]的值将不是'x'
    
13.         a.push_back(j-i);                // 好比 "xxxiii"，上一条语句执行后 i 的值是 0，j 的值是 3，很明显要添加的是 j-i
    
14.         i=j;                             // 此时 i 与 j 直接到了同一位置，开启下一轮循环
    
15.     }
    
16.     for(int i=0; i<a.size(); ++i) //我的编译器不支持 auto ，抱歉暂时改了
    
17.     {
    
18.         //if(a[i]>3)sum+=a[i]-2;
    
19.         //else if(a[i]==3)sum+=1;  //可以合并
    
20.                 if(a[i]>=3) sum += (a[i]-2);
    
21.         }
    
22.     cout<<sum<<endl;
    
23. }

复制代码

小甲鱼

FishC_GPT 发表于 2023-11-24 19:25
双指针是一种常用的算法技巧，在解决某些问题时非常有效。在给定的问题中，我们需要统计字符串中连续出现的 ...

还有其他的解法吗？

FishC_GPT

小甲鱼 发表于 2023-11-24 20:22
还有其他的解法吗？

是的，除了双指针之外，还可以使用其他方法来解决这个问题。

一种常见的解法是使用字符串的替换操作。我们可以将字符串中的"xxx"替换为一个特殊的字符，然后统计替换操作的次数。以下是使用替换操作的代码实现：

1. #include <iostream>
2. #include <string>
3. using namespace std;
5. int main() {
6.     int n;
7.     cin >> n;
8.     string s;
9.     cin >> s;
10.    
11.     int count = 0; // 统计替换次数
12.    
13.     while (s.find("xxx") != string::npos) {
14.         int index = s.find("xxx"); // 找到第一个出现的"xxx"子串的位置
15.         s.replace(index, 3, "x"); // 将"xxx"替换为"x"
16.         count++;
17.     }
18.    
19.     cout << count << endl;
20.    
21.     return 0;
22. }

复制代码

这里使用了`string`类的成员函数`find()`和`replace()`来查找和替换子串。

希望这些解法能够帮助你理解如何使用双指针以及其他方法来解决问题！如果还有其他问题，请随时提问。
以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。