emu in blogjava

现在不是流行pk嘛。

呵呵我是技术理想主义者，sean是实用主义者。

不欣赏gmail的ajax理由是没有充分利用到xml带来的好处，后台必须为前台的每一个请求度身定做一个返回的（超）文本或者脚本，因此也在后台带来了混合编程的问题。

如果实用纯xml来做ajax，后台开发人员可以非常大的被解放出来，更多的关注业务而不是表现，我认为这是ajax带来的另一个方面的好处。有兴趣可以看看
http://qzone-search.qq.com/web/tag/tt_search.html
这个页面就是接收标准的xml数据来显示的。比如页面中间的“最近更新”部分来自于http://qzone-search.qq.com/client/tag/newtags.xml ，而搜索功能的实现则依赖于ajax加载。而tencent公司正在开发中的tm版qzone干脆用ajax技术解析rss数据来生成页面，这样后台开发人员只需要做一套提供rss订阅的cgi就可以了。

但是在gmail这样对跨浏览器要求比较高的场合上，这是很必然的选择，跨浏览器的xml解析始终是一个麻烦的东东，我现在也还搞不定。打算过一段有时间了再好好研究，实在不行就用纯javascript写一个简单一点的xml解析器，跨平台行还更好一些呵呵。

jiniboy ： 本来打算hack掉gmail的脚本来分析gamil的来往数据的，这段时间忙没有办法去做，过阵子吧。至于更详细的技术实现，我认为没有进一步探究的价值了，我认识的网友有超过一打都可以实现得出来。

todogoingmm ：没有仔细研究过其中的差别，其实网上的资料很多了。我认为主要差别是不同浏览器支持的不同版本的xml控件，但是我们尽量向下兼容，使用最通用的功能。

不如讲讲你是怎么定位到com.atlassian.license.DefaultLicense.class这个类上面的？

呵呵你也来啦。我再强能有庄老大强？更不要说现在坐在我隔壁位子的廖大哥了。

是吗？你看到的具体是什么内容呢？关于什么事件的？方舟子的哪些言论你觉得过了？

《上海晨报》网上搜不到它的网站噢，不是据说是华东“最有影响力”的报纸嘛，怎么好像网上没什么影响力。

百度有进步了，我认错。
今天中午再搜百度 http://www.baidu.com/s?wd=%D7%DF%CF%F2%B6%F8%C1%A2%D6%AE%C4%EA+emu&cl=3 已经有我的文章了，不过链接是指向blogjava首页的。


同时 yahoo上原来搜到的rss链接的结果也更新成我的文章的链接了，而且有两个结果。
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

这次两个搜索引擎更新这么快显然和我昨天新发了一篇 Gmail 使用的AJAX技术研究 在blogjava首页上。

而备受我推崇的google今天表现就让人失望了，今天中午还是没有链接到我的文章。
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啊

何必绕这么大一圈呢？还要包装一个exe文件。javaservice其实没有那么难搞的。

我用javaservice把james安装成服务之要写一句：

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自带的文档和示范都很详细的，现在中文资料应该也不难搜到了。

搜了一下，你的文章转载的地方很多呀。看来现在这方面的中文资料真的是太缺乏了。
可惜很多网站都没有给出你的原文链接。以后写技术文章也写一个版权声明上去好了。

哈哈你要写就赶快哈，我也在酝酿中。

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

不如叫AJAH算了。如果你知道我在说什么，我想你会同意我的说法的。

呵呵不用看了，我天天在内部试用新版的foxmail呢。

引用文章不给原文连接不好。我昨天就在donews上面找这篇的原文了，不过找不到。原文连接 http://home.donews.com/donews/article/8/84823.html 早已被删除。

谣言散播出来了以后源出处却已毁尸灭迹死无对证，这个枪手手段果然高明。现在网上到处都有转这篇文章的，反正谁也不用负责任。

我们还是来看看文章本身吧。文章的前面一大部分都是旧内容了，作者显然相信危言耸听一万遍就可以变成真理，值得一看的只有后面最新的几句：

---------------------------------------------------------------------------
我想肯定是QQ安全中心(和金山毒霸合作搞的)拿我们用户当试验品,而腾讯公司为了逃避责任,力图欺骗QQ大众不懂技术,用"动态文件名"来蒙我们.没有一点诚意!

