算法通关村——字符串反转问题解析

1. 反转字符串

反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

1.1 交换

这一题的思路还是简单的，就是将左边的元素和右边的元素交换位置，即可原地修改数组。

    public void reverseString(char[] s) {if(s.length == 0 || s == null){return ;}for(int left =0, right=s.length-1;  left<right; left++,right--){char swap = s[left];s[left]=s[right];s[right]=swap;}}

2. 反转字符串 II

反转字符串
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

2.1 反转

这个题目的叙述有点难以理解，总结就是每个K个就反转前k个，如果剩余长度不能k，那么将剩余元素都反转。

示例 1：
输入：s = “abcdefg”, k = 2
输出：“bacdfeg”

k=2，2k=4，反转ab 变成bacdefg
剩余3，k<3<2k, 反转ef 变成bacdfeg

反转每个下标从2k开始的

 public String reverseStr(String s, int k) {int length = s.length();char [] chars = s.toCharArray();for(int i=0;i<length;i+=2*k){swap(i,Math.min(i+k,length)-1,chars);}return new String(chars);}public void swap(int start,int end,char [] chars){while(start<end){char temp = chars[start];chars[start] = chars[end];chars[end] = temp;start++;end--;}}

3. 仅仅反转字母

仅反转字母
给你一个字符串 s ，根据下述规则反转字符串：

所有非英文字母保留在原有位置。
所有英文字母（小写或大写）位置反转。
返回反转后的 s 。

示例 1：

输入：s = “ab-cd”
输出：“dc-ba”

3.1 反转

这个题目如果不看-符号，就是一个普通的字符交换，但是多了一个字符，只需要每次遇到这个字符的时候就跳过这个字符就可以，其余的交换依然一样。

 public String reverseOnlyLetters(String s) {char [] arr = s.toCharArray();int left = 0;int right = s.length()-1;while(left<right){while(left<right && !Character.isLetter(arr[left])){left++;}while(left<right && !Character.isLetter(arr[right])){right--;}char temp = arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;}return new String(arr);}

这一题一开始没看全就就认为字符是-,但是1，！这些也都是字符所以需要使用Character.isLetter()判断是否为字符。

3.2 栈

当然这一题还可以使用栈来存储里面的英文，然后遍历字符串，栈里面元素出来的顺序就是逆序的，然后和字符串比较，如果不是英文字母，那么就添加这个字符，否则就添加出栈元素。

    public String reverseOnlyLetters(String s) {char [] arr = s.toCharArray();Stack<Character> stack = new Stack<>();for(char c : arr){if(Character.isLetter(c)){stack.push(c);}}StringBuilder sb = new StringBuilder();for(char c:arr){if(Character.isLetter(c)){sb.append(stack.pop());}else{sb.append(c);}}return sb.toString();}

但是很显然，这种方式速度方面不怎么行，但是也是易于理解的。

4. 反转字符串中的单词

反转字符串中的单词
给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

4.1 调用API

可以使用正则匹配来将字符串分组，然后从后遍历字符串数组，将其添加到stringbuilder里面去，每一次添加都需要额外添加一个空格。

  public String reverseWords(String s) {String [] words = s.trim().split("\\s+");StringBuilder sb = new StringBuilder();for(int i = words.length-1;i>=0;i--){sb.append(words[i]);if(i>0){sb.append(" ");}}return sb.toString();}

虽然说这个方式很容易想到，但是实际面试里面不会这么写，而是手动进行切割。

4.2 自定义

总体思路就是，使用两个指针start,end，然后逆序遍历字符串，end就是当前单词末尾位置，start就是当前单词的开始位置，然后再次遍历这个start-end位置的元素添加至stringbuilder里面，添加一个空白。

    public String reverseWords(String s) {int start,end;StringBuilder sb = new StringBuilder();for(int i=s.length()-1;i>=0;i--){// 最后一个元素是哦空格，跳过if(s.charAt(i)  == ' '){ continue;}// 单词结束位置end = i+1;// 获取单词第一个位置while(i>=0 && s.charAt(i)!=' '){i--;}start = i+1;// 添加单词for(int j=start;j<end;j++){sb.append(s.charAt(j));}sb.append(' ');}// 删除最后一个空格sb.deleteCharAt(sb.length()-1);return sb.toString();}

官方的解法较为复杂。