代码随想录算法训练营第 8 天（字符串1）| 344.反转字符串 541. 反转字符串II 卡码网54.替换数字

一、 344.反转字符串

题目：https://leetcode.cn/problems/reverse-string/

视频：https://www.bilibili.com/video/BV1fV4y17748

讲解：https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html

206.反转链表中，使用了双指针的方法。

那么反转字符串依然是使用双指针的方法，只不过对于字符串的反转，其实要比链表简单一些。

因为字符串也是一种数组，所以元素在内存中是连续分布，这就决定了反转链表和反转字符串方式上还是有所差异的。

方法一：秒！

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

方法二：使用异或运算

class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while (l < r) {
            s[l] ^= s[r];  //构造 a ^ b 的结果，并放在 a 中
            s[r] ^= s[l];  //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
            s[l] ^= s[r];  //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
            l++;
            r--;
        }
    }
}

| 异或运算

在给定的代码片段中，s[l] ^= s[r]; 是一种使用异或运算来交换两个变量值的方法，而不需要使用额外的临时变量。这种方法利用了异或运算的特性来实现变量值的交换。

异或运算的特性

• 自反性：对于任何值 a，a ^ a = 0。
• 交换性：a ^ b = b ^ a。
• 结合性：(a ^ b) ^ c = a ^ (b ^ c)。

如何交换两个变量的值
假设我们有两个变量 a 和 b，我们可以通过以下步骤使用异或运算来交换它们的值：

1. a = a ^ b：此时 a 变成了 a ^ b。
2. b = a ^ b：由于 a 现在是 a ^ b，所以 b = (a ^ b) ^ b = a。
3. a = a ^ b：由于 b 现在是 a，所以 a = (a ^ b) ^ a = b。

应用到代码中，在代码片段中：

• s[l] ^= s[r];：首先将 s[l] 和 s[r] 进行异或运算，结果存储在 s[l] 中。此时 s[l] 变成了 s[l] ^ s[r]。
• s[r] ^= s[l];：然后将 s[r] 和新的 s[l]（即 s[l] ^ s[r]）进行异或运算，结果存储在 s[r] 中。由于 s[l] 现在是 s[l] ^ s[r]，所以 s[r] = (s[l] ^ s[r]) ^ s[r] = s[l]。
• s[l] ^= s[r];：最后将新的 s[l]（即 s[l] ^ s[r]）和新的 s[r]（即 s[l]）进行异或运算，结果存储在 s[l] 中。由于 s[r] 现在是 s[l]，所以 s[l] = (s[l] ^ s[r]) ^ s[l] = s[r]。

通过这三步操作，s[l] 和 s[r] 的值就被交换了，而不需要使用额外的临时变量.

| 总结：①a=a^b ②b=a^b ③a=a^b

两个元素换位置，不用额外的内存空间，可以考虑下异或运算。

二、541. 反转字符串II

题目：https://leetcode.cn/problems/reverse-string-ii/

视频：https://www.bilibili.com/video/BV1dT411j7NN

讲解：https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

循环里让i以2k这个距离去移动

每次走2k，在2k中：

起始是 i ,

终止是 ①以i为标准的+k(够k的长度) 或是 ②字符串的结尾 (不够k的长度) 两者取小的

class Solution {
    public String reverseStr(String s, int k) {
        char[] re = s.toCharArray();

        for(int i = 0; i < re.length; i += 2 * k){
            int start = i;
            int end = Math.min(re.length-1, start + k -1);

            while(start < end){
                re[start] ^= re[end];
                re[end] ^= re[start];
                re[start] ^= re[end];

                start++;
                end--;
            }
        }
        return new String(re);
        
    }
}

方法二：定义一个功能函数reverse()

class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
		// 1. 每隔 2k 个字符的前 k 个字符进行反转
        for(int i= 0; i< ch.length; i +=2*k){
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if(i+k < ch.length){
                reverse(ch, i, i+k-1);
                continue;
            }
			// 3. 剩余字符少于 k 个，则将剩余字符全部反转
            reverse(ch, i, ch.length-1);
        }
       return new String(ch);
        
    }

    public void reverse(char[] ch, int i, int j){
        for(; i < j; i++, j--){
            char temp = ch[i];
            ch[i] = ch[j];
            ch[j] = temp;
        }
    }
}

更偏向使用方法一，理由是：

2k满足的情况下，有三种情况：

情况一：看2k里面的k，反转；

情况二：看2k外面剩余部分，满足k个，反转；

情况二：看2k外面剩余部分，不满足k个，不动；

前两种情况一样，都是反转，可以合成一个看；这两种情况与第三种情况不同的是，end所指向的满不满足k个距离。

