ch4/ch4-02

[giscus[bot]]

ch4/ch4-02

中文版

https://gopl-zh.github.io/ch4/ch4-02.html

[xianren68]

4.3

package main

import "fmt"

const length = 10

func main() {
	arr := [length]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	fmt.Println(*(reverse(&arr)))
}

// 用来反转数组
func reverse(arr *[length]int) *[length]int {
	for i := 0; i < length/2; i++ {
		// 换位
		(*arr)[i], (*arr)[length-1-i] = (*arr)[length-1-i], (*arr)[i]
	}
	return arr
}

[xianren68]

4.4

package main

import "fmt"

func main() {
	x := []int{1, 2, 3, 4, 5, 6, 7}

	fmt.Println(rangeRotate(x, 2))

}

// 1. 循环,需要额外空间
func rangeRotate(slice []int, k int) []int {
	res := make([]int, len(slice))
	for i, val := range slice {
		res[(i+k)%len(slice)] = val
	}
	return res

}

// 2. 通过反转完成，不需额外空间
// 旋转切片
// slice 要旋转的切片
// k 要旋转的距离
func rotate(slice []int, k int) {
	k = k % len(slice)
	// 1. 全部反转
	reverse(slice)
	// 2. 局部反转
	reverse(slice[k:])
	reverse(slice[:k])
}

// 反转切片
func reverse(slice []int) {
	l := len(slice)
	for i := 0; i < l/2; i++ {
		slice[i], slice[l-i-1] = slice[l-i-1], slice[i]
	}
}

[yinminggang]

好的

[Gaojc1111]

好的

[LionheartLann]

4.3

func reverse(s *[5]int) {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
}

[xianren68]

4.5

func main() {
	str := []string{"11", "11", "22", "23", "24", "24", "37"}
	str = deduplication(str)
	fmt.Println(str) // [11 22 23 24 37]
}

// 原地消除重复值函数
func deduplication(str []string) []string {
	for i := 1; i < len(str); {
		if str[i] == str[i-1] {
			copy(str[i:], str[i+1:])
			// 删除最后一位
			str = str[:len(str)-1]
		}
		i++
	}
	return str
}

[xianren68]

4.6

func main() {
	str := "afdigneigu  \n\t   fjidfiefh  jsdifj frewf      "
	bytes := []byte(str)
	bytes = onlySpace(bytes)
	fmt.Println(string(bytes)) // afdigneigu fjidfiefh jsdifj
}

// 将多个空格转化为一个
func onlySpace(str []byte) []byte {
	// 定义前后两个指针
	pre := 0
	cur := 1
	for cur < len(str) { // 遇到零值就停下
		if isSpace(str[pre]) { // 如果前面为空格
			for cur < len(str) && isSpace(str[cur]) { // 后面直接走到不是空格的位置
				cur++
			}
			// 通过copy往前挪
			copy(str[pre+1:], str[cur:])

			// 删除最后几位
			str = str[:len(str)-1-(cur-pre-1)]
			pre += 2      // 跳过肯定不是空格的位置
			cur = pre + 1 // 调整cur的位置

		} else {
			pre++
			cur++
		}
	}
	return str
}

// 判断是否为空格
func isSpace(b byte) bool {
	spaces := []byte{'\t', '\n', '\v', '\f', '\r', ' '}
	for _, val := range spaces {
		if b == val {
			return true
		}
	}
	return false
}

[xianren68]

4.7

func main() {
	str := "hfigbiredguivddkdk"
	bytes := []byte(str)
	reverse(bytes)
	fmt.Println(string(bytes))
}

// 反转函数
func reverse(bytes []byte) {
	l := len(bytes)
	for i := 0; i < l/2; i++ {
		bytes[i], bytes[l-1-i] = bytes[l-1-i], bytes[i]
	}
}

[yinxlLearning]

4.7没想明白

