如何在围棋中反向字符串？

如何在 Go 中逆转一个简单的字符串？

119826 次浏览
小开

一个我认为可以在 unicode 上运行的版本，它是基于 utf8.Rune 函数构建的:

func Reverse(s string) string {
b := make([]byte, len(s));
for i, j := len(s)-1, 0; i >= 0; i-- {
if utf8.RuneStart(s[i]) {
rune, size := utf8.DecodeRuneInString(s[i:len(s)]);
utf8.EncodeRune(rune, b[j:j+size]);
j += size;
}
}
return string(b);
}
小开

拉斯 · 考克斯(Russ Cox)在果仁邮件列表上建议

package main
import "fmt"
func main() {
input := "The quick brown 狐 jumped over the lazy 犬"
// Get Unicode code points.
n := 0
rune := make([]rune, len(input))
for _, r := range input {
rune[n] = r
n++
}
rune = rune[0:n]
// Reverse
for i := 0; i < n/2; i++ {
rune[i], rune[n-1-i] = rune[n-1-i], rune[i]
}
// Convert back to UTF-8.
output := string(rune)
fmt.Println(output)
}
小开

注意: 这个答案来自2009年，所以现在可能有更好的解决方案。

看起来有点“迂回”，可能效率不是很高，但是说明了如何使用 Reader 接口读取字符串。当使用 utf8字符串时，IntVector 似乎也非常适合作为缓冲区。

如果省略“大小”部分，通过“插入”插入到向量中，效率会更低，因为每次添加新的符文时，整个向量都需要向后推一。

这个解决方案绝对适用于 utf8字符。

package main


import "container/vector";
import "fmt";
import "utf8";
import "bytes";
import "bufio";




func
main() {
toReverse := "Smørrebrød";
fmt.Println(toReverse);
fmt.Println(reverse(toReverse));
}


func
reverse(str string) string {
size := utf8.RuneCountInString(str);
output := vector.NewIntVector(size);
input := bufio.NewReader(bytes.NewBufferString(str));
for i := 1; i <= size; i++ {
rune, _, _ := input.ReadRune();
output.Set(size - i, rune);
}
return string(output.Data());
}
小开

这对 unicode 字符串有效，它考虑了以下两点:

  • Range 通过枚举 Unicode 字符来处理字符串
  • 字符串可以由 int 切片构造，其中每个元素都是一个 Unicode字符。

这么说吧:

func reverse(s string) string {
o := make([]int, utf8.RuneCountInString(s));
i := len(o);
for _, c := range s {
i--;
o[i] = c;
}
return string(o);
}
小开

这种方法可以正常工作，不需要对函数进行任何修改:

func Reverse(s string) (result string) {
for _,v := range s {
result = string(v) + result
}
return
}
小开

我注意到这个问题时，西蒙公布的 他的解决方案，因为字符串是不可变的，是非常低效的。其他提出的解决方案也有缺陷; 它们不起作用或效率低下。

下面是一个有效的解决方案，除非字符串不是有效的 UTF-8或字符串包含组合字符。

package main


import "fmt"


func Reverse(s string) string {
n := len(s)
runes := make([]rune, n)
for _, rune := range s {
n--
runes[n] = rune
}
return string(runes[n:])
}


func main() {
fmt.Println(Reverse(Reverse("Hello, 世界")))
fmt.Println(Reverse(Reverse("The quick brown 狐 jumped over the lazy 犬")))
}
小开

在 Go1符文是一个内置类型。

func Reverse(s string) string {
runes := []rune(s)
for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
runes[i], runes[j] = runes[j], runes[i]
}
return string(runes)
}
小开

符文是一种类型，所以使用它。此外，围棋不使用分号。

func reverse(s string) string {
l := len(s)
m := make([]rune, l)


for _, c := range s {
l--
m[l] = c
}
return string(m)
}


func main() {
str := "the quick brown 狐 jumped over the lazy 犬"
fmt.Printf("reverse(%s): [%s]\n", str, reverse(str))
}
小开

这是最快的实现

