emu in blogjava

現(xiàn)在不是流行pk嘛。

呵呵我是技術(shù)理想主義者，sean是實(shí)用主義者。

不欣賞gmail的ajax理由是沒有充分利用到xml帶來的好處，后臺必須為前臺的每一個(gè)請求度身定做一個(gè)返回的（超）文本或者腳本，因此也在后臺帶來了混合編程的問題。

如果實(shí)用純xml來做ajax，后臺開發(fā)人員可以非常大的被解放出來，更多的關(guān)注業(yè)務(wù)而不是表現(xiàn)，我認(rèn)為這是ajax帶來的另一個(gè)方面的好處。有興趣可以看看
http://qzone-search.qq.com/web/tag/tt_search.html
這個(gè)頁面就是接收標(biāo)準(zhǔn)的xml數(shù)據(jù)來顯示的。比如頁面中間的“最近更新”部分來自于http://qzone-search.qq.com/client/tag/newtags.xml ，而搜索功能的實(shí)現(xiàn)則依賴于ajax加載。而tencent公司正在開發(fā)中的tm版qzone干脆用ajax技術(shù)解析rss數(shù)據(jù)來生成頁面，這樣后臺開發(fā)人員只需要做一套提供rss訂閱的cgi就可以了。

但是在gmail這樣對跨瀏覽器要求比較高的場合上，這是很必然的選擇，跨瀏覽器的xml解析始終是一個(gè)麻煩的東東，我現(xiàn)在也還搞不定。打算過一段有時(shí)間了再好好研究，實(shí)在不行就用純javascript寫一個(gè)簡單一點(diǎn)的xml解析器，跨平臺行還更好一些呵呵。

jiniboy ： 本來打算hack掉gmail的腳本來分析gamil的來往數(shù)據(jù)的，這段時(shí)間忙沒有辦法去做，過陣子吧。至于更詳細(xì)的技術(shù)實(shí)現(xiàn)，我認(rèn)為沒有進(jìn)一步探究的價(jià)值了，我認(rèn)識的網(wǎng)友有超過一打都可以實(shí)現(xiàn)得出來。

todogoingmm ：沒有仔細(xì)研究過其中的差別，其實(shí)網(wǎng)上的資料很多了。我認(rèn)為主要差別是不同瀏覽器支持的不同版本的xml控件，但是我們盡量向下兼容，使用最通用的功能。

不如講講你是怎么定位到com.atlassian.license.DefaultLicense.class這個(gè)類上面的？

呵呵你也來啦。我再強(qiáng)能有莊老大強(qiáng)？更不要說現(xiàn)在坐在我隔壁位子的廖大哥了。

是嗎？你看到的具體是什么內(nèi)容呢？關(guān)于什么事件的？方舟子的哪些言論你覺得過了？

《上海晨報(bào)》網(wǎng)上搜不到它的網(wǎng)站噢，不是據(jù)說是華東“最有影響力”的報(bào)紙嘛，怎么好像網(wǎng)上沒什么影響力。

百度有進(jìn)步了，我認(rèn)錯(cuò)。
今天中午再搜百度 http://www.baidu.com/s?wd=%D7%DF%CF%F2%B6%F8%C1%A2%D6%AE%C4%EA+emu&cl=3 已經(jīng)有我的文章了，不過鏈接是指向blogjava首頁的。


同時(shí) yahoo上原來搜到的rss鏈接的結(jié)果也更新成我的文章的鏈接了，而且有兩個(gè)結(jié)果。
http://cn.websearch.yahoo.com/search/web_cn?stype=&p=%D7%DF%CF%F2%B6%F8%C1%A2%D6%AE%C4%EA+emu&scch=on&ei=gb

這次兩個(gè)搜索引擎更新這么快顯然和我昨天新發(fā)了一篇 Gmail 使用的AJAX技術(shù)研究 在blogjava首頁上。

而備受我推崇的google今天表現(xiàn)就讓人失望了，今天中午還是沒有鏈接到我的文章。
http://www.google.com/search?num=100&hl=zh-CN&newwindow=1&q=emu+%E8%B5%B0%E5%90%91%E8%80%8C%E7%AB%8B%E4%B9%8B%E5%B9%B4&btnG=%E6%90%9C%E7%B4%A2&lr=

哈哈你也在盯著google啊

何必繞這么大一圈呢？還要包裝一個(gè)exe文件。javaservice其實(shí)沒有那么難搞的。

我用javaservice把james安裝成服務(wù)之要寫一句：

JavaService.exe -install "James" {JAVA_HOME}\jre\bin\server\jvm.dll -Djava.class.path=C:\james-2.2.0\bin\phoenix-loader.jar; -Djava.ext.dirs=C:\james-2.2.0\lib -start org.apache.avalon.phoenix.launcher.Main -err C:\james-2.2.0\james_error.log

卸載也只要一句

JavaService.exe -uninstall "James"

javaservice自帶的文檔和示范都很詳細(xì)的，現(xiàn)在中文資料應(yīng)該也不難搜到了。

搜了一下，你的文章轉(zhuǎn)載的地方很多呀。看來現(xiàn)在這方面的中文資料真的是太缺乏了。
可惜很多網(wǎng)站都沒有給出你的原文鏈接。以后寫技術(shù)文章也寫一個(gè)版權(quán)聲明上去好了。

哈哈你要寫就趕快哈，我也在醞釀中。

document.getElementById(currentPos).innerHTML = http_request.responseText;

不如叫AJAH算了。如果你知道我在說什么，我想你會(huì)同意我的說法的。

呵呵不用看了，我天天在內(nèi)部試用新版的foxmail呢。

引用文章不給原文連接不好。我昨天就在donews上面找這篇的原文了，不過找不到。原文連接 http://home.donews.com/donews/article/8/84823.html 早已被刪除。

謠言散播出來了以后源出處卻已毀尸滅跡死無對證，這個(gè)槍手手段果然高明?，F(xiàn)在網(wǎng)上到處都有轉(zhuǎn)這篇文章的，反正誰也不用負(fù)責(zé)任。

我們還是來看看文章本身吧。文章的前面一大部分都是舊內(nèi)容了，作者顯然相信危言聳聽一萬遍就可以變成真理，值得一看的只有后面最新的幾句：

---------------------------------------------------------------------------
我想肯定是QQ安全中心(和金山毒霸合作搞的)拿我們用戶當(dāng)試驗(yàn)品,而騰訊公司為了逃避責(zé)任,力圖欺騙QQ大眾不懂技術(shù),用"動(dòng)態(tài)文件名"來蒙我們.沒有一點(diǎn)誠意!

