我試圖找到在字母表的圓形排列中等距分隔的單詞/字符串。例如：“zzzzyyyybbbzzzaaaaaxxx”是由“xyzab”組成的列表，分隔符為 0 {xy, yz, za, ab}“aco” 是一個(gè)分隔符為 11 {co, oa} 的列表因此，我想編寫函數(shù) IsSeparated(B) 并在 B 為“isSeparated”時(shí)返回 true以下是我的代碼/解決方案：首先，我嘗試刪除字符串中的重復(fù)項(xiàng)，以便更容易計(jì)算間隔其次，我按字母順序?qū)ψ址M(jìn)行排序第三，排序后，我計(jì)算每個(gè)字母的間隔在“isSeparated”方法中，我嘗試通過使用使其以循環(huán)排列方式計(jì)數(shù)maxpair -1 == count，因?yàn)榭倳?huì)有 1 個(gè)字母沒有配對(duì)，例如[{ab} {bx} {xy} {yz} {za}] - [{0} {21} {0} {0} {0}]]//there are 5
pairs = maxPair -1({-xy}因此，由于它是圓形排列的，中間的總是奇數(shù)，即 21，與其余對(duì)的間隔不相等這是變得棘手的部分，我似乎無法獲得所需的輸出。按字母順序查找每個(gè)字母的長(zhǎng)度/分隔并檢查它們是否均勻分隔的正確方法可能是什么。
1 回答
斯蒂芬大帝
TA貢獻(xiàn)1827條經(jīng)驗(yàn) 獲得超8個(gè)贊
我不太明白你試圖確定分離的部分。在 Go 中，就像在 C 中一樣，您可以對(duì)字符進(jìn)行算術(shù)運(yùn)算。例如，您將獲得每個(gè)小寫字母的從 0 開始的索引：
pos := char - 'a';
你可以"abxyz"轉(zhuǎn)向
{0, 1, 23, 24, 25}.如果你計(jì)算相鄰字母之間的差異，你會(huì)得到
{-25, 1, 22, 1, 1}（-25 是最后一個(gè)值和第一個(gè)值之間的差值。）有兩個(gè)間隙：一個(gè)間隙是循環(huán)在 b 和 w 之間開始的間隙，另一個(gè)間隙是字母表換行的間隙。第二個(gè)間隙是差值為負(fù)的地方，總是在最后一項(xiàng)和第一項(xiàng)之間。您可以在差值上加上 26 來調(diào)整它，也可以使用模算術(shù)，其中使用余數(shù)%來計(jì)算環(huán)繞：
diff := ((p - q + 26) % 26;
如果第一個(gè)操作數(shù)為正，則強(qiáng)制%結(jié)果范圍為 0 到 25。+ 26 強(qiáng)制其為正數(shù)。（下面的程序使用 25，因?yàn)槟鷮?duì)分隔的定義不是位置的差異，而是兩者之間的過濾器數(shù)量。）
現(xiàn)在你已經(jīng)看到了差異
{1, 1, 22, 1, 1}當(dāng)最多只有兩個(gè)不同的值并且其中一個(gè)最多出現(xiàn)一次時(shí)，就滿足您的條件。（我發(fā)現(xiàn)這個(gè)條件測(cè)試起來非常復(fù)雜，見下文，但部分原因是 Go 的映射有點(diǎn)麻煩。）
無論如何，這是代碼：
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 關(guān)注
- 205 瀏覽
添加回答
舉報(bào)
0/150
提交
取消