-Flyぁ梦-

突然有这么个想法，就写了段代码测试了下。在单线程下对Java里所有Map的性能测试，包括HashMap、Hashtable、LinkedHashMap、IdentityMap、TreeMap，没有测试WeakHashMap。

数据为<Integer, Integer>，范围在0~1千万，共1百万对数据，由Python的random.randint()自动生成。

测试的性能包括写入（put）、随机读（get）和遍历（foreach语法），也是Map这个数据结构最常用的三个操作。其中写入就是将这1百万对测试数据依次put一遍，随机读就是在上一步写入之后再按顺序get一遍。数据显示最后Map大小都为995012（当然IdentityMap的size是1百万），就是有近5000条重复的key。
阅读更多…

正常思维下，就会去判断一个矩形的每个点是否在另一个矩形中，然后衍生出4个判断，每个判断都要带上4对大于小于比较，甚是麻烦。

1
2
3
4
5
6

boolean judgeOverlap(Rect A, Rect B){
	for(Point p : all points in A){
		if(p in B) return true;
	}
	return false;
}

上面这段代码其实有一点问题，设A的左上右下点为A1和A2，B的为B1和B2，就是：A与B重叠不等价于judgeOverlap(A1, A2, B1, B2) == true （比如当B真包含于A时就返回false了），而是等价于judgeOverlap(A1, A2, B1, B2) == true || judgeOverlap(B1, B2, A1, A2) == true，这里很容易犯bug。

有一个更容易的方法来解决这个问题，反向思维也很容易，就是排除那些A和B不可能重叠的情况，就4种。

1
2
3
4
5
6
7

boolean judgeOverlap(Rect A, Rect B){
	if(A.right < B.left) return false;
	if(A.left > B.right ) return false;
	if(A.top < B.bottom) return false;
	if(A.bottom > B.top) return false;
	return true;
}

现在项目中还在使用上面版本的代码跑着，觉得第二种方法应该没有问题但没有测试过也没有应用到项目中去实践。

练习DP就从背包开始吧，比较简单一些，因为套路基本都差不多，适合入门。做提前，推荐上网搜一下《背包九讲》读个一遍就大致了解背包题了，顺便再次ym下dd大牛…做了不少zoj里的背包题目，大概估计下来，但背包大小 <= 10w的情况下，一般都不会超时。

阅读更多…

别看字符串挺简单，还真牵扯到好多数据结构和算法啊，给跪了，要将所有的都好好掌握真心是一项艰难的任务。这里就列举下自己做zoj时候碰到过的一些，然后配合自己做过的例题讲一下。不过每种算法、数据结构具体的描述和代码，还请自己去搜索吧。 阅读更多…

后缀数组的代码算法难度比较高，反正没怎么看也不打算看懂，从网上找了好久找到一份比较好用的代码，效率也比较高，据说是用的倍增算法？看不懂 =.= 阅读更多…

网上代码很多，但是大多ACMer的风格，呃不是我说，代码可读性和封装性是比较欠缺的…也许Java出身的码农也就这点还有些优势了吧…纯自己手动敲的，build_ac函数（建立fail指针的过程）学习了网上的教程后模仿着写的，而且带clear()释放内存。 阅读更多…