Go数组及相关算法（下）+ Go 基础笔记

对 Go 数组和相关算法继续学习，并做了笔记。
做了一部分 Go 基础的笔记。
相关链接：代码随想录

• Go 基础笔记
  • Go 基本类型
  • Go 变量声明
  • Go 下划线
  • init 函数和 main 函数
  • Go 类型别名和自定义类型
• 209.长度最小的子数组
  • 暴力解法（力扣超时）
  • 滑动窗口法
• 59.螺旋矩阵II
  • 循环不变量1
  • 循环不变量2

# Go 基础笔记

Go 思想：Less can be more.

Go 优点

• 自带 gc
• 静态编译，编译好后，扔服务器直接运行
• 简单的思想，没有继承、多态、类等
• 丰富的库和详细的开发文档
• 语法层支持并发，和拥有同步并发的 channel 类型，使并发开发变得非常方便
• 简洁的语法、提高开发效率，同时提高代码的阅读性和可维护性
• 超级简单的交叉编译，仅需更改环境变量

Go 语言的主要特性：

1. 自动立即回收
2. 更丰富的内置类型
3. 函数多返回值
4. 错误处理
5. 匿名函数和闭包
6. 类型和接口
7. 并发编程
8. 反射
9. 语言交互性

# Go 基本类型

置顶变量类型，如果没有初始化，则变量默认为零值。

各种类型各自的零值

类型	长度（字节）	默认值	说明
bool	1	false	无法参与数值运算，无法转换为其他类型，也不允许将整型强制转为 bool
byte	1	0	byt e是 uint8 的别名
rune	4	0	Unicode Code Point, 底层是 int32
int, uint	4或8	0	32位或64位
int8, uint8	1	0	-128~127; 0~255; uint8->byte
int16, uint16	2	0	-32768~32767; 0~65535
int32, uint32	4	0	-21亿~21亿; 0~42亿; rune 是 int32 的别名
int64, uint64	8	0
float32	4	0.0
float64	8	0.0
complex64	8		实部和虚部为32位
complex128	16		实部和虚部为64位
uintptr	4或8		用以存储指针的 uint32 或 uint64 整数
array			值类型
struct			值类型
string		“”（空字符串）	UTF-8字符串
slice		nil	引用类型
map		nil	引用类型
channel		nil	引用类型
interface		nil	接口
function		nil	函数

值类型

值类型是指变量直接存储了实际的数据，并且每个变量都拥有独立的存储空间。当一个值类型的变量被复制给另一个变量时，会进行值拷贝。对其中一个变量的修改不会影响到原始变量。

Go 中值类型包含：整型、浮点型、复数、布尔型、字符串型、数组、结构体

值类型有以下特点：

• 直接存储值，不存储地址
• 变量间赋值时、作为参数传递时 进行值复制
• 值类型的变量副本是独立的，修改一个变量的副本不会影响另一个
• 值类型通常在栈上分配，除非是通过 new 函数分配的，或者是作为闭包中的变量被分配到堆上。

引用类型

引用类型并不直接存储数据本身，而是存储指向数据的指针。

当复制一个引用类型的变量时，复制的是指针，新旧变量指向的是相同的底层数据。

Go 中的引用类型包含：

• 切片 slice ： 切片是对数组的封装。当修改切片中的元素时，实际上是在修改底层数组的相应元素
• 映射 map ： 将 map 传递给一个函数、赋值给一个变量时，任何对映射的修改都会反映在所有引用了这个 map 的地方
• 通道 channel
• 接口 interface ： 接口类型是一种抽象类型，定义了一组方法，但不会实现这些方法。接口内部存储的是 指向实现了接口方法的值的指针 和 指向该类型信息的指针
• 函数 function ：当把一个函数赋给另一个变量时，实际上是在复制一个指向该函数的引用。

引用类型有以下特点：

• 存储的是指向该数据的地址，而不是数据本身
• 当引用类型的变量被赋值 或 作为函数参数传递时，实际上是将该地址复制一份，因此多个变量可能共享同一份数据
• 引用类型的数据通常在堆上分配，即使变量本身在栈上
• 引用类型的零值是 nil ，一个未初始化的引用类型的变量值是 nil ，不指向任何内存地址。

整型

uint8 对应 byte

int16 对应 C 中的 short

int64 对应 C 中的 long

int 和 uint 的长度自动根据平台大小调整（uintptr: 用于存储指针值的无符号整型）

字符串

定义多行字符串，使用反引号

