h**o
发帖数: 548 | 1 给一个char* str, 给一个 char pattern, 要求找出8bit pattern在str里出现几次。
e.g. str is "13" 就是0000，0001，0000，0011，pattern is 1000,0001 输出结果就
是1次。
int countPattern(char* str, char pattern); | L*******r
发帖数: 119 | 2 除了转成bitarray，还有啥好方法？太复杂的容易错。。
。
【在 h**o 的大作中提到】
: 给一个char* str, 给一个 char pattern, 要求找出8bit pattern在str里出现几次。
: e.g. str is "13" 就是0000，0001，0000，0011，pattern is 1000,0001 输出结果就
: 是1次。
: int countPattern(char* str, char pattern);
| f*********d
发帖数: 140 | 3 比较基础的好题
八bit是关键 转成整数 对母串 用rolling hash的思路循环取八位 除二去掉最最高位
加入最低位 求值后和模式串对应的数字比较
。
【在 h**o 的大作中提到】
: 给一个char* str, 给一个 char pattern, 要求找出8bit pattern在str里出现几次。
: e.g. str is "13" 就是0000，0001，0000，0011，pattern is 1000,0001 输出结果就
: 是1次。
: int countPattern(char* str, char pattern);
| h**o
发帖数: 548 | 4 没见过这题。 我当时这样写的。
请问哪里有真确答案？
int countByte(char* str1, char* str2, char pattern){
int cnt = 0;
char ch;
for (int i = 0; i < 8; i++){
ch = str1<>(8-i);
if (ch ^ pattern==0) cnt++; //^ means XOR
}
return cnt;
}
int countPattern(char* str, char pattern){
if (!str || *str == ‘ | h**o
发帖数: 548 | 5 没见过这题。 我当时这样写的。
请问哪里有真确答案？
int countPattern(char* str, char pattern){
if(!str) return 0;
int sum = 0;
while(!(str+1) && *(str+1)!= 0){
sum += countByte(str, str+1, pattern);
str++;
}
return sum;
}
int countByte(char* str1, char* str2, char pattern){
int cnt = 0;
char ch;
for (int i = 0; i < 8; i++){
ch = str1<> (8-i);
if (ch ^ pattern==0) cnt++;
}
return cnt;
} | s***e
发帖数: 403 | 6 我也给个解。
这个题目的关键其实是两个字符之间的bitwise roll。因为要检验的只有8个bits。所
以只要每次取两个字符c1和c2，然后依次roll bits即可。
int countPattern2(char c1, char c2, char pattern)
{
int count = 0;
static const char mask = (1 << 7);
int i;
for(i = 0; i < 8; ++i)
{
if (c1 == pattern)
++count;
c1 <<= 1;
c1 += ((c2 & mask) ? 1 : 0);
c2 <<= 1;
}
return count;
}
int countPattern(const char* str, char pattern)
{
const s_length = strlen(str);
int i;
int count = 0;
for(i = 0; i < s_length - 1; ++i)
count += countPattern2(str[i], str[i + 1], pattern);
if (str[s_length - 1] == pattern)
++count;
return count;
} | n****e
发帖数: 678 | 7 我觉得这个想法是好的。
这code有问题：
1， 第2个function里面，对指针变量进行位移？
2， 右移的时候，要考虑最高位补进来的是1.
【在 h**o 的大作中提到】
: 没见过这题。 我当时这样写的。
: 请问哪里有真确答案？
: int countPattern(char* str, char pattern){
: if(!str) return 0;
: int sum = 0;
:
: while(!(str+1) && *(str+1)!= 0){
: sum += countByte(str, str+1, pattern);
: str++;
: }
| h**o
发帖数: 548 | 8 1， 第2个function里面，对指针变量进行位移？
我用i位移的。没觉的油问题。
2. 是个问题， 结论是没事别右移。只能左移。
谢谢
【在 n****e 的大作中提到】
: 我觉得这个想法是好的。
: 这code有问题：
: 1， 第2个function里面，对指针变量进行位移？
: 2， 右移的时候，要考虑最高位补进来的是1.
|
|
