算法|344. 反转字符串、 反转字符串 II、替换空格、反转字符串中的单词、左旋转字符串

一、 344. 反转字符串

题目连接：https://leetcode.cn/problems/reverse-string/
思路：定义左右指针，然后左右指针数据交换

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--; 
        }
    }
}

二、 541. 反转字符串 II

题目连接：https://leetcode.cn/problems/reverse-string-ii/
思路：每2 * k个翻转一次，如果 i + k <= cs.length 则翻转[i, i + k - 1]，反之翻转[i, cs.length - 1];

class Solution {

    private void reverse(char[] cs, int i, int j) {
        while(i < j) {
            char temp = cs[i];
            cs[i] = cs[j];
            cs[j] = temp;
            i++;
            j--;
        }      
    }
    public String reverseStr(String s, int k) {
        char cs[] = s.toCharArray();
        for (int i = 0; i < cs.length; i += k * 2){
            if (i + k <= cs.length) {
                reverse(cs, i, i + k - 1);
                continue;
            }
            reverse(cs, i, cs.length - 1);
        }
        return new String(cs);
    }
}

三、剑指 Offer 05. 替换空格

题目连接：https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
思路一、扫描一片字符串，遇到空格 就放入到stringbuilder，不是空格直接加入当前字符

class Solution {
    public String replaceSpace(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c != ' ') {
                stringBuilder.append(c);
            } else {
                stringBuilder.append("%20");
            }
        }
        return stringBuilder.toString();
    }
}

思路二、双指针法 ,先扫描一遍字符串，统计有多少字符串，需要扩张多少字符串，注意一个空需要用来两个空格来扩充，然后定义两个指针left,right, left表示原先的字符串的指针，right表示新的字符串的指针。如果cs[left] == ' ',则需要替换即 cs[right--] = '0' cs[right--] = '2' cs[right] = '%',如果不是空格则cs[right] = cs[left];

class Solution {
    public String replaceSpace(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                stringBuilder.append("  ");
            }
        }
        if (stringBuilder.length() == 0) return s;
        int left = s.length() - 1;
        s += stringBuilder.toString();
        int right = s.length() - 1;
        char[] cs = s.toCharArray();
        while (left >= 0) {
            char c = cs[left];
            if (c != ' ') {
                cs[right] = cs[left];
            } else {
                cs[right--] = '0';
                cs[right--] = '2';
                cs[right] = '%';
            }
            left--;
            right--;
        }
        return new String(cs);
    }
}

四、151. 反转字符串中的单词

题目连接：https://leetcode.cn/problems/reverse-words-in-a-string/
思路：1、先去掉多余的空格，先定义快慢指针，快指针表示无空格是，慢指针表示符合条件复制
2、翻转所有字符串
3、每个单词翻转

class Solution {
    private char[] removeExraSpace(char[] cs) {
        int slow = 0;
        for (int fast = 0; fast < cs.length; fast++){
            if (cs[fast] != ' ') {
                if (slow != 0) {
                    cs[slow++] = ' ';
                }
                while (fast < cs.length && cs[fast] != ' ') {
                    cs[slow++] = cs[fast++];
                }
            }
        }
        char[] csNew = new char[slow];
        for (int i = 0; i < slow; i++) {
            csNew[i] = cs[i];
        }
        return csNew;
    }
    private void reverse(char[] cs, int left, int right) {
        while (left < right) {
            char temp = cs[left];
            cs[left] = cs[right];
            cs[right] = temp;
            left++;
            right--;
        }
    }
    private void reverseEachWorld(char[] cs) {
        int start = 0;
        for (int end = 0; end <= cs.length; end++) {
           
            if (end == cs.length || cs[end] == ' ') {
                System.out.println(start + " " + (end - 1));
                reverse(cs, start, end - 1);
                start = end + 1;
            }
        }
    }
    public String reverseWords(String s) {
        char[] cs = s.toCharArray();
        cs = removeExraSpace(cs);
        reverse(cs, 0, cs.length - 1);
        reverseEachWorld(cs);
        String result = new String(cs);
        System.out.println(result);
        return result;
    }
}

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

题目连接：https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
思路：先反转整个字符串[0, cs.length - 1]，然后在反正[0, cs.lenth - n - 1],然后在反正[cs.length -n, cs.length - 1]

class Solution {
    private void reverse(char[] cs, int left, int right) {
        while (left < right) {
            char temp = cs[left];
            cs[left] = cs[right];
            cs[right] = temp;
            left++;
            right--;
        }
    }
    public String reverseLeftWords(String s, int n) {
        char[] cs = s.toCharArray();
        reverse(cs, 0, cs.length - 1);
        reverse(cs, 0, cs.length - n - 1);
        reverse(cs, cs.length - n, cs.length - 1);
        return new String(cs);
    }
}