?

1.1 Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structure?

?

這道題讓我們判斷一個字符串中是否有重復(fù)的字符，要求不用特殊的數(shù)據(jù)結(jié)構(gòu)，這里應(yīng)該是指哈希表之類的不讓用。像普通的整型數(shù)組應(yīng)該還是能用的，這道題的小技巧就是用整型數(shù)組來代替哈希表，在之前Bitwise AND of Numbers Range 數(shù)字范圍位相與的解法二中也用到過這種方法。由于ASCII表里的基本表共有128個字符，也就是可以用鍵盤表示出來的，整個表共有256個字符，所以我們只要用一個大小為256的整型數(shù)組就可以包含所有的字符，我們遍歷輸入字符串，對每一個字符都存入到相應(yīng)位置，并賦值1，如果遇到已經(jīng)為1的，說明之前出現(xiàn)過該字符，返回false，如果遍歷完s，則返回true，代碼如下:

?

class Solution { public:bool isUniqueChar(string s) {if (s.size() > 128) return false;int m[256] = {0};for (int i = 0; i < s.size(); ++i) {if (m[s[i]] > 0) return false;m[s[i]] = 1;}return true;} };

?

書上還給了另一種解法，是用位操作 Bit Manipulation，但是這種解法只有當(dāng)輸入字符串是由小寫字母組成的才成立，因?yàn)樾懽帜钢挥?6個，不超過整型int的32位，對于每個字母，我們將對應(yīng)位置設(shè)為1，然后看之前是否是1，是的話返回false，不是的話設(shè)為1。跟上面的方法核心是一樣的，只不過空間上省了很多，但是也對輸入做了更為嚴(yán)格的限制，代碼如下：

?

// Only works when s consists of lower-case letters a-z class Solution { public:bool isUniqueChar(string s) {int m = 0;for (int i = 0; i < s.size(); ++i) {int d = s[i] - 'a';if (m & (1 << d) > 0) return false;m |= (1 << d);}return true;} };

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的[CareerCup] 1.1 Unique Characters of a String 字符串中不同的字符的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。