CodeFights Challenges Cipher_Zeroes

- 写在前面

最近在玩CodeFights（一个进行在线编程PK的网站），这个网站蛮有意思的。相比于ACM的题目，这里的可能简单一点，不过做了几场感觉学到不少（因为可以看别人代码啊！！！）。主要玩法有两种：

CodeWriting：根据题意，完成一个实现相应功能的函数（代码长度越短【空格、回车、注释不记长度】、耗时越少排名越高）
Bugfix：给出一段有bug的代码，根据题意修复代码

为了记录和总结，以后如果有看到好的解法、思路都会在博客中分享出来！

- 题目 Cipher_Zeroes

题意

假如有如下前提：

0, 6, 9 这三个数中有一个可见的0
8 有两个可见的0
其他数字没有可见的0

给定一串数字N，假设M是N中可见0的个数，如果M是大于0的偶数，返回M-1的二进制形式；如果M是奇数，返回M+1的二进制形式；否则返回0。

补全如下函数（java 版）：

1
2
3

int Cipher_Zeroes(String N) {
}

样例

N = “565”
Cipher_Zeroes(N) = 10

解释：
565 中只有6有一个可见0，即：M₁ = 1
M1是奇数，所以结果要加1，M₂ = 2
最终结果为：2₁₀ = 10₂

- 分析

我的思路

根据前提统计可见0的个数
判奇偶
用系统函数Integer.parseInt(Integer.toBinaryString(s));返回结果。

为了使代码尽量短，判断0、6、9的时候不能用 d == 0 || d == 6 || d == 9 的形式（16个字符），因为都是3的倍数，可以用模3的形式判断 d % 3 == 0 && d != 3 （12个字符）

代码如下（176个有效字符，为了方便，以后将省略中文，直接标数字）：

int s, d;                                               //0-7字符
int Cipher_Zeroes(String N) {
    for(char c : N.toCharArray()) {                     //1-67字符
        d = c - '0';
        s += (d % 3 == 0 && d != 3 ? 1 : (d == 8 ? 2 : 0));
    }
    s += (s % 2 == 1 ? 1 : (s > 0 ? -1 : 0));           //2-25字符
    return Integer.parseInt(Integer.toBinaryString(s)); //3-50字符
}

当时已经有上百人提交答案了，而从solutions board看到最短代码才124个字符，差了1/3啊！离Challenges结束还有近1个小时，但是又想不到更好的解法，有点抓狂。在漫长地等待之后，满怀着期待与憧憬终于可以看到别人的思路了，简直比洞房花烛夜等待揭开新娘的面纱还要焦急(／‵Д′)／~ ╧╧

看了前3页的答案之后，有种脑洞被打开的感觉！！！

别人的思路

别人普遍使用的是查表法，不过有三种查表的方法，真他妈神奇！

方法一（144）

//from: sameerkhan2k
int c, r, d = 1;                                            //0-11
int Cipher_Zeroes(String n) {
    for (int i: n.getBytes())                               //1-54
        c += "1000001021".charAt(i - 48) - 48;
    for ( c += c % 2 < 1? -1: 1; c > 0; c /= 2, d *= 10)    //2、3-44
        r += d * (c & 1);
    return r;
}

第一步，这是最直观的字符串查表法。

0 ==> “1”
1 ==> “0”
2 ==> “0”
:
6 ==> “1”
7 ==> “0”
8 ==> “2”
9 ==> “1”

第二步和第三步合并了，没用系统函数而是手动计算的。

方法二（129）

//from: todayhumor
int h;
Integer I;                                              //0-14
int Cipher_Zeroes(String N) {
    for (int e:N.getBytes())                            //1-42
        h += 397313 >> e*2-96 & 3;
    return I.decode(I.toString(h>0?h+h%2*2 - 1:0,2));   //2、3-46
}

对于 397313 这个神奇的网站，哦不，神奇的数字，大家可能一头雾水，我们先把Magic Number 397313 转成二进制以后看看：1100001000000000001。
光看这个数其实还看不出什么，咱往后再瞧瞧。
e是每个字符的int值，从’0’到’9’对应48到57，随便代入两个值到 += 后面的表达式试试：

当 e = 48 (‘0’)时
e * 2 - 96 = 0
1 10 00 01 00 00 00 00 00 01₂ & 3₁₀ = 1

当 e = 49 (‘1’)时
e * 2 - 96 = 2
1 10 00 01 00 00 00 00 00 01₂ & 3₁₀ = 0

当 e = 56 (‘8’)时
e * 2 - 96 = 16
1 10 00 01 00 00 00 00 00 01₂ & 3₁₀ = 2

当 e = 57 (‘9’)时
e * 2 - 96 = 18
1 10 00 01 00 00 00 00 00 01₂ & 3₁₀ = 1

恍然大悟，这是神奇的二进制查表法！！
1100001000000000001 从右往左每两位组成表中的一个值，通过右移操作，移到表中的指定位置，用3₁₀ => 11₂这个mask取出对应位置的值。不过用二进制表的时候，有个字段长度的限制，最多只能用于64位的表（long）。

第二步的奇数+1，偶数-1实现的也蛮有意思的：

h + h % 2 * 2 - 1

才知道，Integer.decode()方法能将字符串型的数字转为数字。

方法三（124）

   //from: zerael
   int Cipher_Zeroes(String N) {
       Integer r = N.replaceAll("(8)|[^690]", "$1$1").length()+1^1; //0、1-56
       return r.valueOf(r.toString(r>0 ? r-1 : 0, 2));              //2、3-41
}

这人竟然用正则替换，弄了一个转换表出来！WTF！
这个正则替换的意思是：
当前字符如果是8，将其替换为88（\$1是使用第一个捕获的分组进行替换，也就是小括号中的8）；当前字符如果不是6、9、0（也就是1、2、3、4、5、7），将其替换为空（因为[^690]没有被包在分组中，所以\$1不起效）；其他（6、9、0）维持不变。

举两个例子：

“565”.replaceAll(“(8)|[^690]”, “\$1\$1”).length() + 1 ^ 1
==> “6”.length() + 1 ^ 1
==> 1 + 1 ^ 1
==> 3

“8200”.replaceAll(“(8)|[^690]”, “\$1\$1”).length() + 1 ^ 1
==> “8800”.length() + 1 ^ 1
==> 4 + 1 ^ 1
==> 4

第一行，其实是把第一步和第二步的一半合并了。
第二步的奇数+1，偶数-1实现方式：

(n + 1 ^ 1) - 1

才知道，Integer的toString()方法能指定转换的基数。

-写在最后

有趣！！！