算法训练（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));}
}