经典算法面试题目-判断一个字符串中的字符是否唯一(1.1)
发布日期:2021-06-29 13:36:44
浏览次数:2
分类:技术文章
本文共 2355 字,大约阅读时间需要 7 分钟。
题目:
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。代码如下:
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;} 左移不改变原来的数值。移位的结果是:第一个操作数乘以2的幂,指数的值是由第二个数给出的。>
两个算法的本质其实是一样的,只不过一个用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;}
转载地址:https://chenhx.blog.csdn.net/article/details/51954734 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月15日 22时17分56秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
中国信通院发布《数据库发展研究报告(2021年)》(附报告和解读PPT下载)
2019-04-29
MySQL 开源工具集合
2019-04-29
西安openGauss Meetup成功举办,共建最佳学术创新平台
2019-04-29
实用教程丨官方下载Oracle各版本安装软件及补丁包
2019-04-29
相约金陵丨7月9日,云和恩墨大讲堂 · 南京站邀您共论数字化转型实践
2019-04-29
Maven进阶使用(Maven聚合工程)
2019-04-29
SSM框架-实现图片上传功能
2019-04-29
SSM框架-分页实现
2019-04-29
SSM框架-多条件组合查询+分页
2019-04-29
SSM框架-加密算法MD5的实现
2019-04-29
技术栈-拓展延伸-redis学习总结
2019-04-29
技术栈-redis学习总结
2019-04-29
spring学习总结
2019-04-29
让心爱的TA不再孤单——Python微信聊天机器人
2019-04-29
Python文件处理——遍历,匹配和处理文件
2019-04-29
Python帮你完成美术作业——图片转灰度,字符画,素描手绘风格
2019-04-29
Python爬虫实战——Quora网站文字自动化爬取和正则匹配筛选信息
2019-04-29
算圆周率的奇怪方式增加了——Python利用物理定律模拟计算圆周率
2019-04-29
数据库处理——用Python将IP转换为地理位置
2019-04-29