欢迎光临Software MyZone,有问题可留言或到站点论坛发帖,争取第一时间帮忙解决 || 站点论坛:火龙论坛 || 淘宝小店:应小心的易淘屋 【欢迎大家提建设性意见】

每日算法(一)转

欢迎热爱编程的朋友们参与到cocos2d-x编程中,为了给大家提供良好的交流环境,网站以开启QQ群
Software MyZone:66202765(群号,欢迎加入,若满,请加1群)
Software MyZone 1群(2dx):286504621
【加群请写:Software MyZone或者是firedragonpzy】
淘宝店:【应小心的易淘屋】初次开店,大家多多支持……
群论坛:火龙论坛正试运营阶段,欢迎大家多提些建设性意见……
摘自:http://hawstein.com/posts/1.1.html

题目:

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

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

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


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;
a[idx] |= (1 << shift);
}
return true;
}

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

完整代码如下:

#include
#include
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;
}

全书题解目录:

Cracking the coding interview—问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview

Tags: ,