主要内容：

1. 序言部分
2. LRU缓存策略实现



### 1 序言部分记录

缓存对于后端来说是必要的，毕竟数据库操作很耗时，不能每个请求都去读写数据库，会严重拖慢服务的速度。缓存可以将近期读取过的数据存入缓存，每次请求数据时，如果命中缓存即可直接返回缓存值。

一个分布式缓存要考虑的问题：

1. 缓存淘汰策略：在缓存已满时，如何淘汰旧有缓存才能保证其余缓存在接下来的请求中命中率最高？
2. 并发控制：多个请求同时到达缓存，如何设计并发控制才能保证线程安全的同时速度最快？
3. 多节点通信同步：如果单机缓存已经到达性能极限，如何扩展缓存系统？如果是水平扩展，节点之间如何通信？如果是垂直扩展，扩展策略应该如何设计？
4. 读写特性：缓存是否为只读？缓存是否设计淘汰时间？缓存类型是什么？

:::tip{title="提示"}
一提到缓存，三个和缓存相关的问题是必须要提的，即缓存雪崩、缓存击穿和缓存穿透。

- **缓存雪崩**：缓存内的大量数据的过期淘汰时间相近，使得这些数据被淘汰后，缓存未能命中大量的请求（或者缓存自身由于某种原因崩溃了），这些请求直接到了数据库里，直接导致数据库崩溃。

- **缓存击穿**：假设缓存中有一个值被极其频繁地访问（该值一般被称为**热点数据**），当这个值过期后，大量的访问请求到达数据库，导致数据库崩溃。

- **缓存穿透**：如果用户访问的数据既不在缓存里，也不在数据库里，后台就无法构建缓存来响应请求。如果大量的这种目标数据既不在缓存里也不在数据库里的请求到来，这些请求一样会到达数据库，导致数据库崩溃。

这三种缓存异常，都是因为各种原因导致缓存命中率不高，使得大量的请求压垮数据库。这些缓存异常的常见解决方法如下：

- **缓存雪崩**：
    1. 均匀设置过期时间：在添加缓存时，在过期时间处添加一个随机数，使得多个缓存不要在同一时间内淘汰
    2. 互斥锁：在构建缓存时上锁。如果有请求到来，并且缓存未能命中，就先访问锁，如果是未上锁的状态，就正常构建缓存；如果是上锁状态，就等锁结束后再次访问缓存，确认是否命中。（另：实现互斥锁的时候，最好设置超时时间，不然第一个请求拿到了锁，然后这个请求发生了某种意外而一直阻塞，一直不释放锁，这时其他请求也一直拿不到锁，整个系统就会出现无响应的现象。）
    3. 后台多一个线程负责更新缓存，请求只到达缓存，不到数据库。如果缓存未命中，就通过消息队列到后台线程去更新缓存。
    4. 如果缓存自己崩了，可以启动服务熔断/请求限流或者构建缓存集群来解决。
 
- **缓存击穿**：同缓存雪崩2，3
- **缓存穿透**：
    1. 限制非法请求
    2. 缓存空值：如果发现数据库没有数据，可以在缓存中对这次请求加一个空值缓存，避免每次都要请求数据库。
    3. 布隆过滤器
:::

Geecache项目实现日程安排如下：

1. LRU缓存淘汰策略
2. 单机并发缓存
3. HTTP客户端
4. 一致性哈希
5. 分布式节点
6. 防止缓存击穿
7. 使用Protubuf通信

另外，该项目可以考虑的扩展方向：

- 多个淘汰策略，比如LFU、ARC
- HTTP通信改为RPC通信
- 细化锁的粒度来提高并发性能
- 实现热点互备来避免热点数据频繁请求影响性能
- 加入etcd
- 加入缓存过期机制

### 1 Day1 LRU缓存策略实现

常见的缓存策略有FIFO、LRU、LFU、ARC等，该项目使用LRU作为缓存策略。

> FIFO算法，顾名思义，先进先出，当缓存满时会自动删除最先进入缓存的数据。但是每次被删除的数据也有可能是最常访问的数据，这一模式并不能很好地匹配缓存的需求。

> LFU算法（Least Frequently Used）：最少使用算法，每次缓存满时会删除最久未使用过的缓存。这种情况能够很好地满足缓存的需求，但是它所占用的开销算是很大的：不仅要存键值对缓存，还要存这个缓存对应的访问次数，而且每次删除缓存时都需要对访问次数排序。不仅如此，如果对缓存的访问形式突然发生改变，以前经常访问的缓存以后都不再访问，那么要淘汰以前访问次数多的缓存也需要很长的时间。

> LRU算法（Least Recently Used）最近最少使用，相对于仅考虑时间的FIFO和仅考虑频率的LFU，该算法认为，如果一个数据被访问了，那么它在未来的一段时间访问的概率就会很高。

LRU算法在Go中的实现，需要一个字典和一个队列（双向链表Cosplay的）组成。队列存储缓存被访问的次序，字典存储具体的数据。每次删除数据时，就将队首的元素出队；每次有缓存被访问时，就将其重新入队，回到队尾。

> GoLand的tab默认是4空格，所以看着可能有点怪。