同時(shí)我警告一些殺毒軟件公司不要干一些違背職業(yè)道德的事,會(huì)遭到大眾的漫罵的.

---------------------------------------------------------------------------

槍手的這個(gè)“肯定”有任何依據(jù)嗎？他憑什么這么肯定呢？
槍手號稱“我已經(jīng)把這病毒程序提交給了諾頓、卡巴司機(jī)等多個(gè)病毒廠商”，這么多天過去了，有否哪一個(gè)殺毒軟件廠商（這個(gè)槍手居然管人家叫“病毒廠商”呵呵）發(fā)布了相關(guān)的安全公告呢？按照槍手的意思，騰訊不但“和金山毒霸合作搞的”，而且還和諸多病毒廠商共同策劃了這樣一個(gè)病毒散播事件，大家可以想想有沒有這樣的可能性呢？

木秀于林，風(fēng)必催之。中國一共才做出來幾個(gè)可以和微軟較勁的軟件，幾個(gè)IM卻居然要在這里窩里斗，讓人心寒。

>>這個(gè)好像不是groovy的問題
呵呵就象朋友經(jīng)常批評的，這是人品問題。我覺得這個(gè)問題上groovy沒有提供一個(gè)簡單的解決方案。

>>類似的東西，偶屢試不爽
是指的什么？import嗎？怎么做呢？

>>前面那個(gè)Dog.groovy并不需要編譯
是指的運(yùn)行不需要編譯還是被其他groovy腳本import之前不需要編譯呢？

不但腳本不是用來“做計(jì)算密集型的東西”的，java也不是c#也不是。正兒八經(jīng)說，高級語言都不是，匯編語言也只是勉強(qiáng)算是。不是用來“做計(jì)算密集型的東西”并非就可以把運(yùn)行效率完全丟開一邊了。我們犧牲一些運(yùn)算效率來換開發(fā)效率是可以接受的，但是犧牲的太多了就不得不要斟酌一下了。

秋水無恨解 http://m.tkk7.com/emu/category/2769.html 也是用的腳本呢。

>但對3721，我覺得確實(shí)不能原諒
理解理解，當(dāng)年我也是不勝其煩。
這次國慶回家，發(fā)現(xiàn)家里的計(jì)算機(jī)的主頁也是hao123呵呵。我單位里面用的電腦的主頁是加加在線，沒有辦法，只要一啟動(dòng)拼音加加2它就幫我重設(shè)一變，我干脆把hosts文件改了，把加加在線映射到我喜歡的地址上，由它去改吧。

其實(shí)這個(gè)事情國慶前就已經(jīng)辟謠了，病毒廠商和專家的看法和評論在網(wǎng)上也很容易看到。幾個(gè)IM廠商和門戶網(wǎng)站收買槍手造謠中傷，平常已極，朋奕何苦摻和？

動(dòng)態(tài)文件名、自我隱藏和自我保護(hù)是對付木馬的無奈之舉，而且對用戶沒有造成傷害和不便，卸載也不象當(dāng)年的3721那么困難（3721后來其實(shí)也改正了，何必念念不忘當(dāng)年的舊帳呢？），“除了破壞數(shù)據(jù)之外所有病毒的特性都有了”言重了吧？它造成機(jī)器變慢？占用額外的資源和帶寬？有傳染性？

至于實(shí)名制，那是政策要求。上個(gè)月的南方周末有過評論了。

呵呵，我現(xiàn)在不做java了，只能在js上干這些事情了。

JK手腳真快，一下發(fā)現(xiàn)了兩個(gè)bug：

1 從一個(gè)textbox把文字拖放到另一個(gè)textbox的情況下不能undo，因?yàn)閕e沒有觸發(fā)兩個(gè)onchange事件給我，不能全怪我啊。

2 修改值后我的undo功能和IE自帶的ctrl-z有沖突，呵呵。

Robert Frost顯然不明白世界是由懶人創(chuàng)造的。

幸運(yùn)的人都是相似的，不幸的人各有各的不幸啊！

相信我，在課本上編造這個(gè)謊言的人自己根本就不相信。

要不怎么說多事之秋呢

1 防民之口，甚于防川

2 水至清則無魚

3 政府和網(wǎng)民意見相左的時(shí)候，ISP成了夾心餅，偏哪邊都不對，最好悶聲發(fā)大財(cái)。

好文章，值得一看！

suite可以通過自嵌套來實(shí)現(xiàn)分層次遞降的測試每個(gè)包，用可變參數(shù)來管理的話能實(shí)現(xiàn)同樣的目的嗎？

真的是好久了哦。我到深圳來了，忙完了聯(lián)系。

原來ｆｏｘｍａｉｌ在３月份被收購了，消息真是遲鈍。

沒有發(fā)現(xiàn)現(xiàn)成的IDE哦，其實(shí)用記事本也可以開放阿，我是用ｅｄｉｔｐｌｕｓ。ｊｃｒｅａｔｏｒ好像不支持ｊａｖａ之外的語言吧？沒用過。

Office ??

這是誰?。啃c來？甄繼業(yè)？

遺憾的很，我這個(gè)答案沒有通過google的系統(tǒng)測試。

遺憾的很，我這個(gè)答案沒有通過google的系統(tǒng)測試。

敗給這一組數(shù)據(jù)了：
{"8 0 7 51", "47 22 26 30 46", "41 4 9 10 20","33 5 28 39 42", "31 12 56 57", "13 6 17 24 27 36 54","58 32 34 45", "19 2", "3 11 15 25 38 48", "23 1 18 21 29 44 55","40 16 35 43 49 52 53 59", "37 14 50"}
期待結(jié)果：50

這是誰??？回復(fù)錯(cuò)地方了？

google的比賽誰都可以參加啊，為什么一定要來中國辦呢？考場里面也見到不少中國人。

3.11版過時(shí)很久啦！
http://m.tkk7.com/emu/archive/2005/08/09/9653.html

居然系統(tǒng)測試失敗
Failed system test 10 on the 375-point problem with args: [8, 1, 1]
EXPECTED: 96
RECEIVED: 48

Failed system test 5 on the 375-point problem with args: [50, 50, 50]
EXPECTED: 9200
RECEIVED: 3360

