leetcode344——Reverse String（C++），leetcode344reverse

leetcode344——Reverse String（C++），leetcode344reverse

Write a function that takes a string as input and returns the string reversed.

Example:
Given s = "hello", return "olleh".

個人博客：http://www.cnblogs.com/wdfwolf3/。

這道題就是簡單的字符串逆置，在C++中字符串類型可以作為數組方式處理，所以經典的數組逆置就可以完成。這裡提供兩種思路：

1.classic方法頭尾交換（16ms）

class Solution {
public:
    string reverseString(string s) {
        int i=0,j=s.size()-1;
        while(i<j)
        {
            swap(s[i],s[j]);
            i++;
            j--;
        }
        return s;
    }
};

2.recursion方法分治遞歸（44ms）

將字符串分為前後兩部分，分別逆置然後合並起來，合並時自然是後半部分在前，前半部分在後。用到字符串截取函數string.substr()，它接收兩個參數，第一個為位置索引，即截取的開始位置，默認參數為0，就是字符串的開始；第二個參數為截取字符的數目，如果省略，就是指截取到字符串的末尾。

class Solution {
public:
    string reverseString(string s) {
        int length=s.size();
        if(length<2)
            return s;
        return reverseString(s.substr(length/2))+reverseString(s.substr(0,length/2));
    }
    
};

P.S.最後關於swap交換元素介紹兩個思路：

1.tmp中間變量，最熟悉的方法。

　　tmp=i;

　　i=tmp;

　　j=tmp;

2.bit的按位抑或^原理，即m^m=0，0^m=m。

　　m=m&n;

　　n=m&n;                 等價於　　　　　　n=m&n&n=m;

　　m=m&n;　　　　　　　　　　　　　 m=m&n&m=n;