英文:
Print the number of characters which are identical and occur in the same position in both strings
问题
例如，如果"abacdead"和"adcbadedga"是两个字符串，那么我们需要打印相同位置和不同位置。
相同位置计数：2
不同位置计数：5
如果我们使用循环的话，a（第一个字母）将检查所有字符（字符串2），所以循环将运行超过140次，这里如何实现O(n)的时间复杂度。如果有任何数据结构，请建议我解决这个问题。
示例代码：
func Test(a, b string) {
r := make([]map[string]interface{}, 0)
for i := 0; i < len(a); i++ {
for j := 0; j < len(b); j++ {
if string(a[i]) == string(b[j]) {
r = append(r, map[string]interface{}{
"position": i,
"char": string(a[i]),
})
}
}
}
}
英文:
For example if "abacdead" and "adcbadedga" are the two strings then we need to print the same position and different position.
same pos count: 2
diff pos count: 5
If we are using loop means, a (first letter) will be checking all the characters (string 2), So the loop will be run by more than 140 times, Here How can we achieve the O (n). If we have any data structure, Please suggest me to solve this issue.
Sample code
func Test(a, b string) {
r := make([]map[string]interface{}, 0)
for i := 0; i < len(a); i++ {
for j := 0; j < len(b); j++ {
if string(a[i]) == string(b[j]) {
r = append(r, map[string]interface{}{
"position": i,
"char": string(a[i]),
})
}
}
}
}
答案1
得分: 0
你只需要统计相同位置上字符的数量，以及每个字符串中每个字符的总数量。然后将每个字符的最小数量相加，并减去相同位置上的数量。
package main
import (
"fmt"
"math"
)
func main() {
a := []rune("abacdead")
b := []rune("adcbadedga")
same := 0
chars := make(map[rune][]int)
for i := 0; i < len(a); i++ {
if i < len(b) && a[i] == b[i] {
same++
}
if _, ok := chars[a[i]]; !ok {
chars[a[i]] = []int{0, 0}
}
chars[a[i]][0]++
}
for i := 0; i < len(b); i++ {
if _, ok := chars[b[i]]; !ok {
chars[b[i]] = []int{0, 0}
}
chars[b[i]][1]++
}
different := -same
for char, vals := range chars {
fmt.Println(string(char), vals[0], vals[1])
different += int(math.Min(float64(vals[0]), float64(vals[1])))
}
fmt.Println("Same: ", same, "Different: ", different)
}
注意，总数与你所说的不一致：
"abacdead"
"adcbadedga"
在相同的位置上，我们有第一个 a 和最后一个 d，如果我们移除它们：
"bacdea"
"dcbadega"
然后进行排序：
"aabcde"
"aabcddeg"
然后我们移除不匹配的字母：
"aabcde"
"aabcde"
我们应该有六个相同的字符，但位置不同。
英文:
You really only need the count of characters in the same position, and the total count of each character in each string. Then sum the minimum count of each character, and subtract the count in the same position.
https://play.golang.org/p/pknsVfZ1ZbM
package main
import (
"fmt"
"math"
)
func main() {
a := []rune("abacdead")
b := []rune("adcbadedga")
same := 0
chars := make(map[rune][]int)
for i := 0; i < len(a); i++ {
if i < len(b) && a[i] == b[i] {
same++
}
if _, ok := chars[a[i]]; !ok {
chars[a[i]] = []int{0, 0}
}
chars[a[i]][0]++
}
for i := 0; i < len(b); i++ {
if _, ok := chars[b[i]]; !ok {
chars[b[i]] = []int{0, 0}
}
chars[b[i]][1]++
}
different := -same
for char, vals := range chars {
fmt.Println(string(char), vals[0], vals[1])
different += int(math.Min(float64(vals[0]), float64(vals[1])))
}
fmt.Println("Same: ", same, "Different: ", different)
}
Caveat being that the totals don't agree with what you said:
"abacdead"
"adcbadedga"
same position we have the first a and the last d, if we remove those:
"bacdea"
"dcbadega"
and then sort
"aabcde"
"aabcddeg"
we then remove unmatched letters
"aabcde"
"aabcde"
we should have six identical characters in different positions.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论