這個(gè)題基本上就是我以前寫的 java版本的escape和unescape函數(shù) 的簡化版了。
public class URLParser {
    public static void main(String[] args)
    {
        URLParser u = new URLParser();
            System.out.println(u.parse("%48%65%6C%6C%6F%20%57%6F%72%6C%64%21"));
    }
    public String parse(String url){
        StringBuffer tmp = new StringBuffer();
        tmp.ensureCapacity(url.length());
        int lastPos = 0, pos = 0;
        char ch;
        while (lastPos < url.length()) {
            pos = url.indexOf("%", lastPos);
            if (pos == lastPos) {
    ch = (char) Integer.parseInt(url.substring(pos + 1, pos + 3),16);
    tmp.append(ch);
    lastPos = pos + 3;
            } else {
                if (pos == -1) {
                    tmp.append(url.substring(lastPos));
                    lastPos = url.length();
                } else {
                    tmp.append(url.substring(lastPos, pos));
                    lastPos = pos;
                }
            }
        }
        return tmp.toString();
    }
}

public class NewStation {
    public static void main(String[] args) {
        NewStation ns = new NewStation(); ;
        String[] grid = {"2312",
 "0233"};
        String[] stations = {"1 1", "1 1"};
        System.out.println(ns.location(grid, stations));
    }

    public String location(String[] grid, String[] stations) {
        int[][] iGrid = new int[grid.length][grid[0].length()];
        for (int i = 0; i < grid.length; i++) {
            String s = grid[i];
            for (int j = 0; j < s.length(); j++) {
                iGrid[i][j] = s.charAt(j) - 48;
            }
        }
        boolean[][] iStations = new boolean[iGrid.length][iGrid[0].length];
        for (int i = 0; i < stations.length; i++) {
            String[] s = stations[i].split(" ");
            iStations[Integer.parseInt(s[0], 10)][Integer.parseInt(s[1], 10)] = true;
        }
        int minDistanceCount = count(iGrid, iStations);
        String result = "";
        for (int x = 0; x < iGrid.length; x++)
            for (int y = 0; y < iGrid[0].length; y++) {
                int c = count(iGrid, iStations, x, y);
                if (c < minDistanceCount) {
                    result = x + " " + y;
                   minDistanceCount = c;
                }
            }
        return result;
    }

    private int count(int[][] iGrid, boolean[][] iStations) {
        int result = 0;
        for (int i = 0; i < iGrid.length; i++)
            for (int j = 0; j < iGrid[0].length; j++)
                if (!iStations[i][j] && iGrid[i][j] > 0) {
                    int minCount = 99999;
                    for (int x = 0; x < iGrid.length; x++)
                        for (int y = 0; y < iGrid[0].length; y++)
                            if (iStations[x][y] &&
                                (Math.abs(x - i) + Math.abs(y - j) * iGrid[i][j]) <
                                minCount)
                                minCount = Math.abs(x - i) +
                                           Math.abs(y - j) * iGrid[i][j];
                    result += minCount;
                }
        return result;
    }

    private int count(int[][] iGrid, boolean[][] iStations, int x, int y) {
        boolean[][] tmpStations  = new boolean[iStations.length][iStations[0].length];
        for (int i=0;i<iStations.length;i++)
            for (int j=0;j<iStations[0].length;j++)
                tmpStations[i][j]=(x==i&&y==j)?(true):(iStations[i][j]);
        return count(iGrid, tmpStations);

    }

}

import java.util.*;
public class SalesFigures {
   
    public static void main(String[] args)
    {
        String[] sales =   {"GEORGE 999 PETS"};
        // CLIENT_ID CNT_1 PRODUCT_1 CNT_2 PRODUCT_2 ...
        String client = "BOB";
        String product = "SHOE";
        System.out.println(new SalesFigures().getCount(sales,client,product));

    }

    public int getCount(String[] sales, String client, String product){
        HashMap salesHsmp = new HashMap();
        for (int i=0;i<sales.length;i++){
            String[] saleDetail = sales[i].split(" ");
            String clientName = saleDetail[0];
            if (!salesHsmp.containsKey(clientName)) salesHsmp.put(clientName,new HashMap());
            HashMap clientHsmp = (HashMap)salesHsmp.get(clientName);
            for (int j=1;j<saleDetail.length;j+=2){
                int unit = Integer.parseInt(saleDetail[j],10);
                String tmpProduct = saleDetail[j+1];
                if (clientHsmp.containsKey(tmpProduct)){
                    Integer productUnit = (Integer)clientHsmp.get(tmpProduct);
                    unit += productUnit.intValue();
                }
                clientHsmp.put(tmpProduct,new Integer(unit));
            }
        }
        HashMap clientHsmp = (HashMap)salesHsmp.get(client);
        if (clientHsmp == null) return 0;
        Integer unitInteger = (Integer)clientHsmp.get(product);
        return unitInteger==null?0:unitInteger.intValue();
    }

   
}

這也太容易了吧？


import java.util.*;

public class SongFilter {
    public static void main(String[] args) {
        String[] collection, filterInfo, result;
        SongFilter sf = new SongFilter();
        collection = new String[] {"jazz-joe pass-virtuoso-cherokee",
                     "rock-led zeppelin-ii-lemon song",
                     "country-dwight yoakam-long way home-things change",
                     "metal-iron maiden-powerslave-aces high",
                     "pop-supremes-more hits-ask any girl",
                     "rock-faith no more-angel dust-rv",
                     "jazz-chuck mangione-feels so good-feels so good",
                     "rock-van halen-ii-spanish fly"};
        filterInfo = new String[] {"genre=rock", "album=ii"};
        result = sf.filter(collection, filterInfo);
        for (int i = 0; i < result.length; i++)
            System.out.println(result[i]);
    }

    String[] filterPrefix = new String[] {"genre=", "artist=", "album=",
                            "song="};
    int filterPrefixLength = filterPrefix.length;
    public String[] filter(String[] collection, String[] filterInfo) {
        String[] filter = new String[filterPrefixLength];
        for (int i = 0; i < filterInfo.length; i++)
            for (int j = 0; j < filterPrefixLength; j++)
                if (filterInfo[i].startsWith(filterPrefix[j]))
                    if (filter[j] == null)
                        filter[j] = filterInfo[i].substring(filterPrefix[j].
                                length());
                    else if (!filter[j].equals(filterInfo[i].substring(
                            filterPrefix[j].length())))
                        return new String[0];
        ArrayList tmpResult = new ArrayList();
        for (int i = 0; i < collection.length; i++) {
            String[] collectionDetail = collection[i].split("-"); //genre-artist-album-song
            boolean match = true;
            for (int j = 0; j < filterPrefixLength; j++)
                if (filter[j] != null &&
                    !collectionDetail[j].equals(filter[j]))
                    match = false;
            if (match)
                tmpResult.add(collection[i]);
        }
        String[] result = new String[tmpResult.size()];
        tmpResult.toArray(result);
        return result;
    }
}

