有道难题

    有道的工程师闲暇之余，将Base64编码改成了Base4编码，即把每个8Bit的字节转换成4个2Bit的字节，然后以4个字符来代替。编码和字符的对应方案如下：
    00 ---- a
    01 ---- o
    10 ---- d
    11 ---- 空格
    这样，编码后的字符串就只会含有字符‘d','a','o'和空格。

    例如字符y ,其ASCII码是121，对应的二进制串是01111001，这样分成 01 11 10 01四块后，用Base4编码后的字符串为"o do"。

    有道的工程师很好奇，按照这种编码方式，编码后的字符串中含有多少个完整的dao呢？一个完整的dao由连续的‘d','a','o'三个字符组成。
输入
    第一行有一个正整数n，代表接下来有n个待编码的原串。（1 <= n <= 10)
    接下来有n行，每行有一个长度不超过106的原串，原串中的字符可能为ASCII码中除换行符以外的任意可见字符。
输出
    共有n行，每行为一个整数k, 表示输入数据中对应的原串用Base4编码后含有多少个完整的dao。
样例输入

    2
    www.youdao.com
    dict.youdao.com

样例输出

    1
    1





以上是“有道难题” 的一个题目，限定用Java或者C系列的语言写，那些东西我都差不多忘光了，实在写不出来。稍微熟悉一点的就是Ruby了，写了个大概的（不完整），希望大家多提意见，也把自己的代码拿出来亮亮。

s="www.youdao.com/youdao"