// 4.6
func replaceAdjacentSpaces(slice []byte) []byte {
	length := len(slice)
	result := make([]byte, 0, length)

	for i := 0; i < length; {
		r, size := utf8.DecodeRune(slice[i:])
		if unicode.IsSpace(r) {
			// 如果当前字符是空格
			result = append(result, ' ') // 将一个空格添加到结果切片
			for i+size < length {
				nextRune, nextSize := utf8.DecodeRune(slice[i+size:])
				if !unicode.IsSpace(nextRune) {
					break // 直到找到下一个非空格字符
				}
				size += nextSize // 继续增加字符大小
			}
		} else {
			// 如果当前字符不是空格
			result = append(result, slice[i:i+size]...)
		}

		i += size
	}

	return result
}

// 4.4 旋转
func rotate(str []string, k int) {
	if str == nil {
		return
	}
	reverse(str[:k])
	reverse(str[k:])
	reverse(str)
}

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

// 4.5 去除重复的值
func removeDuplication(str []string) {
	if str == nil {
		return
	}
	si := 0
	for i := 0; i < len(str); i++ {
		if i != 0 && str[i] == str[i-1] {
			continue
		}
		str[si] = str[i]
		si++
	}
	// si最终结果是len长度
	str = str[:si]
}

// int类型slice反转
func reverseSlice(s []int) {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
}

// 4.3 数组反转
func reverseArray(s *[5]int) {
	if s == nil {
		return
	}
	for left, right := 0, len(s)-1; left < right; left, right = left+1, right-1 {
		s[left], s[right] = s[right], s[left]
	}
}

[GSteve-Paul]

// 4.4
func rotate(slice []int, k int) []int {
	var sliceLen int = len(slice)
	if sliceLen == 0 {
		return nil
	}
	k = k % sliceLen
	reverse(slice[:k])
	reverse(slice[k:])
	reverse(slice)
	return slice
}

// 4.5
func eraseSame(slice []string) []string {
	var idx = 0
	var lastStr string
	for i, str := range slice {
		if i == 0 {
			idx++
			lastStr = str
			continue
		}
		if str == lastStr {
			continue
		}
		slice[idx] = str
		idx++
		lastStr = str
	}
	return slice[:idx]
}

// 4.6
func eraseMultiSpace(slice []byte) []byte {
	var write = 0
	var isPreSpace = false
	var idx int = 0
	for idx < len(slice) {
		ch, size := utf8.DecodeRune(slice[idx:])
		if unicode.IsSpace(ch) && isPreSpace {
			idx += size
			continue
		}
		isPreSpace = unicode.IsSpace(ch)
		copy(slice[write:], slice[idx:idx+size])
		idx += size
		write += size
	}
	return slice[:write]
}

// 4.7
func reverseBytes(slice []byte) []byte {
	var idx = 0
	for idx < len(slice) {
		_, size := utf8.DecodeRune(slice[idx:])
		for i, j := idx, idx+size-1; i < j; i, j = i+1, j-1 {
			slice[i], slice[j] = slice[j], slice[i]
		}
		idx += size
	}
	for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 {
		slice[i], slice[j] = slice[j], slice[i]
	}
	return slice
}

[xq-120]

4.7 DecodeRune还是你想的细啊

[xq-120]

4.7
测试：

su := []byte("哈啰😓 def  世s界 ghi jk！ ty")
//su := []byte("def hello wo ghi jk")
reverseBytes(su)
fmt.Println(string(su))

实现：

func reverseBytes(s []byte) {
	reverseBytesWithRange(s, 0, len(s)-1)
	var m, n int = 0, 0
	for i := 0; i < len(s); i++ {
		if isUTF8FirstByte(s[i]) {
			reverseBytesWithRange(s, m, n)
			n++
			m = n
		} else {
			n++
		}
	}
}

func reverseBytesWithRange(s []byte, from int, to int) {
	if from >= to {
		return
	}
	for i, j := from, to; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
}

func isUTF8FirstByte(b byte) bool {
	if b&0x80 == 0 {
		return true
	}
	if b>>6 == 3 {
		return true
	}
	return false
}

[SuperZ3]

package main

import (
	"fmt"
	"unicode"
)