import java.util.*;
public class ImageLayers {
    public static void main(String[] args) {
        String[] macro = new String[] {"OPEN sky",
                         "OPEN clouds",
                         "OPEN ground",
                         "MERGE 0-1",
                         "OPEN grass",
                         "MERGE 0-2",
                         "OPEN trees",
                         "OPEN leaves",
                         "OPEN birds",
                         "MERGE 1-2",
                         "MERGE 0-1"}
;
        ImageLayers il = new ImageLayers();
        String[] contents = il.contents(macro);
        for (int i=0;i<contents.length;i++)
            System.out.println(contents[i]);
                        

    }

    public String[] contents(String[] macro){
        ArrayList layers = new ArrayList();
        for (int i=0;i<macro.length;i++){
            String command = macro[i];
            if (command.startsWith("OPEN")){
                ArrayList layer = new ArrayList();
                layer.add(command.split(" ")[1]);
                layers.add(layer);
            }
            else if (command.startsWith("MERGE")){
                String[] l = command.split(" ")[1].split("-");
                int layer1 = Integer.parseInt(l[0],10);
                int layer2 = Integer.parseInt(l[1],10);
                ArrayList tmpLayers = (ArrayList)layers.get(layer1);                
                for (int j=layer2;j>layer1;j--)
                    tmpLayers.addAll((ArrayList)layers.remove(j));
            }
        }
        String[] result = new String[layers.size()];
        for (int i=0;i<result.length;i++){
            Object[] stAr = ((ArrayList)layers.get(i)).toArray();
            Arrays.sort(stAr);
            String s =  Arrays.toString(stAr).replace(',',' ');
            result[i] = s.substring(1,s.length()-1);
        }

        return result;
    }

}

public class DiskDefrag {

    public static void main(String[] args) {
        String[] disk = new String[] {"3 4 5 6 8 9 10", "17 16 15"};
        int size = 20;
        assertEquals(new DiskDefrag().minMoves(disk, size), 5);

        disk = new String[] {"0 1 2 3 5 4 6 7 8 9"};
        size = 10;
        assertEquals(new DiskDefrag().minMoves(disk, size), 2);

        disk = new String[] {"1 3 5 7", "0 2 4 8", "6 9"};
        size = 100;
        assertEquals(new DiskDefrag().minMoves(disk, size), 7);

        disk = new String[] {"31 32 30","27 28 29", "13 24 5",  "19 10 21", "12 3 34",
               "15 6 17", "18 9 0","16 7 8","11 22 23","20 1 2","4 25 26","33 14 35"};
        size = 38;
//        assertEquals(new DiskDefrag().minMoves(disk, size), 17);

        disk = new String[] {"8 0 7 51", "47 22 26 30 46", "41 4 9 10 20",
               "33 5 28 39 42", "31 12 56 57", "13 6 17 24 27 36 54",
               "58 32 34 45", "19 2", "3 11 15 25 38 48", "23 1 18 21 29 44 55",
               "40 16 35 43 49 52 53 59", "37 14 50"};
        size = 60;
//        assertEquals(new DiskDefrag().minMoves(disk, size), 50);
        System.out.println("All passed!");

    }

    private static void assertEquals(int a, int b) {
        if (a != b)
            throw new RuntimeException("assert failed!! Expected " + b +
                                       " but got " + a);
    }

    private int fileCount = 0;
    private int secCount, diskSize;
    private Object[] srcDiskElms;
    private int[][] destDiskElms;
    int maxSuperpositionCount = 0;
    public int minMoves(String[] disk, int size) {
        fileCount = disk.length;
        diskSize = size;
        // 整理String數(shù)據(jù)建立int數(shù)組
        srcDiskElms = getDiskElms(disk);
        // 計(jì)算全部文件占用的扇區(qū)數(shù)
        for (int i = 0; i < fileCount; i++)
            secCount += ((int[]) srcDiskElms[i]).length;
        destDiskElms = new int[fileCount][4];
        //[0]==文件在srcDiskElms中的編號
        //[1]==文件的起始位置
        //[2]==文件的最后一個(gè)扇區(qū)的位置+1
        //[3]==文件和原始狀態(tài)的重合區(qū)塊計(jì)數(shù)

        getMaxSuperpositionCount(0, 0, 0, 0);
        return secCount - maxSuperpositionCount;
    }

    private void getMaxSuperpositionCount(int n, int tmpSecCount,
                                          int tmpSuperpositionCount,
                                          int tmpMoveCount) {
        // 找重合程度最高的文件存儲方式
        if (n < fileCount) {
            for (int i = 0; i < fileCount; i++) {
                // 找到一個(gè)還沒有放進(jìn)destDiskElms的文件（的編號）
                int k = 0;
                for (; k < n; k++)
                    if (destDiskElms[k][0] == i)
                        k = fileCount + 1;
                if (k < fileCount) {
                    int[] srcFile = (int[]) srcDiskElms[i];
                    destDiskElms[n][0] = i;
                    int fileSize = srcFile.length;
                    int lastFileEndOffset = (n == 0) ? 0 :
                                            destDiskElms[n - 1][2]; //上一個(gè)文件結(jié)束的位置+1。
                    int maxOffset = diskSize - secCount + tmpSecCount; //文件起始位置不可能超過這個(gè)位置
                    for (int fileOffset = lastFileEndOffset;
                                          fileOffset <= maxOffset; fileOffset++) {
                        destDiskElms[n][1] = fileOffset;
                        destDiskElms[n][2] = fileOffset + fileSize; //文件的最后一個(gè)扇區(qū)的位置+1
                        int superpositionCount = 0;
                        for (int j = 0; j < fileSize; j++)
                            if (srcFile[j] == fileOffset + j)
                                superpositionCount++;
                        int moveCount = fileSize - superpositionCount;
                        if (tmpMoveCount + moveCount<secCount - maxSuperpositionCount){
                            destDiskElms[n][3] = superpositionCount;
                            getMaxSuperpositionCount(n + 1,
                                    tmpSecCount + fileSize,
                                    tmpSuperpositionCount +
                                    superpositionCount,
                                    tmpMoveCount + moveCount);
                        }
                    }
                }
            }
        } else {
            int superpositionCount = 0;
            for (int i = 0; i < n; i++)
                superpositionCount += destDiskElms[i][3];
            if (maxSuperpositionCount < superpositionCount)
                maxSuperpositionCount = superpositionCount;

        }

    }

