题目1：替换空格
请实现一个函数，把字符串中的每个空格替换成"%20"。例如，输入“We are happy.”，则输出“We%20are%20happy.”。
示例 1：
1
2
| 输入：path = "We are happy."
输出："We%20are%20happy"
|
在Java中每对String类型的对象进行操作都会生成一个新的对象，所以我们需要避免使用原字符串进行操作。
解法一：使用StringBuilder
我们需要使用StringBuilder来构造最终的结果，遇到空格时加上"%20"。
1
2
3
4
5
6
7
8
9
10
11
12
13
| public String replaceSpace(String s) {
char[] charArray = s.toCharArray();
StringBuilder sb = new StringBuilder();
for (char c : charArray) {
if (c == ' ') {
sb.append("%20");
}
else {
sb.append(c);
}
}
return sb.toString();
}
|
时间复杂度O(n) 空间复杂度O(n)
解法二：使用数组
直接使用char的数组来表示结果，由于原字符串的char[]长度不够，所以还是需要新建数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public String replaceSpace(String s) {
char[] charArray = s.toCharArray();
int cntSpace = 0;
for (char c : charArray) {
if (c == ' ') {
cntSpace++;
}
}
int resultLength = charArray.length + 2 * cntSpace;
char[] resultCharArray = new char[resultLength];
int indexInResult = resultLength - 1;
for (int i = charArray.length - 1; i >= 0; i--) {
if (charArray[i] == ' ') {
resultCharArray[indexInResult--] = '0';
resultCharArray[indexInResult--] = '2';
resultCharArray[indexInResult--] = '%';
}
else {
resultCharArray[indexInResult--] = charArray[i];
}
}
return new String(resultCharArray);
}
|
这边的遍历顺序是从后往前遍历，在题目1中与使用从前往后遍历的效果没有区别，但是如果原数组的长度本身就足够的，那么就需要从后往前把字符填进去，下面看题目2理解一下。
题目2：将一个排序数组插入到另一个排序数组
有两个排序数组A1,A2，A1末尾有足够多的空余空间容纳A2，实现一个函数将A2插入A1，并所有数字是排序的。
示例1：
1
2
| 输入：A1: [1, 3, 5, 7, NULL, NULL, NULL, NULL] A2: [2, 4, 6, 8]
输出：A1: [1, 2, 3, 4, 5, 6, 7, 8]
|
解法一：倒序遍历数组
因为最终的结果是需要存入A1中的，所以我们需要在A1原数组上做修改。如果使用从前往后遍历，那么就会涉及元素的移动，但是从后往前遍历就不会有这个问题。
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
| public Integer[] mergeArrayInFirst(Integer[] a1, Integer[] a2) {
int indexA1 = a1.length - 1;
for (; indexA1 >= 0; indexA1--) {
if (a1[indexA1] != null) {
break;
}
}
int indexA2 = a2.length - 1;
int indexResult = a1.length - 1;
while (indexA1 >= 0 || indexA2 >= 0) {
if (indexA1 < 0) {
a1[indexResult] = a2[indexA2];
indexA2--;
}
else if (indexA2 < 0) {
a1[indexResult] = a1[indexA1];
indexA1--;
}
else {
if (a1[indexA1] >= a2[indexA2]) {
a1[indexResult] = a1[indexA1];
indexA1--;
}
else {
a1[indexResult] = a2[indexA2];
indexA2--;
}
}
indexResult--;
}
return a1;
}
|
相关代码
https://gitee.com/zhaomin6666/coding-interview/tree/main/src/main/java/com/zm/interview/chapter02/ex003