替换数字
54. 替换数字（第八期模拟笔试） (kamacoder.com)
第一眼：创建新数组，从左到右逐个遍历，当字符是数字时填入number
若不使用额外空间呢？？？
Java解答必须使用创建新数组，因为Java的String是不可变类型
解题思路：双指针 + 扩充数组到目标长度 + 从右向左遍历
- 左指针指向原字符串的尾部，右指针指向扩充数组尾部
- 左指针遍历到数字后，右指针依次将
rebmun加入到目标数组中
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
| #include <iostream>
using namespace std;
int main() {
string s;
while (cin >> s) {
int sOldIndex = s.size() - 1;
int count = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] >= '0' && s[i] <= '9') {
count++;
}
}
s.resize(s.size() + count * 5);
int sNewIndex = s.size() - 1;
while (sOldIndex >= 0) {
if (s[sOldIndex] >= '0' && s[sOldIndex] <= '9') {
s[sNewIndex--] = 'r';
s[sNewIndex--] = 'e';
s[sNewIndex--] = 'b';
s[sNewIndex--] = 'm';
s[sNewIndex--] = 'u';
s[sNewIndex--] = 'n';
} else {
s[sNewIndex--] = s[sOldIndex];
}
sOldIndex--;
}
cout << s << endl;
}
}
|
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
| import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
int len = s.length();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) >= 0 && s.charAt(i) <= '9') {
len += 5;
}
}
char[] ret = new char[len];
for (int i = 0; i < s.length(); i++) {
ret[i] = s.charAt(i);
}
for (int i = s.length() - 1, j = len - 1; i >= 0; i--) {
if ('0' <= ret[i] && ret[i] <= '9') {
ret[j--] = 'r';
ret[j--] = 'e';
ret[j--] = 'b';
ret[j--] = 'm';
ret[j--] = 'u';
ret[j--] = 'n';
} else {
ret[j--] = ret[i];
}
}
System.out.println(ret);
}
}
|
151.翻转字符串里的单词
151. 反转字符串中的单词 - 力扣（LeetCode）
第一眼：创建新数组，从左到右遍历，遇到空格跳过，遇到单词进行反转，最后对整个数组进行反转
不创建新数组在原地修改字符串呢?
Java只能创建新数组，因为Java不可以修改string的内容
解题思路：
- 去除多余的空格
- 将整个字符串进行反转
- 将每个字符进行反转
难点在于：怎么去除多余的空格呢？(不使用split函数)
思路：双指针【左指针指向空格，右指针遍历到非空格后填入左指针位置将左指针右移，进入下一个单词前手动加入空格】
可以将问题转化为字符串种去除指定的字符，区别在于要在每个单词中保留一个空格
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void removeExtraSpaces(string& s) {
int slow = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] != ' ') {
if (slow != 0) s[slow++] = ' ';
while (i < s.size() && s[i] != ' ') {
s[slow++] = s[i++];
}
}
}
s.resize(slow);
}
|
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
| class Solution {
public:
void reverse(string& s, int start, int end){
for (int i = start, j = end; i < j; i++, j--) {
swap(s[i], s[j]);
}
}
void removeExtraSpaces(string& s) {
int slow = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] != ' ') {
if (slow != 0) s[slow++] = ' ';
while (i < s.size() && s[i] != ' ') {
s[slow++] = s[i++];
}
}
}
s.resize(slow);
}
string reverseWords(string s) {
removeExtraSpaces(s);
reverse(s, 0, s.size() - 1);
int start = 0;
for (int i = 0; i <= s.size(); ++i) {
if (i == s.size() || s[i] == ' ') {
reverse(s, start, i - 1);
start = i + 1;
}
}
return s;
}
};
|
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| class Solution {
public String reverseWords(String s) {
StringBuilder sb = removeSpace(s);
reverseString(sb, 0, sb.length() - 1);
reverseEachWord(sb);
return sb.toString();
}
private StringBuilder removeSpace(String s) {
int start = 0;
int end = s.length() - 1;
while (s.charAt(start) == ' ') start++;
while (s.charAt(end) == ' ') end--;
StringBuilder sb = new StringBuilder();
while (start <= end) {
char c = s.charAt(start);
if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
sb.append(c);
}
start++;
}
return sb;
}
public void reverseString(StringBuilder sb, int start, int end) {
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
private void reverseEachWord(StringBuilder sb) {
int start = 0;
int end = 1;
int n = sb.length();
while (start < n) {
while (end < n && sb.charAt(end) != ' ') {
end++;
}
reverseString(sb, start, end - 1);
start = end + 1;
end = start + 1;
}
}
}
|
右旋字符串
55. 右旋字符串（第八期模拟笔试） (kamacoder.com)
第一眼：保存一部分字符，将另一部分进行移动，然后将第一部分填入对应的位置
解题思路：分别对两部分进行反转，然后对整个字符串进行反转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include<iostream>
#include<algorithm>
using namespace std;
int main() {
int n;
string s;
cin >> n;
cin >> s;
int len = s.size();
reverse(s.begin(), s.begin() + len - n);
reverse(s.begin() + len - n, s.end());
reverse(s.begin(), s.end());
cout << s << endl;
}
|
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
| import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s1 = sc.nextLine();
int count = Integer.parseInt(s1);
String s = sc.nextLine();
if (count >= s.length()) {
System.out.println(s);
return;
}
char[] c = s.toCharArray();
reverse(c, 0, c.length - 1 - count);
reverse(c, c.length - count, c.length - 1);
reverse(c, 0, c.length - 1);
System.out.println(new String(c));
}
public static void reverse(char[] c, int left, int right) {
while (left < right) {
char temp = c[left];
c[left] = c[right];
c[right] = temp;
right--;
left++;
}
}
}
|
459.重复的子字符串
459. 重复的子字符串 - 力扣（LeetCode）
解题思路：如果一个字符串s可以由它的子串重复构成，那么s+s（去头去尾）中会出现s
eg：abab，判断时abababab去头去尾是bababa，其中包含abab
1
2
3
4
5
6
| class Solution {
public boolean repeatedSubstringPattern(String s) {
String str = s + s;
return str.substring(1,str.length() - 1).contains(s);
}
}
|