    private Object[] getDiskElms(String[] disk) {
        Object[] result = new Object[disk.length];
        for (int i = 0; i < disk.length; i++) {
            String[] d = disk[i].split(" ");
            int[] ar = new int[d.length];
            for (int j = 0; j < d.length; j++)
                ar[j] = Integer.parseInt(d[j], 10);
            result[i] = ar;
        }
        return result;
    }

}

EP和UE也有g(shù)roovy語法支持的：
http://m.tkk7.com/emu/archive/2005/05/18/4781.html

8月10號jira又發(fā)布了3.3版。releasenotes在這里：

http://confluence.atlassian.com/display/JIRA/JIRA+3.3+Release+Notes

檢討了上面的A*算法，其中存在著兩個(gè)基本錯(cuò)誤：
每擴(kuò)展一個(gè)節(jié)點(diǎn)就把它從隊(duì)列中刪掉，造成下次構(gòu)造出相同的狀態(tài)的時(shí)候沒有辦法知道。
用toString來判斷兩個(gè)狀態(tài)是否相同，但是toString里面除了基本的sector數(shù)據(jù)之外還有評分的數(shù)據(jù)，所以不同情況下生成的相同狀態(tài)會(huì)被判斷成不同狀態(tài)。

修正后的A*算法，可以計(jì)算出一個(gè)比較合理和可行的整理過程，但是沒有辦法保證找到最好的一種（擴(kuò)展過多的可能性會(huì)造成運(yùn)算超時(shí)）。

理論上說只要修改評估策略（countStatus函數(shù)）就可以保證算法總是朝正確的方向擴(kuò)張，但是創(chuàng)造一個(gè)合理的評估函數(shù)本身就是一個(gè)難題。

也許A*算法根本就不是這道題的正解。




import java.util.*;

// 節(jié)點(diǎn)增長方式：
// 1、如果內(nèi)存區(qū)域?yàn)榭?，讀取任一塊數(shù)據(jù)
// 2、如果內(nèi)存區(qū)域非空，寫一個(gè)內(nèi)存塊到任意一個(gè)空白的位置

public class DiskDefrag {
public static void main(String[] args) {

String[] disk = new String[] {"3 4 5 6 8 9 10", "17 16 15"};
int size = 20;
assertEquals(new DiskDefrag().minMoves(disk, size), 5);

disk = new String[] {"1 2 3 5 4 6 7 8"};
size = 10;
assertEquals(new DiskDefrag().minMoves(disk, size), 2);

disk = new String[] {"1 3 5 7", "0 2 4 8", "6 9"};
size = 100;
assertEquals(new DiskDefrag().minMoves(disk, size), 8);

System.out.println("All passed!");

}

private static int countRate = 1000; //為了方便處理評分，把評分值放大一個(gè)倍數(shù)后取整。
private static int memorySector = 2; //內(nèi)存可存放的數(shù)據(jù)
private static void assertEquals(int a, int b) {
if (a != b)
throw new RuntimeException("assert failed!! Expected " + b +
" but got " + a);
}

public int minMoves(String[] disk, int size) {
DiskStatus d = new DiskStatus(disk, size);
// System.out.println(d.countSecotrOrder());
int countAim = disk.length * countRate;
if (countAim == d.countSecotrOrder())
return 0;
ArrayList diskStatus = new ArrayList();
diskStatus.add(d);
while (true) {
d = getMostHopefulStatus(diskStatus);
// System.out.println(d);
if (d.countSecotrOrder() == countAim) {
int result = d.operationCount / 2;
System.out.print("-----------------------------------------\n" +
d);
while (d.parentStatus != null) {
d = d.parentStatus;
System.out.print("\n" + d);
}
return result;
}
d.expanded = true;
for (int i = 0; i < d.files.length; i++) {
int[] file = (int[]) d.files[i];
for (int j = 0; j < file.length; j++) {
if (file[j] >= 0) {
if (d.memoryAvalible > 0) {
DiskStatus newStatus = new DiskStatus(d, i, j, -10);
if (!checkExist(diskStatus, newStatus))
diskStatus.add(newStatus);
}
} else {
for (int k = 0; k < d.sectorFill.length; k++) {
if (!d.sectorFill[k]) {
DiskStatus newStatus = new DiskStatus(d, i, j,
k);
if (!checkExist(diskStatus, newStatus))
diskStatus.add(newStatus);
}
}
}
}
}
}
}

private boolean checkExist(ArrayList statusList, DiskStatus status) {
String map = status.getDiskMap();
for (int i = 0, n = statusList.size(); i < n; i++) {
if (map.equals(((DiskStatus) statusList.get(i)).getDiskMap()))
return true;
}
return false;
}

private DiskStatus getMostHopefulStatus(ArrayList list) {
// System.out.println(list);
DiskStatus result = null;

for (int i = 0, n = list.size(); i < n; i++) {
DiskStatus tmpStatus = (DiskStatus) list.get(i);
if (!tmpStatus.expanded) {
if (result == null) {
result = tmpStatus;
} else {
if (result.countStatus() < tmpStatus.countStatus())
result = tmpStatus;
}
}
}
return result;
}

class DiskStatus {
DiskStatus parentStatus;
boolean expanded = false;
Object[] files;
boolean[] sectorFill;
int order = -1;
int operationCount = 0; //操作次數(shù)記數(shù)
int memoryAvalible = memorySector;
public DiskStatus(DiskStatus d, int fileIndex, int sectorIndex,
int newSector) {
parentStatus = d;
// d.expanded = true;
files = d.files.clone();
sectorFill = d.sectorFill.clone();
int[] file = ((int[]) files[fileIndex]).clone();
memoryAvalible = d.memoryAvalible;
if (file[sectorIndex] >= 0)
sectorFill[file[sectorIndex]] = false;
else
memoryAvalible++; //轉(zhuǎn)移一個(gè)塊到硬盤上
file[sectorIndex] = newSector;
files[fileIndex] = file;
if (newSector >= 0)
sectorFill[newSector] = true;
else
memoryAvalible--; //轉(zhuǎn)移一個(gè)塊到內(nèi)存上
order = -1;
operationCount = d.operationCount + 1;
}

public DiskStatus(String[] disk, int size) {
files = new Object[disk.length];
sectorFill = new boolean[size];
for (int i = 0; i < disk.length; i++) {
String[] tmp = disk[i].split(" ");
int[] fileSectors = new int[tmp.length];
for (int j = 0; j < tmp.length; j++) {
int k = Integer.parseInt(tmp[j], 10);
fileSectors[j] = k;
sectorFill[k] = true;
}
files[i] = fileSectors;
}
}

public int countSecotrOrder() {
if (files == null)
return -1;
if (order >= 0)
return order;
order = 0;
for (int i = 0; i < files.length; i++) {
int[] fileSectors = (int[]) files[i];
int lastSector = fileSectors[0];
int fileOrder = 0, orderedSecCount = 0;
for (int j = 1; j < fileSectors.length; j++) {
int sector = fileSectors[j];
if (sector == lastSector + 1)
orderedSecCount++;
else
orderedSecCount = 0;
if (orderedSecCount > fileOrder)
fileOrder = orderedSecCount;
//統(tǒng)計(jì)最多的連續(xù)塊作為這個(gè)文件順序性的評估標(biāo)準(zhǔn)
lastSector = sector;
}
order += (fileOrder + 1) * countRate / fileSectors.length;
// 順序度的評估值，每個(gè)文件最高countRate分，即整理完成。order=文件個(gè)數(shù)×countRate時(shí)全部排序完成。
}
return order;
}

public int countStatus() {
return countSecotrOrder() - operationCount * 20;
}


public String toString() {
StringBuffer result = new StringBuffer();
for (int i = 0; i < files.length; i++) {
int[] file = (int[]) files[i];
for (int j = 0; j < file.length; j++) {
if (j > 0)
result.append('\t');
if (file[j] >= 0)
result.append(file[j]);
else
result.append('*');
}
result.append("\t\t");
}
result.append('\n');
// result.append("(order:").append(countSecotrOrder())
// .append(")(count:").append(countStatus())
// .append(")(operation:").append(operationCount).append(')')
// .append(
// '\n');
return result.toString();
}

private String diskMap = null;
private String getDiskMap() {
if (diskMap != null)
return diskMap;
StringBuffer map = new StringBuffer();
for (int i = 0; i < files.length; i++) {
int[] file = (int[]) files[i];
for (int j = 0; j < file.length; j++) {
map.append(file[j]).append(',');
}
map.append(';');
}
diskMap = map.toString();
return diskMap;
}
}
}

