yub‘s Algorithmic Adventures_Day12

反转字符串II

link:541. 反转字符串 II - 力扣（LeetCode）

思路分析

关键点在于我们要找对反转思路，2k是一个区间，没达到条件和达到条件之后怎么处理.
因此考虑怎么筛选条件.

首先创建一个字符数组用于存储遍历的下标位置用于筛选【其实类似双指针判断 此时尾指针的判断 避免越界】判断区间为[数组长度-1，起始位置 + k - 1]

class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray(); 
        for(int i = 0;i < ch.length;i += 2*k) {
              int start = i;
          //防止越界 平移判断区间和length比较
              int end = Math.min(ch.length -1 ,start + k - 1);
              while(start < end) {
                ch[start] ^= ch[end];
                ch[end] ^= ch[start];
                ch[start] ^= ch[end];
                start++;
                end--;
              }
        }
        //最终返回字符串
        return new String(ch);
    }
}

反转字符串中的单词

link：151. 反转字符串中的单词 - 力扣（LeetCode）

思路分析

倒序遍历字符串，记录左右边界i，j，找到空格删除，挨个遍历.最后蒋单词拼接返回字符串.

class Solution {
    public String reverseWords(String s) {
        //删除首尾空格
         s = s.trim();
         int j = s.length() - 1;
         int i = j;
         StringBuilder res = new StringBuilder();
         //搜索第一个空格
         while(i >= 0)  {
            while(i >= 0 && s.charAt(i) != ' '){
                i--;
            }
            //添加单词
            res.append(s.substring(i + 1, j + 1) + " ");
            while(i >=  0 && s.charAt(i) == ' '){
                i--;
            }
            //继续遍历下一个单词
            j = i;
         }
         //转换字符串
         return res.toString().trim();
    }
}

除此之外还能用双指针法解决.用fast和slow指针解决空格.

1.首先利用双指针取出空格（但是保留单词之间的空格【slow指针++为空的时候赋值为空再++】
2.反转整个字符串
3.单个单词内部反转

class Solution {
    public String reverseWords(String s) {
        // 将字符串转换为字符数组
        char[] ch = s.toCharArray();
        
        // 去除多余空格并接收返回的字符数组
        ch = removeExtraSpaces(ch);
        
        // 反转整个字符串
        reverse(ch, 0, ch.length - 1);
        
        // 单词内部反转
        reverseWords(ch);
        
        // 输出字符串
        return new String(ch);
    }
    
    public char[] removeExtraSpaces(char[] ch) {
        int slow = 0;
        
        for (int fast = 0; fast < ch.length; fast++) {
            if (ch[fast] != ' ') {
                // 如果 slow 不为 0，意味着不是首单词前的字符，需要添加空格
                if (slow != 0) {
                    ch[slow++] = ' ';
                }
                // 复制单词
                while (fast < ch.length && ch[fast] != ' ') {
                    ch[slow++] = ch[fast++];
                }
            }
        }
        
        // 创建新数组来存储去除多余空格后的字符串
        char[] newCh = new char[slow];
        System.arraycopy(ch, 0, newCh, 0, slow);
        return newCh;
    }
    
    public void reverse(char[] ch, int left, int right) {
        while (left < right) {
            ch[left] ^= ch[right];
            ch[right] ^= ch[left];
            ch[left] ^= ch[right];
            left++;
            right--;
        }
    }
    
    public void reverseWords(char[] ch) {
        int start = 0;
        
        for (int end = 0; end <= ch.length; end++) {
            // 当 end 遇到空格或者到达字符数组末尾，开始反转单词
            if (end == ch.length || ch[end] == ' ') {
                reverse(ch, start, end - 1);
                start = end + 1;
            }
        }
    }
}

Tip

1.String substring(int start, int end) 返回一个新的 String，它包含此序列当前所包含的字符子序列。
2.在使用 StringBuffer 类时，每次都会对 StringBuffer 对象本身进行操作，而不是生成新的对象，所以如果需要对字符串进行修改推荐使用 StringBuffer。
3.trim() 方法用于删除字符串的头尾空白符。