01.01、[簡單] 判定字符是否唯一
1、題目描述
實現一個算法，確定一個字符串 s 的所有字符是否全都不同。
在這一題中，我們的任務是判斷一個字符串 s 中的所有字符是否全都不同。我們將討論兩種不同的方法來解決這個問題，并詳細解釋每種方法的實現過程。
2、方法一：使用哈希表計數
2.1、思路解析
我們可以利用一個哈希表（數組）來記錄字符串中每個字符的出現次數。具體步驟如下：
- 字符數判斷：如果字符串的長度超過 26，那么肯定有重復字符，因為只有 26 個小寫字母。
- 哈希表初始化：創建一個長度為 26 的數組
hash，用于記錄每個字符的出現次數。 - 遍歷字符串：對于字符串中的每個字符，將對應的哈希表位置加 1。
- 重復字符檢測：在遍歷過程中，如果某個字符的出現次數大于 1，直接返回
false。 - 返回結果：遍歷結束后，如果沒有發現重復字符，返回
true。
2.2、代碼實現
class Solution {
public:bool isUnique(string astr) {// 如果字符串長度超過 26，必然有重復字符if (astr.size() > 26) {return false;}// 初始化一個哈希表，長度為 26，對應 26 個字母int hash[26] = {0};// 遍歷字符串中的每個字符for (const auto& ch : astr) {// 將字符轉換為相應的索引位置hash[ch - 'a']++;// 如果某個字符的計數大于 1，則返回 falseif (hash[ch - 'a'] > 1) {return false;}}// 如果沒有發現重復字符，返回 truereturn true;}
};
2.3、代碼詳解
- 首先檢查字符串長度。如果長度超過 26，立即返回
false，因為小寫字母只有 26 個，無法保證全部字符唯一。 - 初始化一個長度為 26 的整型數組
hash，用于記錄每個字母的出現次數。 - 使用范圍循環遍歷字符串中的每個字符。
- 計算當前字符在
hash數組中的索引，并將其對應的值加 1。如果某個字符的計數大于 1，表示該字符重復，立即返回false。 - 遍歷結束后，如果沒有重復字符，則返回
true。
3、方法二：使用位圖優化
3.1、思路解析
第二種方法使用了位圖（bit vector）來優化空間復雜度。這種方法的核心思想是使用一個整數的位來表示字符是否出現過。具體步驟如下：
- 字符數判斷：與方法一相同，首先判斷字符串長度是否超過 26。
- 位圖初始化：使用一個整數
bitMap來表示字符出現情況，初始值為 0。 - 遍歷字符串：對于字符串中的每個字符，檢查
bitMap中相應的位置是否已經設置。 - 重復字符檢測：如果
bitMap中相應的位置已經設置過，返回false。否則，將該位置設置為 1。 - 返回結果：遍歷結束后，如果沒有發現重復字符，返回
true。
3.2、代碼實現
class Solution {
public:bool isUnique(string astr) {// 利用鴿巢原理來做的優化，如果字符串長度超過 26，必然有重復字符if (astr.size() > 26)return false;// 使用位圖（bit vector）來記錄字符出現情況int bitMap = 0;// 遍歷字符串中的每個字符for (const auto& ch : astr) {int i = ch - 'a'; // 將字符轉換為相應的位位置// 判斷當前字符是否已經在 bitMap 中出現過if (((bitMap >> i) & 1) == 1)return false; // 如果已出現，返回 false// 將當前字符加入到 bitMap 中bitMap |= 1 << i;}// 如果沒有發現重復字符，返回 truereturn true;}
};
3.3、代碼詳解
- 同樣首先檢查字符串長度。如果長度超過 26，直接返回
false。 - 初始化一個整型變量
bitMap，初始值為 0，用于記錄字符的出現情況。 - 遍歷字符串中的每個字符。計算當前字符在
bitMap中對應的位位置。 - 檢查
bitMap中相應的位是否已經為 1。如果為 1，表示該字符已出現過，返回false。如果當前字符沒有出現過，將對應的位設置為 1。 - 遍歷結束后，如果沒有重復字符，返回
true。
4、總結
這兩種方法都可以有效地判斷一個字符串中的字符是否全都不同。方法一使用了哈希表，代碼直觀易懂，而方法二使用了位圖優化，節省了空間。如果字符串長度超過 26，直接返回 false，因為小寫字母只有 26 個，因此這是一種基于鴿巢原理的優化。選擇哪種方法取決于具體的需求和優化目標。
