第四章 字符串part01

344.反转字符串 541. 反转字符串II 剑指Offer 05.替换空格 151.翻转字符串里的单词 剑指Offer58-II.左旋转字符串

344.反转字符串 

class Solution {
    public void reverseString(char[] s) {
        // 双指针法 依次交换首尾两个
        for (int i = 0, j = s.length - 1; i < j; i++, j--){
            char tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
        }
    }
}

541. 反转字符串II 

关键在于for循环的逻辑，按照题目的要求

注意点：s.length()

　　　　s.toCharArray()

class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();
        for (int i = 0; i < n; i += 2 * k){
            reverse(arr, i, Math.min(i + k - 1, n - 1));
        }
        return new String(arr); 
    }
    public void reverse(char[] arr, int left, int right){
        while (left < right){
            char tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++;
            right--;
        }
    }
}

剑指Offer 05.替换空格 

很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

这么做有两个好处：

1. 不用申请新数组。
2. 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

class Solution {
    public String replaceSpace(String s) {
        // 双指针法
        // 统计空格个数
        char[] arr = s.toCharArray();
        int count = 0;
        for (char i : arr){
            if (i == ' ') count++;
        }
        // 扩容
        char[] newChar = new char[arr.length + count * 2];
        // 双指针从后往前
        int oldright = arr.length - 1, right = newChar.length - 1;
        while (oldright >= 0){
            if (arr[oldright] == ' '){
                newChar[right--] = '0';
                newChar[right--] = '2';
                newChar[right--] = '%';
            }else{
                newChar[right--] = arr[oldright];
            }
            oldright--;
        }
        return new String(newChar);
    }
}

151.翻转字符串里的单词 

思路：从后向前，不停的把单词添加到 StringBuilder 中，最终返回结果。

关键点：

如何修剪掉两端空格；--> left、right 双指针修剪

如何把单词反转过来；--> index指针从right向左移动，到空格停止

如何跳过中间连续的空格。 --> index向左移动到字符停止，right跟进

class Solution {
    public String reverseWords(String s) {
        char[] charArray = s.toCharArray();
        int left = 0, right = s.length() - 1;
        // 清除字符串两边的空格
        // 清除左边
        while (charArray[left] == ' ') {
            left++;
        }
        // 清除右边
        while (charArray[right] == ' ') {
            right--;
        }
        StringBuilder sb = new StringBuilder();
        // 开始添加单词
        while (left <= right) {
            int index = right;
            // index 向左遍历找到第一个空格
            while (index >= left && charArray[index] != ' ') {
                index--;
            }
            // 现在 index 已经找到第一个空格，i=index+1 后移到字符串出现的位置
            // 添加字符串
            for (int i = index + 1; i <= right; i++) {
                sb.append(charArray[i]);
            }
            // 如果不是最后一个单词，就添加空格
            if (index > left) sb.append(' ');

            // 使用 index 指针 跳过中间可能出现的空格
            while (index >= left && charArray[index] == ' ') {
                index--;
            }
            // 把 right 放到下一个单词出现的位置，继续循环
            right = index;
        }
        return sb.toString();
    }
}

剑指Offer58-II.左旋转字符串

遍历拼接

优化方向：取余操作合并到一个for循环

　　　　　　for(int i = n; i < n + s.length(); i++)
　　　　　　　　sb.append(s.charAt(i % s.length()));

不用额外空间：

通过局部反转+整体反转 达到左旋转的目的。

具体步骤为

　　反转区间为前n的子串

　　反转区间为n到末尾的子串

　　反转整个字符串

最后就可以达到左旋n的目的，而不用定义新的字符串，完全在本串上操作。

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = n; i < s.length(); i++){
            sb.append(s.charAt(i));
        }
        for (int i = 0; i < n; i++){
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}