字符串问题——字符串的替换与调整

Posted on | In ,

1.题目1：给定一个字符类型的数组chas[]，chas右半区全是空字符，左半区不含空字符。现想将左半区的所有空格字符替换成”%20”，假设右半区足够大，可以满足替换所取得空间，请完成替换函数。
例：
左半区看作字符串，为”a b c”，替换后左半区为”a%20b%20%20c”。
2.题目2：给定一个字符数组chas[]，其中只含有数字和”*”字符，现想将所有的”*”移到chas的左边，数字移到chas的右边，请完成调整函数。
例：
如果把chas看成字符串，为”12**345”，调整后为”**12345”。

实现
1.问题1
遍历str可以得到两个信息，chas的长度len，左半区的空格有多少num，则空格字符被”%20”替换后，长度将为len+2num。（’%’、’2’、’0’每个字符占用一个位置，由于空格已经占用了一个位置，因此还需要2空格个长度。char两个字节）
思路一：若从前往后移动字符，遇到空格就往后移动两个字符，用来将包括空格在内的三个字符赋值为”%20”。
若字符长度为N，每遇到一个空格则往后移动的字符数为O(N)，则总时间复杂度为O(N*N)。
思路二：为了避免重复多次移动字符，考虑从后往前移动字符，且移动的同时进行赋值。从右往左，遇到空格就赋值”0”、”2”、”%”。
思路三：利用StringBuffer的append()方法，遇到非空格则直接加入，否则加入%20。

2.问题2
方法一：设计StringBuffer对象，遍历chas，将所有数字存入，然后将’*‘存入。
最后将char数组逆序。
方法二：从右往左遍历chas，遇到数字则存入，剩下的位置存’*’。

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
import java.util.Arrays;
import java.util.concurrent.SynchronousQueue;
/*
 * 将空格替换成"%20"
 */
public class ReplaceBlank {
	/**
	 * 问题1
	 * 思路三：直接用StirngBuffer求解，
	 * 遇到非空格则将字符加入到sb中，
	 * 遇到空格则加入%20.
	 * @param chas
	 * @return
	 */
	public static String replace(char[] chas) {
		if (chas == null || chas.length == 0) {
			return null;
		}
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < chas.length; i++) {
			if (chas[i] != ' ') {
				sb.append(chas[i]);
			} else {
				sb.append("%20");
			}
		}
		return sb.toString();
	}
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
/**
 * 问题2
 * 方法一：
 * 将所有的*放在左边，数字放右边
 * 1.先将所有的数字放入，再将*放入
 * 2.逆序
 * @param chas
 * @return
 */
public static String change(char[] chas) {
	if (chas == null || chas.length == 0) {
		return null;
	}
	StringBuffer sb = new StringBuffer();
	int num = 0; //统计'*'的个数
	for (int i = chas.length - 1; i >= 0; i--) {
		if (chas[i] != '*') {
			sb.append(chas[i]);
		} else {
			num++;
		}
	}
	while (num-- != 0) {
		sb.append('*');
	}
	chas = sb.toString().toCharArray();
	int left = 0;
	int right = chas.length - 1;
	while (left <= right) {
		char temp = chas[left];
		chas[left] = chas[right];
		chas[right] = temp;
		left++;
		right--;
	}
	return Arrays.toString(chas);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 问题2
 * 方法二：
 * 1. 从右往左倒着复制，遇到数字则直接复制，遇到'*'不复制
 * 2. 当把数字复制完，把左半区全部设为'*'。
 * @param chas
 * @return
 */
public static String change2 (char[] chas) {
	if (chas == null || chas.length == 0) {
		return null;
	}
	int j = chas.length - 1;
	for (int i = chas.length - 1; i >= 0; i--) {
		if (chas[i] != '*') {
			chas[j--] = chas[i]; 
		}
	}
	for (; j >= 0; ) {
		chas[j--] = '*';
	}
	return Arrays.toString(chas);
}
1
2
3
4
5
6
7
8
9
	// Test
	public static void main(String[] args) {
		char[] chas = { 'a', ' ', 'b', ' ', ' ', 'c' };
		System.out.println(replace(chas));
		char[] chas2 = { '1', '2', '*', '*', '3', '4','5'};
		System.out.println(change(chas2));
		System.out.println(change2(chas));
	}
}

输出：

1
2
3
a%20b%20%20c
[*, *, 1, 2, 3, 4, 5]
[*, *, 1, 2, 3, 4, 5]