t=s.unpack("B*")
g=[]
t=t.split(//)
t.each_with_index do |x,i|
	if i%2!=0
	 g<<[t[i-1],x]
	end
end

g.map!{|x|x.to_s}
p g
g.map! do |x|
	case x
	when "00"
	  "a"	  
	when "01"
	   "o"
	when "10"
	   "d"
	when "11"
	   " "	   
	end
end

	p g.to_s.scan(/dao/).size

 

 

评论

18 楼 googya 2010-06-07  

jasongreen 写道

googya 写道

相比之下，googya的代码显得相当的笨拙！
部分原因是不熟悉unpack这个方法！用的是，最直接、最原始的想法

用自己的名字替换第一人称是相当伪娘的做法

你不说我还没什么感觉，现在越想越不对劲。

17 楼 Hooopo 2010-06-07  

jasongreen 写道

googya 写道

相比之下，googya的代码显得相当的笨拙！
部分原因是不熟悉unpack这个方法！用的是，最直接、最原始的想法

用自己的名字替换第一人称是相当伪娘的做法

原来如此，怪不得看到别人这么称呼自己的时候觉得怪怪的呢....

16 楼 jasongreen 2010-06-07  

googya 写道

相比之下，googya的代码显得相当的笨拙！
部分原因是不熟悉unpack这个方法！用的是，最直接、最原始的想法

用自己的名字替换第一人称是相当伪娘的做法

15 楼 googya 2010-06-03  

savon_cn 写道

我觉得算法的题目，最好能讲一下思路，代码不好懂的
我的思路就是
  1.先把字符串转成01。。。的串
  2.查找100001的串，看它出现的位置，如果 pos%2=0，那么就算1个，这样累加

是的，我的也是这样的思路，很直观的一种想法。

14 楼 savon_cn 2010-06-03  

我觉得算法的题目，最好能讲一下思路，代码不好懂的
我的思路就是
  1.先把字符串转成01。。。的串
  2.查找100001的串，看它出现的位置，如果 pos%2=0，那么就算1个，这样累加

13 楼 googya 2010-06-02  

楼上的结果没问题！
性能上应该也没有什么问题。比Ruby写的方式要快。

12 楼 litianzzk 2010-06-02  

试试C++的，n久不写了，没怎么测试过：

#include <iostream>
using namespace std;

const unsigned char daos_in_a_byte[2] = {
    0x84, //10000100
    0x21  //00100001
}; 
const unsigned char daos_in_a_byte_mask[2] = {
    0xFC, //11111100
    0x3F  //00111111
};
const unsigned short daos_in_a_word[2] = {
    0x4008, //00001000_01000000
    0x1002  //00000010_00010000
}; 
const unsigned short daos_in_a_word_mask[2] = {
    0xC00F, //00001111_11000000
    0xF003  //00000011_11110000
};

int count_in_byte(const unsigned char byte)
{
    return ((byte & daos_in_a_byte_mask[0]) == daos_in_a_byte[0]) ||
            ((byte & daos_in_a_byte_mask[1]) == daos_in_a_byte[1]);
}

int count_in_word(const unsigned short word)
{
    return ((word & daos_in_a_word_mask[0]) == daos_in_a_word[0]) ||
            ((word & daos_in_a_word_mask[1]) == daos_in_a_word[1]);
}

int count_dao(const unsigned char* str)
{
    int result = 0;
    for (int i = 0; *(str + i) != 0; ++i)
    {
        result += count_in_byte(*(str + i));
        if (*(str + i + 1) != 0)
        {
            result += count_in_word(*(const unsigned short * )(str + i));
        }
    }
    return result;
}

int main(int argc, char** argv) {
    char* str1 = "www.youdao.com";
    char* str2 = "dict.youdao.com";
    cout << count_dao((const unsigned char * )str1) << endl;
    cout << count_dao((const unsigned char * )str2) << endl;
    return 0;
}

11 楼 eric_kong 2010-06-01  

直接用KMP算法不就行了吗？

10 楼 shuiguozheng 2010-05-31  

sevk 写道

为了不超时,只能分段统计.
每段的连接处也要考滤10 00 01 .

  你的图像太有诱惑力了

9 楼 huanyun007 2010-05-31  

public static void main(String[] args) {
List<String> lines = new ArrayList<String>();
char[] codes = new char[] { 'a', 'o', 'd', ' ' };
lines.add("www.youdao.com");
lines.add("dict.youdao.com");
for (String line : lines) {
if (line.length() == 0) {
continue;
}
int size = 0;
char[] queue = new char[] { ' ', ' ', ' ' };
int index = 0;
char[] chars = line.toCharArray();
for (int i = 0; i < chars.length; i++) {
queue[index] = codes[(chars[i] >>> 6) & 0x3];
index = (index + 1) % queue.length;
size += check(queue, index) ? 1 : 0;

queue[index] = codes[(chars[i] >>> 4) & 0x3];
index = (index + 1) % queue.length;
size += check(queue, index) ? 1 : 0;

queue[index] = codes[(chars[i] >>> 2) & 0x3];
index = (index + 1) % queue.length;
size += check(queue, index) ? 1 : 0;

queue[index] = codes[chars[i] & 0x3];
index = (index + 1) % queue.length;
size += check(queue, index) ? 1 : 0;
}
System.out.println(size);
}
}

public static boolean check(char[] chars, int index) {
return chars[index] == 'd' && chars[(index + 1) % chars.length] == 'a'
&& chars[(index + 2) % chars.length] == 'o';
}

#写的有点复杂
按上面的思路不过还可以进行优化，比如可以按照KMP相关的思路减少check次数

8 楼 sevk 2010-05-31  

为了不超时,只能分段统计.
每段的连接处也要考滤10 00 01 .

7 楼 googya 2010-05-31  

beneo 写道

10 的 6 次方的字符串

凡是生成字符串，再去检查出dao字符串的，肯定都得超时

确实，这个问题都还没有考虑！！！

6 楼 beneo 2010-05-31  

10 的 6 次方的字符串

凡是生成字符串，再去检查出dao字符串的，肯定都得超时

5 楼 googya 2010-05-31  

googya 写道

相比之下，googya的代码显得相当的笨拙！
部分原因是不熟悉unpack这个方法！用的是，最直接、最原始的想法

我发现我完全的错了。位数搞错了。我的方法，每个字符产生的只有7位，而应当是8位。

4 楼 googya 2010-05-31  

相比之下，googya的代码显得相当的笨拙！
部分原因是不熟悉unpack这个方法！用的是，最直接、最原始的想法

3 楼 Hooopo 2010-05-31  

"youdao.com".unpack("B*").to_s.scan("dao".unpack("B*").to_s).size

PS:秦汉唐宋明的unpack("B*")很简洁。。
"youdao.com".unpack("C*").map{|x| "%08b" % x}.join也可以实现同样效果，不过罗嗦了点~

这里也有一个Base64编码相关的帖子：http://www.iteye.com/topic/286240

按照楼主的思路写了一个ruby版的实现:

def encode(str)
  keys = "abcdefghijklmnopqrstuvwxyz234567"
  str.unpack("C*").map{|b| "%08b" % b}.join.scan(/\d{1,5}/).map{|x| "0" * 3 + x.ljust(5,"0")}.map{|y| keys[y.to_i(2)].chr}.join
end

2 楼 googya 2010-05-31  

秦汉唐宋明 写道

 table = {'00'=>'a','01'=>'o','10'=>'d','11'=>' '}
 "abcedefgh".unpack('B*')[0].gsub!(/../){|s| table[s]}.scan('dao').length

有1年没写ruby代码了，练习一下

very nice,very smart!

1 楼 秦汉唐宋明 2010-05-31  

 table = {'00'=>'a','01'=>'o','10'=>'d','11'=>' '}
 "abcedefgh".unpack('B*')[0].gsub!(/../){|s| table[s]}.scan('dao').length

有1年没写ruby代码了，练习一下