Jan
18
今天windy在群里提出一个问题: 为什么下面这段代码输出了why?
因为已经有结果了,反推过去,很容易就会想到,php把字符串当作数组来用了。再通过
由于此结论仅为猜测,想进一步证实,但是对php代码不熟悉,翻了zend_hash.c等文件都没找到北,因此请教了雪候鸟大人,得知真正的处理代码位于
@ php-5.2.8/Zend/zend_execute.c +1026
具体实现的代码是
简单写了一点注释,只能大致看懂逻辑,其他边边角角的,暂时就没时间看了:'(
$arr = 'windy';
if (isset($arr['why'])) {
echo 'why';
}
if (isset($arr['why'])) {
echo 'why';
}
因为已经有结果了,反推过去,很容易就会想到,php把字符串当作数组来用了。再通过
echo $arr['why'];
验证一下,发现输出的是w, 也就是$arr{0}的值,可以大致得出一个结论:当把字符串当作数组使用的时候,会自动把索引转换成整形,然后再当作字符串的偏移量读取返回。由于此结论仅为猜测,想进一步证实,但是对php代码不熟悉,翻了zend_hash.c等文件都没找到北,因此请教了雪候鸟大人,得知真正的处理代码位于
@ php-5.2.8/Zend/zend_execute.c +1026
static void zend_fetch_dimension_address(temp_variable *result, zval **container_ptr, zval *dim, int dim_is_tmp_var, int type TSRMLS_DC)
这个函数的作用是:将container_ptr所指向的container这个容器中,索引为dim的值取出放在result所指定的内存中去。具体实现的代码是
1063 switch (Z_TYPE_P(container)) {
1064 zval **retval;
....
1099 case IS_STRING: { //如果这个容器是string
1100 zval tmp;
1101
1102 if (dim == NULL) {
1103 zend_error_noreturn(E_ERROR, "[] operator not supported for strings");
1104 }
1105
1106 if (Z_TYPE_P(dim) != IS_LONG) { //如果偏移量的类型不是LONG
1107 switch(Z_TYPE_P(dim)) {
1108 /* case IS_LONG: */
1109 case IS_STRING:
1110 case IS_DOUBLE:
1111 case IS_NULL:
1112 case IS_BOOL:
1113 /* do nothing */ //允许STRING, DOUBLE, NULL, BOOL四种类型
1114 break;
1115 default: //其他类型都报错
1116 zend_error(E_WARNING, "Illegal offset type");
1117 break;
1118 }
1119
1120 tmp = *dim;
1121 zval_copy_ctor(&tmp);
1122 convert_to_long(&tmp);
1123 dim = &tmp; //将原来的dim转换成LONG
1124 }
1125 switch (type) {
1126 case BP_VAR_R:
1127 case BP_VAR_IS:
1128 case BP_VAR_UNSET:
1129 /* do nothing... */
1130 break;
1131 default:
1132 SEPARATE_ZVAL_IF_NOT_REF(container_ptr);
1133 break;
1134 }
1135 if (result) { //存放结果
1136 container = *container_ptr;
1137 result->str_offset.str = container;
1138 PZVAL_LOCK(container);
1139 result->str_offset.offset = Z_LVAL_P(dim);
1140 result->var.ptr_ptr = NULL;
1141 if (type == BP_VAR_R || type == BP_VAR_IS) {
1142 AI_USE_PTR(result->var);
1143 }
1144 }
1145 return;
1146 }
1147 break;
1064 zval **retval;
....
1099 case IS_STRING: { //如果这个容器是string
1100 zval tmp;
1101
1102 if (dim == NULL) {
1103 zend_error_noreturn(E_ERROR, "[] operator not supported for strings");
1104 }
1105
1106 if (Z_TYPE_P(dim) != IS_LONG) { //如果偏移量的类型不是LONG
1107 switch(Z_TYPE_P(dim)) {
1108 /* case IS_LONG: */
1109 case IS_STRING:
1110 case IS_DOUBLE:
1111 case IS_NULL:
1112 case IS_BOOL:
1113 /* do nothing */ //允许STRING, DOUBLE, NULL, BOOL四种类型
1114 break;
1115 default: //其他类型都报错
1116 zend_error(E_WARNING, "Illegal offset type");
1117 break;
1118 }
1119
1120 tmp = *dim;
1121 zval_copy_ctor(&tmp);
1122 convert_to_long(&tmp);
1123 dim = &tmp; //将原来的dim转换成LONG
1124 }
1125 switch (type) {
1126 case BP_VAR_R:
1127 case BP_VAR_IS:
1128 case BP_VAR_UNSET:
1129 /* do nothing... */
1130 break;
1131 default:
1132 SEPARATE_ZVAL_IF_NOT_REF(container_ptr);
1133 break;
1134 }
1135 if (result) { //存放结果
1136 container = *container_ptr;
1137 result->str_offset.str = container;
1138 PZVAL_LOCK(container);
1139 result->str_offset.offset = Z_LVAL_P(dim);
1140 result->var.ptr_ptr = NULL;
1141 if (type == BP_VAR_R || type == BP_VAR_IS) {
1142 AI_USE_PTR(result->var);
1143 }
1144 }
1145 return;
1146 }
1147 break;
简单写了一点注释,只能大致看懂逻辑,其他边边角角的,暂时就没时间看了:'(
Jan
18
@ php-5.2.8/Zend/zend_builtin_functions.c
1120 #ifdef ZEND_TEST_EXCEPTIONS
1121 ZEND_FUNCTION(crash)
1122 {
1123 char *nowhere=NULL;
1124
1125 memcpy(nowhere, "something", sizeof("something"));
1126 }
1127 #endif
1121 ZEND_FUNCTION(crash)
1122 {
1123 char *nowhere=NULL;
1124
1125 memcpy(nowhere, "something", sizeof("something"));
1126 }
1127 #endif
Jan
11
更多内容,参见laruence大牛的这篇: http://www.laruence.com/2009/07/23/994.html
这么短一段代码,有这么多考究的地方,很值得学习:
1. 5381
2. hash << 5 + hash --> hash * 33 (times 33算法)
3. -= 8
4. switch, break
...
这么短一段代码,有这么多考究的地方,很值得学习:
1. 5381
2. hash << 5 + hash --> hash * 33 (times 33算法)
3. -= 8
4. switch, break
...
static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength)
{
register ulong hash = 5381;
/* variant with the hash unrolled eight times */
for (; nKeyLength >= 8; nKeyLength -= 8) {
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
}
switch (nKeyLength) {
case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 1: hash = ((hash << 5) + hash) + *arKey++; break;
case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
}
return hash;
}
{
register ulong hash = 5381;
/* variant with the hash unrolled eight times */
for (; nKeyLength >= 8; nKeyLength -= 8) {
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
}
switch (nKeyLength) {
case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 1: hash = ((hash << 5) + hash) + *arKey++; break;
case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
}
return hash;
}
Jan
4
在发现有atoi这个函数之后的一段时间里(converts a string to an integer, cppreference.com),每当我需要把integer转换成字符串的时候,我就会想当然地写上itoa,直到编译器告诉我,这个函数不存在。反复几次以后,我终于记住了没有itoa,记住了应该用sprintf(现在想想,是应该用snprintf才对)。直到今天我才意识到自己从来就没有仔细想过,为什么有atoi,却没有itoa。也许还是自己求知欲太低了。
原因其实很简单,简单地说,就是因为不好处理返回值。atoi, atof, atol等函数之所以可以在C标准库中存在,可以列出来的有两个必要条件:一,需求使然;二,返回值类型是基本类型,可以使用匿名变量传递。itoa之所以不在C标准库中,我觉得并不是没有需求,而是因为返回值是字符串,也就是char数组,处理起来比较纠结。
在C里面,字符串始终是个硬伤。如果非要设计这么一个函数,有三种可选的办法:
一,使用一个static的char数组(貌似printf就是这么做的吧)。这有2个问题,1是数组的长度是固定的(当然,简单处理的话可以认为int最多就那么几位,只要初始化某个足够的长度肯定就OK),2是每次调用会覆盖上次的结果,特别地,会导致非线程安全。
二,每次调用,在函数内部malloc一段空间,写入,返回该空间的首地址。存在问题是,分配的空间函数内无法自行释放,需要调用者安排一个free,而这个free是非常容易被忽略的,这就存在了潜在的内存泄漏风险。
三,要求传入一个分配好空间的指针,函数将转换结果写入。这样实际上就是sprintf的做法,重复造轮子。而且还要考虑内存越界访问的问题,再增加一个参数n,然后这就是snprintf做的事情....
综合起来的结果就是:太麻烦了,不实现。
最后,推荐云风的一篇文章,这里探讨了与以上内容比较相关的”一个 C 接口设计的问题“
http://blog.codingnow.com/2009/01/c_interface.html
原因其实很简单,简单地说,就是因为不好处理返回值。atoi, atof, atol等函数之所以可以在C标准库中存在,可以列出来的有两个必要条件:一,需求使然;二,返回值类型是基本类型,可以使用匿名变量传递。itoa之所以不在C标准库中,我觉得并不是没有需求,而是因为返回值是字符串,也就是char数组,处理起来比较纠结。
在C里面,字符串始终是个硬伤。如果非要设计这么一个函数,有三种可选的办法:
一,使用一个static的char数组(貌似printf就是这么做的吧)。这有2个问题,1是数组的长度是固定的(当然,简单处理的话可以认为int最多就那么几位,只要初始化某个足够的长度肯定就OK),2是每次调用会覆盖上次的结果,特别地,会导致非线程安全。
二,每次调用,在函数内部malloc一段空间,写入,返回该空间的首地址。存在问题是,分配的空间函数内无法自行释放,需要调用者安排一个free,而这个free是非常容易被忽略的,这就存在了潜在的内存泄漏风险。
三,要求传入一个分配好空间的指针,函数将转换结果写入。这样实际上就是sprintf的做法,重复造轮子。而且还要考虑内存越界访问的问题,再增加一个参数n,然后这就是snprintf做的事情....
综合起来的结果就是:太麻烦了,不实现。
最后,推荐云风的一篇文章,这里探讨了与以上内容比较相关的”一个 C 接口设计的问题“
http://blog.codingnow.com/2009/01/c_interface.html
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
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亿,需要存放在硬盘中(也就是扫描次数越少越好),这该怎么办呢?
心里已经有些想法了,不过暂时不想写出来,再想想明白。
如果哪位大牛有好的想法,希望互相交流一下:)