344. 反转字符串

简介

在看Leetcode中专项突破的数组和字符串专题中，看完其中双指针技巧 —— 情景一，进行题目练习，

双指针的技巧情景一

我们通过迭代数组来解决一些问题。通常，我们只需要一个指针进行迭代，即从数组中的第一个元素开始，最后一个元素结束。然而，有时我们会使用两个指针进行迭代。

示例:

让我们从一个经典问题开始：

反转数组中的元素。比如数组为 ['l', 'e', 'e', 't', 'c', 'o', 'd', 'e']，反转之后变为 ['e', 'd', 'o', 'c', 't', 'e', 'e', 'l']。

使用双指针技巧，其思想是分别将两个指针分别指向数组的开头及末尾，然后将其指向的元素进行交换，再将指针向中间移动一步，继续交换，直到这两个指针相遇。

这个技巧太好了，简直就是针对字符串翻转的，根本不需要找什么规律。

题目

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

case 1:

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

case 2 :

输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

思考过程

#include<iostream>
#include<vector>

using namespace std;

class Solution {
    public:
        void reverseString(vector<char> &s){
            int i = 0, j = s.size()-1;
            char tmp;
            // while(i != j){ --> bug
            while(i < j)
                if(s[i] != s[j]){
                    tmp = s[i];
                    s[i] = s[j];
                    s[j] = tmp;
                }
                i++;
                j--;
            }
        }
};

int main(){
    vector<char> str = {'a','b','d','e'};
    Solution test_case;
    test_case.reverseString(str);
    for(char ch : str)
        cout << "str :" << ch << endl;
    return 0;
}

基本原理就是定义两个指针，一个指向头，一个指向尾，字符不等的时候进行两两交换，当i != j 的时候，退出循环，但是这个条件是有问题的，如果字符个数刚好是5个时候，循环到2的时候，刚好退出，如果字符的个数是4个时候，条件一直成立，数组索引越界，产生崩溃，所以条件需要改为i < j 才正常