Dec
28
一个完美的框架，应该是一个实现了对修改关闭，对扩展开放的框架。需要修改，意味这这个框架仍然存在瑕疵；不适合扩展，那就没有被称为框架所需的内涵。当然，完美的框架是不存在的，也没有一个框架能够满足所有的情况，所以需要根据具体的情况来做出选择。
我觉得做出这个选择的最重要标准是系统的规模。
对于一个小型系统，也许是一次性的（没有多少扩展需求），或者代码比较少（修改起来比较容易），那么框架的存在就不一定是必要的了。不论是自己设计一个框架，抑或是学习并采用一个现有的框架，都需要耗费比较多的时间精力，对于一个小型系统而言，很可能得不偿失。当然，不需要框架并不意味着可以随意开发（随意开发的过程是痛苦的，越往后越明显，felix深有感受...），高内聚低耦合等基本的设计原则还是必须遵从的，这样能够使开发过程更简单。更严格一点说，一个良好的设计本身就带有一些框架的性质。
对于一个中型系统，如果规模虽然稍大，但是仍然可以在少数几个人的掌握之下，那么一个强大的框架对开发是有相当助益的。在这种情况下，学习框架的开销是可以接受的，一次投入多次产出：在掌握了框架以后，每当需要增加新的功能的时候，只需要按照框架的规则写一个模块并插入到系统中，多余的事情都由框架来完成，非常轻松。
对于一个大型系统，其规模已经大到不是几个人可以掌握的了，那么在开发之初对框架的选择是至关重要的。因为当系统大到一定规模再更换框架，在很多情况下是不现实的，所以在开发之前就必须有足够的考虑。一个强大的框架是必须的，但我觉得这还不是全部：这个框架还必须简单。俗话说计划赶不上变化，当初设计得再好的功能，逐渐也可能会不适应后来的需求（PM一句话，RD两行泪=.=），以至于成为整个系统的累赘。所以框架还必须要简单（无为而治）——这个简单不是说框架需要提供少的功能。引用讲述Unix设计哲学的一段话：框架就应该是提供mechanism(机制)的部分，而策略，就应该是具体的某个功能。这样一个框架就简单了，当你用这个框架进行开发的时候，你是在使用框架提供的机制来实现你的策略，你可以把握策略的实现，而不用担心在什么地方框架带来了难以察觉的干扰。
这些是非常理想化的选择，但是实际中又存在许多难以避免的问题。
其一，温水煮青蛙
这个寓言大家都耳熟能详了，虽然其真实性有待验证，但是其寓意还是很有警示意义的。一个系统的规模并不一定是刚开始的时候就可以知道的。比如创业的小公司，刚开始可能只是设计一个小型或者中型的系统，直到某一天发现系统负载或者是其扩展性已经或者将在可见的未来无法满足要求。这时候为了发展只能进行底层的重构。
其二，机制和策略的矛盾
Unix哲学考虑得很好，程序应该分成机制和策略两块，但是将这二者完全划分清楚未必是好的，甚至是不可能的。如果框架完全不干涉策略的实现，那么意味着每一个模块的开发都会有更多的工作量。如果框架过多地干涉策略，那么意味着框架过于复杂，掌握框架的代价更高。所以这里存在需要权衡的地方，而权衡的标准，还是的得考虑系统的规模和复杂性。于是又回到上一个问题了。
其三，...
需求的不确定、某个语言的局限这样一些具体的问题，也许不应该放在这里，但是在实际的开发和维护过程中，他们又的确会困扰开发者。甚至让人头疼。
----
说了这么多，感觉有点虚，因为没有什么特别具体的例子。公司里的项目不适合拿来讨论，但是正好前几天跟同事聊到一个例子，觉得比较适合放在这里说说。
这个例子就是C++，和C。最近一段时间我对C++有一些排斥，所以很难保证我下面将要说的内容的中立性，有任何问题欢迎探讨。
我觉得C++本质上就是C的一个框架。C++包装了C语言，提供了一些方便开发的特性，比如对面向对象的支持，比如对泛型的支持。根据上面提到的命名方式，我们可以认为这些特性就是这个"C框架"提供的机制，而C++程序员开发相应的程序，就是使用这些机制来完成其特定的策略。另一方面，C++不仅提供了机制，还在一定程度上影响了策略的实现。
比如说，在C++中，类的成员函数是否具有virtual属性，决定了这个类（的这个成员函数）是否可以实现多态。当然，这可以看作是一种机制的实现，但是它不可避免地影响了具体的策略。更特别的是，如果一个被继承的类的析构函数不具有virtual属性的话，可能程序在运行过程中会出现内存泄漏。
比如说，当你编写一个inline函数的时候，你可能期望它总是被inline，但是可能由于某些你不知道的限制，实际上inline属性并没有生效，它还是作为一个函数被反复调用。
再比如说，当你使用一个模板的时候，你可能不会考虑到这些模板对内存的占用。但实际上，模板的每一次特例化，都会使得几乎相同的函数在内存中存在两份拷贝（也许这个例子有些牵强）。另一个模板的例子是在特例化的时候没有特别注意类型，比如说make_pair(1, 2.0)实际上创建了一个pair<int, float>，而不是pair<float, float>。
这些是多少都可以算做是这个C框架不仅提供机制，还影响策略的例子。我相信还有很多类似的例子是我不知道的，但是糟糕的是，要掌握这个C框架的代价太大。这也就是我近来对C++产生排斥感的主要原因（另一个原因是我担心C++用多了，以后写代码会越来越懒~~~）。
说了这些不是想说C++是多么不堪、不能使用，去年暑假有很长一段时间我在仔细学习STL，其中有很多很伟大的设计。从这个角度来说，对C++我是心存敬畏的。从框架的角度来看，C++实际上是一个很强大的C框架，很适合快速开发，比如写一个acm程序，我肯定用C++，好好用上STL。做一个小型的系统，我也许也会选用C++。我只是觉得，这个强大的框架做得不够简单，如果要考虑大型系统的开发，务必要仔细权衡。
---
最后，使用一个很著名的设计原则来结束这篇日志：
KISS: Keep It Simple, Stupid.
我觉得做出这个选择的最重要标准是系统的规模。
对于一个小型系统，也许是一次性的（没有多少扩展需求），或者代码比较少（修改起来比较容易），那么框架的存在就不一定是必要的了。不论是自己设计一个框架，抑或是学习并采用一个现有的框架，都需要耗费比较多的时间精力，对于一个小型系统而言，很可能得不偿失。当然，不需要框架并不意味着可以随意开发（随意开发的过程是痛苦的，越往后越明显，felix深有感受...），高内聚低耦合等基本的设计原则还是必须遵从的，这样能够使开发过程更简单。更严格一点说，一个良好的设计本身就带有一些框架的性质。
对于一个中型系统，如果规模虽然稍大，但是仍然可以在少数几个人的掌握之下，那么一个强大的框架对开发是有相当助益的。在这种情况下，学习框架的开销是可以接受的，一次投入多次产出：在掌握了框架以后，每当需要增加新的功能的时候，只需要按照框架的规则写一个模块并插入到系统中，多余的事情都由框架来完成，非常轻松。
对于一个大型系统，其规模已经大到不是几个人可以掌握的了，那么在开发之初对框架的选择是至关重要的。因为当系统大到一定规模再更换框架，在很多情况下是不现实的，所以在开发之前就必须有足够的考虑。一个强大的框架是必须的，但我觉得这还不是全部：这个框架还必须简单。俗话说计划赶不上变化，当初设计得再好的功能，逐渐也可能会不适应后来的需求（PM一句话，RD两行泪=.=），以至于成为整个系统的累赘。所以框架还必须要简单（无为而治）——这个简单不是说框架需要提供少的功能。引用讲述Unix设计哲学的一段话：
引用
The distinction between mechanism and policy is one of the best ideas behind the Unix design. Most programming problems can indeed be split into two parts: “what capabilities are to be provided” (the mechanism) and “how those capabilities can be used” (the policy). If the two issues are addressed by different parts of the program, or even by different programs altogether, the software package is much easier to develop and to adapt to particular needs.
这些是非常理想化的选择，但是实际中又存在许多难以避免的问题。
其一，温水煮青蛙
这个寓言大家都耳熟能详了，虽然其真实性有待验证，但是其寓意还是很有警示意义的。一个系统的规模并不一定是刚开始的时候就可以知道的。比如创业的小公司，刚开始可能只是设计一个小型或者中型的系统，直到某一天发现系统负载或者是其扩展性已经或者将在可见的未来无法满足要求。这时候为了发展只能进行底层的重构。
其二，机制和策略的矛盾
Unix哲学考虑得很好，程序应该分成机制和策略两块，但是将这二者完全划分清楚未必是好的，甚至是不可能的。如果框架完全不干涉策略的实现，那么意味着每一个模块的开发都会有更多的工作量。如果框架过多地干涉策略，那么意味着框架过于复杂，掌握框架的代价更高。所以这里存在需要权衡的地方，而权衡的标准，还是的得考虑系统的规模和复杂性。于是又回到上一个问题了。
其三，...
需求的不确定、某个语言的局限这样一些具体的问题，也许不应该放在这里，但是在实际的开发和维护过程中，他们又的确会困扰开发者。甚至让人头疼。
----
说了这么多，感觉有点虚，因为没有什么特别具体的例子。公司里的项目不适合拿来讨论，但是正好前几天跟同事聊到一个例子，觉得比较适合放在这里说说。
这个例子就是C++，和C。最近一段时间我对C++有一些排斥，所以很难保证我下面将要说的内容的中立性，有任何问题欢迎探讨。
我觉得C++本质上就是C的一个框架。C++包装了C语言，提供了一些方便开发的特性，比如对面向对象的支持，比如对泛型的支持。根据上面提到的命名方式，我们可以认为这些特性就是这个"C框架"提供的机制，而C++程序员开发相应的程序，就是使用这些机制来完成其特定的策略。另一方面，C++不仅提供了机制，还在一定程度上影响了策略的实现。
比如说，在C++中，类的成员函数是否具有virtual属性，决定了这个类（的这个成员函数）是否可以实现多态。当然，这可以看作是一种机制的实现，但是它不可避免地影响了具体的策略。更特别的是，如果一个被继承的类的析构函数不具有virtual属性的话，可能程序在运行过程中会出现内存泄漏。
比如说，当你编写一个inline函数的时候，你可能期望它总是被inline，但是可能由于某些你不知道的限制，实际上inline属性并没有生效，它还是作为一个函数被反复调用。
再比如说，当你使用一个模板的时候，你可能不会考虑到这些模板对内存的占用。但实际上，模板的每一次特例化，都会使得几乎相同的函数在内存中存在两份拷贝（也许这个例子有些牵强）。另一个模板的例子是在特例化的时候没有特别注意类型，比如说make_pair(1, 2.0)实际上创建了一个pair<int, float>，而不是pair<float, float>。
这些是多少都可以算做是这个C框架不仅提供机制，还影响策略的例子。我相信还有很多类似的例子是我不知道的，但是糟糕的是，要掌握这个C框架的代价太大。这也就是我近来对C++产生排斥感的主要原因（另一个原因是我担心C++用多了，以后写代码会越来越懒~~~）。
说了这些不是想说C++是多么不堪、不能使用，去年暑假有很长一段时间我在仔细学习STL，其中有很多很伟大的设计。从这个角度来说，对C++我是心存敬畏的。从框架的角度来看，C++实际上是一个很强大的C框架，很适合快速开发，比如写一个acm程序，我肯定用C++，好好用上STL。做一个小型的系统，我也许也会选用C++。我只是觉得，这个强大的框架做得不够简单，如果要考虑大型系统的开发，务必要仔细权衡。
---
最后，使用一个很著名的设计原则来结束这篇日志：
KISS: Keep It Simple, Stupid.
Dec
28
注：本文只是简单介绍这三个东西并对比一下其功能、差异，不讨论这些东西是否有存在的必要以及优劣。
· goto
· setjmp, longjmp
· try-catch
一、看看基本的使用
1. goto
这个比较简单，比较容易理解，只要设置一个行标就行了：
例子：
2. setjmp, longjmp
goto用起来是简单，但是存在一个先天缺陷：只能在同一个函数内使用。
有时候我们写一个代码，有两三层的函数嵌套，想要返回的时候就比较囧。
这时候用setjmp和longjmp就很happy。
例子：
输出是:
Hi, I'm foo!
Hi, I'm bar!
i = 1
3. try-catch （在这里算是歪用了，呵呵）
这个是c++提供的语言特性，可以用于捕获throw语句抛出的异常，不仅可以在函数内使用，也可以跨函数～～
例子：
输出是：
Hi, I'm foo!
Hi, I'm bar!
i = 1
二、简单对比一下：
· goto，使用简单方便，看起来比其他两个更容易一点（有行标），但是只能在函数内跳转；
· setjmp和longjmp，稍微麻烦点，需要带个参数(jmp_buf，全局变量，或者传参)，好处是可以跨函数跳转，且可以根据setjmp的返回值得知从何处跳转。还有一个小缺陷就是，因为需要先执行setjmp以后才可以跳转，所以可以跳转的地方有一定限制，也使得代码看起来有点不够清晰。
· try-catch，C++有C没有，看起来结构比较清晰，不需要带额外的参数，抛出不同的值（和类型）方便判断来源。
三、重点考察一个问题：
如果有一个class，比如
所以在使用这三个东西的时候，一定要特别注意，建议在C++里头不使用setjmp，以免查错无门...
· goto
· setjmp, longjmp
· try-catch
一、看看基本的使用
1. goto
这个比较简单，比较容易理解，只要设置一个行标就行了：
例子：
int main ()
{
int i = 0, sum;
for (i = 0; i < 100; ++i) {
sum += i;
if (sum > 1000) goto JMP1;
}
JMP1:
printf("%d\n", i);
return 0;
}
{
int i = 0, sum;
for (i = 0; i < 100; ++i) {
sum += i;
if (sum > 1000) goto JMP1;
}
JMP1:
printf("%d\n", i);
return 0;
}
2. setjmp, longjmp
goto用起来是简单，但是存在一个先天缺陷：只能在同一个函数内使用。
有时候我们写一个代码，有两三层的函数嵌套，想要返回的时候就比较囧。
这时候用setjmp和longjmp就很happy。
例子：
#include <setjmp.h>
jmp_buf jmpbuf1;
void bar() {
printf("Hi, I'm bar!\n");
longjmp(jmpbuf1, 1);
}
void foo() {
printf("Hi, I'm foo!\n");
bar();
printf("Should never come here\n");
}
int main ()
{
int i = 0;
i = setjmp(jmpbuf1);
if (i == 0) { //setjmp第一次某个jmp_buf的时候返回0
foo();
}
else { //否则返回longjmp给出的值
printf("i = %d\n", i);
}
return 0;
}
jmp_buf jmpbuf1;
void bar() {
printf("Hi, I'm bar!\n");
longjmp(jmpbuf1, 1);
}
void foo() {
printf("Hi, I'm foo!\n");
bar();
printf("Should never come here\n");
}
int main ()
{
int i = 0;
i = setjmp(jmpbuf1);
if (i == 0) { //setjmp第一次某个jmp_buf的时候返回0
foo();
}
else { //否则返回longjmp给出的值
printf("i = %d\n", i);
}
return 0;
}
输出是:
Hi, I'm foo!
Hi, I'm bar!
i = 1
3. try-catch （在这里算是歪用了，呵呵）
这个是c++提供的语言特性，可以用于捕获throw语句抛出的异常，不仅可以在函数内使用，也可以跨函数～～
例子：
void bar() {
printf("Hi, I'm bar!\n");
throw 1;
}
void foo() {
printf("Hi, I'm foo!\n");
bar();
printf("Should never come here\n");
}
int main ()
{
try{
foo();
}
catch(int i) {
printf("i = %d\n", i);
}
return 0;
}
printf("Hi, I'm bar!\n");
throw 1;
}
void foo() {
printf("Hi, I'm foo!\n");
bar();
printf("Should never come here\n");
}
int main ()
{
try{
foo();
}
catch(int i) {
printf("i = %d\n", i);
}
return 0;
}
输出是：
Hi, I'm foo!
Hi, I'm bar!
i = 1
二、简单对比一下：
· goto，使用简单方便，看起来比其他两个更容易一点（有行标），但是只能在函数内跳转；
· setjmp和longjmp，稍微麻烦点，需要带个参数(jmp_buf，全局变量，或者传参)，好处是可以跨函数跳转，且可以根据setjmp的返回值得知从何处跳转。还有一个小缺陷就是，因为需要先执行setjmp以后才可以跳转，所以可以跳转的地方有一定限制，也使得代码看起来有点不够清晰。
· try-catch，C++有C没有，看起来结构比较清晰，不需要带额外的参数，抛出不同的值（和类型）方便判断来源。
三、重点考察一个问题：
如果有一个class，比如
class T
{
public:
~T() { printf("I'm dead >_<\n"); }
};
那么使用goto、setjmp或try-catch的时候是否存在问题？{
public:
~T() { printf("I'm dead >_<\n"); }
};
if (1) {
T t1;
goto JMP1;
}
JMP1: ;
有输出I'm dead >_<T t1;
goto JMP1;
}
JMP1: ;
jmp_buf jmpbuf1;
if (setjmp(jmpbuf1) == 0) {
T t1;
longjmp(jmpbuf1, 1);
}
else {
;
}
无输出if (setjmp(jmpbuf1) == 0) {
T t1;
longjmp(jmpbuf1, 1);
}
else {
;
}
try {
T t1;
throw 1;
}
catch(int i) {
;
}
有输出I'm dead >_<T t1;
throw 1;
}
catch(int i) {
;
}
所以在使用这三个东西的时候，一定要特别注意，建议在C++里头不使用setjmp，以免查错无门...
Dec
26
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#define P(a, b) printf(#b ": %" #a "\n", b)
#define Ps(a, c, b) P(a, (c)->b)
#define alloc(name, type, n) type *name = (type *) malloc(sizeof(type) * (n))
#define allocs(name, type, n) alloc(name, struct type, (n))
int main ()
{
time_t t1 = time(NULL);
P(ld, t1);
struct timeval tv1;
gettimeofday(&tv1, NULL);
Ps(ld, &tv1, tv_sec);
Ps(ld, &tv1, tv_usec);
/*
* //t1 += 8 * 3600;
* struct tm *tm1 = gmtime(&t1); //标准时间
*/
struct tm *tm1 = localtime(&t1); //本地时间
Ps(d, tm1, tm_sec);
Ps(d, tm1, tm_min);
Ps(d, tm1, tm_hour);
Ps(d, tm1, tm_mday);
Ps(d, tm1, tm_mon+1); //0-based
Ps(d, tm1, tm_year+1900); //从1900年开始, 0-based
allocs(tm2, tm, 1);
tm2->tm_sec = 0;
tm2->tm_min = 0;
tm2->tm_hour= 0;
tm2->tm_mday= 1;
tm2->tm_mon = 0;
tm2->tm_year= 70;
tm2->tm_isdst = 0;
time_t t2 = mktime(tm2);
//t2 += 3600 * 8; //mktime是本地时间
P(ld, t2);
P(s, asctime(tm1)); //标准时间
P(s, ctime(&t1)); //本地时间
alloc(buf, char, 100);
strftime(buf, 100, "%Y-%m-%d %H:%M:%S", tm1); //标准时间
P(s, buf);
strftime(buf, 100, "%F %T", tm1); //标准时间, 格式和上面的一样
P(s, buf);
return 0;
}
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#define P(a, b) printf(#b ": %" #a "\n", b)
#define Ps(a, c, b) P(a, (c)->b)
#define alloc(name, type, n) type *name = (type *) malloc(sizeof(type) * (n))
#define allocs(name, type, n) alloc(name, struct type, (n))
int main ()
{
time_t t1 = time(NULL);
P(ld, t1);
struct timeval tv1;
gettimeofday(&tv1, NULL);
Ps(ld, &tv1, tv_sec);
Ps(ld, &tv1, tv_usec);
/*
* //t1 += 8 * 3600;
* struct tm *tm1 = gmtime(&t1); //标准时间
*/
struct tm *tm1 = localtime(&t1); //本地时间
Ps(d, tm1, tm_sec);
Ps(d, tm1, tm_min);
Ps(d, tm1, tm_hour);
Ps(d, tm1, tm_mday);
Ps(d, tm1, tm_mon+1); //0-based
Ps(d, tm1, tm_year+1900); //从1900年开始, 0-based
allocs(tm2, tm, 1);
tm2->tm_sec = 0;
tm2->tm_min = 0;
tm2->tm_hour= 0;
tm2->tm_mday= 1;
tm2->tm_mon = 0;
tm2->tm_year= 70;
tm2->tm_isdst = 0;
time_t t2 = mktime(tm2);
//t2 += 3600 * 8; //mktime是本地时间
P(ld, t2);
P(s, asctime(tm1)); //标准时间
P(s, ctime(&t1)); //本地时间
alloc(buf, char, 100);
strftime(buf, 100, "%Y-%m-%d %H:%M:%S", tm1); //标准时间
P(s, buf);
strftime(buf, 100, "%F %T", tm1); //标准时间, 格式和上面的一样
P(s, buf);
return 0;
}
Dec
26
写代码的时候总是觉得printf打起来很麻烦，malloc的强制转换和sizeof很罗嗦，写几个宏，方便多了
#define P(a, b) printf(#b ": %" #a "\n", b)
#define Ps(a, c, b) P(a, (c)->b)
#define alloc(name, type, n) type *name = (type *) malloc(sizeof(type) * (n))
#define allocs(name, type, n) alloc(name, struct type, (n))
#define Ps(a, c, b) P(a, (c)->b)
#define alloc(name, type, n) type *name = (type *) malloc(sizeof(type) * (n))
#define allocs(name, type, n) alloc(name, struct type, (n))
Dec
22
工具->宏->Visual Basic编辑器，工程框中，右击Sheet1，插入模块，在模块1中加入如下代码
如果需要修改单元格的内容：
Sub iterate()
Dim row, col, i, j As Integer
Dim str, addr As String
row = ActiveSheet.UsedRange.rows.Count
col = ActiveSheet.UsedRange.Columns.Count
MsgBox row & " " & col, vbOKOnly
For i = 0 To row - 1
For j = 0 To col - 1
addr = Chr(65 + j) & Chr(i + 48 + 1)
MsgBox Range(addr).Text
Next
Next
End Sub
Dim row, col, i, j As Integer
Dim str, addr As String
row = ActiveSheet.UsedRange.rows.Count
col = ActiveSheet.UsedRange.Columns.Count
MsgBox row & " " & col, vbOKOnly
For i = 0 To row - 1
For j = 0 To col - 1
addr = Chr(65 + j) & Chr(i + 48 + 1)
MsgBox Range(addr).Text
Next
Next
End Sub
如果需要修改单元格的内容：
Range(addr).Select
ActiveCell.FormulaR1C1 = "ooxx"
ActiveCell.FormulaR1C1 = "ooxx"
Dec
13
由于上次和slyar同学提起这个问题，所以才想着还是自己再写一下，而且其实还有自己没解决的问题，希望能抛砖引玉。
剧透
本篇未解决的问题是：在n个数字里面，如果只有3个数字是没有凑对的，能否用O(n)的方法找出来？超过3个又远小于n个的情况呢？
===
WOJ上有2道连在一起的题目，很赞。
找不同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1202
找相同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1203
找不同：给你n*2+1个数，其中有n对是一样的，让你找出没有相同数字的那一个（真寂寞）。
如果我们能把所有的数字按大小排序，那么只要两个两个拿出来
第一次出现不一致的情况或者剩下最后一个数字的情况，就是找到寂寞数字了时候。
可是这样效率太低，就算用基数排序，那个常数也是够大的。
换个思路，由按位异或操作的性质可以知道 a | a = 0 且 (a | b) | c = a | (b | c)
也就是说，按位异或这个“按位模2加”操作的性质是同一个数与自身异或得0，且该操作是可交换的。
所以如果我们将所有数字串起来异或，其实就等于把所有数字排序后再串起来异或。
所有相同的数字想异或都得0，最后异或的结果就是最寂寞的那个。。
找相同：有一组数,很多很多个数,里面有一个数出现了超过一半次,请你把它找出来
可以证明，如果反复地执行这一操作【从这2*n+1个数里面取出两个数ab，如果a，b相同，放回去，如果a，b不同，都舍弃】直到剩下来的所有数字都相同（这一定是可以达到的）。所以只要设计一个最高效的方式来实现这个过程就行了。
最简单的方式是O(n)的，用栈。伪码如下
如果有同学看看1204的话，就会知道，这题是
继续找相同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1204
描述：有 n 个整数, 其中有且仅有一个整数出现了 >= n/2.0 次 (n<=500000)
跟前面那道题的只有一点点的区别，多了一种情况就是，有一个数字可能正好出现一半次。
直接用上面那种方法肯定没法处理了，但是只要稍微想想，其实还是很容易的：
用上面的方法处理前1～n-1个数字，到了最后一个数字的时候，看看和栈里面那个数字是不是一样
如果一样，说明这个数字出现了超过一半次，输出
如果不一样，那么栈里肯定只剩下一个数字，能出现一半次的，肯定是这两个数字之一，重新扫一次数组就行了。
WOJ关于找相同和不同的貌似就只有三道题，但是“继续”其实还没完。
继续找不同：有2n个数字，其中2n-2个数字是两两凑对的，剩下两个数字很寂寞，请找出来。
这题和前面的找不同也很像，解决方法是可以“复用”的。
以前的一篇日志里面有：http://www.felix021.com/blog/read.php?1243
解法是momodi给出的，将全部数字异或以后等到的C = A ^ B != 0 (若C==0则A==B，不符合要求)
然后扫描C的每一bit，如果bit[k] == 1，那么将C和给出的数据中所有bit[k] == 1的整数异或
得出的就是其中一个数字A，然后A ^ C = B
这种解法也是O(n)的，只需要扫描两遍，还是比较快的。
-------------------------------------
最后，重点：
如果是3个数，或者更多一些，有没有O(n)的解法？
当然，用O(n)的基数排序处理以后再遍历，的确是O(n)的效率，但是就是效率太低了，而且需要多次遍历。
假设数字的量超过1000亿，需要存放在硬盘中（也就是扫描次数越少越好），这该怎么办呢？
心里已经有些想法了，不过暂时不想写出来，再想想明白。
如果哪位大牛有好的想法，希望互相交流一下:)
剧透
本篇未解决的问题是：在n个数字里面，如果只有3个数字是没有凑对的，能否用O(n)的方法找出来？超过3个又远小于n个的情况呢？
===
WOJ上有2道连在一起的题目，很赞。
找不同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1202
找相同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1203
找不同：给你n*2+1个数，其中有n对是一样的，让你找出没有相同数字的那一个（真寂寞）。
如果我们能把所有的数字按大小排序，那么只要两个两个拿出来
第一次出现不一致的情况或者剩下最后一个数字的情况，就是找到寂寞数字了时候。
可是这样效率太低，就算用基数排序，那个常数也是够大的。
换个思路，由按位异或操作的性质可以知道 a | a = 0 且 (a | b) | c = a | (b | c)
也就是说，按位异或这个“按位模2加”操作的性质是同一个数与自身异或得0，且该操作是可交换的。
所以如果我们将所有数字串起来异或，其实就等于把所有数字排序后再串起来异或。
所有相同的数字想异或都得0，最后异或的结果就是最寂寞的那个。。
找相同：有一组数,很多很多个数,里面有一个数出现了超过一半次,请你把它找出来
可以证明，如果反复地执行这一操作【从这2*n+1个数里面取出两个数ab，如果a，b相同，放回去，如果a，b不同，都舍弃】直到剩下来的所有数字都相同（这一定是可以达到的）。所以只要设计一个最高效的方式来实现这个过程就行了。
最简单的方式是O(n)的，用栈。伪码如下
init stack(s)
for x in a[1..n]
if empty(s) or s.top() == x
s.push(x)
else
s.pop()
return s.top()
for x in a[1..n]
if empty(s) or s.top() == x
s.push(x)
else
s.pop()
return s.top()
如果有同学看看1204的话，就会知道，这题是
继续找相同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1204
描述：有 n 个整数, 其中有且仅有一个整数出现了 >= n/2.0 次 (n<=500000)
跟前面那道题的只有一点点的区别，多了一种情况就是，有一个数字可能正好出现一半次。
直接用上面那种方法肯定没法处理了，但是只要稍微想想，其实还是很容易的：
用上面的方法处理前1～n-1个数字，到了最后一个数字的时候，看看和栈里面那个数字是不是一样
如果一样，说明这个数字出现了超过一半次，输出
如果不一样，那么栈里肯定只剩下一个数字，能出现一半次的，肯定是这两个数字之一，重新扫一次数组就行了。
WOJ关于找相同和不同的貌似就只有三道题，但是“继续”其实还没完。
继续找不同：有2n个数字，其中2n-2个数字是两两凑对的，剩下两个数字很寂寞，请找出来。
这题和前面的找不同也很像，解决方法是可以“复用”的。
以前的一篇日志里面有：http://www.felix021.com/blog/read.php?1243
解法是momodi给出的，将全部数字异或以后等到的C = A ^ B != 0 (若C==0则A==B，不符合要求)
然后扫描C的每一bit，如果bit[k] == 1，那么将C和给出的数据中所有bit[k] == 1的整数异或
得出的就是其中一个数字A，然后A ^ C = B
这种解法也是O(n)的，只需要扫描两遍，还是比较快的。
-------------------------------------
最后，重点：
如果是3个数，或者更多一些，有没有O(n)的解法？
当然，用O(n)的基数排序处理以后再遍历，的确是O(n)的效率，但是就是效率太低了，而且需要多次遍历。
假设数字的量超过1000亿，需要存放在硬盘中（也就是扫描次数越少越好），这该怎么办呢？
心里已经有些想法了，不过暂时不想写出来，再想想明白。
如果哪位大牛有好的想法，希望互相交流一下:)
Dec
10
在int32(64位机器则为int64)的范围内的证书作为数组索引来存储数据的话，
在php中，会自动将这种可以转换成int的字符串转换成int作为索引使用。
以下面这一段脚本的输出来说明这个问题：
在php中，会自动将这种可以转换成int的字符串转换成int作为索引使用。
以下面这一段脚本的输出来说明这个问题：
<?php
$arr = array(
123 => 'a',
'123' => 'b',
0123 => 'c',
'0123' => 'd',
);
var_dump($arr);
?>
输出：
array(3) {
[123]=>
string(1) "b" //第一个123的a消失了，却出来了一个b，说明"123"在索引中被当作int处理了，并覆盖了之前123索引对应的值
[83]=> //0123是八进制的83
string(1) "c"
["0123"]=> //字符串
string(1) "d"
}
$arr = array(
123 => 'a',
'123' => 'b',
0123 => 'c',
'0123' => 'd',
);
var_dump($arr);
?>
输出：
array(3) {
[123]=>
string(1) "b" //第一个123的a消失了，却出来了一个b，说明"123"在索引中被当作int处理了，并覆盖了之前123索引对应的值
[83]=> //0123是八进制的83
string(1) "c"
["0123"]=> //字符串
string(1) "d"
}
Nov
24
zz from http://hi.baidu.com/whuisland/blog/item/17ba47ce6920340993457e4b.html
我是一个硬盘。
在一个普普通通的台式机里工作。别人总认为我们是高科技白领，工作又干净又体面，似乎风光得很。也许他们是因为看到洁白漂亮的机箱才有这样的错觉吧。其实象我们这样的小台式机，工作环境狭迫，里面的灰尘吓得死人。每天生活死水一潭，工作机械重复。跑跑文字处理看看电影还凑活，真要遇到什么大软件和游戏上上下下就要忙的团团转，最后还常常要死机。
我是一个硬盘。
在一个普普通通的台式机里工作。别人总认为我们是高科技白领，工作又干净又体面，似乎风光得很。也许他们是因为看到洁白漂亮的机箱才有这样的错觉吧。其实象我们这样的小台式机，工作环境狭迫，里面的灰尘吓得死人。每天生活死水一潭，工作机械重复。跑跑文字处理看看电影还凑活，真要遇到什么大软件和游戏上上下下就要忙的团团转，最后还常常要死机。