func reverse(s *[6]int) {
	l := len(s) - 1
	for i := 0; 2*i <= l; i += 1 {
		s[i], s[l-i] = s[l-i], s[i]
	}
}

// assume left rotated
func rotate(s []int, n int) {
	// planA
	// stack := s[n:]
	// stack = append(stack, s[:n]...)
	// return stack

	// planB
	for i := n; i < len(s); i++ {
		s[i-n], s[i] = s[i], s[i-n]
	}
}

func unique(str []string) {
	if len(str) == 0 {
		return
	}
	flag := str[0]
	for i := 1; i < len(str); i++ {
		if str[i] != flag {
			flag = str[i]
		} else {
			str[i] = ""
		}
	}
}

func singleSpace(s []byte) []byte {
	count := -1
	i := 0
	for  ;i < len(s); i++ {
		if unicode.IsSpace(rune(s[i])) {
			count++
		} else {
			if count > 0 {
				move := s[i:]
				copy(s[i-count:], move)
				s = s[:len(s) - count]
				i = i - count
			}
			count = -1
		}
	}
	return s
}

func main() {
	a := [6]int{4, 2, 9, 6, 1, 7}
	b := []int{4, 2, 9, 6, 1, 7}
	c := []string{"aa", "cc", "cc", "aa", "dd", "ee", "ee", "ee"}
	d := []byte("   a b  c    d  ee ")

	// 4.3
	reverse(&a)
	fmt.Println(a)

	// 4.4
	// fmt.Println(rotate(b, 2))
	rotate(b, 2)
	fmt.Println(b)

	// 4.5
	unique(c)
	fmt.Println(c)

	// 4.6
	d = singleSpace(d)
	fmt.Println(string(d))
	
	// 4.7 can't understand
}

[lyb88999]

// 4.6
func replaceAdjacentSpaces2(data []byte) []byte {
	var (
		write  int
		spaced bool
		r      rune
		size   int
	)
	for read := 0; read < len(data); read += size {
		r, size = utf8.DecodeRune(data[read:])
		if unicode.IsSpace(r) {
			if !spaced {
				data[write] = ' '
				write++
				spaced = true
			}
		} else {
			write += utf8.EncodeRune(data[write:], r)
			spaced = false
		}
	}
	return data[:write]
}

[scutBCH]

// 4.6
func removeDupSpace(slides []byte) []byte {
	i, j := 0, 0

	for j < len(slides) {
		slides[i] = slides[j]
		
		if !unicode.IsSpace(rune(slides[i])) {
			i++
			j++
			continue
		}

		i++
		for j < len(slides) && unicode.IsSpace(rune(slides[j])) {
			j++
		}
	}
	return slides[:i]
}

[scutBCH]

// 4.7
func reverseStrBytes(str []byte) []byte {
	idx := 0
	for idx < len(str) {
		_, size := utf8.DecodeRune(str[idx:])
		reverseBytes(str[idx : idx+size])
		idx += size
	}
	reverseBytes(str)
	return str
}

func reverseBytes(slide []byte) {
	for i, j := 0, len(slide)-1; i < j; i, j = i+1, j-1 {
		slide[i], slide[j] = slide[j], slide[i]
	}
}

[haofeng98]

func ReversebyPtr(ptr *[]int) {
	slice := *ptr
	for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 {
		slice[i], slice[j] = slice[j], slice[i]
	}
}

[hup2c]

练习 4.6： 编写一个函数，原地将一个UTF-8编码的[]byte类型的slice中相邻的空格（参考unicode.IsSpace）替换成一个空格返回

func TestClearSpace(t *testing.T) {
	fmt.Println(string(clearSpace([]byte("  1  2 \n\t  3 4  56 7   "))))
}

// clearSpace 无拷贝(注意尾部多个空格的话也需要保留一个)
func clearSpace(arr []byte) []byte {
	j := 0
	for i := 1; i < len(arr); i++ {
		if isSpace(arr[i]) && isSpace(arr[j]) {
			continue
		}
		j++
		arr[j] = arr[i]
	}
	return arr[:j+1]
}

