英文:
Is it possible to find duplicate characters in a random unicode string using the bitwise operations?
问题
我正在寻找一种在字符串中查找重复字符的解决方案，并且对使用位操作的解决方案很感兴趣。
我找到了一个使用位操作的变体。但是，在这个变体中，搜索发生在ASCII表的a-z范围内。
func HasDuplicates(str string) (string, bool) {
checker := 0
for _, char := range str {
val := char - 'a'
fmt.Println(val)
if (checker & (1 << val)) > 0 {
fmt.Printf("'%c' 是重复的\n", char)
return str, false
}
checker |= 1 << val
}
return str, true
}
是否可能创建一个通用的解决方案，类似上面的示例，但适用于随机的Unicode字符串（象形文字、表情符号等）？
英文:
I was looking for a solution to find duplicate characters in a string and I was interested in a solution with bitwise operations.
I found such a variant with bitwise operations. But in it, the search occurs in the range a-z of the ASCII table.
func HasDuplicates(str string) (string, bool) {
checker := 0
for _, char := range str {
val := char - 'a'
fmt.Println(val)
if (checker & (1 << val)) > 0 {
fmt.Printf("'%c' is Duplicate\n", char)
return str, false
}
checker |= 1 << val
}
return str, true
}
Is it possible to make a universal solution, like the example above, only for a random unicode string (hieroglyphs, emoji, etc.)?
答案1
得分: 2
使用big.Int作为位集：
func HasDuplicates(str string) (string, bool) {
var bits big.Int
for _, char := range str {
val := int(char)
fmt.Println(val)
if bits.Bit(val) != 0 {
fmt.Printf("'%c' 是重复的\n", char)
return str, false
}
bits.SetBit(&bits, val, 1)
}
return str, true
}
这个方法的效率取决于big.Int的实现，你无法像在简单整数上使用位操作那样控制它。
你也可以使用一个布尔值的映射，不过这样就不再是位操作了：
func HasDuplicates(str string) (string, bool) {
var bits = make(map[int]bool)
for _, char := range str {
val := int(char)
fmt.Println(val)
if bits[val] {
fmt.Printf("'%c' 是重复的\n", char)
return str, false
}
bits[val] = true
}
return str, true
}
英文:
Use a big.Int as a bitset:
func HasDuplicates(str string) (string, bool) {
var bits big.Int
for _, char := range str {
val := int(char)
fmt.Println(val)
if bits.Bit(val) != 0 {
fmt.Printf("'%c' is Duplicate\n", char)
return str, false
}
bits.SetBit(&bits, val, 1)
}
return str, true
}
https://go.dev/play/p/kS-OxYPts5G
How efficient this is will depend on the implementation of big.Int, you're not in control of that the way you are when using bitwise operations on a simple integer.
You could also use a map of booleans, although then it wouldn't be bitwise operations any more:
func HasDuplicates(str string) (string, bool) {
var bits = make(map[int]bool)
for _, char := range str {
val := int(char)
fmt.Println(val)
if bits[val] {
fmt.Printf("'%c' is Duplicate\n", char)
return str, false
}
bits[val] = true
}
return str, true
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论