同时我警告一些杀毒软件公司不要干一些违背职业道德的事,会遭到大众的漫骂的.

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

枪手的这个“肯定”有任何依据吗？他凭什么这么肯定呢？
枪手号称“我已经把这病毒程序提交给了诺顿、卡巴司机等多个病毒厂商”，这么多天过去了，有否哪一个杀毒软件厂商（这个枪手居然管人家叫“病毒厂商”呵呵）发布了相关的安全公告呢？按照枪手的意思，腾讯不但“和金山毒霸合作搞的”，而且还和诸多病毒厂商共同策划了这样一个病毒散播事件，大家可以想想有没有这样的可能性呢？

木秀于林，风必催之。中国一共才做出来几个可以和微软较劲的软件，几个IM却居然要在这里窝里斗，让人心寒。

>>这个好像不是groovy的问题
呵呵就象朋友经常批评的，这是人品问题。我觉得这个问题上groovy没有提供一个简单的解决方案。

>>类似的东西，偶屡试不爽
是指的什么？import吗？怎么做呢？

>>前面那个Dog.groovy并不需要编译
是指的运行不需要编译还是被其他groovy脚本import之前不需要编译呢？

不但脚本不是用来“做计算密集型的东西”的，java也不是c#也不是。正儿八经说，高级语言都不是，汇编语言也只是勉强算是。不是用来“做计算密集型的东西”并非就可以把运行效率完全丢开一边了。我们牺牲一些运算效率来换开发效率是可以接受的，但是牺牲的太多了就不得不要斟酌一下了。

秋水无恨解 http://www.blogjava.net/emu/category/2769.html 也是用的脚本呢。

>但对3721，我觉得确实不能原谅
理解理解，当年我也是不胜其烦。
这次国庆回家，发现家里的计算机的主页也是hao123呵呵。我单位里面用的电脑的主页是加加在线，没有办法，只要一启动拼音加加2它就帮我重设一变，我干脆把hosts文件改了，把加加在线映射到我喜欢的地址上，由它去改吧。

其实这个事情国庆前就已经辟谣了，病毒厂商和专家的看法和评论在网上也很容易看到。几个IM厂商和门户网站收买枪手造谣中伤，平常已极，朋奕何苦掺和？

动态文件名、自我隐藏和自我保护是对付木马的无奈之举，而且对用户没有造成伤害和不便，卸载也不象当年的3721那么困难（3721后来其实也改正了，何必念念不忘当年的旧帐呢？），“除了破坏数据之外所有病毒的特性都有了”言重了吧？它造成机器变慢？占用额外的资源和带宽？有传染性？

至于实名制，那是政策要求。上个月的南方周末有过评论了。

呵呵，我现在不做java了，只能在js上干这些事情了。

JK手脚真快，一下发现了两个bug：

1 从一个textbox把文字拖放到另一个textbox的情况下不能undo，因为ie没有触发两个onchange事件给我，不能全怪我啊。

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

Robert Frost显然不明白世界是由懒人创造的。

幸运的人都是相似的，不幸的人各有各的不幸啊！

相信我，在课本上编造这个谎言的人自己根本就不相信。

要不怎么说多事之秋呢

1 防民之口，甚于防川

2 水至清则无鱼

3 政府和网民意见相左的时候，ISP成了夹心饼，偏哪边都不对，最好闷声发大财。

好文章，值得一看！

suite可以通过自嵌套来实现分层次递降的测试每个包，用可变参数来管理的话能实现同样的目的吗？

真的是好久了哦。我到深圳来了，忙完了联系。

原来ｆｏｘｍａｉｌ在３月份被收购了，消息真是迟钝。

没有发现现成的IDE哦，其实用记事本也可以开放阿，我是用ｅｄｉｔｐｌｕｓ。ｊｃｒｅａｔｏｒ好像不支持ｊａｖａ之外的语言吧？没用过。

Office ??

这是谁啊？肖庆来？甄继业？

遗憾的很，我这个答案没有通过google的系统测试。

遗憾的很，我这个答案没有通过google的系统测试。

败给这一组数据了：
{"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"}
期待结果：50

这是谁啊？回复错地方了？

google的比赛谁都可以参加啊，为什么一定要来中国办呢？考场里面也见到不少中国人。

3.11版过时很久啦！
http://www.blogjava.net/emu/archive/2005/08/09/9653.html

