FILL YOUR DISK 不指定

这程序写了好几次了,干脆贴出来吧~附上exe。
#include <stdio.h>
#include <stdlib.h>

char str[65536];

int main() {
    int i;
    for (i = 0; i < 65536; i++) str[i] = '1';
    str[65535] = '\0';
    i = 0;
    while (1) {
        i++;
        if (i % 3000 == 0) {
            sleep(1);
        }
        puts(str);
    }
    return 0;
}
下载文件 (已下载 次)

非递归二分查找一个元素在有序数组中应处的位置 不指定

@2019-03-19 STL里的lowerbound算法简单有效。

该元素在数组中不一定存在,只是要找一个i,使得 arr[i] <= t <= arr[i+1]。非递归的代码看起来真蛋疼。
//区间是 [s, e),左闭右开,类似STL。
int binsearch(int arr[], int t, int s, int e)
{
    int left = s, right = e, mid;
    while (left < right)
    {
        mid = left + (right - left) / 2;
        if (arr[mid] == t)
            return mid;
        else if (arr[mid] < t)
        {
                //right most    OR ...right here
            if (mid + 1 >= right || t < arr[mid + 1])
                return mid;
            else
                left = mid + 1;
        }
        else /* arr[mid] > t */
        {      //left most    OR ...right here
            if (mid - 1 < left || arr[mid - 1] <= t)
                return mid - 1;
            else
                //11.18.DELETED: right = mid - 1;
                right = mid; //[11.18.update]发现这里是个BUG……
        }
    }
    return -2; //bad range
}

Manacher's ALGORITHM: O(n)时间求字符串的最长回文子串 不指定

Translated to ENGLISH VERSION

源于这两篇文章:
http://blog.csdn.net/ggggiqnypgjg/article/details/6645824
http://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-palindrome-sub-string/

这个算法看了三天,终于理解了,在这里记录一下自己的思路,免得以后忘了又要想很久- -.

首先用一个非常巧妙的方式,将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度:在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#, aba变成 #a#b#a#。 为了进一步减少编码的复杂度,可以在字符串的开始加入另一个特殊字符,这样就不用特殊处理越界问题,比如$#a#b#a#(注意,下面的代码是用C语言写就,由于C语言规范还要求字符串末尾有一个'\0'所以正好OK,但其他语言可能会导致越界)。

下面以字符串12212321为例,经过上一步,变成了 S[] = "$#1#2#2#1#2#3#2#1#";

然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度(包括S[i],也就是把该回文串“对折”以后的长度),比如S和P的对应关系:
S  #  1  #  2  #  2  #  1  #  2  #  3  #  2  #  1  #
P  1  2  1  2  5  2  1  4  1  2  1  6  1  2  1  2  1
(p.s. 可以看出,P[i]-1正好是原字符串中回文串的总长度)

那么怎么计算P[i]呢?该算法增加两个辅助变量(其实一个就够了,两个更清晰)id和mx,其中 id 为已知的 {右边界最大} 的回文子串的中心,mx则为id+P[id],也就是这个子串的右边界。

然后可以得到一个非常神奇的结论,这个算法的关键点就在这里了:如果mx > i,那么P[i] >= MIN(P[2 * id - i], mx - i)。就是这个串卡了我非常久。实际上如果把它写得复杂一点,理解起来会简单很多:
//记j = 2 * id - i,也就是说 j 是 i 关于 id 的对称点(j = id - (i - id))
if (mx - i > P[j])
    P[i] = P[j];
else /* P[j] >= mx - i */
    P[i] = mx - i; // P[i] >= mx - i,取最小值,之后再匹配更新。

当然光看代码还是不够清晰,还是借助图来理解比较容易。

当 mx - i > P[j] 的时候,以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中,由于 i 和 j 对称,以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中,所以必有 P[i] = P[j],见下图。
点击在新窗口中浏览此图片

当 P[j] >= mx - i 的时候,以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中,但是基于对称性可知,下图中两个绿框所包围的部分是相同的,也就是说以S[i]为中心的回文子串,其向右至少会扩张到mx的位置,也就是说 P[i] >= mx - i。至于mx之后的部分是否对称,就只能老老实实去匹配了。
点击在新窗口中浏览此图片