func Reverse(s string) string {
size := len(s)
buf := make([]byte, size)
for start := 0; start < size; {
r, n := utf8.DecodeRuneInString(s[start:])
start += n
utf8.EncodeRune(buf[size-start:], r)
}
return string(buf)
}


const (
s       = "The quick brown 狐 jumped over the lazy 犬"
reverse = "犬 yzal eht revo depmuj 狐 nworb kciuq ehT"
)


func TestReverse(t *testing.T) {
if Reverse(s) != reverse {
t.Error(s)
}
}


func BenchmarkReverse(b *testing.B) {
for i := 0; i < b.N; i++ {
Reverse(s)
}
}
小开

这里还有另一个解决方案:

func ReverseStr(s string) string {
chars := []rune(s)
rev := make([]rune, 0, len(chars))
for i := len(chars) - 1; i >= 0; i-- {
rev = append(rev, chars[i])
}
return string(rev)
}

然而，Yazu 上面的解决方案更加优雅，因为他在适当的位置反转了 []rune切片。

小开

另一种解决方案(tm) :

package main
import "fmt"


type Runes []rune


func (s Runes) Reverse() (cp Runes) {
l := len(s); cp = make(Runes, l)
// i <= 1/2 otherwise it will mess up with odd length strings
for i := 0; i <= l/2; i++ {
cp[i], cp[l-1-i] = s[l-1-i], s[i]
}
return cp
}


func (s Runes) String() string {
return string(s)
}


func main() {
input := "The quick brown 狐 jumped over the lazy 犬 +odd"
r := Runes(input)
output := r.Reverse()
valid := string(output.Reverse()) == input
fmt.Println(len(r), len(output), r, output.Reverse(), valid)
}
小开

如果需要处理字符集群，请使用 unicode 或 regexp 模块。

package main


import (
"unicode"
"regexp"
)


func main() {
str := "\u0308" + "a\u0308" + "o\u0308" + "u\u0308"
println("u\u0308" + "o\u0308" + "a\u0308" + "\u0308" == ReverseGrapheme(str))
println("u\u0308" + "o\u0308" + "a\u0308" + "\u0308" == ReverseGrapheme2(str))
}


func ReverseGrapheme(str string) string {


buf := []rune("")
checked := false
index := 0
ret := ""


for _, c := range str {


if !unicode.Is(unicode.M, c) {


if len(buf) > 0 {
ret = string(buf) + ret
}


buf = buf[:0]
buf = append(buf, c)


if checked == false {
checked = true
}


} else if checked == false {
ret = string(append([]rune(""), c)) + ret
} else {
buf = append(buf, c)
}


index += 1
}


return string(buf) + ret
}


func ReverseGrapheme2(str string) string {
re := regexp.MustCompile("\\PM\\pM*|.")
slice := re.FindAllString(str, -1)
length := len(slice)
ret := ""


for i := 0; i < length; i += 1 {
ret += slice[length-1-i]
}


return ret
}
小开

此代码保留完整的组合字符序列，并且 也应该使用无效的 UTF-8输入。

package stringutil
import "code.google.com/p/go.text/unicode/norm"


func Reverse(s string) string {
bound := make([]int, 0, len(s) + 1)


var iter norm.Iter
iter.InitString(norm.NFD, s)
bound = append(bound, 0)
for !iter.Done() {
iter.Next()
bound = append(bound, iter.Pos())
}
bound = append(bound, len(s))
out := make([]byte, 0, len(s))
for i := len(bound) - 2; i >= 0; i-- {
out = append(out, s[bound[i]:bound[i+1]]...)
}
return string(out)
}

如果 unicode/norm 原语可以更高效一些 允许迭代字符串的边界 分配。参见 https://code.google.com/p/go/issues/detail?id=9055。

小开

来自 转到示例项目: golang/example/stringutil/overse.Go，作者 Andrew Gerrand

