344 反转字符串
https://leetcode.com/problems/reverse-string/description/
双指针解法 把左右交换即可
两种交换方法，一种是常见交换，一种是位运算
- 常见交换
int temp = a;
a = b;
b = temp;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution{
public void reverseString(char[] s){
int left = 0, right = s.length - 1;
while (left < right){
swapInArray(s,left++,right--);
}
}
private void swapInArray(char[] s, int m, int n){
char temp = s[m];
s[m] = s[n];
s[n] = temp;
}
}
|
- 位运算
a ^= b //a = a ^ b
b ^= a //b = a ^ b ^ a = a, a = a ^ b
a ^= b //a = a ^ b ^ b = b, b = a
//完成转化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution{
public void reverseString(char[] s){
int left = 0;
int right = s.length - 1;
while (left < right){
swapInArray(s, left++, right--);
}
}
private void swapInArray(char[] s, int m, int n){
s[m] ^= s[n];
s[n] ^= s[m];
s[m] ^= s[n];
}
}
|
541 反转字符串II
https://leetcode.com/problems/reverse-string-ii/description/
使用指针做法，查找k的位置，reverse方法记住，在外面套一层逻辑来判断什么需要反转什么不需要反转，要背下来，在array中区间反转逻辑
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution{
public String reverseStr(String s, int k) {
char[] str = s.toCharArray();
int left = 0;
while (left < str.length){
int right = left + k - 1;
if (right > str.length - 1){
reverseList(str, left, str.length - 1);
} else {
reverseList(str, left, right);
}
left += 2 * k;
}
return new String(str);
}
private void reverseList(char[] str, int m, int n){
int left = m, right = n;
while (left < right) swapInArray(str, left++, right--);
}
private void swapInArray(char[] str, int m, int n){
str[m] ^= str[n];
str[n] ^= str[m];
str[m] ^= str[n];
}
}
|
替换数字
https://kamacoder.com/problempage.php?pid=1064
由于c++可以扩充数组，则可使用双指针记录读到数字的位置，然后把在数组最后的指针向后移出number的位置，但是java更简单，可以直接用Stringbuilder做
注意代码用法：
- Character.isDigit
- Scanner 用法
- StringBuilder 用法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++){
if (Character.isDigit(s.charAt(i))){
sb.append("number");
} else {
sb.append(s.charAt(i));
}
}
System.out.println(sb);
sc.close();
}
}
|
151 翻转字符串里的单词
https://leetcode.com/problems/reverse-words-in-a-string/
要求不使用辅助空间，空间复杂度为O（1）
具体实现：
先移除多余的空格，后反转整个字符串，之后在单独反转单词部分
- 移除多余空格，使用StringBuilder 重构string
先把开头和结尾的空格去掉
在append不是空格的部分，遇到空格是检查StringBuilder上一个元素是否为空格，不是就添加，是就跳过
返回StringBuilder
- 整个数组反转
in-place: 双指针互换左右字符
StringBuilder: 重建StringBuilder，设置左右数
- 反转各个单词
利用快慢指针，找到每个单词的起始和终止位置，然后in-place翻转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| class Solution {
public String reverseWords(String s) {
char[] str = removeExtraSpaces(s);
reverseList(str, 0, str.length - 1);
System.out.println(str.length);
int left = 0;
int right = 1;
while (left < str.length){
while(right < str.length && str[right] != ' '){
right++;
}
reverseList(str, left, right - 1);
left = right + 1;
right++;
}
return new String(str);
}
private char[] removeExtraSpaces(String s){
StringBuilder sb = new StringBuilder();
int left = 0, right = s.length() - 1;
while (left < s.length() && s.charAt(left) == ' ') left++;
while (right > 0 && s.charAt(right) == ' ') right--;
while (left <= right){
if (s.charAt(left) != ' ' || sb.charAt(sb.length() - 1) != ' '){
sb.append(s.charAt(left));
}
left++;
}
return sb.toString().toCharArray();
}
private void reverseList(char[] str, int m, int n){
int left = m, right = n;
while (left < right){
swapInArray(str, left++, right--);
}
}
private void swapInArray(char[] str, int m, int n){
str[m] ^= str[n];
str[n] ^= str[m];
str[m] ^= str[n];
}
}
|
右旋字符串
https://kamacoder.com/problempage.php?pid=1065
解法与翻转字符串里的单词差不多
把整体反转之后，再把局部的长度反转，得到结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();
String s = sc.nextLine();
char[] str = s.toCharArray();
reverseList(str, 0, s.length()-1);
reverseList(str, 0, n-1);
reverseList(str, n, s.length()-1);
System.out.println(str);
sc.close();
}
private static void reverseList(char[] str, int m, int n){
int left = m, right = n;
while(left < right){
swapInArray(str, left++, right--);
}
}
private static void swapInArray(char[] str, int m, int n){
str[m] ^= str[n];
str[n] ^= str[m];
str[m] ^= str[n];
}
}
|