对于 mx <= i 的情况,无法对 P[i]做更多的假设,只能P[i] = 1,然后再去匹配了。

于是代码如下:
//输入,并处理得到字符串s
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++) {
    p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
    while (s[i + p[i]] == s[i - p[i]]) p[i]++;
    if (i + p[i] > mx) {
        mx = i + p[i];
        id = i;
    }
}
//找出p[i]中最大的

OVER.

#UPDATE@2013-08-21 14:27
@zhengyuee 同学指出,由于 P[id] = mx,所以 S[id-mx] != S[id+mx],那么当 P[j] > mx - i 的时候,可以肯定 P[i] = mx - i ,不需要再继续匹配了。不过在具体实现的时候即使不考虑这一点,也只是多一次匹配(必然会fail),但是却要多加一个分支,所以上面的代码就不改了。

无聊的scanf 不指定

#include <stdio.h>

int main()
{
    int a, b;
    scanf("%d%*[, ]%d", &a, &b);
    printf("%d + %d = %d\n", a, b, a + b);
    return 0;
}

<= 1 2
=> 1 + 2 = 3

<= 1,2
=> 1 + 2 = 3

<= 1 , 2
=> 1 + 2 = 3

在PHP的扩展(extension)中调用其他的php函数 不指定

=> How to call a php function in a php extension

详细的说明参见:

[php-5.2.17]
    /Zend/zend_execute_API.c +623 & +636    call_user_function_ex
    /ext/standard/basic_functions.c +5174    PHP_FUNCTION(call_user_func_array)                                                                       
    /ext/pcre/pcre.c +833  (in function "preg_do_repl_func")

http://man.chinaunix.net/develop/php/php_manual_zh/html/zend.calling-user-functions.html

http://www.phpfreaks.com/forums/index.php?topic=10272.0

PHP_FUNCTION (caller)
{
    //call_user_function_ex
    zval *function, *str, *arr;
    zval **params[10];

    MAKE_STD_ZVAL(function);
    ZVAL_STRING(function, "var_dump", 1);  //I wanna call var_dump

    /*  //pass a string as its param
    MAKE_STD_ZVAL(str);
    ZVAL_STRING(str, "Hello, world!", 1);

    params[0] = &str;
    */

    //pass an array as its param
    MAKE_STD_ZVAL(arr);
    array_init(arr);
    add_assoc_string(arr, "name", "felix021", 1);
    params[0] = &arr;

    zval *ret;
    if (call_user_function_ex(CG(function_table), NULL,
            function, &ret, 2, params, 0, NULL TSRMLS_CC) != FAILURE)
    {
        *return_value = *ret;
        zval_copy_ctor(return_value);
        zval_ptr_dtor(&ret);
        return;
    }
    else {
        RETURN_FALSE;
    }
}

使用PHP的mcrypt模块进行DES加密/解密 不指定

网上摘下来的代码,没什么好说的了(因为那一堆 mcrypt_* 函数太乱了,用就是了):
<?php

class DES
{
    public static function pkcs5_pad ($text, $blocksize) {
        $pad = $blocksize - (strlen($text) % $blocksize);
        return $text . str_repeat(chr($pad), $pad);
    }

    public static function pkcs5_unpad($text) {
        $pad = ord($text{strlen($text)-1});
        if ($pad > strlen($text)) {
            return false;
        }
        if (strspn($text, chr($pad), strlen($text) - $pad) != $pad) {
            return false;
        }
        return substr($text, 0, -1 * $pad);
    }

    public static function encrypt($key, $data) {
        $size = mcrypt_get_block_size('des', 'ecb');
        $data = DES::pkcs5_pad($data, $size);
        $td = mcrypt_module_open('des', '', 'ecb', '');
        $iv = @mcrypt_create_iv(mcrypt_enc_get_iv_size($td), MCRYPT_RAND);
        @mcrypt_generic_init($td, $key, $iv);
        $data = mcrypt_generic($td, $data);
        mcrypt_generic_deinit($td);
        mcrypt_module_close($td);
        return $data;
    }