http://befresh.bjug.org/content/view/27/5/

手術(shù)情況
作者： Administrator
2005-08-15
手術(shù)情況還算順利，他妹妹上周末已出院。

王俊還在住院觀察，需要在這周才能知道更多情況。
我們的募捐活動(dòng)將在這周得知確切結(jié)果后結(jié)束。

感謝所有的好心人們。

在8月6日活動(dòng)上，王俊通過電話向大家介紹了自己的情況，并感謝所有人的幫助。

用A*算法來擴(kuò)展?fàn)顟B(tài)樹，當(dāng)問題稍微復(fù)雜一點(diǎn)的時(shí)候狀態(tài)樹生長的太厲害，沒有辦法在規(guī)定時(shí)間內(nèi)找到解，失敗！

import java.util.*;

// 節(jié)點(diǎn)增長方式：
// 1、如果內(nèi)存區(qū)域?yàn)榭?，讀取任一塊數(shù)據(jù)
// 2、如果內(nèi)存區(qū)域非空，寫一個(gè)內(nèi)存塊到任意一個(gè)空白的位置

public class DiskDefrag {
public static void main(String[] args) {
String[]disk = new String[] {"3 4 5 6 8 9 10", "17 16 15"};
int size = 20;
assertEquals(new DiskDefrag().minMoves(disk, size), 5);

disk = new String[] {"1 2 3 5 4 6 7 8"};
size = 10;
assertEquals(new DiskDefrag().minMoves(disk, size), 2);
/*
disk = new String[] {"1 3 5 7","0 2 4 8","6 9"};
size = 100;
assertEquals(new DiskDefrag().minMoves(disk, size), 7);
*/
System.out.println("All passed!");

}

private static int countRate = 100; //為了方便處理評分，把評分值放大一個(gè)倍數(shù)后取整。
private static int memorySector = 2; //內(nèi)存可存放的數(shù)據(jù)
private static void assertEquals(int a, int b) {
if (a != b)
throw new RuntimeException("assert failed!! Expected " + b +
" but got " + a);
}

public int minMoves(String[] disk, int size) {
DiskStatus d = new DiskStatus(disk, size);
// System.out.println(d.countSecotrOrder());
int countAim = disk.length * countRate;
if (countAim == d.countSecotrOrder())
return 0;
ArrayList diskStatus = new ArrayList();
diskStatus.add(d);
while (true) {
d = getMostHopefulStatus(diskStatus);
System.out.println(d);
if (d.countSecotrOrder() == countAim)
return d.operationCount / 2;
diskStatus.remove(d);
for (int i = 0; i < d.files.length; i++) {
int[] file = (int[]) d.files[i];
for (int j = 0; j < file.length; j++) {
if (file[j] >= 0) {
if (d.memoryAvalible > 0) {
DiskStatus newStatus = new DiskStatus(d, i, j, -1);
if (!checkExist(diskStatus, newStatus))
diskStatus.add(newStatus);
}
} else {
for (int k = 0; k < d.sectorFill.length; k++) {
if (!d.sectorFill[k]) {
DiskStatus newStatus = new DiskStatus(d, i, j,
k);
if (!checkExist(diskStatus, newStatus))
diskStatus.add(newStatus);
}
}
}
}
}
}
}

private boolean checkExist(ArrayList statusList, DiskStatus status) {
String st = status.toString();
for (int i = 0, n = statusList.size(); i < n; i++) {
if (st.endsWith(statusList.get(i).toString()))
return true;
}
return false;
}

private DiskStatus getMostHopefulStatus(ArrayList list) {
// System.out.println(list);
DiskStatus result = (DiskStatus) list.get(0);
for (int i = 1, n = list.size(); i < n; i++) {
DiskStatus tmpStatus = (DiskStatus) list.get(i);
if (result.countStatus() < tmpStatus.countStatus())
result = tmpStatus;
}
return result;
}

class DiskStatus {
// DiskStatus parentStatus;
// boolean expanded = false;
Object[] files;
boolean[] sectorFill;
int order = -1;
int operationCount = 0; //操作次數(shù)記數(shù)
int memoryAvalible = memorySector;
public DiskStatus(DiskStatus d, int fileIndex, int sectorIndex,
int newSector) {
// parentStatus = d;
// d.expanded = true;
files = d.files.clone();
sectorFill = d.sectorFill.clone();
int[] file = ((int[]) files[fileIndex]).clone();
memoryAvalible = d.memoryAvalible;
if (file[sectorIndex] >= 0)
sectorFill[file[sectorIndex]] = false;
else
memoryAvalible++; //轉(zhuǎn)移一個(gè)塊到硬盤上
file[sectorIndex] = newSector;
files[fileIndex] = file;
if (newSector >= 0)
sectorFill[newSector] = true;
else
memoryAvalible--; //轉(zhuǎn)移一個(gè)塊到內(nèi)存上
order = -1;
operationCount = d.operationCount + 1;
}

public DiskStatus(String[] disk, int size) {
files = new Object[disk.length];
sectorFill = new boolean[size];
for (int i = 0; i < disk.length; i++) {
String[] tmp = disk[i].split(" ");
int[] fileSectors = new int[tmp.length];
for (int j = 0; j < tmp.length; j++) {
int k = Integer.parseInt(tmp[j], 10);
fileSectors[j] = k;
sectorFill[k] = true;
}
files[i] = fileSectors;
}
}

public int countSecotrOrder() {
if (files == null)
return -1;
if (order >= 0)
return order;
order = 0;
for (int i = 0; i < files.length; i++) {
int[] fileSectors = (int[]) files[i];
int lastSector = fileSectors[0];
int fileOrder = 0, orderedSecCount = 0;
for (int j = 1; j < fileSectors.length; j++) {
int sector = fileSectors[j];
if (sector == lastSector + 1)
orderedSecCount++;
else
orderedSecCount = 0;
if (orderedSecCount > fileOrder)
fileOrder = orderedSecCount;
//統(tǒng)計(jì)最多的連續(xù)塊作為這個(gè)文件順序性的評估標(biāo)準(zhǔn)
lastSector = sector;
}
order += (fileOrder + 1) * countRate / fileSectors.length;
// 順序度的評估值，每個(gè)文件最高countRate分，即排序完成。order=文件個(gè)數(shù)×countRate時(shí)全部排序完成。
}
return order;
}

public int countStatus() {
return countSecotrOrder() - operationCount*2;
}

// public int compareTo(Object o) {
// return ((DiskStatus) o).countSecotrOrder() - countSecotrOrder();
// }

public String toString() {
StringBuffer result = new StringBuffer();
for (int i = 0; i < files.length; i++) {
int[] file = (int[]) files[i];
for (int j = 0; j < file.length; j++) {
if (j > 0)
result.append('.');
result.append(file[j]);
}
result.append("(order:").append(countSecotrOrder()).append(")(count:").append(countStatus()).append(')').append(
'\n');
}
return result.toString();
}
}
}

