01.01、[簡(jiǎn)單] 判定字符是否唯一

1、題目描述

實(shí)現(xiàn)一個(gè)算法，確定一個(gè)字符串 s 的所有字符是否全都不同。

在這一題中，我們的任務(wù)是判斷一個(gè)字符串 s 中的所有字符是否全都不同。我們將討論兩種不同的方法來(lái)解決這個(gè)問(wèn)題，并詳細(xì)解釋每種方法的實(shí)現(xiàn)過(guò)程。

2、方法一：使用哈希表計(jì)數(shù)

2.1、思路解析

我們可以利用一個(gè)哈希表（數(shù)組）來(lái)記錄字符串中每個(gè)字符的出現(xiàn)次數(shù)。具體步驟如下：

1. 字符數(shù)判斷：如果字符串的長(zhǎng)度超過(guò) 26，那么肯定有重復(fù)字符，因?yàn)橹挥?26 個(gè)小寫(xiě)字母。
2. 哈希表初始化：創(chuàng)建一個(gè)長(zhǎng)度為 26 的數(shù)組 hash，用于記錄每個(gè)字符的出現(xiàn)次數(shù)。
3. 遍歷字符串：對(duì)于字符串中的每個(gè)字符，將對(duì)應(yīng)的哈希表位置加 1。
4. 重復(fù)字符檢測(cè)：在遍歷過(guò)程中，如果某個(gè)字符的出現(xiàn)次數(shù)大于 1，直接返回 false。
5. 返回結(jié)果：遍歷結(jié)束后，如果沒(méi)有發(fā)現(xiàn)重復(fù)字符，返回 true。

2.2、代碼實(shí)現(xiàn)

class Solution {
public:bool isUnique(string astr) {// 如果字符串長(zhǎng)度超過(guò) 26，必然有重復(fù)字符if (astr.size() > 26) {return false;}// 初始化一個(gè)哈希表，長(zhǎng)度為 26，對(duì)應(yīng) 26 個(gè)字母int hash[26] = {0};// 遍歷字符串中的每個(gè)字符for (const auto& ch : astr) {// 將字符轉(zhuǎn)換為相應(yīng)的索引位置hash[ch - 'a']++;// 如果某個(gè)字符的計(jì)數(shù)大于 1，則返回 falseif (hash[ch - 'a'] > 1) {return false;}}// 如果沒(méi)有發(fā)現(xiàn)重復(fù)字符，返回 truereturn true;}
};

2.3、代碼詳解

• 首先檢查字符串長(zhǎng)度。如果長(zhǎng)度超過(guò) 26，立即返回 false，因?yàn)樾?xiě)字母只有 26 個(gè)，無(wú)法保證全部字符唯一。
• 初始化一個(gè)長(zhǎng)度為 26 的整型數(shù)組 hash，用于記錄每個(gè)字母的出現(xiàn)次數(shù)。
• 使用范圍循環(huán)遍歷字符串中的每個(gè)字符。
• 計(jì)算當(dāng)前字符在 hash 數(shù)組中的索引，并將其對(duì)應(yīng)的值加 1。如果某個(gè)字符的計(jì)數(shù)大于 1，表示該字符重復(fù)，立即返回 false。
• 遍歷結(jié)束后，如果沒(méi)有重復(fù)字符，則返回 true。

3、方法二：使用位圖優(yōu)化

3.1、思路解析

第二種方法使用了位圖（bit vector）來(lái)優(yōu)化空間復(fù)雜度。這種方法的核心思想是使用一個(gè)整數(shù)的位來(lái)表示字符是否出現(xiàn)過(guò)。具體步驟如下：

1. 字符數(shù)判斷：與方法一相同，首先判斷字符串長(zhǎng)度是否超過(guò) 26。
2. 位圖初始化：使用一個(gè)整數(shù) bitMap 來(lái)表示字符出現(xiàn)情況，初始值為 0。
3. 遍歷字符串：對(duì)于字符串中的每個(gè)字符，檢查 bitMap 中相應(yīng)的位置是否已經(jīng)設(shè)置。
4. 重復(fù)字符檢測(cè)：如果 bitMap 中相應(yīng)的位置已經(jīng)設(shè)置過(guò)，返回 false。否則，將該位置設(shè)置為 1。
5. 返回結(jié)果：遍歷結(jié)束后，如果沒(méi)有發(fā)現(xiàn)重復(fù)字符，返回 true。

3.2、代碼實(shí)現(xiàn)

class Solution {
public:bool isUnique(string astr) {// 利用鴿巢原理來(lái)做的優(yōu)化，如果字符串長(zhǎng)度超過(guò) 26，必然有重復(fù)字符if (astr.size() > 26)return false;// 使用位圖（bit vector）來(lái)記錄字符出現(xiàn)情況int bitMap = 0;// 遍歷字符串中的每個(gè)字符for (const auto& ch : astr) {int i = ch - 'a'; // 將字符轉(zhuǎn)換為相應(yīng)的位位置// 判斷當(dāng)前字符是否已經(jīng)在 bitMap 中出現(xiàn)過(guò)if (((bitMap >> i) & 1) == 1)return false; // 如果已出現(xiàn)，返回 false// 將當(dāng)前字符加入到 bitMap 中bitMap |= 1 << i;}// 如果沒(méi)有發(fā)現(xiàn)重復(fù)字符，返回 truereturn true;}
};

3.3、代碼詳解

• 同樣首先檢查字符串長(zhǎng)度。如果長(zhǎng)度超過(guò) 26，直接返回 false。
• 初始化一個(gè)整型變量 bitMap，初始值為 0，用于記錄字符的出現(xiàn)情況。
• 遍歷字符串中的每個(gè)字符。計(jì)算當(dāng)前字符在 bitMap 中對(duì)應(yīng)的位位置。
• 檢查 bitMap 中相應(yīng)的位是否已經(jīng)為 1。如果為 1，表示該字符已出現(xiàn)過(guò)，返回 false。如果當(dāng)前字符沒(méi)有出現(xiàn)過(guò)，將對(duì)應(yīng)的位設(shè)置為 1。
• 遍歷結(jié)束后，如果沒(méi)有重復(fù)字符，返回 true。

4、總結(jié)

這兩種方法都可以有效地判斷一個(gè)字符串中的字符是否全都不同。方法一使用了哈希表，代碼直觀易懂，而方法二使用了位圖優(yōu)化，節(jié)省了空間。如果字符串長(zhǎng)度超過(guò) 26，直接返回 false，因?yàn)樾?xiě)字母只有 26 個(gè)，因此這是一種基于鴿巢原理的優(yōu)化。選擇哪種方法取決于具體的需求和優(yōu)化目標(biāo)。