剑指Offer(5) 替换空格

发表于 | 分类于 | 阅读次数:

替换空格

本文有两道题。
第一道题，请实现一个函数，把字符串中的每个空格替换成”%20”。例如输入“We are happy.”，则输出“We%20are%20happy.”。

第二道题，实现对一组无序的字母进行从小到大排序（区分大小写），当两个字母相同时，小写字母放在大写字母前。要求时间复杂度为O(n)。

题目一

请实现一个函数，把字符串中的每个空格替换成”%20”。例如输入“We are happy.”，则输出“We%20are%20happy.”。

思路

首先要询问面试官是新建一个字符串还是在原有的字符串上修改，本题要求在原字符串上进行修改。

若从前往后依次替换，在每次遇到空格字符时，都需要移动后面O(n)个字符，对于含有O(n)个空格字符的字符串而言，总的时间效率为O(n^2)。

转变思路：先计算需要的总长度，然后从后往前进行复制和替换，则每个字符只需要复制一次即可。时间效率为O(n)。

测试用例

  1. 字符串中无空格
  2. 字符串中含有空格（连续空格，空格在首尾等）
  3. 字符串为空字符串或者为null

Java代码

根据牛客网的编程练习参考，方法的输入为StringBuffer（String无法改变长度，所以采用StringBuffer），输出为String。

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
public class ReplaceSpaces {
	public String replaceSpaces(StringBuffer str) {
	if (str == null) {
		System.out.println("输入错误")；
		return null;
	}

	int length = str.length();
	int indexOfOriginal = length - 1;
	for (int i = 0; i < str.length(); i++) {
		if (str.charAt(i) == ' ') {
			length += 2;
		}
	}

	str.setLength(length);
	int indexOfNew = length - 1;

	while (indexOfNew > indexOfOriginal) {
		if (str.charAt(indexOfOriginal) != ' ') {
			str.setCharAt(indexOfNew--, str.charAt(indexOfOriginal));
		} else {
			str.setCharAt(indexOfNew--, '0');
			str.setCharAt(indexOfNew--, '2');
			str.setCharAt(indexOfNew--, '%');
		}
		indexOfOriginal--;
	}
	return str.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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class ReplaceSpaces {
	// ==================================测试代码==================================
 
    /**
     * 输入为null
     */
    public void test1() {
        System.out.print("Test1：");
        StringBuffer sBuffer = null;
        String s = replaceSpace(sBuffer);
        System.out.println(s);
    }
     
    /**
     * 输入为空字符串
     */
    public void test2() {
        System.out.print("Test2：");
        StringBuffer sBuffer = new StringBuffer("");
        String s = replaceSpace(sBuffer);
        System.out.println(s);
    }
     
    /**
     * 输入字符串无空格
     */
    public void test3() {
        System.out.print("Test3：");
        StringBuffer sBuffer = new StringBuffer("abc");
        String s = replaceSpace(sBuffer);
        System.out.println(s);
    }
     
    /**
     * 输入字符串为首尾空格，中间连续空格
     */
    public void test4() {
        System.out.print("Test4：");
        StringBuffer sBuffer = new StringBuffer(" a b  c  ");
        String s = replaceSpace(sBuffer);
        System.out.println(s);
    }
     
    public static void main(String[] args) {
        ReplaceSpaces rs = new ReplaceSpaces();
        rs.test1();
        rs.test2();
        rs.test3();
        rs.test4();
    }
}

替换空格-采用数组的方法

因为java字符串是不可变的，所以也可以使用字符数组来解决这个问题。

处理字符串的时候，常见做法是从尾部开始编辑，从后往前反向操作。这种做法很有用，因为字符串尾部有额外的缓冲，可以直接修改，不必担心会覆写原有数据。
采用上面的做法，进行两次扫描，第一次扫描先数出字符串中有多少空格，从而计算出最终的字符串有多长。第二次扫描才真正开始反向编辑字符串。检测到空格则将%20复制到下一个位置，若不是空白，就复制原先的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void replaceSpace(char[] str, int length) {
    int spaceCount = 0;
    int newLength;
    for (int i = 0; i < length; i++) {
        if (str[i] == ' ') {
            spaceCount++;
        }
    }
    newLength = length + spaceCount * 2;
    str[newLength] = '\0';
    for (int i = length - 1; i >= 0 ; i--) {
        if (str[i] == ' ') {
            str[--newLength] = '0';
            str[--newLength] = '2';
            str[--newLength] = '%';
        } else {
            str[--newLength] = str[i];
        }
    }
}

总结

  1. 对于一个错误
1
2
3
4
5
6
// 这里用了 for (int i = 0; i < length; i++) {
   // 非常之愚蠢，因为在for循环体里面 length的值一直在变化
   for (int i = 0; i < length; i++) {
       if (str.charAt(i) == ' ')
           length += 2;
   }

  1. 如果在从前往后进行复制时，需要多次移动数据，则可以考虑从后往前复制，从而减小移动次数，提高效率。

  2. Java 打印输出字符数组 Java 中，char 类型数组可以直接使用数组名打印。char 类型的数组就相当于一个字符串。 输出流 System.out 是 PrintStream 对象，PrintStream 有多个重载的 println 方法，其中一个就是 public void println(char[ ] x)它会直接调用这个方法来打印字符数组。因此可以直接打印出数组内容，而不是地址。

  3. 不要使用 i % 2 == 1 来判断是否是奇数，因为i为负奇数时不成立，请 使用 i % 2 != 0 来判断是否是奇数，或使用 高效式 (i & 1) != 0来判断奇数，奇数与1相与必为1。。

  4. 生成char array的方法

1
2
3
4
5
6
7
8
9
10
11
//生成char Array
String s = "HappyBirthdayzLinkeRuIlikeyouazz";
char[] src = s.toCharArray();

//打印char 数组成字符串
System.out.print(src);

//数组转字符串
String[] arr = {"laowang", "stone", "wanglei"};
String str2 = Arrays.toString(arr);
System.out.println(str2);  // 输出[laowang, stone, wanglei]
  1. 数组拷贝
1
2
3
int[] arr = {3, 4, 9};
int[] arr2 = Arrays.copyOf(arr, arr.length);
System.out.println(Arrays.toString(arr2));

无序字母排序

本题不属于剑指offer。

题目二

实现对一组无序的字母进行从小到大排序（区分大小写），当两个字母相同时，小写字母放在大写字母前。要求时间复杂度为O(n)。

思路

使用排序算法在最好的情况下的时间复杂度都在O(nlogn)，不满足题目要求。
通常字母为26个，当区分大小写后，变成26*2=52个，所以申请长度为52的int型数组，按照aAbB…zZ(小写字母保存在下标为偶数的位置，大写字母保存在下标为奇数的位置)的顺序一次记录各个字母出现的次数，当记录完成后，就可以遍历这个数组按照各个字母出现的次数来重组排序后的数组。

Java代码

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
public class SortCharacters {

	public static void main(String[] args) {
		String s = "HappyBirthdayzLinkeRuIlikeyouazz";
		char[] src = s.toCharArray();
		sort(src);
		for (char ch : src) {
			System.out.print(ch + " ");
		}
	}

	private static void sort(char[] src) {
		if (src == null) {
			System.out.println("参数不合法");
			return;
		}
		// 用于保存52个字符出现的次数，小写字母保存在下标为偶数的位置，大写字母保存在奇数位置

		int[] charCount = new int[52];

		for (int i = 0; i < src.length; i++) {
			//
			if (src[i] >= 'a' && src[i] <= 'z') {
				charCount[(src[i] - 'a') * 2]++;
			} else if (src[i] >= 'A' && src[i] <= 'Z') {
				charCount[(src[i] - 'A') * 2 + 1]++;
			}

		}

		int index = 0;

		for (int i = 0; i < charCount.length; i++) {
			if (charCount[i] != 0) {
				if (i % 2 == 0) { // 小写字母
					for (int j = 0; j < charCount[i]; j++)
						src[index++] = (char) (i / 2 + 'a');
				} else { // 大写字母
					for (int j = 0; j < charCount[i]; j++)
						src[index++] = (char) ((i - 1) / 2 + 'A');
				}
			}
		}
	}
}
0%