程序员面试金典 - 面试题 01.01. 判定字符是否唯一

题目难度: 简单

原题链接

休息了一个月, 我又满血回来了 ???? 今天我们来开始一个新的系列 - leetcode 的程序员面试金典, 它相比剑指 Offer 难度大了一些, 但大部分题目的出现频率仍然相当高, 推荐程度依旧 5 颗星 ✨✨✨✨✨

最近一段时间我都挺忙的, 所以这个系列的更新频率可能不像之前那么高了, 估计几天一更吧. 不过更新时间还是老样子: 晚上的 6 点 45 分, 大家可以多多关注哦

另外大家在我的公众号"算法精选"中的聊天框中回复 面试金典 就能看到该系列当前已经更新的文章了

题目描述

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

限制：

0 <= len(s) <= 100
如果你不使用额外的数据结构，会很加分。

示例 1：

输入: s = “leetcode”
输出: false

示例 2：

输入: s = “abc”
输出: true

题目思考

1. 如何做到不使用额外数据结构?

解决方案

思路

• 显然我们可以使用集合存储当前遇到的字符, 但这样就用到了额外数据结构, 不满足进阶要求, 那不用集合又该怎么做呢?
• 集合的常见空间优化是转成位图来存储, 这样就能把 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

大家可以在下面这些地方找到我~????

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~????

最后

以上就是勤劳石头为你收集整理的程序员面试金典 - 面试题 01.01. 判定字符是否唯一的全部内容，希望文章能够帮你解决程序员面试金典 - 面试题 01.01. 判定字符是否唯一所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。