s1 := `第一行
第二行
第三行
`
fmt.Println(s1)

反引号间换行将被作为字符串中的换行，但是所有的转义字符均无效，文本将会原样输出。

字符串常见操作

方法	说明
len(str)	求长度
+ 或 fmt.Sprintf	拼接字符串
strings.Split	分割
strings.Contains	判断是否包含
strings.HasPrefix, strings.HasSuffix	前缀/后缀判断
strings.Index(), strings.LastIndex()	子串出现的位置
strings.Join(a[]string, sep string)	join 操作

byte和rune类型

组成每个字符串的元素叫做“字符”，可以通过遍历或者获取单个字符串元素获得字符。字符用单引号'包裹起来，如：

var a := '中
var b := 'x

Go 语言的字符有两种

• uint8 类型，或者叫 byte 型，代表了 ASCII 码的一个字符
• rune 类型，代表一个 UTF-8 字符

当需要处理中文、日文或者其他复合字符时，则需要用到 rune 类型。rune 类型实际上是一个int32。

Go 使用了特殊的 rune 类型来处理 Unicode，让基于 Unicode 的文本处理更为方便，也可以使用 byte 型进行默认字符串处理。

// 遍历字符串
func traversalString() {
    s := "pprof.cn博客"
    for i := 0; i < len(s); i++ { //byte
        fmt.Printf("%v(%c) ", s[i], s[i])
    }
    fmt.Println()
    for _, r := range s { //rune
        fmt.Printf("%v(%c) ", r, r)
    }
    fmt.Println()
}

输出：

112(p) 112(p) 114(r) 111(o) 102(f) 46(.) 99(c) 110(n) 229(å) 141() 154() 229(å) 174(®) 162(¢)
112(p) 112(p) 114(r) 111(o) 102(f) 46(.) 99(c) 110(n) 21338(博) 23458(客)