所以三种情况其实就可以看成是两种情况，区间内满不满足k个距离。两个指标，一个是以start为标准的k个距离，另一个是末尾一个元素，两者哪个小，就是哪种情况。

讲解中还有第三种方法（随想录官网中的解法一），是用StringBuffer变长字符串来存储，然后根据截取字符串来进行相应的操作，没太看懂，再说吧……

三、 卡码网：54.替换数字

题目：https://kamacoder.com/problempage.php?pid=1064

视频：

讲解：https://programmercarl.com/kamacoder/0054.%E6%9B%BF%E6%8D%A2%E6%95%B0%E5%AD%97.html#%E6%80%9D%E8%B7%AF

在ACM模式下：自己写接口，自己写main函数，自己写输入输出

为什么要从后向前填充，从前向后填充不行么？

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

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

方法一：写好函数在main函数中引用

import java.util.Scanner;

public class Main{
    public static String replace(String s){
        int count = 0;
        int sOldSize = s.length();
        for(int i = 0; i < s.length(); i++){
            if(Character.isDigit(s.charAt(i))){
                count++;
            }
        }
        
        char[] newS = new char[s.length() + count * 5];
        int sNewSize = newS.length;
        
        System.arraycopy(s.toCharArray(), 0, newS, 0, sOldSize);
        
        for(int i = sNewSize-1, j = sOldSize-1; j<i; j--, i--){
            if(!Character.isDigit(newS[j])){
                newS[i] = newS[j];
            } else {
                newS[i] = 'r';
                newS[i-1] = 'e';
                newS[i-2] = 'b';
                newS[i-3] = 'm';
                newS[i-4] = 'u';
                newS[i-5] = 'n';
                i -= 5;
            }
        }
        return new String(newS);
        
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        System.out.println(replace(s)); 
    }
    
}

| Character.isDigit(s.charAt(i)) 是一个方法调用：

用来检查字符串 s 中的第 i 个字符是否是一个数字。

• Character 是 Java 中的一个类，提供了用于字符处理的静态方法。
• isDigit 是 Character 类的一个静态方法，用来检查传入的字符是否是数字（0-9）。
• s.charAt(i) 是获取字符串 s 中索引为 i 的字符。

所以，Character.isDigit(s.charAt(i)) 这个表达式的作用是：检查字符串 s 中索引为 i 的字符是否是数字。如果是数字，返回 true；如果不是数字，返回 false。

在这段代码的上下文中，这个表达式用于遍历字符串 s，统计其中的数字字符数量，并在后续的逻辑中将这些数字字符替换为字符串 “number”。

| System.arraycopy() 是一个用于数组拷贝的方法。具体解释如下：

System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

参数说明:

• src：源数组，即要从中复制数据的数组。
• srcPos：源数组中的起始位置，从该位置开始复制数据。
• dest：目标数组，即要将数据复制到的数组。
• destPos：目标数组中的起始位置，从该位置开始填充数据。
• length：要复制的数组元素的数量。

System.arraycopy() 方法用于将一个数组中的部分元素高效地复制到另一个数组中。它是一个本地方法（native method），由 Java 虚拟机（JVM）直接实现，因此比普通的循环复制要高效得多。

在题中的代码片段中，System.arraycopy 用于将原始字符串 s 的字符数组内容复制到新创建的字符数组 newS 中。具体代码如下：

System.arraycopy(s.toCharArray(), 0, newS, 0, sOldSize);

• s.toCharArray()：将字符串 s 转换为字符数组。
• 0：源数组 s.toCharArray() 的起始位置，从第 0 个字符开始复制。
• newS：目标数组，即新创建的字符数组。
• 0：目标数组 newS 的起始位置，从第 0 个字符开始填充。
• sOldSize：要复制的字符数量，即原始字符串 s 的长度。

这行代码的作用是将原始字符串 s 的所有字符复制到新数组 newS 的前 sOldSize 个位置。这样，新数组 newS 的前 sOldSize 个字符与原始字符串 s 的内容完全相同，而剩余的位置则用于后续的数字替换操作。

写法二：全部在main函数中实现

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        
        int len = s.length();
        
        for(int i = 0; i < s.length(); i++){
            if(Character.isDigit(s.charAt(i))){
                len += 5;
            }
        }
        
        char[] newS = new char[len];
        for(int i = 0; i < s.length(); i++){
            newS[i] = s.charAt(i);
        }
        
        for(int i = s.length()-1, j = len -1; i >=0; i--){
            if(Character.isDigit(s.charAt(i))){
                newS[j--] = 'r';
                newS[j--] = 'e';
                newS[j--] = 'b';
                newS[j--] = 'm';
                newS[j--] = 'u';
                newS[j--] = 'n';
            } else {
                newS[j--] = newS[i];
            }
        }
        System.out.println(newS);
        
    }
}