Leetcode 344 反转字符串

题目链接: 反转字符串
自己的思路:要交换第一个元素和最后一个元素，交换第二个元素和倒数第二个元素。。。，可以分析出是两个指针移动的过程，所以我们想到用双指针法来处理，定义左右两个指针，分别交换两个指针的元素，移动指针，一直到两个指针相等为止。

正确思路:双指针

代码:

class Solution {public void reverseString(char[] s) {//定义左右两个指针int left = 0;int right = s.length-1;while(left<right){//交换两个指针对应的元素char temp = s[left];s[left] = s[right];s[right] = temp;//移动两个指针left++;right--;}}
}

复杂度分析：
时间复杂度：$\mathcal{O}(n)$
空间复杂度：$\mathcal{O}(1)$

Leetcode 541 反转字符串 II

题目链接: 反转字符串 II
自己的思路:自己没想到

正确思路:首先将字符串转换为数组，方便进行操作，每次让i移动2k个单位（这非常重要），移动之后使用双指针反转前k个元素，如果剩余元素不足k个，那么反转剩余元素，所以要对chars.length-1和i+k-1的大小进行判断，取最小值，因为可能剩余元素不足k个，最后返回新的字符串即可。

代码:

class Solution {public String reverseStr(String s, int k) {//先将字符串转换为数组，方便操作char[] chars= s.toCharArray();//i每次移动2k个单位for (int i =0;i<chars.length;i+=2*k){int start = i;//判断是否还剩下k个元素，int end = Math.min(chars.length-1,i+k-1);//反转前k个元素或者反转剩余元素while(start<end){char temp = chars[start];chars[start] = chars[end];chars[end] = temp;start++;end--;}}//返回新字符串return new String(chars);}
}

复杂度分析：
时间复杂度：$\mathcal{O}(n)$
空间复杂度：$\mathcal{O}(n)$

Leetcode 剑指 Offer 05. 替换空格

题目链接: 替换空格
自己的思路:在替换完以后数组一定会扩大，由于java的字符串不可变，所以不能在原有的字符串的基础上进行扩容，我们选择新建一个字符串来存放替换之后的字符，使用双指针来完成赋值操作，一个指针index1指向原先字符串的尾部，另一个指针index2指向新字符串的尾部，如果index1指向非空格字符，则直接赋值给index2的位置，否则依次给index2的指针赋值’0’，‘2’，‘%’，直到index指向非0为止。

正确思路:扩容+双指针

代码:

class Solution {public String replaceSpace(String s) {//最初s的长度int length = s.length();//记录空格的数量int count = 0;for (int i =0;i<length;i++){if (s.charAt(i)==' '){count++;}}//新建一个数组存储最后的字符数组char[] chars = new char[length+count*2];//定义两个指针用于存储新数组的元素int index1 = length - 1;int index2 = chars.length-1;while(index1>=0){//如果不是空格的话直接赋值给chars即可if (s.charAt(index1)!=' '){chars[index2] = s.charAt(index1);index1--;index2--;}else{//如果是空格的话，则依次给chars赋值chars[index2] = '0';index2--;chars[index2] = '2';index2--;chars[index2] = '%';index2--;index1--;}}//返回最后的字符串return new String(chars);}
}

复杂度分析：
时间复杂度：$\mathcal{O}(n)$
空间复杂度：$\mathcal{O}(n)$

Leetcode 151. 反转字符串中的单词

题目链接: 反转字符串中的单词
自己的思路:没想出来

正确思路:双指针法+新建字符串；使用双指针进行处理，左右双指针，先使用双指针去除左右两边的空格，然后移动右边的指针，当碰到第一个为空格的字符时，说明已经遍历了一个单词，则将这个单词放置在新的字符串中，再加入一个空格，继续遍历，直到遍历完整个字符串。

代码:

class Solution {public String reverseWords(String s) {//定义两个指针int left = 0;int right = s.length()-1;//新建一个可变的字符串StringBuilder sb = new StringBuilder();//除去左右两边空格while(s.charAt(left)==' ')left++;while(s.charAt(right)==' ')right--;while(left<=right){int index = right;while(index>=left&&s.charAt(index)!=' ') index--;//将单词赋值给新的字符串for (int i = index+1;i<=right;i++){sb.append(s.charAt(i));}//如果没有把所有单词加进去，则加个空格if (index>left) sb.append(' ');while(index>=left&&s.charAt(index)==' ') index--;right = index;}return sb.toString();}
}

复杂度分析：
时间复杂度：$\mathcal{O}(n)$
空间复杂度：$\mathcal{O}(n)$

Leetcode 剑指 Offer 58 - II. 左旋转字符串

题目链接: 左旋转字符串
自己的思路:拼接截取；先将原来字符串加上原来字符串，然后从n到n+length进行截取即可

正确思路:

代码:

class Solution {public String reverseLeftWords(String s, int n) {int length = s.length();//将原来字符串复制一份进行拼接String res = s + s;//直接截取res = res.substring(n,n+length);return res;}
}

复杂度分析：
时间复杂度：$\mathcal{O}(1)$
空间复杂度：$\mathcal{O}(n)$