/*
Copyright 2014 Google Inc.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/


// Reverse returns its argument string reversed rune-wise left to right.
func Reverse(s string) string {
r := []rune(s)
for i, j := 0, len(r)-1; i < len(r)/2; i, j = i+1, j-1 {
r[i], r[j] = r[j], r[i]
}
return string(r)
}

转到游乐场反向字符串

在反转字符串“ bròwn”之后，正确的结果应该是“ nwòrb”，而不是“ nsomething orb”。
注意字母 o 上面的坟墓。

为了保留 Unicode 组合字符，如“ as df”和反向结果“ f ds a”,
请参阅下列其他代码:

Http://rosettacode.org/wiki/reverse_a_string#go

小开 
package reverseString


import "strings"


// ReverseString - output the reverse string of a given string s
func ReverseString(s string) string {


strLen := len(s)


// The reverse of a empty string is a empty string
if strLen == 0 {
return s
}


// Same above
if strLen == 1 {
return s
}


// Convert s into unicode points
r := []rune(s)


// Last index
rLen := len(r) - 1


// String new home
rev := []string{}


for i := rLen; i >= 0; i-- {
rev = append(rev, string(r[i]))
}


return strings.Join(rev, "")
}

测试

package reverseString


import (
"fmt"
"strings"
"testing"
)


func TestReverseString(t *testing.T) {


s := "GO je úžasné!"
r := ReverseString(s)


fmt.Printf("Input: %s\nOutput: %s", s, r)


revR := ReverseString(r)


if strings.Compare(s, revR) != 0 {
t.Errorf("Expecting: %s\n. Got: %s\n", s, revR)
}
}

输出

Input: GO je úžasné!
Output: !énsažú ej OG
PASS
ok      github.com/alesr/reverse-string 0.098s
小开

这里有太多答案了。有些是明显的复制品。但是，即使从左边开始，也很难选择最好的解决方案。

所以我仔细检查了答案，扔掉了不适用于 unicode 的那个，还删除了重复的。我以幸存者为基准，找出最快的。因此，带有归因的 这是结果(如果你注意到我错过的答案，但值得添加，请随意修改基准) :

Benchmark_rmuller-4   100000         19246 ns/op
Benchmark_peterSO-4    50000         28068 ns/op
Benchmark_russ-4       50000         30007 ns/op
Benchmark_ivan-4       50000         33694 ns/op
Benchmark_yazu-4       50000         33372 ns/op
Benchmark_yuku-4       50000         37556 ns/op
Benchmark_simon-4       3000        426201 ns/op

这就是 最快法:

func Reverse(s string) string {
size := len(s)
buf := make([]byte, size)
for start := 0; start < size; {
r, n := utf8.DecodeRuneInString(s[start:])
start += n
utf8.EncodeRune(buf[size-start:], r)
}
return string(buf)
}

由于某种原因，我不能添加基准测试，所以您可以从 PlayGround复制它(您不能在那里运行测试)。重命名它并运行 go test -bench=.

小开

它肯定不是最有效的内存解决方案，但是对于一个“简单”的 UTF-8安全解决方案，以下内容将完成这项工作，而不会破坏符文。

在我看来，它是这一页中最易读和最容易理解的。

func reverseStr(str string) (out string) {
for _, s := range str {
out = string(s) + out
}


return
}
小开

这里有很大的不同，我会说更多的功能性方法，没有列在其他答案中:

func reverse(s string) (ret string) {
for _, v := range s {
defer func(r rune) { ret += string(r) }(v)
}
return
}
小开

尝试以下代码:

package main


import "fmt"


func reverse(s string) string {
chars := []rune(s)
for i, j := 0, len(chars)-1; i < j; i, j = i+1, j-1 {
chars[i], chars[j] = chars[j], chars[i]
}
return string(chars)
}


func main() {
fmt.Printf("%v\n", reverse("abcdefg"))
}

更多信息检查 http://golangcookbook.com/chapters/strings/reverse/
还有一个 http://www.dotnetperls.com/reverse-string-go

小开

下面两个方法比最快的 保留组合字符的解决方案运行得更快，但这并不是说我在基准测试设置中遗漏了什么。

//input string s
bs := []byte(s)
var rs string
for len(bs) > 0 {
r, size := utf8.DecodeLastRune(bs)
rs += fmt.Sprintf("%c", r)
bs = bs[:len(bs)-size]
} // rs has reversed string

第二种方法的灵感来自 这个

//input string s
bs := []byte(s)
cs := make([]byte, len(bs))
b1 := 0
for len(bs) > 0 {
r, size := utf8.DecodeLastRune(bs)
d := make([]byte, size)
_ = utf8.EncodeRune(d, r)
b1 += copy(cs[b1:], d)
bs = bs[:len(bs) - size]
} // cs has reversed bytes
小开

我编写了以下 Reverse函数，它尊重 UTF8编码和组合字符:

// Reverse reverses the input while respecting UTF8 encoding and combined characters
func Reverse(text string) string {
textRunes := []rune(text)
textRunesLength := len(textRunes)
if textRunesLength <= 1 {
return text
}


i, j := 0, 0
for i < textRunesLength && j < textRunesLength {
j = i + 1
for j < textRunesLength && isMark(textRunes[j]) {
j++
}


if isMark(textRunes[j-1]) {
// Reverses Combined Characters
reverse(textRunes[i:j], j-i)
}


i = j
}


// Reverses the entire array
reverse(textRunes, textRunesLength)


return string(textRunes)
}


func reverse(runes []rune, length int) {
for i, j := 0, length-1; i < length/2; i, j = i+1, j-1 {
runes[i], runes[j] = runes[j], runes[i]
}
}


// isMark determines whether the rune is a marker
func isMark(r rune) bool {
return unicode.Is(unicode.Mn, r) || unicode.Is(unicode.Me, r) || unicode.Is(unicode.Mc, r)
}

我尽力使它尽可能高效和易读。这个想法很简单，遍历符文寻找组合字符，然后就地反转组合字符的符文。一旦我们已经覆盖了他们所有，逆转符文的整个字符串也在地方。

假设我们想逆转这个字符串 bròwn。ò由两个如尼文表示，一个代表 o，一个代表代表“坟墓”的这个单码 \u0301a。

为了简单起见，让我们像这样表示字符串 bro'wn。我们要做的第一件事就是寻找组合字符并将它们反转。现在我们有了字符串 br'own。最后，我们反转整个字符串，最终得到 nwo'rb。这是返回给我们的 nwòrb

你可以在这里找到它 https://github.com/shomali11/util，如果你想使用它。

下面是一些测试用例，展示了几个不同的场景:

func TestReverse(t *testing.T) {
assert.Equal(t, Reverse(""), "")
assert.Equal(t, Reverse("X"), "X")
assert.Equal(t, Reverse("b\u0301"), "b\u0301")
assert.Equal(t, Reverse("😎⚽"), "⚽😎")
assert.Equal(t, Reverse("Les Mise\u0301rables"), "selbare\u0301siM seL")
assert.Equal(t, Reverse("ab\u0301cde"), "edcb\u0301a")
assert.Equal(t, Reverse("This `\xc5` is an invalid UTF8 character"), "retcarahc 8FTU dilavni na si `�` sihT")
assert.Equal(t, Reverse("The quick bròwn 狐 jumped over the lazy 犬"), "犬 yzal eht revo depmuj 狐 nwòrb kciuq ehT")
}
小开

您还可以导入一个现有的实现:

import "4d63.com/strrev"

然后:

strrev.Reverse("abåd") // returns "dåba"

或者反转包含 Unicode 组合字符的字符串:

strrev.ReverseCombining("abc\u0301\u031dd") // returns "d\u0301\u031dcba"

这些实现支持 Unicode 多字节的正确排序和反向的梳理字符。

注意: 许多编程语言中的内置字符串反向函数不保留组合，并且识别组合字符需要显著更多的执行时间。

小开

对于简单的字符串，可以使用这样的结构:

func Reverse(str string) string {
if str != "" {
return Reverse(str[1:]) + str[:1]
}
return ""
}

对于 Unicode 字符串，它可能如下所示:

func RecursiveReverse(str string) string {
if str == "" {
return ""
}
runes := []rune(str)
return RecursiveReverse(string(runes[1:])) + string(runes[0])
}
小开 
    func reverseString(someString string) string {
runeString := []rune(someString)
var reverseString string
for i := len(runeString)-1; i >= 0; i -- {
reverseString += string(runeString[i])
}
return reverseString
}
小开 
//Reverse reverses string using strings.Builder. It's about 3 times faster
//than the one with using a string concatenation
func Reverse(in string) string {
var sb strings.Builder
runes := []rune(in)
for i := len(runes) - 1; 0 <= i; i-- {
sb.WriteRune(runes[i])
}
return sb.String()
}




//Reverse reverses string using string
func Reverse(in string) (out string) {
for _, r := range in {
out = string(r) + out
}
return
}


BenchmarkReverseStringConcatenation-8   1000000 1571 ns/op  176 B/op    29 allocs/op
BenchmarkReverseStringsBuilder-8        3000000 499 ns/op   56 B/op 6 allocs/op

使用字符串.Builder 比使用字符串串联快3倍左右

小开

使用 rune的一个简单的中风:

func ReverseString(s string) string {
runes := []rune(s)
size := len(runes)
for i := 0; i < size/2; i++ {
runes[size-i-1], runes[i] = runes[i],  runes[size-i-1]
}
return string(runes)
}


func main() {
fmt.Println(ReverseString("Abcdefg 汉语 The God"))
}

: doG ehT 语汉 gfedcbA
小开 
func Reverse(s string) string {
r := []rune(s)
var output strings.Builder
for i := len(r) - 1; i >= 0; i-- {
output.WriteString(string(r[i]))
}


return output.String()
}
小开 
func reverseStr(b string) {
for _, v := range []rune(b) {
defer fmt.Printf("%c", v)


}
}

推迟是有用的，因为它是后进先出的最后

小开 
func ReverseString(str string) string {
output :=""
for _, char := range str {
output = string(char) + output
}
return output
}


// "Luizpa" -> "apziuL"
// "123日本語" -> "語本日321"
// "⚽😎" -> "😎⚽"
// "´a´b´c´" -> "´c´b´a´"
小开

简单，甜蜜，高效

func reverseStr(str string) string {
strSlice := []rune(str)  //converting to slice of runes
length := len(strSlice)


for i := 0; i < (length / 2); i++ {
strSlice[i], strSlice[length-i-1] = strSlice[length-i-1], strSlice[i]
}
return string(strSlice)  //converting back to string
}
小开

逐字颠倒字符串也是类似的过程。首先，我们将字符串转换为一个字符串数组，其中每个条目都是一个单词。接下来，我们将正常的反向循环应用于该数组。最后，我们将结果重新压缩到一个字符串中，以便返回给调用者。

package main


import (
"fmt"
"strings"
)


func reverse_words(s string) string {
words := strings.Fields(s)
for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
words[i], words[j] = words[j], words[i]
}
return strings.Join(words, " ")
}


func main() {
fmt.Println(reverse_words("one two three"))
}
小开

在 golang 中，字符串是不可变物件的，不像 C 那样，在 golang 中不可能使用反向。 使用 C，你可以做类似于,

void reverseString(char *str) {
int length = strlen(str)
for(int i = 0, j = length-1; i < length/2; i++, j--)
{
char tmp = str[i];
str[i] = str[j];
str[j] = tmp;
}
}

但是对于 golang，接下来的是使用 byte 首先将输入转换成字节，然后在反转字节数组后将其反转，在返回之前将其转换回字符串。只能用于非 unicode 类型的字符串。

package main


import "fmt"


func main() {
s := "test123 4"
fmt.Println(reverseString(s))
}


func reverseString(s string) string {
a := []byte(s)
for i, j := 0, len(s)-1; i < j; i++ {
a[i], a[j] = a[j], a[i]
j--
}
return string(a)
}
小开

另一种方法是使用内置的语言特性，例如 defer:

package main


import "fmt"


func main() {
var name string
fmt.Scanln(&name)


for _, char := range []rune(name) {
defer fmt.Printf("%c", char) // <-- LIFO does it all for you
}
}

提交答案