也是送分題。但是要在規(guī)定時(shí)間內(nèi)麻利的分析處理全部字符串形成規(guī)則和判斷就靠熟練了。
public class SimpleRouter {

public static void main(String[] args) {
SimpleRouter s = new SimpleRouter();
String[] rules = {"FORWARD 192.168.000.* 001-100 192.168.0.10",
"FORWARD 192.168.0.1 80 10.10.95.184 8080",
"ACCEPT 192.168.*.* 25", "REJECT 192.168.5.38 *"
};
String[] packets = {"192.168.0.43 80",
"00192.00168.000.001 00080",
"192.168.0.1 110",
"192.168.1.73 80",
"192.168.1.73 25",
"206.26.210.5 53",
"192.168.5.38 25"
};
String[] result = s.route(rules, packets);

for (int i = 0; i < result.length; i++)
System.out.println(result[i]);
System.out.println("-------------------------------------------------------------------------------");

rules = new String[] {"FORWARD *.*.*.* * 192.168.0.1"};
packets = new String[] {"213.148.161.82 9484",
"172.230.108.145 16627",
"122.141.122.130 46874",
"241.145.145.77 26390",
"139.97.106.125 35305",
"244.131.151.77 26390"
};
result = s.route(rules, packets);
for (int i = 0; i < result.length; i++)
System.out.println(result[i]);
System.out.println("-------------------------------------------------------------------------------");

rules = new String[] {"REJECT *.20-252.114-157.36-91 13171-54085",
"ACCEPT *.*.73-180.* *",
"FORWARD 55.63.173.239 * 168.154.33.25",
"REJECT *.72-73.*.48-191 *",
"REJECT 20.51.*.* 4579",
"ACCEPT 70-166.*.*.86-182 *",
"REJECT 88-190.*.119-157.* 3316-27844",
"FORWARD *.52-221.134-250.66-207 * 116.94.120.82"};
packets = new String[] {"203.11.104.45 44072",
"154.92.128.87 30085",
"20.51.68.55 4579",
"177.73.138.69 14319",
"112.65.145.82 26287",
"55.63.173.239 45899"
};
result = s.route(rules, packets);
for (int i = 0; i < result.length; i++)
System.out.println(result[i]);

System.out.println("-------------------------------------------------------------------------------");

rules = new String[] {"FORWARD *.*.*.* * 00.012.00000.099",
"FORWARD 192.168.0.1 110 00.00.00.00 000001"};
packets = new String[] {"192.168.0.43 80", "00192.00168.000.001 00080",
"192.168.0.1 110", "192.168.1.73 80", "192.168.1.73 25",
"206.26.210.5 53", "192.168.5.38 25"};
result = s.route(rules, packets);
for (int i = 0; i < result.length; i++)
System.out.println(result[i]);

}


public String[] route(String[] rules, String[] packets) {
String[] result = new String[packets.length];
for (int i = 0; i < packets.length; i++) {
result[i] = getRoute(rules, packets[i]);
}
return result;
}


private String getRoute(String[] rules, String packet) {
for (int i = rules.length - 1; i > -1; i--) {
String m = match(rules[i], packet);
if (m != null) {
// System.out.println("match rule"+i+":"+rules[i]);
return m;
}
}
return "REJECT";
}

private String match(String rule, String packet) {
String[] ruleParts = rule.split(" ");
String[] packetParts = packet.split(" ");
String ip = packetParts[0];
String port = packetParts[1];
String[] ipParts = ip.split("\\.");
if ("ACCEPT".equals(ruleParts[0])) {
String ipRange = ruleParts[1];
String portRange = ruleParts[2];
String[] ipRangeParts = ipRange.split("\\.");
return (matchPart(ipRangeParts[0], ipParts[0]) &&
matchPart(ipRangeParts[1], ipParts[1]) &&
matchPart(ipRangeParts[2], ipParts[2]) &&
matchPart(ipRangeParts[3], ipParts[3]) &&
matchPart(portRange, port)) ? "ACCEPT" : null;
}
if ("REJECT".equals(ruleParts[0])) {
String ipRange = ruleParts[1];
String portRange = ruleParts[2];
String[] ipRangeParts = ipRange.split("\\.");
return (matchPart(ipRangeParts[0], ipParts[0]) &&
matchPart(ipRangeParts[1], ipParts[1]) &&
matchPart(ipRangeParts[2], ipParts[2]) &&
matchPart(ipRangeParts[3], ipParts[3]) &&
matchPart(portRange, port)) ? "REJECT" : null;
}
if ("FORWARD".equals(ruleParts[0])) {
String ipRange = ruleParts[1];
String portRange = ruleParts[2];
String[] ipRangeParts = ipRange.split("\\.");
if (!(matchPart(ipRangeParts[0], ipParts[0]) &&
matchPart(ipRangeParts[1], ipParts[1]) &&
matchPart(ipRangeParts[2], ipParts[2]) &&
matchPart(ipRangeParts[3], ipParts[3]) &&
matchPart(portRange, port)))
return null;

String[] forwardIp = ruleParts[3].split("\\.");

return Integer.parseInt(forwardIp[0], 10) + "." +
Integer.parseInt(forwardIp[1], 10) + "." +
Integer.parseInt(forwardIp[2], 10) + "." +
Integer.parseInt(forwardIp[3], 10) + ":" +
Integer.parseInt((ruleParts.length>4?ruleParts[4]:port),10);
}
return null;
}

private boolean matchPart(String range, String data) {
if ("*".equals(range))
return true;
if (range.indexOf('-') > -1) {
String[] r = range.split("-");
int lower = Integer.parseInt(r[0], 10);
int upper = Integer.parseInt(r[1], 10);
int i = Integer.parseInt(data, 10);
return (lower <= i && upper >= i);
}
if (Integer.parseInt(range) == Integer.parseInt(data))
return true;
return false;
}
}

