我試圖找到在字母表的圓形排列中等距分隔的單詞/字符串。例如：“zzzzyyyybbbzzzaaaaaxxx”是由“xyzab”組成的列表，分隔符為 0 {xy, yz, za, ab}“aco” 是一個分隔符為 11 {co, oa} 的列表因此，我想編寫函數 IsSeparated(B) 并在 B 為“isSeparated”時返回 true以下是我的代碼/解決方案：首先，我嘗試刪除字符串中的重復項，以便更容易計算間隔其次，我按字母順序對字符串進行排序第三，排序后，我計算每個字母的間隔在“isSeparated”方法中，我嘗試通過使用使其以循環排列方式計數maxpair -1 == count，因為總會有 1 個字母沒有配對，例如[{ab} {bx} {xy} {yz} {za}] - [{0} {21} {0} {0} {0}]]//there are 5
pairs = maxPair -1({-xy}因此，由于它是圓形排列的，中間的總是奇數，即 21，與其余對的間隔不相等這是變得棘手的部分，我似乎無法獲得所需的輸出。按字母順序查找每個字母的長度/分隔并檢查它們是否均勻分隔的正確方法可能是什么。
1 回答
斯蒂芬大帝
TA貢獻1827條經驗 獲得超8個贊
我不太明白你試圖確定分離的部分。在 Go 中，就像在 C 中一樣，您可以對字符進行算術運算。例如，您將獲得每個小寫字母的從 0 開始的索引：
pos := char - 'a';
你可以"abxyz"轉向
{0, 1, 23, 24, 25}.如果你計算相鄰字母之間的差異，你會得到
{-25, 1, 22, 1, 1}（-25 是最后一個值和第一個值之間的差值。）有兩個間隙：一個間隙是循環在 b 和 w 之間開始的間隙，另一個間隙是字母表換行的間隙。第二個間隙是差值為負的地方，總是在最后一項和第一項之間。您可以在差值上加上 26 來調整它，也可以使用模算術，其中使用余數%來計算環繞：
diff := ((p - q + 26) % 26;
如果第一個操作數為正，則強制%結果范圍為 0 到 25。+ 26 強制其為正數。（下面的程序使用 25，因為您對分隔的定義不是位置的差異，而是兩者之間的過濾器數量。）
現在你已經看到了差異
{1, 1, 22, 1, 1}當最多只有兩個不同的值并且其中一個最多出現一次時，就滿足您的條件。（我發現這個條件測試起來非常復雜，見下文，但部分原因是 Go 的映射有點麻煩。）
無論如何，這是代碼：
package main
import "fmt"
func list(str string) int {
present := [26]bool{}
pos := []int{}
count := map[int]int{}
// determine which letters exist
for _, c := range str {
if 'a' <= c && c <= 'z' {
present[c-'a'] = true
}
}
// concatenate all used letters (count sort, kinda)
for i := 0; i < 26; i++ {
if present[i] {
pos = append(pos, i)
}
}
// find differences
q := pos[len(pos)-1]
for _, p := range pos {
diff := (p - q + 25) % 26
count[diff]++
q = p
}
// check whether input is a "rambai"
if len(count) > 2 {
return -1
}
which := []int{}
occur := []int{}
for k, v := range count {
which = append(which, k)
occur = append(occur, v)
}
if len(which) < 2 {
return which[0]
}
if occur[0] != 1 && occur[1] != 1 {
return -1
}
if occur[0] == 1 {
return which[1]
}
return which[0]
}
func testme(str string) {
fmt.Printf("\"%s\": %d\n", str, list(str))
}
func main() {
testme("zzzzyyyybbbzzzaaaaaxxx")
testme("yacegw")
testme("keebeebheeh")
testme("aco")
testme("naan")
testme("mississippi")
testme("rosemary")
}
package main
import "fmt"
func list(str string) int {
present := [26]bool{}
pos := []int{}
count := map[int]int{}
// determine which letters exist
for _, c := range str {
if 'a' <= c && c <= 'z' {
present[c-'a'] = true
}
}
// concatenate all used letters (count sort, kinda)
for i := 0; i < 26; i++ {
if present[i] {
pos = append(pos, i)
}
}
// find differences
q := pos[len(pos)-1]
for _, p := range pos {
diff := (p - q + 25) % 26
count[diff]++
q = p
}
// check whether input is a "rambai"
if len(count) > 2 {
return -1
}
which := []int{}
occur := []int{}
for k, v := range count {
which = append(which, k)
occur = append(occur, v)
}
if len(which) < 2 {
return which[0]
}
if occur[0] != 1 && occur[1] != 1 {
return -1
}
if occur[0] == 1 {
return which[1]
}
return which[0]
}
func testme(str string) {
fmt.Printf("\"%s\": %d\n", str, list(str))
}
func main() {
testme("zzzzyyyybbbzzzaaaaaxxx")
testme("yacegw")
testme("keebeebheeh")
testme("aco")
testme("naan")
testme("mississippi")
testme("rosemary")
}
https://play.golang.org/p/ERhLxC_zfjl
- 1 回答
- 0 關注
- 199 瀏覽
添加回答
舉報
0/150
提交
取消