转换abc三种字母组合的字符串

2014-11-24 09:26:34 · 作者: · 浏览: 0
第1次写这个算法的思路:循环里,只要符合替换规则就直接进行替换,当没有符合的就结束替换行为, 这样提交到庞果,提示错误。。。
后发现原因是:替换顺序有先后 —— 没有按照我的想法 每次替换一组,再从头开始 找到符合规则 继续替换。。。。 弄了半小时
第2~ 次思路:必须要修复上面的bug,所以 就查出 哪个组合先出现,就先替换它。。。。。。转换思路有点慢,整了一个小时。。
我感觉我应该是解决了,结果庞果网 提示 缺少什么 符号。。。
 
import java.util.Arrays;  
  
  
/** 
 * 给定一个字符串,仅由a,b,c 3种小写字母组成。 
 * 当出现连续两个不同的字母时,你可以用另外一个字母替换它, 
 * 如 有ab或ba连续出现,你把它们替换为字母c; 
 * 有ac或ca连续出现时,你可以把它们替换为字母b; 
 * 有bc或cb 连续出现时,你可以把它们替换为字母a。 
 * 你可以不断反复按照这个规则进行替换,你的目标是使得最终结果所得到的字符串尽可能短,求最终结果的最短长度。  
 * @author szy 
 * 
 */  
public class Pongo {  
    public static void main(String[] args) {  
        System.out.println(minLength("bbbbcacbbabccabbbcabccaccbccaccbaaaabcbabaaacbbbbccabaccbcbccabacaaaccaaabbaaabcabacbabbbabababaabbabcbcbbcabbcccccbbbacbbaacbbabcaacaabbacabbabcccabaaccbbcacacbaccbcbaaabbbbcbcccaacbabccccccbbbacbbbb"));  
//      System.out.println(minLength("bbbbbbbbbbbcacbbabccabbcbaaabbacbbabccabbbcabccaccbccaccbaaaabcbabbbcbcccaacbabccccccbbbacbbbb"));  
        //System.out.println("bbbbbbbbbbbcacbbabccabbbcabccaccbccaccbaaaabcbabaaacbbbbccabaccbcbccabacaaaccaaabbaaabcabacbabbbabababaabbabcbcbbcabbcccccbbbacbbaacbbabcaacaabbacabbabcccabaaccbbcacacbaccbcbaaabbbbcbcccaacbabccccccbbbacbbbb".indexOf("ab"));  
          
    }  
      
    public static int minLength(String s) {  
        int len = s.length();  
        int ab = -1, ba = -1, ac = -1, ca = -1, bc = -1, cb = -1;  
        int []sortAry = new int[6];  
          
        int index = 0;  
        outer:  
        for (int i = 0; i < len; i++) {  
            System.out.println("每次进入循环转换的字符串:"  + s);  
              
            //各种类型的 开始出现的索引值  
            ab = s.indexOf("ab");  
            ba = s.indexOf("ba");  
            ac = s.indexOf("ac");  
            ca = s.indexOf("ca");  
            bc = s.indexOf("bc");  
            cb = s.indexOf("cb");  
            sortAry = new int[] {ab, ba, ac, ca, bc, cb}; //索引数组  
            Arrays.sort(sortAry); //索引数组 从小到大排序  
            System.out.println(Arrays.toString(sortAry));  
              
            //求出最小组合 出现的  大于等于0的索引值,如果都为-1,则退出;  
            for (int j = 0; j < 6; j++) {  
                if (sortAry[j] == -1 && j < 6 - 1) {   
                    continue;  
                } else if (sortAry[j] != -1) {  
                    index = j;  
                    break;  
                } else if (j == 6 - 1 && sortAry[j] == -1) {  
                    break outer;  
                }  
            }  
              
            //索引数组中 index 位置的元素值  == 什么组合,则使用这个组合来 替换  
            if (sortAry[index] == ab) {  
                s = s.replace("ab", "c");  
            } else if (sortAry[index] == ba) {  
                s = s.replace("ba", "c");  
            } else if (sortAry[index] == ac) {  
                s = s.replace("ac", "b");  
            } else if (sortAry[index] == ca) {  
                s = s.replace("ca", "b");  
            } else if (sortAry[index] == bc) {  
                s = s.replace("bc", "a");  
            } else if (sortAry[index] == cb) {  
                s = s.replace("cb", "a");  
            }  
              
            //替换完成后,从头开始循环  
            i = -1;  
            len = s.length();  
              
        }  
        System.out.println("最后的转成的字符串:" + s);  
        return s.length();  
    }  
}