// isSpace 参考 unicode.IsSpace
func isSpace(testByte byte) bool {
	for _, spaceByte := range []byte{'\t', '\n', '\v', '\f', '\r', ' ', 0x85, 0xA0} {
		if testByte == spaceByte {
			return true
		}
	}
	return false
}

[coderZoe]

4.4 一次遍历完成旋转

func test2[T any](slice []T, index int) []T {
	slice = append(slice, slice[:index]...)
	slice = slice[index:]
	return slice
}

4.5 消除相邻相等元素

func test3(slice []string) []string {
	if len(slice) == 0 || len(slice) == 1 {
		return slice
	}
	count := 0
	for i := 1; i < len(slice); i++ {
		if slice[i] != slice[i-1] {
			count++
			slice[count] = slice[i]
		}
	}
	return slice[:count+1]
}

[soondubu137]

Exercise 4.5

func removeAdjacentDuplicates(s []string) []string {
    // edge case
	if len(s) <= 1 {
		return s
	}
	i := 1
	curr := s[0]
	for j := 1; j < len(s); j++ {
		if s[j] != curr {
			s[i] = s[j]
			i++
			curr = s[j]
		}
	}	
	return s[:i]
}

[Apahno]

4.6
func onlySpace(str []byte) []byte {
//定义前后两个指针
//pre := 0
resp := make([]byte, len(str))
//cur := 0
resp[0] = str[0]
respIdx := 1
for i := 1; i < len(str); i++ {
//如果当前是空格且前一个位置不是空格，那么记录当前位置
if unicode.IsSpace(rune(str[i])) {
if !unicode.IsSpace(rune(str[i-1])) {
resp[respIdx] = str[i]
respIdx++
} else {
continue
}
} else {
resp[respIdx] = str[i]
respIdx++
}
}
return resp[:respIdx]
}
func main() {
str := "afdigneigu \n\t fjidfiefh jsdifj frewf "
bytes := []byte(str)
bytes = onlySpace(bytes)
fmt.Println(string(bytes)) // afdigneigu fjidfiefh jsdifj
fmt.Println(len(bytes))
}

[ww-tj]

func eraseStr(s []string) []string {
	fmt.Println(s)
	var i, j int
	for i = 0; i < len(s) && j < len(s); i++ {
		j = i + 1
		for j < len(s) && s[j] == s[i] {
			j++
		}
		if j-i > 1 {
			copy(s[i+1:], s[j:])
			fmt.Println(s)
		}
	}
	return s[:i]
}
func main() {
	s := []string{"a", "a", "b", "b", "b", "c"}
	fmt.Println(eraseStr(s))
}

[ilikeyu]

func reverseByte() {
s := 修改reverse函数用于原地反转UTF-8编码的[]byte。是否可以不用分配额外的内存？
bs := []byte(s)
for i, j := 0, len(bs)-1; i < j; i, j = i+1, j-1 {
bs[i], bs[j] = bs[j], bs[i]
}
for i := 0; i < len(bs); i += 1 {
m := bs[i] >> 4
if m == 0b1111 {
bs[i], bs[i-3] = bs[i-3], bs[i]
bs[i-1], bs[i-2] = bs[i-2], bs[i-1]
} else if m == 0b1110 {
bs[i], bs[i-2] = bs[i-2], bs[i]
} else if m == 0b1100 {
bs[i], bs[i-1] = bs[i-1], bs[i]
}
}
ss := string(bs)
fmt.Println(ss)
}

[LikeAPhoenix]

4.7

package main

import (
	"fmt"
	"unicode/utf8"
)

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

func main() {
	str := "你好，世界！Hello, world!"
	b := []byte(str)

	for i := 0; i < len(b); {
		_, size := utf8.DecodeRune(b[i:])
		reverse(b[i:i+size])
		i += size
	}
	reverse(b)

	fmt.Println(string(b))
}

[hongjiala]

// 练习 4.3： 重写reverse函数，使用数组指针代替slice
package main

import "fmt"

