讨论/技术交流/面试遇到的题目:设计一个函数,将“ab**cd*e**fgh*”,将*移到最前方,统计*数,并不能改变字母次序,时间空间复杂度尽可能小。/
面试遇到的题目:设计一个函数,将“ab**cd*e**fgh*”,将*移到最前方,统计*数,并不能改变字母次序,时间空间复杂度尽可能小。

我只想到时间复杂度O(n),空间复杂度O(n)的算法。

那如果要O(1)空间复杂度怎么处理?

代码

public class StarString {

	public static void main(String[] args) {
		String ori = "ab**cd*e**fgh*";
		StringBuilder sb = new StringBuilder();
		int res = StringHandler(ori, sb);
		System.out.print("* number is:"+res+"\n"+sb.toString());
	}
	
	public static int StringHandler(String ori,StringBuilder sb) {
		int cnt=0;
		String half ="";
		String star_half = "";
		
		for(int i=0;i<ori.length();i++) {
			if(ori.charAt(i)=='*') {
				star_half+=ori.charAt(i);
				cnt++;
			}
			else if(ori.charAt(i)>='a'&& ori.charAt(i)<='z'){
				half+=ori.charAt(i);
			}
		}
		sb.append(star_half);sb.append(half);
		return cnt;
	}

}

感谢各位佬!已解决~

思路

  1. 双指针,一个用于扫描,一个用于指定当前结果串位置
  2. 倒着扫描。

空间复杂度O(1)代码

public static void main(String[] args) {
		StringBuilder ori =new StringBuilder("ab**cd*e**fgh*");
		int index;					//工作指针
		int res = ori.length()-1;   //结果指针
		
		for(index=ori.length()-1;index>=0;index--) {
			if(ori.charAt(index)>='a'&&ori.charAt(index)<='z') {
				//移动字母到最后
				ori.replace(res, res+1, ori.substring(index, index+1));
				res--;
			}else if(ori.charAt(index)=='*')continue;
		}
		
		while(res>=0) {
			//填充*号
			ori.replace(res, res+1, "*");
			res--;
		}
		
		System.out.print(ori.toString());
	}	
共 3 个回复

双指针,倒过来处理

3

你从末尾开始,把每个字母往后面移动。剩下的全部填*

1

java里面string不能修改,新建一个stringbuilder或者转化为charArray是不是O(n)的复杂度了

1