欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 面试题 01.01. 判定字符是否唯一

程序员文章站 2024-03-04 11:08:35
...

leetcode 面试题 01.01. 判定字符是否唯一
https://leetcode-cn.com/problems/is-unique-lcci/
测试发现s中的字符ch都满足’a’<=ch<=‘z’

class Solution:
    def isUnique(self, astr: str) -> bool:	
    	#---
    	# 1.
        # return True if len(set(astr))==len(astr) else False
        #---
        # 2.
        # d=[0]*128
        # for ch in astr:
        #     ind=ord(ch)-ord('a')
        #     if d[ind]:
        #         return False
        #     d[ind]=1
        # return True
        #---
        

很容易想到上面两种解法
再往下想就有点想不到了

评论区看到一个特别厉害的想法
由于测试集中的字符都是小写的26个字母
那么我们假设字符’a’为’起点’
那么’b’和a’的距离是1
'c’和’a’的距离是2

以此类推
我们可以用一个大小为26bit的标记flag(只是假设大小为26bit,具体大小因不同语言而异)来记录一个字符串中的距离
每次遇到一个新字符,检查标志位是否为1,如果不为1获得它与起点的距离,然后修改flag对应的位,如果为1则有了重复字符
例如刚开始flag=0,'c’和’a’的距离是2 我们修改标志位3 为1 (标志位=距离+1,如果不这么做的话,"aa"字符串会判断不正确)
修改flag变成 00 0000 0000 0000 0000 0000 0100
那么下一次再碰到同样的’c’时候,先检查唯一的标志位是否为1即可

因为太妙了忍不住自己写了一下这个思路,原地址 https://leetcode-cn.com/problems/isomorphic-strings/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-42/

class Solution:
    def isUnique(self, astr: str) -> bool:
        flag=0
        for ch in astr:
            ind=ord(ch)-ord('a')
            mask=1<<ind
            if flag & mask :
                return False
            flag=flag|mask
        return True

这道题起始有点像之前的同构字符串 https://blog.csdn.net/hhmy77/article/details/104695922
思路都是一个字符映射到一个位置
大多数人的想法是使用list来存放映射
但是实际上可以用位来存放映射,是很巧妙的做法

相关标签: leetcode