By

文章目录
  1. 1. 题目
  2. 2. 解析1
  3. 3. 解析2
  4. 4. 参考

题目

函数将字符串中的字符'*'移到串的前部分,前面的非'*'字符后移,但不能改变非'*'字符的先 后顺序,函数返回串中字符'*'的数量。如原始串为:ab**cd**e*12,处理后为*****abcde12, 函数并返回值为 5。(要求使用尽量少的时间和辅助空间)

解析1

之前做过奇数偶数分离可能很快就想到使用快排分区的思想来解此题了：

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
/**
 * 使用快排分区 
 * 首位的左侧是* 右侧是非*
 * @param cs
 * @return
 */
public static int putxToHead(char[] cs)
{
	char k=cs[0];
	int i=0,j=cs.length-1;
	char c='*';
	while(i<j)
	{
		while(cs[j]!=c && i<j)
			j--;
		cs[i]=cs[j];
		
		while(cs[i]==c && i<j)
			i++;
		cs[j]=cs[i];
	}
	cs[i]=k;
	
	return (k==c)?i+1:i;//如果首位是* 则需要多加一个
}

马上进行测试：

1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args) {
	String str="ab**cd**e*12";
	char[] cs=new char[str.length()];
	for(int i=0;i<cs.length;i++)
		cs[i]=str.charAt(i);
	
	System.out.println(putxToHead(cs));
	for(int i=0;i<cs.length;i++)
		System.out.print(cs[i]);
	
}

看到的结果为

5
*****adceb12

咦，*的个数是计算出来的，但是字母的顺序却乱掉了，这是由于分区过程中快排是不考虑同一区里面两两的顺序

解析2

好吧，现在这种做法可以满足，使用两个指针，从后开始遍历，依次将当前非*的字符串给交换进来，这样就可以保证原来数据的顺序了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int putxToHead2(char[] cs)
{
	int i=cs.length-1,j=cs.length-1,count=0;
	char c='*';
	for(;i>=0;i--)
	{
		if(cs[i]!=c)
		{
			char t=cs[i];//进行交换  将非*按顺序往后排
			cs[i]=cs[j];
			cs[j]=t;
			j--;
			count++;//这里交换的次数就是代表非*的个数
		}
	}
	
	return cs.length-count;
	
}

使用上面的测试程序的结果为：

5
*****abcde12

恩，这样就对了，上述两种方法的复杂度同样都是O(n)

参考

  • July 微软面试100题 第88题

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权

文章目录
  1. 1. 题目
  2. 2. 解析1
  3. 3. 解析2
  4. 4. 参考