cpp算法题目整理——双指针篇

反转字符串中的字符

题目描述：

实现一个算法来实现反转字符数组的功能。反转的要求如下：

1. 将字符数组的字符进行反转，例如 ['b', ' ', 'a', 'r'] 变成 ['r', 'a', ' ', 'b']。

2. 将字符数组替换为反转后的数组。

解题思路：

这个题是典型的双指针，只需要定义左右两个指针，然后将两个指针对应的字符交换位置，然后继续向中间遍历即可。

#include <iostream> #include <string> using namespace std; int main(){ string s; cin >> s; //定义左指针和右指针 int l = 0; int r = s.size() - 1; //当左右指针未重合时 while(l <= r){ //定义一个temp中间变量用来暂时存储需要交换位置的字符 char temp = s[l]; s[l] = s[r]; s[r] = temp; //两个指针同时向中间移动 l++; r--; } //遍历s输出 //这里的意思是遍历s 将s中的每个字符赋值给a并输出 for(char a : s){ cout << a; } return 0; }

回文判定

题目描述：

给定一个长度为 n 的字符串 S。请你判断字符串 S 是否回文。

解题思路：

也是标准双指针模板题，只需要定义一个双指针，额外需要一个flag来判断字符串是否回文。

#include <iostream> #include <string> #include <vector> using namespace std; int main() { //定义字符串s接收输入 string s; cin >> s; //定义左右双指针 int left = 0; int right = s.size() - 1; //定义一个bool类型 用来判断前后字符是否相等 bool flag = true; while(left <= right){ //对前后两个字符判断 如果不相等 //flag置false 这个时候可以直接结束循环 if(s[left] != s[right]){ flag = false; break; } //如果满足上方条件 左右指针向中间移动 left++; right--; } //对flag判断 为true说明是回文 if(flag){ cout << "Y" << endl; } else{ cout << "N" << endl; } return 0; }