c – 找出2个相似或不相似的字符串

发布时间：2020-12-16 09:37:02 所属栏目：百科来源：网络整理

导读：规则： 2个字符串,a和b,它们都由ASCII字符和非ASCII字符组成(例如,中文字符gbk编码). If the non-ASCII chars contained in b also show up in a and no less than the times they appear in b,then we say b is similar with a. 例如： a = "ab中ef日jkl中

规则：
2个字符串,a和b,它们都由ASCII字符和非ASCII字符组成(例如,中文字符gbk编码).

If the non-ASCII chars contained in b also show up in a and no less than the times they appear in b,then we say b is similar with a.

例如：

a = "ab中ef日jkl中本"  //non-ASCII chars:'中'(twice),'日'(once),'本'(once)
b = "bej中中日"  //non-ASCII chars:'中'(twice),'日'(once)
c = 'lk日日日'   //non-ASCII chars:'日'(3 times,more than twice in a)

根据规则,b与a类似,但c不是.
这是我的问题：
我们不知道a和b中有多少非ASCII字符,可能很多.
因此,为了找出a和b中出现非ASCII字符的次数,我应该使用哈希表来存储它们的出现时间吗？
以字符串a为例：

[non-ASCII's hash-value]:[times]
     中's hash-val      : 2
     日's hash-val      : 1
     本's hash-val      : 1

检查字符串b,如果我们在b中遇到非ASCII字符,则对其进行哈希并检查哈希表,如果字符串存在于哈希表中,则其出现时间减1.
如果出现时间小于0(-1),那么我们说b与a不相似.

还是有更好的方法吗？

PS：
我逐字节读取字符串,如果字节小于128,那么我将其作为ASCII字符,否则我将其作为非ASCII字符(多字节)的一部分.
我正在做的是找出非ASCII字符.
这样对吗？

解决方法

你问过两个问题：

>我们可以使用哈希表来计算非ASCII字符吗？答：当然.在读取字符(而不是字节)时,请检查代码点.对于大于127的任何代码点,将其放入计数哈希表中.对于字符c,如果c不在表中,则添加(c,1),如果c已经在表中,则将(c,x)更新为(c,x 1).
>有没有更好的方法来解决这个问题,而不是在你运行b时递增计数和递减计数的方法？如果您的哈希表实现提供了几乎O(1)访问,那么我怀疑不是.您正在查看字符串中的每个字符一次,并且对于每个字符,您正在执行哈希表插入或查找以及加法或减法,并检查0.对于未排序的字符串,您必须查看所有字符无论如何,这两个字符串,所以你认为,你已经给出了最好的解决方案.

面试官可能正在寻找你说的话,“嗯,如果这些字符串实际上是大量不适合记忆的文件,我该怎么办？”或者你问“好的字符串排序了吗？因为如果它们是,我可以更快地做到……”.

但现在让我们说这些字符串很大.您在内存中存储的唯一内容是哈希表. Unicode只有大约100万个代码点,并且你为每个代码点存储一个整数,所以即使你从千兆字节大小的文件中获取数据,你的哈希表只需要大约4MB左右(或者是这个的一小部分,因为它会是开销).

在没有任何其他条件的情况下,您的算法很好.事先对字符串进行排序并不好;它占用更多内存,而不是线性时间操作.

附录

由于你的原始注释提到了char类型而不是wchar_t,我想我会展示一个使用宽字符串的例子.见http://codepad.org/B3MXOgqc

希望有所帮助.

附录2

好的,这是一个C程序,它准确地显示了如何通过宽字符串并在角色级别工作：

http://codepad.org/QVX3QPat

这是一个非常短的程序,所以我也将它贴在这里：

#include <stdio.h>
#include <string.h>
#include <wchar.h>

char *s1 = "abd中日";
wchar_t *s2 = L"abd中日";

int main() {
    int i,n;
    printf("length of s1 is %dn",strlen(s1));
    printf("length of s2 using wcslen is %dn",wcslen(s2));
    printf("The codepoints of the characters of s2 aren");
    for (i = 0,n = wcslen(s2); i < n; i++) {
        printf("%02xn",s2[i]);
    } 
    return 0;
}

输出：

length of s1 is 9
length of s2 using wcslen is 5
The codepoints of the characters of s2 are
61
62 
64
4e2d
65e5

我们可以从中学到什么？几件事：

>如果对CJK字符使用普通旧字符,则字符串长度将是错误的.
>要在C中使用Unicode字符,请使用wchar_t
>字符串文字对于宽字符串具有前导L.

在这个例子中,我定义了一个带有CJK字符的字符串,并使用了wchar_t和一个带有wcslen的for循环.请注意,我正在使用真实字符,而不是BYTES,所以我得到正确的字符数,即5.现在我打印出每个代码点.在你的面试问题中,你将看看代码点是否是> = 128.我用Hex显示它们,就像文化一样,所以你可以寻找> 0x7F的.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!