实现一个算法,确定一个字符串 s 的所有字符是否全都不同。
时间: 2023-05-31 19:21:01 浏览: 66
### 回答1:
可以使用哈希表或者数组来实现。具体步骤如下:
1. 定义一个哈希表或者数组,用来记录每个字符是否出现过。
2. 遍历字符串 s 中的每个字符,如果该字符在哈希表或者数组中已经出现过,则说明字符串 s 中存在重复字符,返回 false。
3. 如果遍历完字符串 s 中的所有字符都没有发现重复字符,则说明字符串 s 中所有字符都不同,返回 true。
下面是使用哈希表实现的代码示例:
```
bool isUnique(string s) {
unordered_map<char, bool> hash;
for (char c : s) {
if (hash[c]) {
return false;
}
hash[c] = true;
}
return true;
}
```
下面是使用数组实现的代码示例:
```
bool isUnique(string s) {
bool exist[256] = {false};
for (char c : s) {
if (exist[c]) {
return false;
}
exist[c] = true;
}
return true;
}
```
### 回答2:
题意理解:
本题要求实现一个算法,来确定一个字符串是否所有字符都不同。也就是说,如果一个字符串中包含重复的字符,那么算法返回 false,否则返回 true。下面的讨论中,我们假设输入字符串 s 只包含 ASCII 码字符。
方法一:
最简单的方法应该是对字符串 s 中的所有字符进行比较。具体来说,我们可以使用双重循环,将 s 中的每个字符与其后面的所有字符进行比较。如果存在相等的字符,那么算法返回 false,否则返回 true。代码如下:
```python
def is_unique(s):
for i in range(len(s)):
for j in range(i+1, len(s)):
if s[i] == s[j]:
return False
return True
```
时间复杂度 O(n^2)。
方法二:
我们可以尝试将字符映射到一个数值上。由于 ASCII 码字符总共有 128 个,因此我们可以使用一个长度为 128 的布尔型数组来实现。具体来说,数组中的第 i 个元素表示字符 i 是否出现在 s 中。首先将数组全部初始化为 False,然后遍历 s 中的每个字符 c,将对应的位置数组元素设为 True。如果在遍历过程中,发现数组元素已经为 True,那么说明字符 c 已经在之前出现过,算法返回 false,否则返回 true。代码如下:
```python
def is_unique(s):
if len(s) > 128: # 如果字符个数大于 128,那么肯定有重复的字符
return False
char_set = [False] * 128 # 初始化字符集
for c in s:
if char_set[ord(c)]: # 如果字符对应的布尔型数组元素为 True,说明之前已经出现过
return False
char_set[ord(c)] = True # 标记当前字符已经出现
return True
```
时间复杂度 O(n),空间复杂度 O(1)。
方法三:
方法二的空间复杂度为 O(1),但时间复杂度是线性的,不能满足使用场景中大多数情况下的要求。因此我们需要一种时间复杂度与空间复杂度均为 O(1) 的算法。具体来说,我们可以使用一个长度为 4 的整型数组来保存字符串中出现的 ASCII 码字符。对于字符串中的每一个字符 c,算法将其转化为其对应的 ASCII 码 num,然后计算 num/32 和 num%32,分别得到两个数值,假设为 i 和 j。那么数组的第 i 个元素的第 j 个 bit 位就表示字符 num 是否已经出现过。如果这个 bit 位为 1,说明字符 num 已经出现过,算法返回 false,否则将该 bit 位更新为 1。这个算法的实现如下:
```python
def is_unique(s):
if len(s) > 128:
return False
checker = [0] * 4 # 初始化 checker
for c in s:
num = ord(c)
i, j = num // 32, num % 32 # 分别计算 i 和 j
if checker[i] & (1 << j) != 0: # checker[i] 的第 j 个 bit 位为 1,说明字符 num 已经出现过
return False
checker[i] |= 1 << j # 更新 checker[i] 的第 j 个 bit 位为 1
return True
```
时间复杂度 O(n),空间复杂度 O(1)。
### 回答3:
算法实现思路:
这个问题可以采用哈希表来解决,我们可以创建一个长度为 256 的布尔类型数组,用于表示 ASCII 码表中的每个字符是否出现过。初始值都为 false,当遍历到一个字符时,即把该字符对应的布尔类型数值变成 true,如果发现下一个字符的布尔类型数值已经是 true,那么说明这两个字符是相同的字符,字符串中有重复字符,直接返回 false;否则继续往后遍历,直到所有字符均被遍历完,返回 true。
算法的关键细节:
1. 哈希表的长度为 256,对应 ASCII 码表上的全部字符。
2. 由于字符串中包含的字符为 ASCII 码表上的字符,因此可以用字符的 ASCII 码作为哈希表的键。
3. 遍历字符串时,用字符的 ASCII 码作为键,可以快速定位哈希表中对应的布尔类型数值,判断字符是否出现过。
4. 如果字符串中的所有字符均不相同,遍历完后会返回 true,否则会返回 false。
算法实现代码:
bool isUnique(string s) {
if(s.length() > 256) return false;
vector<bool> hash_table(256);
for(char c: s) {
if(hash_table[c]) return false;
hash_table[c] = true;
}
return true;
}
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)