如何找到数组中最长的字符串？

Question

实际上，我可以使用 Go 语言中的两个循环来完成它，例如，如果我有如下数组：["aa", "aab", "bcd", "a", "cdf", "bb"]我需要返回具有 maxLength 的字符串。所以输出将是：["aab", "bcd", "cdf"]这就是我在做什么。package mainimport "fmt"func allLongestStrings(inputArray []string) []string {    maxLength := len(inputArray[0])    outputArray := []string{}    for _, value := range inputArray {        if len(value) > maxLength {            maxLength = len(value)        }    }    for _, val := range inputArray {        if len(val) == maxLength {            outputArray = append(outputArray, val)        }    }    return outputArray}func main() {    xs := []string{"aa", "aab", "bcd", "a", "cdf", "bb"}    fmt.Println(allLongestStrings(xs))}是否可以在一个循环中执行此操作，因为我正在运行相同的循环两次以查找长度并在 outputArray 中附加字符串。

Answer 1

尝试这个：

func allLongestStrings(inputArray []string) []string {

    max := -1 // -1 is guaranteed to be less than length of string

    var result []string

    for _, s := range inputArray {

        if len(s) < max {

            // Skip shorter string

            continue

        }

        if len(s) > max {

            // Found longer string. Update max and reset result.

            max = len(s)

            result = result[:0]

        }

        // Add to result

        result = append(result, s)

    }

    return result

}

结果切片的容量可以大于所需的容量，并且可以包含超过切片长度的字符串值。额外的分配和字符串引用在某些情况下可能是个问题（结果保留很长时间，字符串很大，...）。如果分配和引用是一个问题，则返回切片的副本。

func allLongestStrings(inputArray []string) []string {

    ...

    return append([]string(nil), result...)

}

如果函数可以改变原始切片，则可以在输入切片中构造函数结果。这避免了结果切片的分配。

func allLongestStrings(inputArray []string) []string {

    n := 0

    max := -1

    for i, s := range inputArray {

        if len(s) < max {

            // Skip shorter string

            continue

        }

        if len(s) > max {

            // Found longer string. Update max and reset result.

            max = len(s)

            n = 0

        }

        inputArray[n], inputArray[i] = inputArray[i], inputArray[n]

        n++

    }

    return inputArray[:n]

}

Answer 2

我会通过使用 sort 包来做到这一点。基本上，您要做的是通过实现sort.Interface并使用sort.Sort来创建自定义排序功能。

package main

import "sort"

import "fmt"

type sortByLength []string

// Len implements Len of sort.Interface

func (s sortByLength) Len() int {

   return len(s)

}

// Swap implements Swap of sort.Interface

func (s sortByLength) Swap(i, j int) {

   s[i], s[j] = s[j], s[i]

}

// Less implements Less of sort.Interface

func (s sortByLength) Less(i, j int) bool {

    return len(s[i]) > len(s[j])

}

func main() {

    toFind := []string{"aa", "aab", "bcd", "a", "cdf", "bb"}

    // We sort it by length, descending

    sort.Sort(sortByLength(toFind))

    // The first element is sure to be the longest

    longest := []string{toFind[0]}

    // In case we have more than one element in toFind...

    if len(toFind) > 1 {

        // ...we need to find all remaining elements of toFind...

        for _, str := range toFind[1:] {

            // ...which are not smaller than the first element of longest.

            if len(str) < len(longest[0]) {

                // In case the current element is smaller in length, we can stop iterating

                // over toFind.

                break

            }

            // We know that str has the same length as longest[0], so we append it

            longest = append(longest, str)

        }

    }

    fmt.Println(longest)

}

然而，虽然您自己的代码中只有一个循环，但排序显然也会遍历输入。

Answer 3

例如

package main

import "fmt"

func longest(a []string) []string {

    var l []string

    if len(a) > 0 {

        l = append(l, a[0])

        a = a[1:]

    }

    for _, s := range a {

        if len(l[0]) <= len(s) {

            if len(l[0]) < len(s) {

                l = l[:0]

            }

            l = append(l, s)

        }

    }

    return append([]string(nil), l...)

}

func main() {

    a := []string{"aa", "aab", "bcd", "a", "cdf", "bb"}

    fmt.Println(len(a), a)

    l := longest(a)

    fmt.Println(len(l), cap(l), l)

}

游乐场：https://play.golang.org/p/JTvl4wVvSEK

输出：

6 [aa aab bcd a cdf bb]
3 4 [aab bcd cdf]

例如，对于最大值和最小值问题，避免使用特殊值作为初始最大值或最小值。不要过度分配内存，也不要留下悬空指针。

Gostring实现为：

type stringStruct struct {

    str unsafe.Pointer

    len int

}

如果列表由 1,000 个长度为 1,000 的字符串和一个长度为 1,001 的字符串组成，则返回的列表的长度为 1，容量至少为 1,000。999 个条目有指向 1,000 字节字符串的悬垂指针，Go gc 将无法释放这些字符串，浪费超过 1 兆字节。

package main

import (

    "fmt"

    "strings"

    "unsafe"

)

type stringStruct struct {

    str unsafe.Pointer

    len int

}

func main() {

    var l []string

    for n := 0; n < 1000; n++ {

        l = append(l, strings.Repeat("x", 1000))

    }

    l = l[:0]

    l = append(l, strings.Repeat("y", 1001))

    over := (cap(l) - len(l)) * int(unsafe.Sizeof(stringStruct{}))

    for i, o := len(l), l[:cap(l)]; i < cap(l); i++ {

        over += len(o[i])

    }

    fmt.Println(over) // 1015368 bytes 64-bit, 1007184 bytes 32-bit 

}

游乐场：https://play.golang.org/p/Fi7EgbvdVkp

一个程序要正确，就必须是可读的。首先，在不受错误或特殊情况干扰的情况下编写基本算法。

var l []string

for _, s := range a {

    if len(l[0]) <= len(s) {

        if len(l[0]) < len(s) {

            l = l[:0]

        }

        l = append(l, s)

    }

}

接下来，在不中断基本算法流程的情况下添加特殊情况。在这种情况下，处理零和一长度列表。

var l []string

if len(a) > 0 {

    l = append(l, a[0])

    a = a[1:]

}

for _, s := range a {

    if len(l[0]) <= len(s) {

        if len(l[0]) < len(s) {

            l = l[:0]

        }

        l = append(l, s)

    }

}

最后，确保函数对 CPU 和内存都有效。分配是精确的，没有指向未使用字符串的悬垂指针。

var l []string

if len(a) > 0 {

    l = append(l, a[0])

    a = a[1:]

}

for _, s := range a {

    if len(l[0]) <= len(s) {

        if len(l[0]) < len(s) {

            l = l[:0]

        }

        l = append(l, s)

    }

}

return append([]string(nil), l...)