刷题记录
- 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(n)
O(n)
空间复杂度:
O
(
1
)
O(1)
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)
O(n)
空间复杂度:
O
(
n
)
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)
O(n)
空间复杂度:
O
(
n
)
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));
}
}