【题目】
Chapter 1 | Arrays and Strings
原文:
1.1 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。
该算法的时间复杂度为O(n)。
【思路二】
我们还可以通过位运算来减少空间的使用量。其实就是用所谓的Bit-map的原理来存储。就是用一个bit位来标记某个元素对应的Value,在这就是该元素是否出现的bool值,而Key即是该元素。用每一位表征相应位置字符是否出现。对于ASCII字符,我们需要256位,即一个长度为8的int数组map即可(8*4*8)。
这里的关键是要把字符对应的ASCII,映射到正确的位上去。
举个例子:
字符'a'对应的ASCII是97,那么我们应该将数组中的哪一位置为1呢?
用97除以32,得到对应数组map的下标:3。97对32取模得到相应的位:1。
【代码】
/*********************************
* 日期:2014-05-04
* 作者:SJF0115
* 题目: 字符串中字符判重
* 来源:CareerCup
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
bool IsUnique(string str){
bool visited[256];
//初始化
memset(visited,false,sizeof(visited));
int len = str.length();
for(int i = 0;i < len;i++){
int index = (int)str[i];
//判断是否有重复
if(!visited[index]){
visited[index] = true;
}
else{
//有重复直接返回
return true;
}
}
return false;
}
int main(){
string str = "i am xiaosi";
bool result = IsUnique(str);
cout<<result<<endl;
return 0;
}
【代码2】
/*********************************
* 日期:2014-05-04
* 作者:SJF0115
* 题目: 字符串中字符判重
* 来源:CareerCup
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
//判断字符串中字符是否重复
bool IsUnique(string str){
//8*4*8 共256位可以表示256个元素
int map[8];
//初始化
memset(map,0,sizeof(map));
int len = str.length();
for(int i = 0;i < len;i++){
int value = (int)str[i];
int index = value / 32, offset = value % 32;
//判断是否已经存储过
if(map[index] & (1 << offset)) {
//重复
return false;
}
map[index] |= (1 << offset);
}
return true;
}
int main(){
string str = "i amxos ";
bool result = IsUnique(str);
cout<<result<<endl;
return 0;
}
分享到:
相关推荐
编写函数void fun(char *s,char *t,char *p)将未在字符串s中出现、而在字符串t中出现的字符, 形成一个新的字符串放在p中,p中字符按原字符串中字符顺序排列,但去掉重复字符。 例如: 当s为"12345", t为"8624677"时, p...
本文实例讲述了C#判断字符串是否存在字母及字符串中字符的替换的方法。分享给大家供大家参考。具体实现方法如下: 首先要添加对命名空间“using System.Text.RegularExpressions;”的引用 下面以一个字符串为例: ...
编写程序:从键盘上输入一个包含10个字符的字符串,把该字符串与程序中给定的字符串("bacdbcabca") //依次比较,统计两个字符串对应字符相等的数目。然后输出从键盘上输入的字符串, //并把两个字符串中对应字符不...
C++ 语言中关于字符串编程。字符串中查找字符串。。。。
indexOf() 方法可返回某个指定的字符串值在字符串中首次出现的位置。如果要检索的字符串值没有出现,则该方法返回 -1。 方法二:match() var str = "123" var reg = RegExp(/3/); if(str.match(reg)){ //包含; } ...
传入一个字符串和整数m,将此字符串中从第m个字符开始的全部字符复制成为另一个字符串并打印出来。
假定输入的字符串中只包含字母和*号。请编写函数fun,它的功能是:形参p已指向字符串中最后的一个字母。在编写函数时,不得使用C语言提供的字符串函数。 例如,字符串中的内容为:****A*BC*DEF*G*******,删除后,字符...
java 字符串转16进制 16进制转字符串 将两个ASCII字符合成一个字节; java 字符串转16进制 16进制转字符串 将两个ASCII字符合成一个字节; java 字符串转16进制 16进制转字符串 将两个ASCII字符合成一个字节; java ...
编写一个applet程序,在窗口界面中实现当输入一个字符串和一个字符后,原字符串中所有该字符将被删除并显示出结果
java接收用户输入的一个字符串和一个字符,将字符串中出现的所有该字符删除,打印新生成的字符串。
string常用截取字符串方法有很多,但是配合使用以下两种,基本都能满足要求: find(string strSub, npos); ...例1:直接查找字符串中是否具有某个字符串(返回”2″) std::string strPath = E:\\
mfc 字符串中查找特殊字符 利用特殊字符分割字符串 mfc 字符串中查找特殊字符 利用特殊字符分割字符串 mfc 字符串中查找特殊字符 利用特殊字符分割字符串 mfc 字符串中查找特殊字符 利用特殊字符分割字符串 mfc 字符...
C#字符串删除指定字符串|C#字符串删除子字符串
输入一个字符串,分别统计出其中英文字母、空格、数字和其它字符的个数,本文给出解决方法 编写思路: 1、字符串的遍历,和列表类似,可以把字符串当做元素都是一个字符的一个字符列表,它可以和列表有公共的语法 2...
给定一个字符串列表’strlist’和整数‘k’ 请编写函数‘func’, 它返回字符串列表中‘k’个相邻字符串中最长的第一个
select f_find('Ap@2233ll@@l@@','@') from dual 返回结果为5,代表‘@’在该字符串中出现5次。 同理 select f_find('Ap@223SWEQQQ3ll@@l@@','Q') from dual---返回3,代表Q在字符串中出现了3次, select f_find('我...
入一个字符,再输入一个以回车结束的字符串(少于80个字符)在字符串中查找该字符。
给写了2个方法,一个是直接截取单个需要的字符串,比如字符串string a="ab123456",我只需要提取3,那么就是单独截取就可以了,从2开始到4结束就行。 第二个是把所有的符合条件的字符串都截取出来,提取出来,比如...
Delphi 7.0 提取字符串中指定子字符串后的字符串,这个平时在字符处理时候使用几率也挺高的,获取指定字符串后面的字符串,比如获取扩展名等也可以用此方法,本例中要用到After函数,测试时,当单击按钮时,执行以下...
这个代码可以添加一个新的字符串到已有的字符串数组中,并确保不会重复添加相同的字符串。具体来说,它首先创建了一个包含3个字符串的字符串数组`strArray`,然后定义了一个新的字符串`newStr`。接着,使用`ismember...