面试题 01.01. 判定字符是否唯一————简单

题目

面试题 01.01. 判定字符是否唯一
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：
输入: s = "leetcode"
输出: false 

示例 2：
输入: s = "abc"
输出: true

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

解题思路

• 仔细想想面试官真正想问的是什么，如果你直接遍历一遍字符串，这样做确实是对的，但是这并不是面试官想要的答案。
• 真正的思路是利用位运算来解决这道题目。
• 假设有26个bit对应26个字符，对于每个字符，我们只需要检查它的下标值就可以了。那么怎么检查下标值呢？
• 我们要通过字符到’a‘的距离来计算，1 << distance即对应下标。如果出现过，则它的下标值定义为1，其余下标都为0。然后我们和mark(长度为26的bool的数组)做与运算。如果这个字符出现过，那么结果一定不为0，否则结果为0.（因为我们每次对出现过的字符都会进行标记为1的操作。）
• 对于没有出现过的字符，我们用或运算mark | (1 << distance)来将对应的下标置为1.

Code

class Solution:
    def isUnique(self, astr: str) -> bool: 
        mark = 0
        for char in astr:
            distance = ord(char) - ord('a')
            if (mark & (1 << distance)):
                return False
            else:
                mark |= (1 << distance)
        return True

运行结果

最后

以上就是精明狗最近收集整理的关于面试题 01.01. 判定字符是否唯一————简单的全部内容，更多相关面试题内容请搜索靠谱客的其他文章。