    public static function decrypt($key, $data) {
        $td = mcrypt_module_open('des','','ecb','');
        $iv = @mcrypt_create_iv(mcrypt_enc_get_iv_size($td), MCRYPT_RAND);
        $ks = mcrypt_enc_get_key_size($td);
        @mcrypt_generic_init($td, $key, $iv);
        $decrypted = mdecrypt_generic($td, $data);
        mcrypt_generic_deinit($td);
        mcrypt_module_close($td);
        $result = DES::pkcs5_unpad($decrypted);
        return $result;
    }
}

/*  test code

$in = "04fMaWegkH1/BL9CNYxgusFpYK8wdraBX06mPiRmxJP+uVm31GQvyw==";
$des = base64_decode($in);
echo DES::decrypt("12345678", $des);
echo "\n";

$in = "cea3e8e1659582206e0be32539729e9f";
$des = DES::encrypt("12345678", $in);
$out = base64_encode($des);
echo $out;
echo "\n";

// */

?>

使用Linux libc/glibc提供的ecb_crypt来进行DES加密/解密 不指定

在"libc 4.6.27 and later, and glibc 2.1 and later"中,提供了 rpc/des_crypt.h这个头文件,其中有几个函数,比如:
void des_setparity(char *key);
int ecb_crypt(char *key, char *data, unsigned datalen, unsigned mode);

这个函数可以用于DES的加密/解密。详情可以看 man des_crypt ,以下说 ecb_crypt() 函数几个比较坑爹的地方:

1. 虽然提供给DES的密钥(key)是8个字节,但是实际上只用到了其中的56个bit,另外8个bit是用于奇偶校验的(从用户处取得一个64位长的密码key ,去除64位密码中作为奇偶校验位的第8、16、24、32、40、48、56、64位,剩下的56位作为有效输入密钥)。所以需要调用 des_setparity(key) 来处理key。

2. 必须在data后面补上1~8个 "\x8",以将datalen补齐到8的倍数。对,是1~8个。假设要加密的data是32个字节,需要先补齐到40个字节。

3. 传给des_setparity()的key和给ecb_crypt的data会被直接改写。

以下是样例代码:
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <rpc/des_crypt.h>

//注意:这里有个坑,需要保证 data 可以存放的字符串在后面补了\8 不会越界。否则结果是不确定的。
void des_encrypt(const char *key, char *data, int len)
{
    char pkey[8];
    strncpy(pkey, key, 8);
    des_setparity(pkey);
    do {
        data[len++] = '\x8';
    } while (len % 8 != 0);
    ecb_crypt(pkey, data, len, DES_ENCRYPT);
}

void des_decrypt(const char *key, char *data, int len)
{
    char pkey[8];
    strncpy(pkey, key, 8);
    des_setparity(pkey);
    ecb_crypt(pkey, data, len, DES_DECRYPT);
}

int main(int argc, char *argv[])
{
    /*
    * char data[4096] = "cea3e8e1659582206e0be32539729e9f";
    * des_encrypt("12345678", data, strlen(data));
    * printf("%s\n", data);
    * //should be "04fMaWegkH1/BL9CNYxgusFpYK8wdraBX06mPiRmxJP+uVm31GQvyw=="
    */

    char data[4096];
    int i = 0;
    while (EOF != (data[i] = fgetc(stdin))) {
        i++;
    }
    data[i] = '\0';
    des_decrypt("12345678", data, strlen(data));
    printf("%s\n", data);
    /*
    * echo -n 04fMaWegkH1/BL9CNYxgusFpYK8wdraBX06mPiRmxJP+uVm31GQvyw== | base64 -d | ./des
    * should be "cea3e8e1659582206e0be32539729e9f"
    */
    return 0;
}

话说PHP的call_user_func_array 不指定

前些天写的程序在上线的时候出现BUG了,错误提示就是call_user_func_array无法调用指定的函数。

代码大概是这样的
class foo {
  public static function bar($arg1, $arg2) {
    //do sth.
  }
}

call_user_func_array("foo:bar", array(1, 2));


追了一下发现是PHP版本的问题,开发环境使用的是php 5.2.17,而线上环境是旧版本的5.1.6。5.1版的php的call_user_func / call_user_func_array函数没法调用类的静态函数,所以出现了这个问题。

没有很好的解决方法,大致就是

1. 升级PHP(最后我们是这么做的)

2. 使用字符串拼出一段php代码,然后用eval来执行。很挫,但是也能用。