算法训练营day07 | {344.反转字符串, 541.反转字符串II, 15.三数之和，18.四数之和}

第四章字符串-part01，知识点为反转字符串、双指针。

344. 反转字符串

题目链接：344.反转字符串
状态：打基础的时候，不要太迷恋库函数。

1.1 解题过程

String是不可变对象，而StringBuilder是可变对象，reverse()要求原地修改，所以这行代码等价于本题的实现：
1
2
StringBuilder sb = new StringBuilder(String.valueof(s)).reverse(); String newStr = sb.toString();

▶

344. 反转字符串

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

541. 反转字符串II

题目链接：541. 反转字符串II
状态：模拟题。写得还可以再优雅一点。

2.1 解题过程

当需要以固定规律一段一段去处理字符串时，要想想for循环，在遍历字符串时，让i += 2 * k，然后判断是否有需要反转的区间。
也属于双指针的题目，因为有交换操作。之前做的原地反转链表题也是哦。

▶

541. 反转字符串II（优雅）

class Solution {
    public void reverse(char[] arr, int left, int right) {
        while(left < right) {
            char tmp = arr[left];
            arr[left++] = arr[right];
            arr[right--] = tmp;
        }
    }

    public String reverseStr(String s, int k) {
        char[] str = s.toCharArray();
        int n = str.length;
        for (int i = 0; i < n; i += 2 * k) {
            reverse(str, i, Math.min(i + k, n) - 1);
        }
        return String.valueOf(str);
    }
}

卡码网：54.替换数字

题目链接：卡码网：54.替换数字
状态：用StringBuilder对象做，简单。

3.1 解题过程

看作业提示，还不明白后序处理指什么，看了题解之后觉得还不错啊，又用到了双指针的思想。
具体来说，把本题作为一个数组填充类的问题，通常的做法是先预先给数组扩容到填充后的大小，然后在从后向前进行操作。好处是：
- 不用申请新数组。
- 从后往前填充，避免了从前往后填充时，每次要将添加元素之后的元素往后移动的问题。

▶

StringBuilder

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        char[] str = s.toCharArray();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length; i++) {
            if (str[i] - 'a' >=0 && str[i] - 'a' < 26) {
                sb.append(str[i]);
            }
            else {
                sb.append("number");
            }
        }
        System.out.println(sb.toString());
        scanner.close();
    }
}

▶

双指针填充

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        int cntNum = 0;
        for (int i = 0; i < s.length(); i++) {
            if (Character.isDigit(s.charAt(i))) cntNum++;
        }

        char[] newS = new char[s.length() + cntNum * 5];
        System.arraycopy(s.toCharArray(), 0, newS, 0, s.length());

        for (int i = newS.length - 1, j = s.length() - 1; i >= 0; ) {
            if (Character.isDigit(newS[j])) {
                System.arraycopy("number".toCharArray(), 0, newS, i - 5, 6);
                i -= 6;
                j--;
            } else {
                newS[i--] = newS[j--];
            }
        }
        System.out.println(new String(newS));
    }
}