在Go中按字母顺序查找均等分隔的字符串/单词

anon_n5:

我正在尝试查找在字母的圆形排列中均等分开的单词/字符串。例如:

  • “ 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,与其余的对不相等地分开

这是棘手的部分,我似乎无法获得所需的输出。找到字母顺序的每个字母的长度/分隔并检查它们是否均匀分隔的正确方法是什么?


package main

import (
    "fmt"
    "strings"
)

//Q3
func separationCount(x, y string) int {
    alphabets := [26]string{"a","b","c","d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u","v", "w", "x", "y", "z"}
    separation := 0

    for i:=0; i < len(alphabets); i++{
        if x == alphabets[i]{

            for j:= i+1; j <len(alphabets); j++{
            if y == alphabets[i+1]{
            fmt.Println(separation)
            return separation
            }else{
                i++
                separation++
            } 
            }
                }else{
            //do nothing
        }
    }
    //fmt.Println(separation)
    return 0
}

func isSeparated(B [] string) bool {
    var N int = len(B) - 1
    var maxPair int
    var item1 string
    var item2 string
    var separation int = 0 
    count := 0
    var intialSeparation int

    //calling the methods
    fmt.Println("Original array:",B)
    B = removeDuplicates(B)
    B = sortedList(B)

    item1 = B[0]
    item2 = B[1]
    intialSeparation = separationCount(item1,item2)

    for i := 0; i< N; i++{
        item1 = B[i]
        item2 = B[i + 1]

        separation = separationCount(item1,item2)
        maxPair++
        if intialSeparation == separation{
            count++
        }

        if maxPair == count{
            return true
        }else{
            return false
        }

    }
    return false
}

//to sort the alphabets 
func sortedList(B []string) [] string {
    N  := len(B)
    //max := 0
    element1 := 0 
    element2 := 1

    for element2 < N {
        var item1 string = B[element1]
        var item2 string = B[element2]

        //using function call
        if greater(item1, item2){
            B[element1] = item2
            B[element2] = item1
        }
        element1++
        element2++
    } 
    fmt.Println("Alphabetically sorted:", B )
    return B
}

//for sorting
func greater(a, b string) bool {
    if strings.ToLower(a) > strings.ToLower(b) {
      return true
    } else {
      return false
    }
  }

  //removing duplicates
func removeDuplicates(B []string) []string {
    encountered := map[string]bool{}

    // Create a map of all unique elements.
    for v:= range B {
        encountered[B[v]] = true
    }

    // Place all keys from the map into a slice.
    result := []string{}
    for key, _ := range encountered {
        result = append(result, key)
    }
    fmt.Println("Duplicates removed:", result )
    return result
}

func main(){
    //q3
    B := []string{"y", "a", "a", "a", "c", "e", "g", "w", "w", "w"}
    fmt.Println(isSeparated(B))
}



M Oehm:

我不太了解您尝试确定分离的部分。在Go中,就像在C中一样,您可以对字符进行算术运算。例如,您将获得每个小写字母的从0开始的索引:

pos := char - 'a';

你可以转向"abxyz"

{0, 1, 23, 24, 25}.

如果您将相邻字母之间的差值考虑在内,则会得到

{-25, 1, 22, 1, 1}

(-25 ist表示最后一个值与第一个值之间的差。)您有两个间隙:一个间隙,循环在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")
}

https://play.golang.org/p/ERhLxC_zfjl

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

按字母顺序查找最长的子字符串

按字母顺序重新排列字符串中的单词

按字母顺序从字符串中查找并计算后一对

在字符串中按字母顺序对字符进行排序

查找字符串中的点分隔单词

在ruby中按字母顺序比较字符串是错误的

以不同的顺序查找字符串中的字母

如何按字母顺序对由逗号分隔的字符串进行排序,并按成员的姓氏按字母顺序进行排序?

字符串按字母顺序排列-不按字母顺序排列第一个单词

在字符串中按顺序搜索单词列表

按字母顺序比较字符串

查找字符串中所有缺少的字母(字符串按字母顺序排列)

按索引查找字符串中的单词

如何使用sql按字符串排序的字母顺序对单词进行排序

Python在字符串中查找首字母大写后跟字母数字字符的单词

如何在Python中按字母顺序对字符串中的字母进行排序

在PostgreSQL中按字母顺序对字符串中的字母进行排序

将字母表中的字母按顺序添加到字符串中

字符串中最低字母(按字母顺序)的方法

如何使用Regex使用Python按字母顺序查找字符串?

在给定字符串之前按字母顺序查找文件

查找按字母顺序排列的Kth最小字符串

按字母顺序排列的字符串中的字符,然后将按字母顺序排列的字符放入新的字符串中?

Python:如何按字母顺序对字符串中的字母进行排序,以区分大写和小写

按字母顺序对字符串变量中的字母进行排序

按字母顺序将字符串中的字母大写并创建要存储的数组

Python函数,用于在字符的字母顺序列表中按字母顺序排列字符串

如何查找在字符串中是否存在紧随非字母字符的单词

在进行二等分搜索时,如果确定单个字符是否位于字母顺序的字符串中,则表示“无”