[数据结构与算法]?代码随想录算法训练营第八天 | 344.反转字符串、541. 反转字符串II、剑指Offer 05.替换空格、151.翻转字符串里的单词、剑指Offer58-II.左旋转字

LeetCode?344.反转字符串

思路：

• 将 left 指向字符数组首元素，right 指向字符数组尾元素。
• 当 left < right：
  • 交换 s[left] 和 s[right]；
  • left 指针右移一位，即 left = left + 1；
  • right 指针左移一位，即 right = right - 1

class Solution {
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while(left < right){
            char temp = s[right];
            s[right] = s[left];
            s[left] = temp;
            left++;
            right--;
        }
    }
}

LeetCode?541. 反转字符串II

自己写的（思路方法是对的，就是不够简洁）：

class Solution {
    public String reverseStr(String s, int k) {
        char[] chars = s.toCharArray();
        int round = s.length() / (2 * k);
        int i = 0;
        int left, right;
        while(round-- > 0){
            left = 2 * k * i;
            right = left + k - 1;
            i++;
            reverse(chars, left, right);
        }
        left = 2 * k * i;
        right = s.length() - 1;
        if(right - left + 1 < k){     
            reverse(chars, left, right);
        }else{
            right = left + k - 1;
            reverse(chars, left, right);
        }
        return String.valueOf(chars);
    }

    public void reverse(char[] chars, int left, int right){
        while(left < right){
            char temp = chars[right];
            chars[right] = chars[left];
            chars[left] = temp;
            left++;
            right--;
        }
    }
}

思路：每隔2k个反转前k个，尾数不够k个时候全部反转（好惊艳好会总结）

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

    public void reverse(char[] ch, int left, int right){
        while(left < right){
            char temp = ch[right];
            ch[right] = ch[left];
            ch[left] = temp;
            left++;
            right--;
        }
    }
}

剑指Offer 05.替换空格

class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for(char c : s.toCharArray()){
            if(c == ' ')
                sb.append("%20");
            else
                sb.append(c);
        }
        return sb.toString();
    }
}

LeetCode?151.翻转字符串里的单词

自己写的：

class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        StringBuilder sb = new StringBuilder();
        int fast = s.length() - 1, slow = fast;
        while(fast >= 0){
            while(fast >= 0 && s.charAt(fast) != ' ')
                fast--;
            sb.append(s.substring(fast + 1, slow + 1) + " ");
            while(fast >= 0 && s.charAt(fast) == ' ')
                fast--;
            slow = fast;
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }
}

剑指Offer58-II.左旋转字

没想到可以用翻转字符串：

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

class Solution {
    public String reverseLeftWords(String s, int n) {
        char[] ch = s.toCharArray();
        // 反转区间为前n的子串
        reverse(ch, 0, n - 1);
        // 反转区间为n到末尾的子串
        reverse(ch, n, ch.length - 1);
        // 反转整个字符串
        reverse(ch, 0, ch.length - 1);
        return String.valueOf(ch);
    }

    public void reverse(char[] ch, int left, int right){
        while(left < right){
            char temp = ch[right];
            ch[right] = ch[left];
            ch[left] = temp;
            left++;
            right--;
        }
    }
}