``` go
// src/geecache/lru/lru.go
// LRU 采用了LRU策略的缓存类
type LRU struct {
	maxMemoryBytes  int64                         // 允许使用的最大内存
	memoryUsedBytes int64                         // 当前已经使用的内存
	queue           *list.List                    // 队列 存储访问频率
	cacheMap        map[string]*list.Element      // 字典 存储具体的缓存的键值对 这里的值存的是双向链表的元素指针类型 具体的值在链表里
	OnEntryDeleted  func(key string, value Value) // 当缓存被删除时的回调函数 这种函数类型的默认值就是nil
}

// NewLRU LRU的构造函数
func NewLRU(maxMemoryBytes int64, onEntryDeleted func(string, Value)) (cache *LRU) {
	cache = &LRU{
		maxMemoryBytes: maxMemoryBytes,
		queue:          list.New(),
		cacheMap:       make(map[string]*list.Element),
		OnEntryDeleted: onEntryDeleted,
	}
	return
}

// Value 一条键值对缓存具体要存储的值的接口 该接口的目的是为了确保值对所有类型的通用性
type Value interface {
	GetMemoryUsed() int // 返回该缓存的值所占用的内存大小
}

// entry Cache中双向链表所存储的类型
type entry struct {
	key string
	// 之所以在双向链表中存储键 是为了删除更加方便 能够直接根据键去字典中删除元素
	value Value // 值必须是实现了Value接口的类型
}

// 开始实现功能

// GetValue 在缓存里查找值
func (cache *LRU) GetValue(key string) (value Value, isOk bool) {
	if element, isOk := cache.cacheMap[key]; isOk {
		cache.queue.MoveToFront(element) // 如果元素存在 则移动到队尾 注意双向链表的队尾是相对的 规定Front是队尾即可
		entry := element.Value.(*entry)  // 这个节点的值取出来 转换为entry类型
		return entry.value, true
	}
	value = nil
	isOk = false
	return
}

// RemoveOldestCache 淘汰一次缓存
func (cache *LRU) RemoveOldestCache() {
	element := cache.queue.Back() // 取出队首元素
	if element != nil {
		cache.queue.Remove(element) // 从双向链表中移除该元素
		cacheEntry := element.Value.(*entry)
		delete(cache.cacheMap, cacheEntry.key) // 从字典中移除该键值对
		cache.memoryUsedBytes -= int64(len(cacheEntry.key)) + int64(cacheEntry.value.GetMemoryUsed()) // 修改已使用的内存
		if cache.OnEntryDeleted != nil { // 如果回调函数不为空 则调用回调函数
			cache.OnEntryDeleted(cacheEntry.key, cacheEntry.value)
		}
	}
}

// SetValue 添加/修改缓存
func (cache *LRU) SetValue(key string, value Value) {
	if element, isOk := cache.cacheMap[key]; isOk { // 键存在
		cache.queue.MoveToFront(element)
		cacheEntry := element.Value.(*entry)
		cache.memoryUsedBytes += int64(value.GetMemoryUsed()) - int64(cacheEntry.value.GetMemoryUsed())
		cacheEntry.value = value
	} else { // 键不存在
		element = cache.queue.PushFront(&entry{key: key, value: value})
		cache.cacheMap[key] = element
		cache.memoryUsedBytes += int64(len(key)) + int64(value.GetMemoryUsed())
	}
	for cache.memoryUsedBytes > cache.maxMemoryBytes && cache.memoryUsedBytes != 0 { // 看已经使用的缓存内存有多大来淘汰旧缓存
		cache.RemoveOldestCache()
	}
}

// GetLRUEntryNumber 返回当前已缓存的键值对数量
func (cache *LRU) GetLRUEntryNumber()(len int) {
	len = cache.queue.Len()
	return
}
```

### 3 今日内容结构图

