代码随想录算法训练营Day7 | 344.反转字符串、541.反转字符串||、替换数字、151.反转字符串中的单词、右旋字符串

本题思路：反转字符串比较简单，定义两个指针，一个 i = 0, 一个 j = s.length-1。然后定义一个临时变量 tmp，进行交换 s[i] 和 s[j]。

class Solution {public void reverseString(char[] s) {int i = 0;int j = s.length-1;while(i <= j){char tmp = s[i];s[i] = s[j];s[j] = tmp;i++;j--;}}
}

本题思路：最重要的理解题目含义，就是每一次走 2*k 步，如果剩余的字符长度大于等于k，就反转前 k 个字符，如果小于 k , 就将剩下的全部反转。 个人感觉这个剩余字符小于 2k的条件毫无软用，

下面用一个例子来分析下思路，方便更好理解。

• 初始情况下 i = 0, i 每次走 i += 2 * k 步
• 判断剩余个数是否大于等于 k =2，其实就是判断(i + k <= array.length) 此时符合条件，反转前 K 个 ，调用 reverseSubStr(i,i+k,array)，左闭右开。
• i 往后移动 i = i + 2 * k，此时 i = 0 + 4 = 4
• 继续判断 (i + k <= array.length) ，此时条件符合 4 + 2 <= 6, 反转前 K 个 ，调用 reverseSubStr(i,i+k,array)，左闭右开。
• 此时 i = i + 2 * k = 4 + 8，不符合循环，结束。最终结果如下

class Solution {public String reverseStr(String s, int k) {// 将字符串转换成数组char[] array = s.toCharArray();for(int i = 0; i < array.length; i+=2*k){// 先判断如果剩余字符个数大于 k,或者小于 2k, 就反转这前 K个// 本题主要理清楚，只要剩余个数大于等于k，if(i + k <= array.length){reverseSubStr(i,i+k,array);continue;}// 如果小于 K,就反转剩下的全部reverseSubStr(i,array.length,array);}return new String(array);}// 左闭右开public static void reverseSubStr(int l,int r, char[] s){while(l <= r-1){char tmp = s[l];s[l] = s[r-1];s[r-1] = tmp;l++;r--;}}
}

本题思路：

1. 去掉前面、后面、单词之间的重复空格
2. 先整体反转
3. 再单个单词反转

通过示例 2 ，来画个图分析下思路，下面是初始状态

• 首先是去空格判断，定义一个 Trim() 方法，来进行去除两端的空格，通过定义两个指针，一个 left ，一个 right, left++, right–。碰到第一个不为空格的就停下。
• 这是去掉两端空格以后的字符串 s
• 接下里就要进行字符串之间的多余空格进行去重，遍历字符串 s 分为两步; 新定义一个字符串拼接 StringBuilder sb
  • 如果不是空格的话，就直接拼接 sb.append(s.charAt(left)），如下，left++，直到遇到空格停止
  • 可以看到上图，此时就遇到了空格，因为可能有多个空格，我们需要保留一个空格，所以需要判断 (left-1) 这个元素是不是空格，如果是空格，说明空格已经保存了，就跳过不做任何处理，直到遇到的不是空格为止， 可以看到上图 left-1 元素不是空格，所以直接拼接空格，并且left++;
  • 此时上图，又遇到不是空格，直接拼接
• 最终得到 sb, 去掉多余空格以后的新字符串 sb

• 接下来就是反转全部字符串，这个逻辑的话和上述反转字符串一样，定义两个指针，一个 left, 一个 right, 然后定义一个 临时变量来交换 这两个数字
• 最后反转每一个单词。

此处，使用 StringBuilder的时候， 不能 sb.charAt(left) = sb.charAt(right),会有语法错误。必须使用 sb.setCharAt(原值，要改变的值)

class Solution {public String reverseWords(String s) {// 1. 先去掉多余的空格StringBuilder sb = Trim(s);// 2. 先反转全部Reverse(sb,0,sb.length()-1);// 3. 反转每一个单词;// 定义反转起始位置int start = 0;// 定义反转结束位置int end = 0;for (int i = 0; i < sb.length(); i++) {// 找到第一个为空格的下标if (sb.charAt(i) == ' ') {end = i - 1;Reverse(sb, start, end);start = end + 2;}}// 最后一个单词单独进行反转Reverse(sb,start,sb.length()-1);return sb.toString();}// 反转所有单词public static void Reverse(StringBuilder s, int start, int end) {int left = start;int right = end;while (left <= right) {char tmp = s.charAt(left);s.setCharAt(left, s.charAt(right));s.setCharAt(right, tmp);left++;right--;}}// 去空格public static StringBuilder Trim(String s) {int left = 0;int right = s.length() - 1;StringBuilder sb = new StringBuilder();// 去除前面的空格while (left <= right && s.charAt(left) == ' ') {left++;}// 去除后面的空格while (left <= right && s.charAt(right) == ' ') {right--;}// 去重字符串之间的多余空格while (left <= right) {// 如果不等于空格，直接拼接这个字符if (s.charAt(left) != ' ') {sb.append(s.charAt(left));left++;} else { // 此时等于空格，需要判断前面一个是否为空格if (s.charAt(left - 1) != ' ') {sb.append(s.charAt(left));left++;} else {left++;}}}return sb;}
}

虽然整体逻辑不难，但是写代码的时候，出现了很多错误，考虑不周到。还得多写几遍，没那么简单。