for i := 0; i < len(s); i++ { //byte } 是以字节为单位遍历的。

for range 是以 Unicode 码点（rune）遍历字符串的。

字符串底层是一个 byte 数组，所以可以和 []byte 类型相互转换。字符串是不能直接修改的。

字符串有 byte 字节组成，所以 len(s) 是 byte 字节的长度。

rune 类型用来表示 UTF-8 字符。因为 UTF-8 编码下，一个中文由 3~4 个字节组成，所以不能按照字节去遍历一个包含中文的字符串，否则就会出现上面输出中第一行的结果。

修改字符串

要修改字符串，需要将其先转成 []rune 或 []byte ，完成后再转换为 string 。无论哪种转换，都会重新分配内存，并复制字节数组。

func changeString() {
    s1 := "hello"
    // 强制类型转换
    byteS1 := []byte(s1)
    byteS1[0] = 'H'
    fmt.Println(string(byteS1))

    s2 := "博客"
    runeS2 := []rune(s2)
    runeS2[0] = '狗'
    fmt.Println(string(runeS2))
}

# Go 变量声明

Go 声明可见性

1. 声明在函数内部，是函数的本地值，类似 private
2. 声明在函数外部，是对当前包可见（包内所有 .go 文件都可见）的全局值，类似 protect
3. 声明在函数外部且首字母大写是所有包可见的全局值，类似 public

Go 语言在声明变量的时候，会自动对变量对应的内存区域进行初始化操作。每个变量会被初始化成其类型的默认值。（参考上文的类型表格）

不同声明方法

var name string

// 声明时初始化
var name2 string = "kiramux"
var num int = 1

// 批量声明
var (
    a string
    b int
    c bool
    d float32
)

// 批量声明+初始化
var (
    color string = "blue"
    x int = 10
    is_X bool = true
)

// 类型推导
var domain = "kiramux.com"

// 一次初始化多个变量
var name3, y = "kiramux", 1

// ---
// 全局变量m
var m = 100

// 函数内部的短变量声明
func main() {
    n := 10
    m := 100 // 此处声明局部变量m
    
}

在使用多重赋值时，如果想要忽略某个值，可以使用匿名变量，用下划线_表示。

for _, val := range nums {
    // ...
}

匿名变量不占用命名空间，不会分配内存，所以匿名变量之间不存在重复声明。

注意：

• 函数外的每个语句都必须以关键字开始（var、const、func 等）
• := 不能在函数外使用
• _ 多用于占位，表示忽略值

# Go 下划线

下划线在 import 中

在导入一个包时，该包下的文件里所有的 init() 函数都会被执行。

当我们仅希望它执行 init() 函数，不需要把整个包都倒进来，就可以用 import 引入该包。即 import _ 包路径 只是引用该包，仅仅为了调用 init() 函数，所以无法通过包名来调用包中的其他函数。例如：

代码结构
    src 
    |
    +--- main.go            
    |
    +--- hello
           |
            +--- hello.go

package main

import _ "./hello"

func main() {
    // hello.Print() 
    // 启用上一行代码会编译报错：./main.go:6:5: undefined: hello
}

hello.go

package hello

import "fmt"

func init() {
    fmt.Println("imp-init() come here.")
}

func Print() {
    fmt.Println("Hello!")
}

输出结果

imp-init() come here.

# init 函数和 main 函数

init 函数

1. init 函数是用于程序执行前做包的初始化的函数，比如初始化包里的变量等
2. 每个包可以有多个 init 函数
3. 包的每个源文件也可以拥有多个 init 函数
4. 同一个包中多个 init 函数的执行顺序 go 语言没有明确的定义（说明）
5. 不同包的 init 函数按照包导入的依赖关系决定该初始化函数的执行顺序
6. init 函数不能被其他函数调用，而会在 main 函数执行之前自动被调用

init 函数 和 main 函数的异同

相同点：

• 两个函数在定义时不能有任何的参数和返回值，且 Go 程序自动调用。

不同点：

• init 可以应用于任意包中，且可以重复定义多个。
• main 函数只能用于 main 包中，且只能定义一个。

init 函数和 main 函数的执行顺序

对同一个 go 文件的 init 函数调用顺序是从上到下的。

对同一个 package 中不同文件是按照文件名字符串比较“从小到大”顺序调用各文件中的 init 函数

对于不同的 package ，如果不相互依赖的话，按照 main 包中“先 import 后调用其包中的 init 函数”。如果 package 存在依赖，则先调用最早被依赖的 package 中的 init 函数。

最后调用 main 函数。

---

如果 init 函数中使用了 println() 或者 print() ，会发现在执行过程中二者不会按照想象中的顺序执行。

这两个函数官方只推荐在测试环境中使用，在正式环境不要使用。

# Go 类型别名和自定义类型

自定义类型

Go 中有整型、string 等基本的数据类型，可以使用 type 关键字来自定义类型。

自定义类型是一个全新的类型。可以基于内置的基本类型定义，也可以通过 struct 定义

//将MyInt定义为int类型
type MyInt int

MyInt 就是一种新类型，它具有 int 的特性。

类型别名

TypeAlias 只是 Type 的别名，本质上两者是同一个类型。

就像一个人小时候有小名、乳名、中文名、英文名，但这些名字都是指它一个人。

type TypeAlias = Type

// rune和byte就是类型别名
type byte = uint8
type rune = int32

类型定义和类型别名的区别

//类型定义
type NewInt int

//类型别名
type MyInt = int

func main() {
    var a NewInt
    var b MyInt

    fmt.Printf("type of a:%T\n", a) //type of a:main.NewInt
    fmt.Printf("type of b:%T\n", b) //type of b:int
}

结果显示

a 的类型是 main.NewInt ，表示 main 包下定义的 NewInt 类型；

b 的类型是 Int 。MyInt 类型只会在代码中存在，编译完成时并不会有 MyInt 类型。

如果怕记错的话，想一想 struct 的定义， struct 就是一种新类型

type cats struct {
    name string
    age int
}

# 209.长度最小的子数组

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104

进阶：

• 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

# 暴力解法（力扣超时）

时间复杂度：O(n^2)

直接遍历所有子数组，寻找符合条件的情况。

相当于 i 是头， j 是尾。

func minSubArrayLen(target int, nums []int) int {
    len := len(nums)
    var sum int = 0
    var result int = len + 1
    for i := 0; i < len; i++ {
        sum = 0
        for j := i; j < len; j++ {
            sum += nums[j]
            if sum >= target {
                subLen := j - i + 1
                if subLen < result {
                    result = subLen
                break
                } 
            }
        }
    }
    if result == len + 1 {
        return 0
    } else {
        return result
    }
}

# 滑动窗口法

• 时间复杂度：O(n)
• 空间复杂度：O(1)

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们想要的结果。

也可以理解成一种双指针法。

在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程。

尝试使用一个 for 循环：

以题目中的示例来举例，target=7， 数组是 2，3，1，2，4，3，查找过程：

最后找到 4，3 是最短距离。

j代表滑动窗口的“尾”，先找到总和大于 target 的子数组，再移动头部缩小子数组。

如果 j 代表起始位置的话，就和暴力解法没区别了。

func minSubArrayLen(target int, nums []int) int {
    len := len(nums)
    var sum int = 0
    var result int = len + 1
    i := 0

    // j 是滑动窗口的终止位置，如果代表起始位置的话，和暴力解法没区别
    for j := 0; j < len; j++ {
        sum += nums[j]
        for sum >= target {
            subLen := j - i + 1 // 求长度所以+1 
            if subLen < result {
                result = subLen
            }
            // 起始位置移动
            sum -= nums[i]
            i++
        }
    }

    if result == len + 1 {
        return 0
    } else {
        return result
    }
}

本题实现滑动窗口，主要确定以下三点：

• 窗口内的是什么？
• 如何移动窗口的初始位置？
• 如何移动窗口的结束位置？

本题的窗口： 满足其和≥target 的最小的连续子数组；

本题的起始位置如何移动：如果当前窗口的值≥target ，窗口就要向右移动了（窗口该缩小了）；

本题的终止位置如何移动：窗口的结束位置就是数组的遍历指针，也就是 for 循环中的索引。

---

解题的关键在于，窗口的起始位置如何移动：

滑动窗口的精妙之处在于：根据当前子序列和大小的情况，不断调整子序列的起始位置，从而将O(n^2)暴力解法降为O(n)。

**时间复杂度是O(n)**的原因：

不是两个 for 循环嵌套就是O(n^2)，主要看每个元素被操作的次数。

每个元素在滑动窗口进来操作一次，出去操作一次，每个元素都是被操作两次。所以时间复杂度是 2*n 也就是 O(n)。

# 59.螺旋矩阵II

# 循环不变量1

模拟顺时针画矩阵的过程:

• 填充上行从左到右
• 填充右列从上到下
• 填充下行从右到左
• 填充左列从下到上

可以发现这里的边界条件非常之多，在一个循环中，如此多的边界条件，如果不按照固定的规则来遍历，上来就i:=固定值。那么就是 一进循环深似海，从此offer是路人。

方法1: 每一边都坚持左闭右开原则（或者左开右闭原则）

每一个拐角处都不处理，交给下一条边来处理。

圈数 loop == n / 2，如果n是奇数，那么就把中间的值赋值 n*n 即可。

定好每一行开始的位置和结束的位置，每完成一圈，offset++

func generateMatrix(n int) [][]int {
    var (
        loop = n / 2
        startx = 0
        starty = 0
        offset = 1
        counter = 1
    )

    var nums = make([][]int, n)
    for i := 0; i < n; i++ {
        nums[i] = make([]int, n)
    }
    for loop > 0 {
        i,j  := startx, starty
        for j = starty; j < n - offset; j++ {
            nums[startx][j] = counter
            counter++
        }
        for i = startx; i< n - offset; i++ {
            nums[i][j] = counter
            counter++
        }
        for ;j > starty; j-- {
            nums[i][j] = counter
            counter++
        }
        for ;i > startx; i-- {
            nums[i][starty] = counter
            counter++
        }
        loop--
        startx++
        starty++
        offset++
    }
    if n % 2 == 1 {
    nums[n/2][n/2] = n*n 
    }
    return nums
}

# 循环不变量2

这个思路是：规定未处理的范围 left, right, top, bottom, 坚持左闭右闭原则。

每处理完一条边，就把未处理的范围减去一条边，明确下一条边要处理的范围。例如处理完红色的第一行，那么就top++。

这个思路优点是代码简单，思路容易想到。缺点是每一条边的具体操作不一致，可能会容易出错。

func generateMatrix(n int) [][]int {
    left, right := 0, n-1
    top, bottom := 0, n-1
    counter := 1
    tar := n * n

    var matrix = make([][]int, n)
    for i := 0; i < n; i++ {
        matrix[i] = make([]int, n)
    }

    for counter <= tar {
        for i := left; i <= right; i++ {
            matrix[top][i] = counter
            counter++
        }
        top++
        for i := top; i <= bottom; i++ {
            matrix[i][right] = counter
            counter++
        }
        right--
        for i := right; i >= left; i-- {
            matrix[bottom][i] = counter
            counter++
        }
        bottom--
        for i := bottom; i >= top; i-- {
            matrix[i][left] = counter
            counter++
        }
        left++
    }

    return matrix
}