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

本文发布于：2023年1月4日

字数：1.9k字

时长：8分钟

在之前刷力扣的过程中，我每刷道题都是先看题解然后再去边写边看，很多内容根本没消化，在进度上欺骗自己，感觉之前刷的都忘了，能力没有什么提升，现在还是一道都不会做。所以这次报了卡哥的算法训练营，希望能够按计划地有效刷题。本次刷题，我用的是 Java 语言解题，有余力的话也可能会加上 C++ 的题解。以下是算法训练营第八天的刷题记录和思考笔记。

一、字符串

在 Java 中字符串属于对象，Java 提供了 String 类来创建和操作字符串。String 类是不可变类，即一旦一个 String 对象被创建以后，包含在这个对象中的字符序列是不可改变的，直至这个对象被销毁。

Java 提供了两个可变字符串类 StringBuffer 和 StringBuilder，即字符串缓冲区。

String 是 Java 中基础且重要的类，被声明为 final class，是不可变字符串。因为它的不可变性，所以拼接字符串时候会产生很多无用的中间对象，如果频繁的进行这样的操作对性能有所影响。

StringBuffer 就是为了解决大量拼接字符串时产生很多中间对象问题而提供的一个类。它提供了 append 和 add 方法，可以将字符串添加到已有序列的末尾或指定位置，它的本质是一个线程安全的可修改的字符序列。

在很多情况下我们的字符串拼接操作不需要线程安全，所以 JDK1.5 发布了 StringBuilder，它和 StringBuffer 本质上没什么区别，就是去掉了保证线程安全的那部分，减少了开销。

一般情况下，速度从快到慢为 StringBuilder > StringBuffer > String，当然这是相对的，不是绝对的。

操作少量的数据时使用 String。单线程操作大量数据时使用 StringBuilder。多线程操作大量数据时使用 StringBuffer。

二、344 反转字符串

题目

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

1 2	输入：s = ["h","e","l","l","o"] 输出：["o","l","l","e","h"]

解题思路

双指针：

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

补充知识点：swap 除了交换数值，也可以是通过位运算实现：

1
2
3

s[left] ^= s[right];  // 构造 a ^ b 的结果，并放在 a 中
s[right] ^= s[left];  // 将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
s[left] ^= s[right];  // a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换

三、541 反转字符串 II

题目

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

1 2	输入：s = "abcdefg", k = 2 输出："bacdfeg"

解题思路

在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。每隔 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);    // 判断尾数够不够k个来决定end指针的位置
            while (left < right) {
                char temp = ch[left];
                ch[left++] = ch[right];
                ch[right--] = temp;
            }
        }
        return new String(ch);
    }
}

四、剑指 Offer 05 替换空格

题目

请实现一个函数，把字符串 s 中的每个空格替换成 %20。

1 2	输入：s = "We are happy." 输出："We%20are%20happy."

解题思路

对于很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。这么做有两个好处：首先是不用申请新数组；而且从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {    
            if (s.charAt(i) == ' ') {    // 等同于if (" ".equals(String.valueOf(s.charAt(i)))){}
                sb.append("%20");
            } else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}

补充：对于所有线性数据结构的填充或者删除，后序处理都会高效的多。

五、151 翻转字符串里的单词

题目

给你一个字符串 s ，请你反转字符串中单词的顺序。单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

1 2	输入：s = "the sky is blue" 输出："blue is sky the"

解题思路

分部解题：去除首尾以及中间多余空格，再将整个字符串反转，再将每个单词反转回来。

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = removeSpace(s);
        reverseString(sb, 0, sb.length() - 1);
        reverseEachWord(sb);
        return sb.toString();
    }

    private StringBuilder removeSpace(String s) {
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;    // 去除开头空格
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        return sb;
    }

    public void reverseString(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
    }

    private void reverseEachWord(StringBuilder sb) {
        int start = 0;
        int end = 1;
        int n = sb.length();
        while (start < n) {
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            reverseString(sb, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
    }
}

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

题目

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串 "abcdefg" 和数字 2，该函数将返回左旋转两位得到的结果 "cdefgab"。

1 2	输入: s = "abcdefg", k = 2 输出: "cdefgab"

解题思路

经典题目，反转区间为前 n 的子串，反转区间为 n 到末尾的子串，最后反转整个字符串。

class Solution {
    public String reverseLeftWords(String s, int n) {
        int len = s.length();
        StringBuilder sb = new StringBuilder(s);
        reverseString(sb, 0, n - 1);
        reverseString(sb, n, len - 1);
        reverseString(sb, 0, len - 1);
        return sb.toString();
    }

    private StringBuilder reverseString(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start++, sb.charAt(end));
            sb.setCharAt(end--, temp);
        }
        return sb;
    }
}

LeetCode

Bezhuang

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

在之前刷力扣的过程中，我每刷道题都是先看题解然后再去边写边看，很多内容根本没消化，在进度上欺骗自己，感觉之前刷的都忘了，能力没有什么提升，现在还是一道都不会做。所以这次报了卡哥的算法训练营，希...

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