Java排队吃饭问题

小灰灰 2022-08-01 06:10 188阅读 0赞

某公司员工到餐厅吃饭，吃饭要排队。因为公司的员工都是有素质的，让女同事排在队伍的前面。只要男同事发现自己的后面是一位女同事的话，该男同事将会与后面的女同事调换位置，调换位置需要1秒钟的时间。在同一时间可能会有多位男同事与后面女同事调换位置。我们需要求队伍调整完毕需要的总时间。M代表男同事，F代表女同事，排队顺序使用字符串，字符串的开头代表队伍的最前面。现在举个例子，假设初始的队伍是”MFMF“，那么第一秒中将有两位男同事与后面的女同事调换位置，此时的队伍变成”FMFM“，然后再接下来的一秒钟有一位男同事与后面女同事调换位置，现在队伍就变成”FFMM“，这样所有的女同事都排在男同事的前面，总时间用了2秒钟。（本题来源于互联网）

1.求出所有字串"MF"在队伍的位置

public static List<Integer> getIndex(String str) {
     		List<Integer> list = new ArrayList<Integer>();
     		for (int index = 0; index < str.length();) {
     			int j = str.indexOf("MF", index);
    			 if(j==-1)
     				break;
    			list.add(j);
     			index = j + 2;
    		}
    		 return list;
    	}

2.一次调换位置

public static String replace(String str, List<Integer> list) {
      		char[] c = str.toCharArray();
     		for (int i = 0; i < list.size(); i++) {
    			 c[list.get(i)] = 'F';
    			 c[list.get(i) + 1] = 'M';
    		}
    		return new String(c);
    	}

3.计算"MF"在队伍中出现的次数

public static Integer getCount(String str) {
    		Integer i = 0;
    		for (int index = 0; index < str.length();) {
    			
    			int j=str.indexOf("MF", index);
    			if(j==-1)
    				break;
    			i++;
    			index = j + 2;
    		}
    		return i;
    	}

4.递归求出队伍好调整需要的总时间

public static Integer getResult(String str) {
    		if (getCount(str) == 0) {
    			return 0;
    		}
    		return getResult(replace(str, getIndex(str)))+1;
    	}