- 写在前面
最近在玩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 版):
样例
N = “565”
Cipher_Zeroes(N) = 10解释:
565 中只有6有一个可见0,即:M1 = 1
M1是奇数,所以结果要加1,M2 = 2
最终结果为:210 = 102
- 分析
我的思路
- 根据前提统计可见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个有效字符,为了方便,以后将省略中文,直接标数字):
当时已经有上百人提交答案了,而从solutions board看到最短代码才124个字符,差了1/3啊!离Challenges结束还有近1个小时,但是又想不到更好的解法,有点抓狂。在漫长地等待之后,满怀着期待与憧憬终于可以看到别人的思路了,简直比洞房花烛夜等待揭开新娘的面纱还要焦急(/‵Д′)/~ ╧╧
看了前3页的答案之后,有种脑洞被打开的感觉!!!
别人的思路
别人普遍使用的是查表法,不过有三种查表的方法,真他妈神奇!
方法一(144)
1234567891011//from: sameerkhan2kint c, r, d = 1; //0-11int Cipher_Zeroes(String n) {for (int i: n.getBytes()) //1-54c += "1000001021".charAt(i - 48) - 48;for ( c += c % 2 < 1? -1: 1; c > 0; c /= 2, d *= 10) //2、3-44r += d * (c & 1);return r;}第一步,这是最直观的字符串查表法。
0 ==> “1”
1 ==> “0”
2 ==> “0”
:
6 ==> “1”
7 ==> “0”
8 ==> “2”
9 ==> “1”第二步和第三步合并了,没用系统函数而是手动计算的。
方法二(129)
12345678//from: todayhumorint h;Integer I; //0-14int Cipher_Zeroes(String N) {for (int e:N.getBytes()) //1-42h += 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()方法能将字符串型的数字转为数字。
方法三(124)
12345//from: zeraelint Cipher_Zeroes(String N) {Integer r = N.replaceAll("(8)|[^690]", "$1$1").length()+1^1; //0、1-56return 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()方法能指定转换的基数。
-写在最后
有趣!!!