![7a8850f09e60bcdd8e85183db6b6124.jpg](https://www.misaka19327.cc/static/img/0614c00e47e6238a1bc3fe9f3437f87e.7a8850f09e60bcdd8e85183db6b6124.jpg)

### 4 测试文件

``` go
// src/geecache/lru/lru_test.go
package lru

import (
	"reflect"
	"testing"
)

type String string

func (string String) GetMemoryUsed() int { // 要实现Value接口的那个方法 下面才能直接添加什么的
	return len(string)
}

func TestCache_GetValue(t *testing.T) {
	lru := NewLRU(int64(100), nil)
	lru.SetValue("key1", String("1234"))
	if value, isOK := lru.GetValue("key1"); !isOK || value != String("1234") {
		t.Fatalf("cache hit key1=1234 failed, value actually is %s", value)
	}
	if _, isOK := lru.GetValue("key2"); isOK {
		t.Fatalf("cache miss key2 failed")
	}
}

func TestCache_RemoveOldestCache(t *testing.T) {
	key1, key2, key3 := "key1", "key2", "key3"
	value1, value2, value3 := "value1", "value2", "value3"

	cap := len(key1 + key2 + value1 + value2)
	lru := NewLRU(int64(cap), nil)
	lru.SetValue(key1, String(value1))
	lru.SetValue(key2, String(value2))
	lru.SetValue(key3, String(value3))

	if _, isOk := lru.GetValue(key1); isOk || lru.GetLRUEntryNumber() != 2 {
		t.Fatalf("Removeoldest key1 failed")
	}
}

func TestCache_OnEntryDeleted (t *testing.T) {
	keys := make([]string, 0)
	callback := func(key string, value Value) {
		keys = append(keys, key)
	}
	lru := NewLRU(int64(20), callback)
	lru.SetValue("key1", String("value1"))
	lru.SetValue("key2", String("value2"))
	lru.SetValue("key3", String("value3"))
	lru.SetValue("key4", String("value3"))
	expected := []string {"key1", "key2"}

	if !reflect.DeepEqual(expected, keys) {
		t.Fatalf("Call OnEvicted failed, expect keys equals to %s, now keys are %s", expected, keys)
	}
}
```

Geecache分布式缓存 | 序言&第一天记录

今日任务：

1. 01背包问题
2. 01背包问题+滚动dp数组
3. LeetCode416 分割等和子集



资料来源：

1. [代码随想录 | 01背包问题](https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html)
2. [代码随想录 | 01背包问题+滚动dp数组](https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html)
3. [代码随想录 | LeetCode416 分割等和子集](https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html)

### 1 01背包问题

背包问题，指的是一类可以被抽象为以下问题的问题类型：

> 假设当前有一个容量为j的背包，面前有n个体积、价值各不相同的物品，要如何挑选物品使得一次能带走的所有物品的价值最大？

背包问题可以被细分为多个小问题：01背包（体积和价值相同的物品只有一个）、多重背包（体积和价值相同的物品有多个，且不同的物品数量不同）、完全背包（体积和价值相同的物品可以无限取）和分组背包（物品按组打包，每组物品选一个）等等。

其中，01背包是最基础的背包问题，它可以被阐述为：

> 假设当前有一个容量为j的背包，面前有n种体积、价值各不相同的物品，**且每种物品只有1个**，要如何挑选物品使得一次能带走的所有物品的价值最大？

首先先说暴力解法。对，01背包是有暴力解法的（不如说整个背包问题都可以暴力解），它的暴力解法就是回溯。既然每个物品只有取和不取两种选择，那么直接对每种物品的取和不取两种情况向下搜索，然后再回溯即可。只是这种解法在一般情况下都会超时，因为它的时间复杂度是$$ 2 ^ n$$。

再说动规解法，它的核心递推思路就是：对每个物品，对取这个物品和不取这个物品的两种情况的背包总价值取最大值，而这两种情况可以由**判断这个物品前背包的最大价值**和**背包容量减去当前物品重量所对应的背包容量下的背包最大价值加上这个物品的价值**得到。假设现在有一个容量为4的背包，有三个物品，第一个物品重量1价值15、第二个物品重量3价值20、第三个物品重量4价值30，那么它的dp数组应该长这样：

![21b4b58e1ce6f28000fb9936e52e7f5.jpg](https://www.misaka19327.cc/static/img/9f1a70f38b7b1287cf811e938ebafa87.21b4b58e1ce6f28000fb9936e52e7f5.jpg)

红字即为那一种情况的递推过程。

对着这个图，还是动态规划五部曲：

1. 确定dp数组和下标含义：对于这个dp数组，在它下标为i，j的位置的含义是，背包容量为j时，任取物品1到i所能携带的最大价值
2. 递推公式：没有取到物品i时，背包容量为j的最大价值和没有取到物品i时，背包容量为j减去物品i的重量的最大价值，再加上物品i的价值的最大值（具体看红色箭头）
3. dp数组初始化：只初始化背包容量为0时，对于所有物品的可以携带的最大价值和只取物品1时，所有背包容量情况下的最大价值（即为图中的第一排和第一列），其他位置无需初始化（反正都是要在之后的递推中被覆盖的）
4. 确定遍历顺序：一定是从左向右、从上到下遍历（因为递推出一种情况所需要的值，**一定是从它的上一排的左侧和正上方取值**，所以遍历时一定保证上一排的左侧和正上方一定有值），至于是先从左向右还是先从上到下，这个都可以。
5. 举例推导dp数组：见上图。

### 2 01背包问题+滚动dp数组

还是上面用那张图说明。

![21b4b58e1ce6f28000fb9936e52e7f5.jpg](https://www.misaka19327.cc/static/img/9f1a70f38b7b1287cf811e938ebafa87.21b4b58e1ce6f28000fb9936e52e7f5.jpg)

仅对于背包容量为3，取到第二个物品时那一种情况来说，**对它有意义的只有它上方那一排的值，或者更具体的来说，是它上面那一排的左侧和正上方的值**。而且01背包只需要知道最后能取到的最大价值是多少，并不关心过程。因此出现了一种使用一维数组求解01背包的写法，具体如下图：

![cec66a04e7cffe7ea6e1f750d59db57.jpg](https://www.misaka19327.cc/static/img/a10dfd43685201007e20fb2213909b08.cec66a04e7cffe7ea6e1f750d59db57.jpg)

一维数组的写法，就是去掉了二维数组中，已经求过并且已经没有任何的递推情况会使用的值之后的写法。这个写法就是抽象版本的二维数组，所以五部曲中大部分都可以直接用，只有遍历顺序需要注意，从上往下不变，但是**左右的遍历顺序必须是从右向左**，因为从左向右遍历的时候，按递推公式，它会直接取更新后的这一行的左侧，而不是还未更新的上一行的左侧。

### 3 LeetCode416 分割等和子集

:::info{title="题目"}
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

 

示例 1：
```
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
```
示例 2：
```
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
```

提示：

- 1 <= nums.length <= 200
- 1 <= nums[i] <= 100
:::

~~个人觉得，背包问题最难的不是背包问题本身，而是怎么把背包问题和现实问题对应上。~~

既然已经限定了是两个子集，而且目标是两个子集元素和相等，并且还允许不相等的情况，那目标就很明确了：在给定的数字中，挑出一些数字，使得它们的和为所有元素和的一半，找得到就返回true，找不到就返回false；如果所有元素和是个奇数，直接返回false就行。

之后再把这个问题和背包问题进行对应：子集就是背包本身，目标就是要求特定总和的子集，所以子集里面元素的和不能超过子集，而且确实要实时统计子集的和，所以每个数字都是一个物品，而且**这个物品的重量和价值都等于这个数字，这样才能保证背包能够装下（子集里面元素的和不能超过子集）而且实时看到背包能装的物品的最大价值（实时统计子集的和）**。之后就是按照01背包写就可以了，注意下例是一维dp数组的写法。

``` go
func canPartition(nums []int) bool {
    target := 0
    i := 0
    for {
        if i >= len(nums) {
            break
        }
        target += nums[i]
        i++
    }
    if target%2 != 0 {
        return false
    }
    target = target / 2
    dpArray := make([]int, target+1)
    for i := range nums { // 遍历物品
        for j := target; j >= nums[i]; j-- { // 遍历背包 这个循环条件是先确保物品能够放到这个背包里
            dpArray[j] = max(dpArray[j], dpArray[j - nums[i]] + nums[i])
        }
    }
    return dpArray[target] == target
}
```

代码随想录算法训练营第四十二天 | LeetCode416 分割等和子集

今日任务：

1. LeetCode343 整数拆分
2. LeetCode96 不同的二叉搜索树



资料来源：

1. [代码随想录 | LeetCode343 整数拆分](https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.htmlhttps://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html)
2. [代码随想录 | LeetCode96 不同的二叉搜索树](https://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html)

### 1 LeetCode343 整数拆分

:::info{title="题目"}
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

 

示例 1:
```
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
```
示例 2:
```
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
```

提示:

- 2 <= n <= 58
:::

先明确dp数组的含义：**对于下标i，dp[i]所储存的就是数字i的拆分数字的乘积最大值**。它的递推思路就是，对于每个数字i来说，它都需要进行下一层从1到i- 1的循环j，每次循环都要比较当前已经存储的最大乘积，j * (i - j)（仅分拆一次）和j * (i - j)位置的最大乘积。

举例来说，对于数字4，它所需要在循环中查找的就是：

```
1 * 3 -> 这个代表分拆成两个数字
1 * dp[3] -> 注意dp[3]的含义：数字3的拆分数字的成绩最大值 这个代表分拆成多个数字
2 * 2
2 * dp[2] 注意 从中间数字开始之后的循环时可以优化的
3 * 1
3 * dp[1]
```

:::tip{title="提示"}
这题也有一个数论解法，即每次都分拆3，如果剩下的是4就停止分拆，否则继续分拆3，直到产生余数。这个解法有个印象就行。
:::

``` go
func integerBreak(n int) int {
    dp_array := make([]int, n+1)
    dp_array[2] = 1
    for i := 3; i <= n; i++ {
        for j := 1; j < i; j++ { // 第二层循环 这个循环从1还是从2开始都可以 因为分拆1必然不可能是最大值
            dp_array[i] = max(dp_array[i], j*(i-j), j*dp_array[i-j])
        }
    }

    return dp_array[n]
}
```

``` java
class Solution {
    public int integerBreak(int n) {
        int[] dp_array = new int[n + 1];
        dp_array[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp_array[i] = Integer.max(dp_array[i], Integer.max(j * (i - j), j * dp_array[i - j]));
            }
        }
        return dp_array[n];
    }
}
```

``` python
class Solution:
    def integerBreak(self, n: int) -> int:
        dp_array = [0] * (n + 1)
        dp_array[2] = 1
        for i in range(3, n + 1):
            for j in range(2, i):
                dp_array[i] = max(dp_array[i], j * (i - j), j * dp_array[i - j])
        return dp_array[n]
```        

### 2 LeetCode96 不同的二叉搜索树

:::info{title="题目"}
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

 

示例 1：
```
输入：n = 3
输出：5
```
示例 2：
```
输入：n = 1
输出：1
```

提示：

- 1 <= n <= 19
:::

这个题可以被转化为：n个节点组成二叉树的可能的树的形状有多少。还是先明确dp数组的含义：**对于下标i，dp[i]表示i个节点组成的互不相同的树的种类**。再说递推关系：如果按照题意理解，那么对于任意的节点数量n，它有可能组成的搜索二叉树的种类数量包括从数字1开始到数字n作为根节点的所有搜索二叉树，每个根节点对应的左子树和右子树的数量分别为j和i - 1 - j（j >= 0）。

举例来说，如果要求的n为4时，它所能组成的搜索二叉树如下：

![9baf1caf00134be9b55ceada1f19f5a.jpg](https://www.misaka19327.cc/static/img/1c49e96f4018122fe0d296750fd64066.9baf1caf00134be9b55ceada1f19f5a.jpg)

可知dp数组元素之间的递推关系。


``` go
func numTrees(n int) int {
    dp_array := make([]int, n+1)
    dp_array[0] = 1
    for i := 1; i <= n; i++ { // 针对每个节点数
        for j := 1; j <= i; j++ { // 对于每个节点数i来说 要算的是0 * (i - 1)循环到(i - 1) * 0
            dp_array[i] += dp_array[j-1] * dp_array[i-j]
        }
    }

    return dp_array[n]
}
```

``` java
class Solution {
    public int numTrees(int n) {
        int[] dp_array = new int[n + 1];
        dp_array[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) { // 0 * i - 1 到i - 1 * 0
                dp_array[i] += dp_array[j] * dp_array[i - 1 - j];
            }
        }

        return dp_array[n];
    }
}
``` 

``` python
class Solution:
    def numTrees(self, n: int) -> int:
        dp_array = [0] * (n + 1)
        dp_array[0] = 1
        for i in range(1, n + 1):
            for j in range(0, i):
                dp_array[i] += dp_array[j] * dp_array[i - 1 - j]
        return dp_array[n]
```

代码随想录算法训练营第四十一天 | LeetCode343 整数拆分、LeetCode96 不同的二叉搜索树

记录Go语言的基础语法和基本知识。



> Go语言是Google开发的一种**静态强类型、编译型**、并发型，并**具有垃圾回收功能**的编程语言。

### 1 HelloWorld

``` go
// helloWorld.go
package main

import {
    "fmt"
}

func main() {
    fmt.Println("Hello World!\n")
}
```

注意，Go语言使用包来组织代码，一个包可以提供一些类型和方法来给其他包使用。

**Go语言的唯一程序执行入口，只在main包里的main函数。**

### 2 变量与内置数据类型

**声明变量语法**：

``` go
var i int // 仅声明
var j int = 1 // 声明并且赋值
var k = 1 // 声明并且赋值 类型支持自动推导
l := 1 // 声明并且赋值
```

注意Go语言的类型声明在变量名后面。

****

**简单类型**：

- 空值：nil
- 整型：int，uint8，uint16，uint32，int8，int16，int32...
- 浮点型：float32，float64
- 字节型：byte（等效uint8）
- 字符串类型：string
- 布尔型：boolean

****

**字符串**：

在Go中，字符串类型变量一般使用UTF-8编码，并且使用uint8数组来保存字符，英文一个字符占8个字节，中文一般情况下占3个字节。所以在中英文混合的字符串中，如果打印字符串中中文的任意一个位置，大概率打出来也是乱码。这种情况下，如果需要打印其中的中文字符，需要将其转换为rune数组：

``` go
str2 := "Go语言"
runeArr := []rune(str2)
fmt.Println(reflect.TypeOf(runeArr[2]).Kind()) // 查看类型 int32
fmt.Println(runeArr[2], string(runeArr[2]))    // 35821 语
fmt.Println("len(runeArr)：", len(runeArr))    // len(runeArr)： 4
```

转换为rune数组后，字符串中的每个字符都会被以int32来存储，因此可以正确处理中文。

****

**数组、切片：**

声明数组：

``` go
package main

import "fmt"

func main() {
	var array = [5]int{} // 声明一维int数组
	var array2 = [5][2]int{} // 声明二维int数组
	fmt.Println(array) // [0 0 0 0 0]
	fmt.Println(array2) // [[0 0] [0 0] [0 0] [0 0] [0 0]]
	var array3 = [5]int{1, 2, 3, 4, 5} // 声明并且赋值
	fmt.Println(array3) // [1 2 3 4 5]
	array3[1] = 10 // 根据下标修改值
	fmt.Println(array3) // [1 10 3 4 5]
}
```

数组是定长的，如果想要像python的list一样灵活的数组，可以使用切片：

``` go
package main

import "fmt"

func main() {
	slice := make([]int, 5) // 声明一个长度为5的切片
	slice2 := make([]int, 5, 10) // 声明一个长度为5 容量为10的切片
	fmt.Println(slice) // [0 0 0 0 0]
	fmt.Println(slice2) // [0 0 0 0 0]
        // len函数访问长度 cap函数访问容量
	fmt.Println(len(slice), cap(slice)) // 5 5
	fmt.Println(len(slice2), cap(slice2)) // 5 5
}
```

一个切片有3个重要的部分：长度、容量、指向这个切片的指针。对于切片来说，无论是长度还是容量都可以随时扩展。

``` go
package main

import "fmt"

func main() {
	slice2 := make([]int, 5, 10) // 声明切片
	slice2 = append(slice2, 1, 2, 3, 4, 5, 6, 7) // 为切片添加元素
	fmt.Println(slice2) // [0 0 0 0 0 1 2 3 4 5 6 7]
	fmt.Println(len(slice2), cap(slice2)) // 12 20
	sub1 := slice2[3:] // 为切片进行切片
	sub2 := slice2[4:6] // 同上
	combined := append(sub1, sub2...) // 合并切片 切片后面加... 是解包的写法
	fmt.Println(combined) // [0 0 1 2 3 4 5 6 7 0 1]
}
```

****

**字典：**

各方面同python的dict。

``` go
package main

import "fmt"

func main() {
	map1 := map[string]string{} // 声明 []里面是键类型 外面是值类型
	fmt.Println(map1) // map[]
	map2 := map[string]int{ // 声明并且赋值
		"test": 1,
		"test2": 2,
	}
	fmt.Println(map2) // map[test:1 test2:2]
	map2["test2"] = 3 // 赋值/修改值
	fmt.Println(map2) // map[test:1 test2:3]
}
```

****

**指针：**

对，就是那个指针。

``` go
package main

import "fmt"

func main() {
	str := "golang"
	var pointer *string = &str // 获取指针 指针类型就是原类型前面加星号 获取一个变量的指针使用&
	*pointer = "hello" // 在指针前加星号 等效这个指针指向的变量
	fmt.Println(pointer) // 0xc000026070
	fmt.Println(str) // hello
}
```

函数参数会用指针。如果参数类型不是指针类型，那么实际传进去的是参数的副本，不影响参数本身；反之传入了指针的话，就能对这个变量直接进行修改。

### 3 流程控制

**if-else：**

``` go
age := 18
if age < 18 {
    fmt.Printf("Kid")
} else {
    fmt.Printf("Adult")
}

// 可以简写为：
if age := 18; age < 18 { // 赋值语句和判断语句在一起也没问题
    fmt.Printf("Kid")
} else {
    fmt.Printf("Adult")
}
```

****

**switch：**

不需要break。如果需要向下执行下面的分支的话，可以加fallthrough关键字

``` go
package main

import "fmt"

func main() {
	a := 1
	switch a {
	case 1: { // 这个冒号后面的大括号可以省略
		fmt.Println("1") // 1
                // 如果在这里加fallthrough关键字 那么下面分支都会被执行
	}
	case 2: {
		fmt.Println("2")
	}
	default: {
		fmt.Println("default")
	}
	}
}
```

****

**for：**

``` go
sum := 0
for i := 0; i < 10; i++ {
    if sum > 50 {
        break
    }
    sum += i
}
```

Go还支持直接对数组，切片和字典进行遍历：

``` go
nums := []int{10, 20, 30, 40}
for i, num := range nums { // 这个遍历方式好评
	fmt.Println(i, num)
}
// 0 10
// 1 20
// 2 30
// 3 40
m2 := map[string]string{
	"Sam":   "Male",
	"Alice": "Female",
}

for key, value := range m2 {
	fmt.Println(key, value)
}
// Sam Male
// Alice Female
```

### 4 函数

Go里面的函数支持多个返回值。一个简单的函数定义如下：

``` go
func test(i int, j int) (int, int) { // 先是参数 后是返回值 返回值只有一个的时候可以不要括号 也可以没有返回值
	return i + j, i - j
}
```

return也可以配合返回值这么写：

``` go
func test2 (i int) (a int){ // 直接在返回处定义一个变量 在函数内对这个变量进行操作 直接返回
	a = i
	return 
}
```

****

**异常处理：**

Go的异常处理和其他语言有比较大的差异，反而和c语言可能有点像。

``` go
package main

import (
    "errors"
    "fmt"
)

func main() {
    if j, e := test("1"); e != nil { // 如果函数运行正常 那么e就是nil 如果被赋值了 那就表示有异常
        fmt.Println(e)
    } else {
        fmt.Println(j)
    }
}

func test(i string) (j string, e error) { // 返回值里除了正常返回的值 还有返回的异常
    if len(i) < 2 {
        e = errors.New("string is too short") // 返回异常
        return
    }
    j = i + "test"
    return // 正常返回
}
```

这种错误属于那种“可以被预估的”异常，还有一种不可预估的异常，会直接中断Go程序的运行，这被称为Panic。

``` go
package main

import "fmt"

func main() {
	fmt.Println(get(5)) // 数组越界
}

func get(i int) int {
	array := [3]int{1, 2, 3}
	return array[i]
}

// 报错：
// panic: runtime error: index out of range [5] with length 3

// goroutine 1 [running]:
// main.get(...)
// 	C:/Users/Misaka19327/OneDrive/Projects/GoLandProjects/Test/src/test2.go:11
// main.main()
// 	C:/Users/Misaka19327/OneDrive/Projects/GoLandProjects/Test/src/test2.go:6 +0x18
```

与try-catch类似的，Go有defer和recover两个关键字用来处理Panic。

``` go
package main

import "fmt"

func main() {
    fmt.Println(get(5))
    fmt.Println("Finished!")
}

func get(i int) (result int) {
    defer func() { // 异常处理函数
        if r := recover(); r != nil { // r即为报错信息
            fmt.Println(r)
            result = -1 // 直接返回-1 不继续执行
        }
    }() // 这个函数声明之后必须马上调用
    array := [3]int{1, 2, 3}
    return array[i]
}

// 运行结果：
// runtime error: index out of range [5] with length 3
// -1
// Finished!
```

在程序运行中，如果触发了Panic，程序控制权会直接移交给defer函数，defer函数中可以使用recover函数来使程序恢复运行。

### 5 结构体、方法、接口

Go语言中没有特别明确的类的概念，可以通过结构体的方式来近似的实现类的功能。

``` go
package main

import "fmt"

type ClassTest struct { // 结构体当类用
    property1 string
    property2 string
}

func (classTest *ClassTest) classMethodTest(param1 string) (result string) { // 类方法 其实它就是传入了一个结构体的指针来近似的实现类方法的效果
    result = param1 + classTest.property1
    return
}

func main() {
    classTest := &ClassTest{ // 实例化一个类（结构体）
        property1: "111",
        property2: "222",
    }
    classTest.property2 = "333" // 修改类（结构体）的成员变量
    fmt.Println(classTest.property2)
    result := classTest.classMethodTest("1") // 调用方法
    fmt.Println(result)
}

// 结果：
// 333
// 1111
```

:::tip{title="提示"}
注意，`func (class *Class) classMethod`和`func (class Class) classMethod`两者并不等效。除了之前函数里说过的，传入的是指针和传入的是值本身的区别以外，前者只会被实例化的类的指针变量调用，后者只会被实例化的类的变量调用。只是Go语言做了优化，对于可寻址的被实例化的类的变量，依然可以调用前者，只是传入的仍然是指针。

对于上例来说，`classTest.classMethodTest("1")`实际执行的是`*(classTest).classMethodTest("1")`。

这两种写法的函数（暂且叫作指针方法和值方法），大部分情况下都是指针方法更加常用，只有在类不算大且不对类的成员进行修改的情况下，可以创建值方法。
:::

类还可以通过new函数来实例化：`classTest2 = new(ClassTest)`，只是此时的实例内部的成员变量全部都是默认值。

****

**接口：**

定义了一组方法的集合，就能叫接口。这个接口不需要继承，直接实现就行。

``` go
package main

import "fmt"

type interfaceTest interface { // 定义接口 下面是两个方法和返回值
    getAttr1() string
    getAttr2() string
}

type classFromInterface struct { // 定义类 实现接口
    attr1 string
    attr2 string
}

func (c *classFromInterface) getAttr1() string { // 实现方法1
    return c.attr1
}

func (c *classFromInterface) getAttr2() string { // 实现方法2
    return c.attr2
}

func getClassFromInterface(attr1 string, attr2 string) (result *classFromInterface) { // 类的构造方法 返回一个指针
    result = &classFromInterface{
        attr2: attr2,
        attr1: attr1,
    }
    return
}

func main() {
    var class interfaceTest = getClassFromInterface("111", "222") // 获取类指针
    fmt.Println(class.getAttr2()) // 调用接口方法
    fmt.Println(class.getAttr1()) // 调用接口方法
}
```

:::tip{title="提示"}
注意，如果不创建并且使用一个类，Go语言并不会检查这个类是否全部实现了一个接口。就上例来说，想检查这一点可以通过类似`var _ interfaceTest = (*classFromInterface)(nil)`来让Go在编译期就检查是否全部实现了接口。

这条语句的意思是，将空值转换为*classFromInterface类型，再转换为interfaceTest接口，如果转换失败，说明classFromInterface类并没有实现interfaceTest接口的所有方法。

接口和实例可以互相强制转换。
:::

****

**空接口：**

如果一个接口里没有任何的方法，那么这个接口可以代表任意类型。

``` go
func main() {
	m := make(map[string]interface{})
	m["name"] = "Tom"
	m["age"] = 18
	m["scores"] = [3]int{98, 99, 85}
	fmt.Println(m) // map[age:18 name:Tom scores:[98 99 85]]
}
```

### 6 包，模块

一般来说，一个文件夹即可作为一个包，包内的方法，变量，类，方法互相可见。如果想让一个方法/类对包外也可见，需要将其首字母大写。如果首字母小写，它就是一个类似private的状态。包之间互相调用也需要import。

Go语法入门

今日任务：

1. LeetCode62 不同路径
2. LeetCode63 不同路径 Ⅱ



资料来源：

1. [代码随想录 | LeetCode62 不同路径](https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html)
2. [代码随想录 | LeetCode63 不同路径 Ⅱ](https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html)

### 1 LeetCode62 不同路径

:::info{title="题目"}
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

 

示例 1：

![image.png](https://www.misaka19327.cc/static/img/e4564ba9068dbdc6ae566243f89e7fc6.image.png)
```
输入：m = 3, n = 7
输出：28
```
示例 2：
```
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
```
示例 3：
```
输入：m = 7, n = 3
输出：28
```
示例 4：
```
输入：m = 3, n = 3
输出：6
```

提示：

- 1 <= m, n <= 100
- 题目数据保证答案小于等于 $$2 * 10 ^ 9$$
:::

很经典的两层数组的动态规划，还是按照动态规划五部曲走：

1. dp数组的含义和下标含义：从起点到达当前位置的可能的路径数量
2. 确定递推公式：`dp_array[i][j] = dp_array[i - 1][j] + dp_array[i][j - 1]`
3. dp数组初始化：第一横行和第一竖行全部初始化为1，意味着从起点到达这些点的可能路径只有1条。由于n，m可能为1，所以`dp_array[0][0]`也得初始化为1
4. 确定遍历顺序：先行后列还是先列后行没有影响
5. 举例推导：以用例1为例，它的dp数组应该是：
    
    | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
    | --- | --- | --- | --- | --- | --- | --- |
    | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
    | 1 | 3 | 6 | 10 | 15 | 21 | 28 |
    
    可见没有问题
    
:::tip{title="提示"}
另外，这题还有一个数论的解法。首先，对于给定的m，n，从起点走到终点一定会走$$m + n - 2$$步，而且其中一定有$$m - 1$$步是向下走的，别管什么时候向下走。那也就是说，这题可以转化为一个数学问题：在$$m + n - 2$$个数中，挑出$$m - 1$$个数，可以有多少种挑法？结果就是$$C^{m - 1}_{m + n - 2}$$。
:::


``` python
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 初始化
        dp_array = [[0] * n] * m
        for i in range(n):
            dp_array[0][i] = 1
        for i in range(m):
            dp_array[i][0] = 1

        # 开始dp
        for i in range(1, m):
            for j in range(1, n):
                dp_array[i][j] = dp_array[i - 1][j] + dp_array[i][j - 1]

        return dp_array[-1][-1]
```

``` java
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp_array = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp_array[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp_array[0][i] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp_array[i][j] = dp_array[i - 1][j] + dp_array[i][j - 1];
            }
        }
        return dp_array[m - 1][n - 1];
    }
}
```

``` go
func uniquePaths(m int, n int) int {
    dpArray := make([][]int, m)
    for i := range dpArray {
        dpArray[i] = make([]int, n)
        dpArray[i][0] = 1
    }
    for i := range dpArray[0] {
        dpArray[0][i] = 1
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dpArray[i][j] = dpArray[i - 1][j] + dpArray[i][j - 1]
        }
    }
    return dpArray[m - 1][n - 1]
}
```

### 2 LeetCode63 不同路径 Ⅱ

:::info{title="题目"}
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

![image.png](https://www.misaka19327.cc/static/img/92f6af59950f735b340f54e9b4052c82.image.png)
```
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
```
示例 2：
```
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
```

提示：

- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] 为 0 或 1
:::

~~不是，这题给的用例也太坑，完全看不出来这二维数组是按行存的还是按列存的气死个人。~~

这题的思路和上面的62是完全一致的，但是有的地方不一样。一方面是遍历dp数组的过程中，如果遇到障碍，说明这块是永远不可抵达的，所以要将其置为0；另一方面是初始化dp数组的过程中，如果遇到障碍，那么从这个障碍之后的所有位置都要置0，因为初始化的那一行/列本来就只有一条路，有个障碍在那里直接就把这一条路堵死了。

``` python
from typing import List

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if obstacleGrid[0][0] == 1:
            return 0
        # 这题的obstacleGrid是按列存的 obstacleGrid[i]代表的是一列的数据 注意
        # 初始化
        for i in range(1, len(obstacleGrid)):  # 因为是一旦遇到障碍 后面赋值为0 所以不能从头开始循环 否则下一个初始化会有问题
            if obstacleGrid[i][0] == 0:
                obstacleGrid[i][0] = 1
            else:
                # 一旦遇到障碍 后面全部赋值为0
                obstacleGrid[i][0] = 0
                if i < len(obstacleGrid) - 1:
                    obstacleGrid[i + 1][0] = 1
        for i in range(len(obstacleGrid[0])):
            if obstacleGrid[0][i] == 0:
                obstacleGrid[0][i] = 1
            else:
                obstacleGrid[0][i] = 0
                if i < len(obstacleGrid[0]) - 1:
                    obstacleGrid[0][i + 1] = 1

        for i in range(1, len(obstacleGrid)):
            for j in range(1, len(obstacleGrid[0])):
                if obstacleGrid[i][j] == 1:
                    obstacleGrid[i][j] = 0
                else:
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]

        return obstacleGrid[-1][-1]
```

``` java
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1) return 0;
        for (int i = 1; i < obstacleGrid.length; i++) {
            if (obstacleGrid[i][0] == 0) {
                obstacleGrid[i][0] = 1;
            } else {
                obstacleGrid[i][0] = 0;
                if (i < obstacleGrid.length - 1) {
                    obstacleGrid[i + 1][0] = 1;
                }
            }
        }
        for (int i = 0; i < obstacleGrid[0].length; i++) {
            if (obstacleGrid[0][i] == 0) {
                obstacleGrid[0][i] = 1;
            } else {
                obstacleGrid[0][i] = 0;
                if (i < obstacleGrid[0].length - 1) {
                    obstacleGrid[0][i + 1] = 1;
                }
            }
        }

        for (int i = 1; i < obstacleGrid.length; i++) {
            for (int j = 1; j < obstacleGrid[0].length; j++) {
                if (obstacleGrid[i][j] == 0) {
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                } else {
                    obstacleGrid[i][j] = 0;
                }
            }
        }
        return obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
    }
}
```

``` go
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	if obstacleGrid[0][0] == 1 {
		return 0
	}
	for i := 1; i < len(obstacleGrid); i++ {
		if obstacleGrid[i][0] == 1 {
			obstacleGrid[i][0] = 0
			if i < len(obstacleGrid) - 1 {
				obstacleGrid[i+1][0] = 1
			}
		} else {
			obstacleGrid[i][0] = 1
		}
	}
	for i := 0; i < len(obstacleGrid[0]); i++ {
		if obstacleGrid[0][i] == 1 {
			obstacleGrid[0][i] = 0
			if i < len(obstacleGrid[0]) - 1 {
				obstacleGrid[0][i + 1] = 1
			}
		} else {
			obstacleGrid[0][i] = 1
		}
	}
	for i := 1; i < len(obstacleGrid); i++ {
		for j := 1; j < len(obstacleGrid[0]); j++ {
			if obstacleGrid[i][j] == 1 {
				obstacleGrid[i][j] = 0
			} else {
				obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
			}
		}
	}
	return obstacleGrid[len(obstacleGrid) - 1][len(obstacleGrid[0]) - 1]
}
```