送分題。主要難度是在理解題目的描述上。

public class CellPlans
{
public static void main(String[] args)
{
String [] plans = new String []{"2999 1000 29 T","5999 3000 49 F","999 0 19 F"};
int[] peakMinutes = new int[]{1543,463,754,405,0,30};
int[] offMinutes = new int[]{100,2053,1003,534,2595,3056};
int cheapest = new CellPlans().cheapest(plans,peakMinutes,offMinutes);
System.out.println("cheapest plan is :"+cheapest);

plans = new String []{"10000 0 0 T","10000 0 0 F"};
peakMinutes = new int[]{20000,25000};
offMinutes = new int[]{25000,20000};
cheapest = new CellPlans().cheapest(plans,peakMinutes,offMinutes);
System.out.println("cheapest plan is :"+cheapest);

plans = new String []{"100000 0 1000 F","100000 0 10 F"};
peakMinutes = new int[]{25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,
25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,
25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,
25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,
25000,25000,25000,25000,25000,25000};
offMinutes = new int[]{25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,
25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,
25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,
25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,25000,
25000,25000,25000,25000,25000,25000};
cheapest = new CellPlans().cheapest(plans,peakMinutes,offMinutes);
System.out.println("cheapest plan is :"+cheapest);

}

public int cheapest(String[] plans, int[] peakMinutes, int[] offMinutes){
double min = count(plans[0],peakMinutes,offMinutes);
int result = 0;
for (int i=1;i<plans.length;i++){
double c = count(plans[ i ],peakMinutes,offMinutes);
if (c<min){
min=c;
result = i;
}
}
return result;
}
private double count(String plan,int[] peakMinutes,int[] offMinutes){
String[] ar = plan.split(" ");
double price = Float.parseFloat(ar[0]);
int minutes = Integer.parseInt(ar[1],10);
double costPerMin = Float.parseFloat(ar[2]);
boolean offHours = "T".equals(ar[3]);
double result = peakMinutes.length*price;
for(int i=0;i<peakMinutes.length;i++){
if (offHours){
result += costPerMin*((peakMinutes[ i ]>minutes?(peakMinutes[ i ]-minutes):0));
}else{
result += costPerMin*((peakMinutes[ i ]+offMinutes[ i ])>minutes?(peakMinutes[ i ]+offMinutes[ i ]-minutes):0);
}
}
return result;
}

}

改用BigInteger，decree就可以無限增大了。

import java.math.BigInteger;
public class Alphabet {
public static void main(String[] args) {
long timeMillis = System.currentTimeMillis();
Alphabet a = new Alphabet();
String st = "BABABABABABABABABABABABABABABABABABABABABABABABAB";
System.out.println(st+" = "+a.choices(st));
}

private static void assertEquals(int a, int b) {
if (a != b)
throw new RuntimeException("assert failed!! Expected " + b +
" but got " + a);
}

public BigInteger choices(String decree) {
BigInteger[] oldPosList = new BigInteger[3];
BigInteger timesCount = BigInteger.ONE;
oldPosList[decree.startsWith("A")?1:2]=BigInteger.ONE;
for (int i = 2; i <= decree.length(); i++) {
timesCount = BigInteger.ZERO;
BigInteger[] newPosList = new BigInteger[i + 2];
char ch = decree.charAt(i - 1);
if (ch == 'A') {
for (int j = 1; j <= i; j++) {
BigInteger times = oldPosList[j];
if (times == null) times = BigInteger.ZERO;
if (i < decree.length())
for (int k = 1; k <= j; k++)
newPosList[k] = (newPosList[k]==null)?times:newPosList[k].add(times);
// timesCount += j*times;
timesCount = timesCount.add(new BigInteger(j+"").multiply(times));
}
} else {
for (int j = 1; j <= i; j++) {
BigInteger times = oldPosList[j];
if (times == null) times = BigInteger.ZERO;
if (i < decree.length())
for (int k = j + 1; k <= i + 1; k++)
newPosList[k] = (newPosList[k]==null)?times:newPosList[k].add(times);
// timesCount += (i-j+1)*times;
timesCount = timesCount.add(new BigInteger((i-j+1)+"").multiply(times));
}
}
oldPosList = newPosList;
// if (timesCount > 1000000000) return -1;
}
return timesCount;
}
}