# 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
让我们实现一个算法,在python中使用位操作检查字符串是否包含重复字符。 返回True表示“abcdgt”,返回False表示“bdb”
检查重复的位操作算法只需要O(n)个时间
和O(1)空间,因为我们将只使用4字节的空间来检查 字符串是否包含重复字符。 对于这个问题,我们只假设字符串只包含a-z字符,因为整数最多只能存储32位。你知道吗
下面是算法的代码。你知道吗
返回True
希望,我能够解释位操纵,因为我的很多朋友甚至不理解这个概念,觉得这很难,但实际上很容易。你知道吗
从人们在网上的说法来看,似乎是这样的:
假设您有一个字符串(仅包含集合a-z或集合a-z中的字符,但不能同时包含这两个字符),您可以通过使用逐位操作翻转整数中的位来跟踪以前看到的字符。例如,如果字符串是“aza”,则将整数的第一位设置为1,然后将第二十六位设置为1,然后再次尝试将第一位设置为1。因为它已经被翻转了,你可以断言这个角色以前见过,因此不是唯一的。字符集(a-z或a-z)的限制似乎源于这样一个事实:在大多数语言中,字母表中有26个字母,整数中有32位,因此有足够的位来表示整个字母表。你知道吗
但是,我不认为这是使用Python解决问题的好方法,因为整数在Python中具有任意精度。在我看来,这也不是一个很好的解决方案。最好使用
set()
来跟踪以前看到的字符,然后断言字符串的长度与集合的长度匹配。你知道吗相关问题 更多 >
编程相关推荐