使用位操作确定字符串中的所有字符是否唯一

2024-03-29 13:36:24 发布

您现在位置:Python中文网/ 问答频道 /正文

Implement an algorithm to determine if all the characters in a string are unique.

有人能解释一下如何使用位操作吗?有一个解决方案提供了使用比特在CTCI,但我无法理解它。你知道吗


Tags: thetoinanstringifallimplement
2条回答

让我们实现一个算法,在python中使用位操作检查字符串是否包含重复字符。 返回True表示“abcdgt”,返回False表示“bdb”

检查重复的位操作算法只需要O(n)个时间

和O(1)空间,因为我们将只使用4字节的空间来检查 字符串是否包含重复字符。 对于这个问题,我们只假设字符串只包含a-z字符,因为整数最多只能存储32位。你知道吗

    # 1<<val shifts 1 by to the left by appending zeros equal to val. So 1<<5 would be 100000. So this means that if a char is present in string, we assign 1 at its place else 0. If checker already has 1 at the place of char and we take '&' with val(value of character in range 0-26) again, we will get 1 (1 & 1), which is greater than zero. Hence it shows that char is present or string contains duplicate characters. 
    Lets take an example for str = 'bdb'. 
      checker = 0
    1. c = 'b' 
         => val = 98 - 97 = 1 
         => 0 & 1<<1 
         => 0 & 10 
         => 0
         checker = 0 | 10
         checker = 10
    2. c = 'd'
         => val = 100 - 97 = 3
         => 10 & 1<<3
         => 10 & 1000
         => 0
         checker = 10 | 1000
         checker = 1010
   3. c = 'b'
         => val = 98 - 97 = 1 
         => 1010 & 1<<1 
         => 1010 & 10 
         => 1 > 0; return False (which is true as string contains duplicates)

下面是算法的代码。你知道吗

def checkDuplicates(str):
    checker = 0  
    for c in str:  
    #Gets the difference in ASCII between character and 'a'
    val = ord(c) - ord('a')
    if (checker & 1<<val) > 0:
        return False
    checker |= 1<<val

返回True

希望,我能够解释位操纵,因为我的很多朋友甚至不理解这个概念,觉得这很难,但实际上很容易。你知道吗

从人们在网上的说法来看,似乎是这样的:

假设您有一个字符串(仅包含集合a-z或集合a-z中的字符,但不能同时包含这两个字符),您可以通过使用逐位操作翻转整数中的位来跟踪以前看到的字符。例如,如果字符串是“aza”,则将整数的第一位设置为1,然后将第二十六位设置为1,然后再次尝试将第一位设置为1。因为它已经被翻转了,你可以断言这个角色以前见过,因此不是唯一的。字符集(a-z或a-z)的限制似乎源于这样一个事实:在大多数语言中,字母表中有26个字母,整数中有32位,因此有足够的位来表示整个字母表。你知道吗

但是,我不认为这是使用Python解决问题的好方法,因为整数在Python中具有任意精度。在我看来,这也不是一个很好的解决方案。最好使用set()来跟踪以前看到的字符,然后断言字符串的长度与集合的长度匹配。你知道吗

相关问题 更多 >