ITKeyword,专注技术干货聚合推荐

注册 | 登录

经典算法面试题目-判断一个字符串中的字符是否唯一(1.1)

qq_26525215 分享于 2016-07-19

推荐:算法与数据结构面试题(21)-在一个字符串中找到第一个只出现一次的字符

题目 在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。 解题思路 上一道题是求字符串中各个字符的个数,其实大同小异,这道题比上道题还

2020腾讯云共同战“疫”,助力行业复工(优惠前所未有!),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1053

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

题目:
Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?

实现一个算法来判断一个字符串中的字符是否唯一(即没有重复).不能使用额外的数据结构。 (即只使用基本的数据结构)

解答:
首先,你可以问面试官,构成字符串的字符集有多大?是ASCII字符,还是只是26个字母? 还是有更大的字符集,对于不同的情况,我们可能会有不同的解决方案。

如果我们假设字符集是ASCII字符,那么我们可以开一个大小为256的bool数组来表征每个字 符的出现。数组初始化为false,遍历一遍字符串中的字符,当bool数组对应位置的值为真, 表明该字符在之前已经出现过,即可得出该字符串中有重复字符。否则将该位置的bool数组 值置为true。代码如下:

推荐:算法与数据结构面试题(23)-将字符串转化为整形

题目 输入一个表示整数的字符串,把该字符串转换成整数并输出。 例如输入字符串"345",则输出整数 345。 个人理解 这个面试题不太 涉及算法和数据结构,主要考察你

bool isUnique1(string s)
{
    bool a[256];
    memset(a, 0, sizeof(a));
    int len = s.length();
    for(int i=0; i < len; ++i)
    {
        int v = (int)s[i];
        if(a[v]) return false;
        a[v] = true;
    }
    return true;
}

该算法的时间复杂度为O(n)。我们还可以通过位运算来减少空间的使用量。 用每一位表征相应位置字符的出现。对于ASCII字符,我们需要256位,即一个长度为8的int 数组a即可。这里的关键是要把字符对应的数字,映射到正确的位上去。比如字符’b’对应的 代码是98,那么我们应该将数组中的哪一位置为1呢?用98除以32,得到对应数组a的下标: 3。98对32取模得到相应的位:2。相应代码如下:

bool isUnique2(string s)
{
    int a[8];
    memset(a, 0, sizeof(a));
    int len = s.length();
    for(int i=0; i < len; ++i)
    {
        int v = (int)s[i];
        int idx = v/32, shift=v%32;

        if(a[idx] & (1 << shift)) return false;//<<左移不改变原来的数值。移位的结果是:第一个操作数乘以2的幂,指数的值是由第二个数给出的。
        //右边空出用0填补.在不溢出的情况下,每左移一位相当于乘以2
        a[idx] |= (1 << shift);
        //只要没有出现重复的,a[idx]是会从0开始一直加下去的,a[idx] & (1 << shift)一直会是0,从0加到2的31次方,接下来就是a[idx+1]的了。我是差不多这样理解的。
    }
    return true;
}

两个算法的本质其实是一样的,只不过一个用bool单元来表征字符出现,一个用位来表征。

完整代码如下:

#include <iostream>
#include <cstring>
using namespace std;

bool isUnique1(string s)
{
    bool a[256];
    memset(a, 0, sizeof(a));
    int len = s.length();
    for(int i=0; i < len; ++i)
    {
        int v = (int)s[i];
        if(a[v]) return false;
        a[v] = true;
    }
    return true;
}

bool isUnique2(string s)
{
    int a[8];
    memset(a, 0, sizeof(a));
    int len = s.length();
    for(int i=0; i < len; ++i)
    {
        int v = (int)s[i];
        int idx = v/32, shift=v%32;
        if(a[idx] & (1 << shift)) return false;
        a[idx] |= (1 << shift);
    }
    return true;
}
int main()
{
    string s1 = "i am hawstein.";
    string s2 = "abcdefghijklmnopqrstuvwxyzABCD1234567890";
    cout << isUnique1(s1) << " " << isUnique1(s2) << endl;
    cout << isUnique2(s1) << " " << isUnique2(s2) << endl;
    return 0;
}

如果字符集只是a-z(或是A-Z),那就更好办了,用位运算只需要一个整型数即可。

bool isUnique3(string s)
{
    int check = 0;
    int len = s.length();
    for(int i=0; i < len; ++i)
    {
        int v = (int)(s[i]-'a');
        if(check & (1 << v)) return false;
        check |= (1 << v);
    }
    return true;
}

推荐:一道面试题:从一个字符串中找出第一个不重复字符;算法一;

一道面试题:从一个字符串中找出第一个不重复字符;比如对于字符串abbbccdefafgg,其中d、e只出现一次,只需要找出d(第一个出现的不重复字符)即可 。 import jav

题目: Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures 实现一个算法来判断一个字符串中的字符是否唯一(

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。