147
CareerCup之1.1字符串中字符判重
【題目】
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;
}
最後更新：2017-04-03 12:56:30