题目难度: 简单
休息了一个月, 我又满血回来了 😂 今天我们来开始一个新的系列 - leetcode 的程序员面试金典, 它相比剑指 Offer 难度大了一些, 但大部分题目的出现频率仍然相当高, 推荐程度依旧 5 颗星 ✨✨✨✨✨
最近一段时间我都挺忙的, 所以这个系列的更新频率可能不像之前那么高了, 估计几天一更吧. 不过更新时间还是老样子: 晚上的 6 点 45 分, 大家可以多多关注哦
另外大家在我的公众号"算法精选"中的聊天框中回复 面试金典 就能看到该系列当前已经更新的文章了
题目描述
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
限制：
0 <= len(s) <= 100
如果你不使用额外的数据结构，会很加分。
示例 1：
输入: s = "leetcode"
输出: false
示例 2：
输入: s = "abc"
输出: true
题目思考
- 如何做到不使用额外数据结构?
解决方案
思路
- 显然我们可以使用集合存储当前遇到的字符, 但这样就用到了额外数据结构, 不满足进阶要求, 那不用集合又该怎么做呢?
- 集合的常见空间优化是转成位图来存储, 这样就能把 O(N) 复杂度降为 O(1), 但要求数据是数字, 且在一定范围内
- 所以我们只要能把字符进行一些转换, 将其映射为数字, 就能利用上述的优化了, 不难想到可以利用字符的 ASCII 码值来做到 (python 中对应的就是
ord(chr)) - 转成数字后, 左移相应的位数, 利用
|操作可以将当前数字加入位图,&操作可以验证当前数字是否已经存在 - 注意 python 由于数字无限位数, 所以直接用一个变量即可; 而 Java/C++等语言就需要两个 64 位 long 变量分别表示低位和高位, 因为总共有 128 个 ASCII 码
复杂度
- 时间复杂度 O(N): 只需要遍历字符串一遍
- 空间复杂度 O(1): 只使用了几个变量
代码
class Solution:
def isUnique(self, astr: str) -> bool:
# 不使用额外数据结构 --- 位图/位运算
# 左移对应的位数, &判断, |加入
if not astr:
return True
mask = 0
for c in astr:
bit = 1 << ord(c)
if mask & bit:
return False
mask |= bit
return True 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号