代码随想录第八天|字符串part01--344.反转字符串、541.反转字符串Ⅱ、卡玛网54.替换数字

资源引用：

leetcode题目：

344.反转字符串（344. 反转字符串 - 力扣（LeetCode））

541.反转字符串Ⅱ（541. 反转字符串 II - 力扣（LeetCode））

卡玛网题目：

卡玛网54.替换数字（54. 替换数字（第八期模拟笔试） (kamacoder.com)）

碎碎念回归：

本来应该11月6号打卡的，因为接连4天的考试+多个竞赛，导致推迟到了今天才补做，现在也到了这个学期最忙的最后一个星期了，希望自己能调整好状态，安排好时间，脚踏实地朝着目标前进，加油！

344.反转字符串（344. 反转字符串 - 力扣（LeetCode））

题目分析：

要将输入的字符串反转过来，通过原地修改输入数组进行实现（即空间复杂度为O(1)），已经提示每个字符都是ASCII码表中的。不能使用reverse函数解决，考虑使用左右双指针和临时交换量解决。

解题思路：

左指针left初始化为0即指向字符串开头，右指针right初始化为s.length-1即指向字符串末尾。不断交换left和right所指向的两个字符，每交换一次，left++和right--，直至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--;
        }
    }
}

541.反转字符串Ⅱ（541. 反转字符串 II - 力扣（LeetCode））

题目分析：

对字符串s做跨步为2k的反转操作，每跨步2k，对前k个字符串做反转计算。注意两个边界情况：若该次跨步的剩余字符不足k个，则全部反转；若该次跨步的剩余字符不足2k个但不少于k个，则仍反转前k个字符。仍然考虑使用双指针和位运算交换来解决。

解题思路：

设计一个交换函数mySwap(string S, int left, int right)，left和right用于标示将要反转的字符串区间。主函数使用循环进行多次跨步操作，循环不变量是当前的指针不可越界，跨步操作注意三种不同情况的跨步结束。

总结反思：

1.跨步一次跨2k步即可

2.使用Math.min(chars.length-1, cur+k-1)可以方便判断当前剩余区间长度是否小于k，并取两者之中的小者作为反转区间的右区间，完成反转操作。

3.注意String和char[]之间的转化：

char[] chars= string.toCharArray();

String string= new String(chars[]);

String string= String.valueOf(chars);

class Solution {
    public String reverseStr(String s, int k) {
        if(s.length() == 0){
            return s;
        }

        char[] chars = s.toCharArray();
        int cur=0;
        int left=0;
        int right=0;
        while(cur < chars.length){
            left=cur;
            right=Math.min(chars.length-1, cur+k-1);//用于判断此次反转区间的长度是否不足k，若不足k则将剩余区间全部反转
            myReverse(chars,left,right);
            cur+=2*k;
        }
        return String.valueOf(chars);
    }
    public char[] myReverse(char[] s,int left,int right){
        while(left<right){
            s[left]^=s[right];
            s[right]^=s[left];
            s[left]^=s[right];
            left++;
            right--;
        }
        return s;
    }
}

卡玛网54.替换数字（54. 替换数字（第八期模拟笔试） (kamacoder.com)）

题目分析：

对包含小写字母和数字字符的字符串s做替换，将每一个数字字符替换为"number"。这样的操作会导致字符串长度改变，在java中字符串和数组长度均不可变，故需另外新建数组，通过遍历该字符串根据其中包含的数字字符个数来确定新字符串的长度。

解题思路：

将字符串转换为字符数组chars，遍历chars记录数字字符个数，每多一个数字字符，新字符串的长度在原来的字符串的长度上+5（替换后的number有6个字符）。

然后再次遍历字符串数组，逐步填充新的字符串数组，最后打印输出。

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        scanner.close();
        char[] chars = s.toCharArray();
        int l=chars.length;
        for(char i : chars){
            if(i-'a'>=0 && i-'a'<=25){
                continue;
            }else{
                l+=5;
            }
        }
        char[] newS = new char[l];
        int index = 0;
        for(char i : chars){
            if(i-'a'>=0 && i-'a'<=25){
                newS[index++]=i;
            }else{
                newS[index++]='n';
                newS[index++]='u';
                newS[index++]='m';
                newS[index++]='b';
                newS[index++]='e';
                newS[index++]='r';
            }
        }
        System.out.println(new String(newS));
    }
}

总结反思：

由于java中的字符串和数组长度均不可变，故不得不申请新的空间。若使用其他编程语言，例如c++，在原String的基础上可以扩充长度，如果不允许申请新的字符串数组，可以考虑从后往前填充新的数组，已经读取并填充过的字符会被“安全”覆盖（不会丢失信息）。