2016.8.3 Leetcode (C++, Xcode)（1

因为一直写的都是android程序，所以之前想用java文件去提交，弄了半天android studio，终于将java程序运行了起来，可是一查，却发现java运行效率是c语言的三分之一。

OK，开始查刷OJ用什么语言比较好，查到一般用C++，但是如果遇到高精度和匹配度的问题，用java水才比较好，好吧，以后将C++捡起来~

开始安装mac的C++编辑器，Xcode和Qtcreator，后来发现Xcode很好用（虽然3.8G，下载了好久。。。），但是果断卸载Qtcreator，Xcode将来也可以用来将来编Swift。

第一次刷leetcode，还按照以前的int main的思路，发现编译不通过，后来查了一下，发现leetcode上面必须有个Solution的类，也就是切换到C++提交方式时，默认的东西。

下面的解法按照时间从短到长排序：

解法一：
提交时间：：Your runtime beats <u>9.99%</u> of cppsubmissions
时间复杂度：O(n/2).
思路：直接用c++自带的reverse函数。

string reverseString(string s) {
        reverse(s.begin(), s.end());
        return s;
    }

ps：过后查了一下reverse这个函数，reverse这个函数的解法，是for循环了一半的长度，从两头到中间，首位加，末尾减，然后交换，交换内置的是swap操作，swap就是最常用的一个拷贝构造，两次赋值操作。

结果：

ps：这种解法用了颇多的时间，主要是c++和xcode用的不熟练的原因，在string和char[]互相转换上用了颇多时间。

解法二：
提交时间：Your runtime beats <u>9.99%</u> of cppsubmissions
时间复杂度：O（n）。
思路：分治递归。

string reverseString(string s) {           
    if(s.length()<2)
        return s;
    else{
        string s1 = s.substr(0, s.length()/2-1);
        string s2 = s.substr(s.length()/2-1, s.length());
        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());
        s = s2+s1;
        return s;
    }
}

解法三：
提交时间：Your runtime beats <u>4.65%</u> of cppsubmissions
时间复杂度：O（n）
思路：新建字符串，将就字符串倒着拼接。

string reverseString(string s) {
   string newstr = "";
   int length = (int)s.length();
   for(int i = 0; i<length;i++){
       newstr+=s.at(length-i-1);
  }
  return newts;
}

暂时没想到更好的结题方法，但是这个效率是很低的，一定是有更好的解题方法的。