CodeFights Challenges Cipher_Zeroes

- 写在前面

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

  1. CodeWriting:根据题意,完成一个实现相应功能的函数(代码长度越短【空格、回车、注释不记长度】、耗时越少排名越高)
  2. 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,即:M1 = 1
M1是奇数,所以结果要加1,M2 = 2
最终结果为:210 = 102

- 分析

我的思路

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

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

代码如下(176个有效字符,为了方便,以后将省略中文,直接标数字):

1
2
3
4
5
6
7
8
9
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页的答案之后,有种脑洞被打开的感觉!!!

别人的思路

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

  1. 方法一(144)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //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”

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

  2. 方法二(129)

    1
    2
    3
    4
    5
    6
    7
    8
    //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 012 & 310 = 1

    • 当 e = 49 (‘1’)时
      e * 2 - 96 = 2
      1 10 00 01 00 00 00 00 00 012 & 310 = 0

    • 当 e = 56 (‘8’)时
      e * 2 - 96 = 16
      1 10 00 01 00 00 00 00 00 012 & 310 = 2

    • 当 e = 57 (‘9’)时
      e * 2 - 96 = 18
      1 10 00 01 00 00 00 00 00 012 & 310 = 1

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

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

    h + h % 2 * 2 - 1

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

  3. 方法三(124)

    1
    2
    3
    4
    5
    //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()方法能指定转换的基数。

-写在最后

有趣!!!

热评文章