居然系统测试失败
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

这个题基本上就是我以前写的 java版本的escape和unescape函数 的简化版了。
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数据建立int数组
        srcDiskElms = getDiskElms(disk);
        // 计算全部文件占用的扇区数
        for (int i = 0; i < fileCount; i++)
            secCount += ((int[]) srcDiskElms[i]).length;
        destDiskElms = new int[fileCount][4];
        //[0]==文件在srcDiskElms中的编号
        //[1]==文件的起始位置
        //[2]==文件的最后一个扇区的位置+1
        //[3]==文件和原始状态的重合区块计数

        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++) {
                // 找到一个还没有放进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]; //上一个文件结束的位置+1。
                    int maxOffset = diskSize - secCount + tmpSecCount; //文件起始位置不可能超过这个位置
                    for (int fileOffset = lastFileEndOffset;
                                          fileOffset <= maxOffset; fileOffset++) {
                        destDiskElms[n][1] = fileOffset;
                        destDiskElms[n][2] = fileOffset + fileSize; //文件的最后一个扇区的位置+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也有groovy语法支持的：
http://www.blogjava.net/emu/archive/2005/05/18/4781.html

8月10号jira又发布了3.3版。releasenotes在这里：

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

检讨了上面的A*算法，其中存在着两个基本错误：
每扩展一个节点就把它从队列中删掉，造成下次构造出相同的状态的时候没有办法知道。
用toString来判断两个状态是否相同，但是toString里面除了基本的sector数据之外还有评分的数据，所以不同情况下生成的相同状态会被判断成不同状态。

修正后的A*算法，可以计算出一个比较合理和可行的整理过程，但是没有办法保证找到最好的一种（扩展过多的可能性会造成运算超时）。

理论上说只要修改评估策略（countStatus函数）就可以保证算法总是朝正确的方向扩张，但是创造一个合理的评估函数本身就是一个难题。

也许A*算法根本就不是这道题的正解。




import java.util.*;

// 节点增长方式：
// 1、如果内存区域为空，读取任一块数据
// 2、如果内存区域非空，写一个内存块到任意一个空白的位置

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; //为了方便处理评分，把评分值放大一个倍数后取整。
private static int memorySector = 2; //内存可存放的数据
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; //操作次数记数
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++; //转移一个块到硬盘上
file[sectorIndex] = newSector;
files[fileIndex] = file;
if (newSector >= 0)
sectorFill[newSector] = true;
else
memoryAvalible--; //转移一个块到内存上
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;
//统计最多的连续块作为这个文件顺序性的评估标准
lastSector = sector;
}
order += (fileOrder + 1) * countRate / fileSectors.length;
// 顺序度的评估值，每个文件最高countRate分，即整理完成。order=文件个数×countRate时全部排序完成。
}
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/

手术情况
作者： Administrator
2005-08-15
手术情况还算顺利，他妹妹上周末已出院。

王俊还在住院观察，需要在这周才能知道更多情况。
我们的募捐活动将在这周得知确切结果后结束。

感谢所有的好心人们。

在8月6日活动上，王俊通过电话向大家介绍了自己的情况，并感谢所有人的帮助。

用A*算法来扩展状态树，当问题稍微复杂一点的时候状态树生长的太厉害，没有办法在规定时间内找到解，失败！

import java.util.*;

// 节点增长方式：
// 1、如果内存区域为空，读取任一块数据
// 2、如果内存区域非空，写一个内存块到任意一个空白的位置

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; //为了方便处理评分，把评分值放大一个倍数后取整。
private static int memorySector = 2; //内存可存放的数据
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; //操作次数记数
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++; //转移一个块到硬盘上
file[sectorIndex] = newSector;
files[fileIndex] = file;
if (newSector >= 0)
sectorFill[newSector] = true;
else
memoryAvalible--; //转移一个块到内存上
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;
//统计最多的连续块作为这个文件顺序性的评估标准
lastSector = sector;
}
order += (fileOrder + 1) * countRate / fileSectors.length;
// 顺序度的评估值，每个文件最高countRate分，即排序完成。order=文件个数×countRate时全部排序完成。
}
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();
}
}
}

也是送分题。但是要在规定时间内麻利的分析处理全部字符串形成规则和判断就靠熟练了。
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;
}
}