代码随想录算法训练营第8天

今日任务

● 344.反转字符串 ● 541. 反转字符串II ● 卡码网：54.替换数字 ● 151.翻转字符串里的单词 ● 卡码网：55.右旋转字符串

链接：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH (opens in a new tab)

344.反转字符串

自己想法

双指针

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

541. 反转字符串II

自己想法

class Solution {
    public String reverseStr(String s, int k) {
        char tmp;
        int fast = 0;
        int i, j;
        int count = 1;
        StringBuilder strBuilder = new StringBuilder(s);
        while (fast < strBuilder.length()) {
            if (count < 2 * k && fast != strBuilder.length() - 1 ) {
                count++;
            }
            else {
                if (count > k) {
                    i = fast - count + 1;
                    j = i + k - 1;
                }
                else {
                    i = fast - count + 1;
                    j = fast;
                }
                while (i < j) {
                    tmp = strBuilder.charAt(i);
                    strBuilder.setCharAt(i, strBuilder.charAt(j));
                    strBuilder.setCharAt(j, tmp);
                    i++;
                    j--;
                }
                count = 1;
            }
            fast++;
        }
        return strBuilder.toString();
    }
}

回顾

java String操作：使用StringBuilder：setCharAt，charAt，toString，同样也有length方法。

StringBuilder strBuilder = new StringBuilder(s);
strBuilder.setCharAt(i, strBuilder.charAt(j));

卡码网：54.替换数字

题解想法

理解：为什么要从后向前填充

从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素整体向后移动。

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

p.s. 不过java反正都得重新申请空间，所以这个优化意义不大。但是思想还是要学习的。

学习时可以用char[] ch = s.toCharArray();将字符串转换成字符数组，模拟一下。

首先扩充数组到每个数字字符替换成 "number" 之后的大小。

然后从后向前替换数字字符，也就是双指针法，过程如下：i指向新长度的末尾，j指向旧长度的末尾。

151.翻转字符串里的单词

题解想法

时间复杂度O(n)

移除多余空格
将整个字符串反转
将每个单词反转

这里我为了写java版本，使用了char[] chs = s.toCharArray();将字符串转换成字符数组，模拟一下题解思路。

class Solution {
    public String reverseWords(String s) {
        char[] chs = s.toCharArray();
        int true_length = 0;
 
        // 去除首尾、重复空格（全部删除再添加）
        int slow = 0;
        // 快指针i遍历数组
        for(int i = 0; i < chs.length; i++) {
            // 如果遇到不是空格，进行处理；否则跳过，i++
            if(chs[i] != ' ') {
                // 处理时，以单词为单位处理
                // 若不是第一个单词，则添加前导空格
                if(slow != 0) chs[slow++] = ' ';
                // 处理一个单词
                for(; i < chs.length && chs[i] != ' '; slow++, i++) {
                    chs[slow] = chs[i];
                }
                true_length = slow;
            }
        }
 
        // 先整体反转
        reverseInterval(chs, 0, true_length - 1);
        // System.out.println(Arrays.copyOfRange(chs, 0, true_length));
        // 再挨个单词反转回去
        int start = 0;
        for(int i = 0; i < true_length; i++) {
            // 找一个单词的尾
            for(; i < true_length && chs[i] != ' '; i++);
            reverseInterval(chs, start, i - 1);
            i++;
            start = i;
        }
 
        return new String(Arrays.copyOfRange(chs, 0, true_length));
    }
 
    public void reverseInterval(char[] chs, int start, int end) {
        char tmp;
        int left = start;
        int right = end;
        while(left < right) {
            tmp = chs[left];
            chs[left] = chs[right];
            chs[right] = tmp;
            left++;
            right--;
        }
    }
}