func main() {
s := []int{5, 6, 7, 8, 9}
reverse(&s)
fmt.Println(s)
}

func reverse(s *[]int) {
for i, j := 0, len(*s)-1; i < j; i, j = i+1, j-1 {
(*s)[i], (*s)[j] = (*s)[j], (*s)[i]
}
}

[hongjiala]

// 练习 4.4： 编写一个rotate函数，通过一次循环完成旋转
package main

import "fmt"

func main() {
s := []int{5, 6, 7, 8, 9}
reverse(&s, 2)
fmt.Println(s)
}

func reverse(s *[]int, n int) {
for i := 0; i < n; i++ {
*s = append((*s)[1:], (*s)[0])
}

}

[hongjiala]

// 练习 4.5： 写一个函数在原地完成消除[]string中相邻重复的字符串的操作。
package main

import (
"fmt"
)

func main() {
s := []string{"a", "a", "b", "b", "c", "c", "c", "d", "d", "e", "e", "e", "e", "f", "f", "f", "f", "f"}
s = clearRepeat(s)
fmt.Println(s)
}

func clearRepeat(s []string) []string {
for flag := 1; ; {
for i := 0; i < len(s)-1; i++ {
if s[i] == s[i+1] {
copy(s[i+1:], s[i+2:])
// 删除最后一位
s = s[:len(s)-1]
flag = 0
break
} else {
flag = flag + 1

		}
	}
	if flag == len(s)-1 {
		break
	}
}
return s

}

[hongjiala]

// 练习 4.6： 编写一个函数，原地将一个UTF-8编码的[]byte类型的slice中相邻的空格（参考unicode.IsSpace）替换成一个空格返回
package main

import (
"fmt"
"unicode"
)

func main() {
str := []byte("hello world")
str = deduplication(str)
fmt.Println(string(str))
}

// 原地消除重复值函数
func deduplication(str []byte) []byte {
for i := 1; i < len(str); {
if str[i] == str[i-1] && unicode.IsSpace(rune(str[i])) {
// 删除重复值
copy(str[i:], str[i+1:])
// 删除最后一位
str = str[:len(str)-1]
}
i++
}
return str
}

[hongjiala]

// 练习 4.7： 修改reverse函数用于原地反转UTF-8编码的[]byte。是否可以不用分配额外的内存
package main

import (
"fmt"
)

func main() {
str := []byte("hello 世界")
reverse(str)
fmt.Println(string(str))
}

// reverse 原地反转 UTF-8 编码的 []byte，不分配额外内存
func reverse(s []byte) {
// 第一步：整体反转整个字节切片
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
// 第二步：修正每个 UTF-8 字符的字节顺序
for i := 0; i < len(s); {
j := i
// 由于反转后，多字节字符的字节块会以一个或多个续字节开头，
// 我们先跳过所有属于续字节的部分（续字节范围为 0x80~0xBF）
for j < len(s) && s[j] >= 0x80 && s[j] <= 0xBF {
j++
}
// 再加上那个非续字节（如果存在），它实际上是该字符原来的首字节
if j < len(s) {
j++
}
// 反转当前区间 [i, j) 内的字节，即可恢复该字符内部的正确顺序
for k, l := i, j-1; k < l; k, l = k+1, l-1 {
s[k], s[l] = s[l], s[k]
}
i = j
}
}

[iriskl]

4.7

func Reverse(s []byte) {
	// 初始化两个指针 i 和 j，分别指向切片的开头和结尾
	for i, j := 0, len(s); i < j; {
		// 解码当前字符
		_, iLen := utf8.DecodeRune(s[i:])
		_, jLen := utf8.DecodeLastRune(s[:j])

		// 如果 i 和 j 指向的字符长度不同，则无法交换，直接退出
		if iLen != jLen {
			break
		}

		// 交换 i 和 j 位置的字符
		for k := 0; k < iLen; k++ {
			s[i+k], s[j-jLen+k] = s[j-jLen+k], s[i+k]
		}

		// 移动 i 和 j 指针，继续处理下一个字符
		i += iLen
		j -= jLen
	}
}