ヘビーローテーション


557. Reverse Words in a String III

这就是5开头的新题,完全没有价值把它当做新题来出,leetcode现在出的新题很多都没什么价值,要么是特别难写不好处理,要么没有难度模仿前题,这种滥竽充数的感觉特别不好,拉低了leetcode的质量,因为很多新题不涉及新的数据结构,不能反映新的算法思想,只是一个新的壳子。啰嗦了两句。

III比II简单,因为III只需要倒转单词,II比I简单,因为已经告诉你了没有 trailing zeros 而且中间空格只有一个。就像是当时的二叉树路径问题中,也是有一道题II比I简单。

while 循环里套 while 的时候,记得把外层的判断条件也放到内层,否则容易越界。

public class Solution {
    public String reverseWords(String s) {
        char[] array = s.toCharArray();
        int start = 0;
        int index = 0;
        while (index < array.length) {
            while (index < array.length && array[index] != ' ') index++;
            reverse(array, start, index - 1);
            index++;
            start = index;
        }
        StringBuilder sb = new StringBuilder();
        for (char ch : array) {
            sb.append(ch);
        }
        return sb.toString();
    }
    private void reverse(char[] array, int start, int end) {
        while (start < end) {
            char tmp = array[start];
            array[start] = array[end];
            array[end] = tmp;
            start++;
            end--;
        }
    }
}

186. Reverse Words in a String II

把每个词都翻转一下,最后把整个string都倒过来输出。这么做是因为输入是char数组,完全打碎的字母,不是单词。

public class Solution {
    public void reverseWords(char[] s) {
        int start = 0;
        int index = 0;
        while (index < s.length) {
            while (index < s.length && s[index] != ' ') {
                index++;
            }
            reverse(s, start, index - 1);
            index++;
            start = index;
        }
        reverse(s, 0, s.length - 1);
    }
    private void reverse(char[] s, int start, int end) {
        while (start < end) {
            char tmp = s[start];
            s[start] = s[end];
            s[end] = tmp;
            start++;
            end--;
        }
    }
}

151. Reverse Words in a String

稍微麻烦点,要处理各种 trailing space 和中间。当然这题也没说要in-place,但不in-place就没做的价值了。

String题目里StringBuilder和trim()以后可能会经常用到。

public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) return "";
        int start = 0;
        int index = 0;
        char[] array = s.toCharArray();

        while (index < array.length) {
            while (index < array.length && array[index] == ' ') index++;
            start = index;
            while (index < array.length && array[index] != ' ') index++;
            reverse(array, start, index - 1);
        }
        StringBuilder sb = new StringBuilder();

        index = array.length - 1;
        while (index >= 0) {
            while (index >= 0 && array[index] == ' ') index--;
            while (index >= 0 && array[index] != ' ') sb.append(array[index--]);
            sb.append(' ');
        }
        return sb.toString().trim();
    }
    private void reverse(char[] s, int start, int end){
        while(start < end){
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;

            start ++;
            end --;
        }
    }
}

344. Reverse String / 541. Reverse String II

344太过trivial就不说了,稍微说一下541,注意尾指针的取值,用一个min函数取较小的index别越界就行了。

public class Solution {
    public String reverseStr(String s, int k) {
        if (s == null || s.length() == 0) return s;
        char[] array = s.toCharArray();
        int i = 0;
        while (i < array.length) {
            int j = Math.min(i + k - 1, array.length - 1);
            swap(array, i, j);
            i += 2 * k;
        }
        StringBuilder sb = new StringBuilder();
        for (char ch : array) {
            sb.append(ch);
        }
        return sb.toString();
    }
    private void swap (char[] array, int start, int end) {
        while (start < end) {
            char tmp = array[start];
            array[start++] = array[end];
            array[end--] = tmp;
        }
    }
}

189. Rotate Array

多步翻转法的另一个应用。

这题让我想起了链表,肯定有很多种做法,用多步翻转是比较简洁的。

public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        reverse(nums, 0, nums.length - k - 1);
        reverse(nums, nums.length - k, nums.length - 1);
        reverse(nums, 0, nums.length - 1);
    }
    private void reverse(int[] nums, int start, int end){
        while(start < end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;

            start ++;
            end --;
        }
    }
}

results matching ""

    No results matching ""