算法训练（leetcode）二刷第七天 | 344. 反转字符串、541. 反转字符串 II、54. 替换数字（第八期模拟笔试）

344. 反转字符串

leetcode题目地址

使用双指针对数组进行循环首尾交换即可。

Tips： 使用位运算中的异或操作也可实现交换。

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 完成交换

时间复杂度： $O(n)$
空间复杂度： $O(1)$

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

541. 反转字符串 II

leetcode题目地址

根据题意，每2k个字符反转前k个，即反转k个，保持原样k个，使用一个flag来标志当前是否反转。由于java的字符串类型是不可变的，因此需要先转为字符数组。

Tips： 也可以在遍历时指针每次移动2*k个位置，然后再对前k个元素做反转。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
class Solution {

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

    public String reverseStr(String s, int k) {
        char[] arr = s.toCharArray();
        int len = arr.length - (arr.length % k), i;
        boolean flag = true;
        for(i=1; i<=len; i++){
            if(i%k==0){
                if(flag){
                    reverse(arr, i-k, i-1);
                }
                flag = !flag;
            }
        }
        // 剩余少于k个字符
        if(flag && i<arr.length){
            reverse(arr, i-1, arr.length-1);
        }

        return new String(arr);
    }
}

54. 替换数字（第八期模拟笔试）

KamaCoder题目地址

先统计字符串中数字的个数，然后开辟结果数组的长度为原数组长度+数字个数*5，因为题目数字替换为number，number共6位，原字符串中的数字还占一位，因此是乘5。然后遍历遇到数字进行填充即可。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        // char[] arr = s.toCharArray();
        int len = s.length();
        int cnt = 0;
        for(int i=0; i<len; i++){
            if(s.charAt(i)>='0' && s.charAt(i)<='9'){
                cnt++;
            }            
        }
        
        char[] res = new char[len + cnt * 5];
        int k=0;
        for(int i=0; i<len; i++){
            if(s.charAt(i)>='0' && s.charAt(i)<='9'){
                
                res[k++] = 'n';
                res[k++] = 'u';
                res[k++] = 'm';
                res[k++] = 'b';
                res[k++] = 'e';
                res[k++] = 'r';
            }else{
                res[k++] = s.charAt(i);
            } 
        }
        System.out.println(new String(res));
    }
}