19-《进阶》打表和矩阵处理相关问题.md

[TOC]

# 1 打表技巧和矩阵处理技巧

在一个数组arr中，每个数的大小不超过1000，例如[10,9,6,12],所有的数，求所有数质数因子的个数总和？

`10=2*5`

`9=3*3`

`6=3*3`

`12=3*2*2`

我们可以把1000以内的数的质数因子个数求出来，存到我们的表中，查表即可


## 1.1 打表法

1）问题如果返回值不太多，可以用hardcode的方式列出，作为程序的一部分

2）一个大问题解决时底层频繁使用规模不大的小问题的解，如果小问题的返回值满足条件1），可以把小问题的解列成一张表，作为程序的一部分

3）打表找规律（本节课重点）


### 1.1.1 打表找规律

1）某个面试题，输入参数类型简单，并且只有一个实际参数

2）要求的返回值类型也简单，并且只有一个

3）用暴力方法，把输入参数对应的返回值，打印出来看看，进而优化code


### 1.1.2 例题1 小虎买苹果

小虎去买苹果，商店只提供两种类型的塑料袋，每种类型都有任意数量。

1）能装下6个苹果的袋子

2）能装下8个苹果的袋子

小虎可以自由使用两种袋子来装苹果，但是小虎有强迫症，他要求自己使用的袋子数量必须最少，且使用的每个袋子必须装满。
给定一个正整数N，返回至少使用多少袋子。如果N无法让使用的每个袋子必须装满，返回-1


> 暴力思路，例如N=100个苹果，我们全部用8号袋装，最多使用12个8号袋子，剩4个苹果，6号袋没装满。8号袋减1，需要2个6号袋，满足。如果依次递减8号袋，为0个仍未有答案，则无解


```Go
package main

import "fmt"

func minBags(apple int) int {
	if apple < 0 {
		return -1
	}

	bag6 := -1
	bag8 := apple / 8
	rest := apple - 8 * bag8
	for bag8 >= 0 && rest < 24 {
		restUse6 := minBagBase6(rest)
		if restUse6 != -1 {
			bag6 = restUse6
			break
		}

		rest = apple - 8 * (bag8)
		bag8--
	}
	if bag6 == -1 {
		return -1
	} else {
		return bag6 + bag8
	}
}

// 如果剩余苹果rest可以被装6个苹果的袋子搞定，返回袋子数量
// 不能搞定返回-1
func minBagBase6(rest int) int {
	if rest % 6 == 0 {
		return rest / 6
	} else {
		return -1
	}
}

// 根据打表规律写code
func minBagAwesome(apple int) int {
	if apple & 1 != 0 {// 如果是奇数，返回-1
		return -1
	}

	if apple < 18 {
		if apple == 0 {
			return 0
		} else {
			if apple == 6 || apple == 8 {
				return 1
			} else {
				if apple == 12 || apple == 24 || apple == 16 {
					return 2
				} else {
					return -1
				}
			}
		}
	}

	return (apple - 18) / 8 + 3
}

// 打表看规律，摒弃数学规律
func main() {
	for apple:=1; apple < 100; apple++ {
		fmt.Println(minBags(apple))
	}
}
```

### 1.1.2 例题2 牛羊吃草

给定一个正整数N，表示有N份青草统一堆放在仓库里
有一只牛和一只羊，牛先吃，羊后吃，它俩轮流吃草
不管是牛还是羊，每一轮能吃的草量必须是：

1，4，16，64…(4的某次方)

谁最先把草吃完，谁获胜

假设牛和羊都绝顶聪明，都想赢，都会做出理性的决定

根据唯一的参数N，返回谁会赢


> 暴力思路打表找规律

```
package main

import "fmt"

// n份青草放在一堆
// 先手后手都绝顶聪明
// string "先手" "后手"
func winner1(n int) string {
	// 0  1  2  3 4
	// 后 先 后 先 先
	// base case
	if n < 5 {
		if n == 0 || n == 2 {
			return "后手"
		} else {
			return "先手"
		}
	}

	// n >= 5 时
	base := 1 // 当前先手决定吃的草数
	// 当前是先手在选
	for base <= n {
		// 当前一共n份草，先手吃掉的是base份，n - base 是留给后手的草
		// 母过程 先手 在子过程里是 后手
		if winner1(n -base) == "后手" {
			return "先手"
		}
		if base > n / 4 { // 防止base*4之后溢出
			break
		}
		base *= 4
	}
	return "后手"
}

// 根据打表的规律，写代码
func winner2(n int) string {
	if n % 5 == 0 || n % 5 == 2 {
		return "后手"
	} else {
		return "先手"
	}
}

// 暴力打表找规律
func main() {
	for i:=0; i<=50; i++ {
		fmt.Println(fmt.Sprintf("%d : %s", i, winner1(i)))
	}
}
```

### 1.1.3 例题3 

定义一种数：可以表示成若干（数量>1）连续正数和的数
比如:

5 = 2+3，5就是这样的数

12 = 3+4+5，12就是这样的数

1不是这样的数，因为要求数量大于1个、连续正数和

2 = 1 + 1，2也不是，因为等号右边不是连续正数

给定一个参数N，返回是不是可以表示成若干连续正数和的数


```Go
package main

import "fmt"

// isMSum1 暴力法。给定一个参数N，返回是不是可以表示成若干连续正数和的数
func isMSum1(num int) bool {
	for i := 1; i<=num; i++ {
		sum := i
		for j := i + 1; j <= num; j++ {
			if sum + j > num {
				break
			}
			if sum + j == num {
				return true
			}
			sum += j
		}
	}
	return false
}

// 根据打表的规律写代码
func isMSum2(num int) bool {
	if num < 3 {
		return false
	}
	return (num & (num - 1)) != 0
}

// 打表
func main() {
	for num := 1; num <200; num++ {
		fmt.Println(fmt.Sprintf("%d : %v", num, isMSum1(num)))
	}
	fmt.Println("test begin")
	for num := 1; num < 5000; num++ {
		if isMSum1(num) != isMSum2(num) {
			fmt.Println("Oops!")
		}
	}
	fmt.Println("test end")
}
```

### 1.2 矩阵处理技巧

1）zigzag打印矩阵

2）转圈打印矩阵

3）原地旋转正方形矩阵

核心技巧：找到coding上的宏观调度

#### zigzag打印矩阵

> 矩阵的特殊轨迹问题，不要把思维限制在具体某个坐标怎么变化

对于一个矩阵，如何绕圈打印，例如：

```math
\begin{matrix}
1&2&3 \\   
4&5&6 \\
7&8&9 \\
\end{matrix}
```

打印的顺序为：1，2，4，7，5，3，6，8，9

> 思路：准备A和B两个点，坐标都指向0，0位置。A和B同时走，A往右走，走到尽头后往下走，B往下走，走到不能再走了往右走。通过这么处理，A和B每个位置的连线都是一条斜线，且无重复。A和B每同时走一步，打印每次逆序打印，即开始时从B往A打印，下一步从A往B打印，循环往复


```Go
package main

import "fmt"

func printMatrixZigZag(matrix [][]int) {
	// A的行row
	tR := 0
	// A的列coulum
	tC := 0
	// B的行row
	dR := 0
	// B的列coulum
	dC := 0
	// 终止位置的行和列
	endR := len(matrix) - 1
	endC := len(matrix[0]) - 1
	// 是不是从右上往左下打印
	fromUp := false
	// A的轨迹不会超过最后一行
	for tR != endR + 1 {
		// 告诉当前A和B,打印方向，完成打印
		printLevel(matrix, tR, tC, dR, dC, fromUp)
		// 打印完之后，A和B再移动。A到最右再向下，B到最下再向右
		if tC == endC {
			tR = tR + 1
		} else {
			tC = tC + 1
		}
		if dR == endR {
			dC = dC + 1
		} else {
			dR = dR + 1
		}
		// A和B来到下一个位置之后，改变打印方向
		fromUp = !fromUp
	}
	fmt.Println()
}

func printLevel(m [][]int, tR int, tC int, dR int, dC int, f bool) {
	if f {
		for tR != dR + 1 {
			fmt.Print(fmt.Sprintf("%d ", m[tR][tC]))
			tR++
			tC--
		}
	} else {
		for dR != tR -1 {
			fmt.Print(fmt.Sprintf("%d ", m[dR][dC]))
			dR--
			dC++
		}
	}
}

// 1 2 5 9 6 3 4 7 10 11 8 12
func main() {
	matrix := [][]int{
		{ 1, 2, 3, 4 }, 
		{ 5, 6, 7, 8 }, 
		{ 9, 10, 11, 12 },
	}
	printMatrixZigZag(matrix)
}
```

#### 转圈打印矩阵


```math
\begin{matrix}
1&2&3&4 \\   
5&6&7&8 \\
9&10&11&12 \\
13&14&15&16 \\
\end{matrix}
```

打印轨迹是：1，2，3，4，8，12，16，15，14，13，9，5，6，7，11，10

> 思路：每个圈，我们知道左上角的位置，和右下角的位置，我们就可以得到需要转圈的圈的大小，

```Go
package main

import "fmt"

// 转圈打印矩阵
func spiralOrderPrint(matrix [][]int) {
	// A行
	tR := 0
	// A列
	tC := 0
	// B行
	dR := len(matrix) - 1
	// B列
	dC := len(matrix[0]) - 1
	for tR <= dR && tC <= dC {
		printEdge(matrix, tR, tC, dR, dC)
		tR++
		tC++
		dR--
		dC--
	}
}

// 当前打印，左上角和右下角的位置
func printEdge(m [][]int, tR int, tC int, dR int, dC int) {
	// 表示区域只剩下一条横线的时候
	if tR == dR {
		for i:=tC; i<=dC; i++ {
			fmt.Print(fmt.Sprintf("%d ", m[tR][i]))
		}
	} else if tC == dC { // 表示区域只剩下一条竖线了
		for i:=tR; i<=dR; i++ {
			fmt.Print(fmt.Sprintf("%d ", m[i][tC]))
		}
	} else { // 通用情况
		curC := tC
		curR := tR
		for curC != dC {
			fmt.Print(fmt.Sprintf("%d ", m[tR][curC]))
			curC++
		}
		for curR != dR {
			fmt.Print(fmt.Sprintf("%d ", m[curR][dC]))
			curR++
		}
		for curC != tC {
			fmt.Print(fmt.Sprintf("%d ", m[dR][curC]))
			curC--
		}
		for curR != tR {
			fmt.Print(fmt.Sprintf("%d ", m[curR][tC]))
			curR--
		}
	}
}

// 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 
func main() {
	matrix := [][]int{
		{ 1, 2, 3, 4 },
		{ 5, 6, 7, 8 },
		{ 9, 10, 11, 12 },
		{ 13, 14, 15, 16 },
	}
	spiralOrderPrint(matrix)
}
```

#### 矩阵调整-原地旋转正方形矩阵

必须要是正方形矩阵，非正方形的旋转会越界；题意的意思是每一个数都顺时针旋转90度


```math
\begin{matrix}
1&2&3&4 \\   
5&6&7&8 \\
9&10&11&12 \\
13&14&15&16 \\
\end{matrix}
```

调整后的结构为：

```math
\begin{matrix}
13&9&5&1 \\   
14&10&6&2 \\
5&11&7&3 \\
16&12&8&4 \\
\end{matrix}
```


> 思路：一圈一圈的转，和旋转打印思路比较像。按圈，再按小组旋转，第一圈的第一个小组为四个角。分别为：1，4，16，13；第二小组为：2，8，15，9；依次旋转小组，最终达到旋转该圈的目的。接着旋转下一个圈的各个小组。每一层的小组数目等于该圈的边长减1

```Go
package main

import "fmt"

// 原地旋转正方形矩阵
func rotate(matrix [][]int) {
	// a行
	a := 0
	// b列
	b := 0
	// c行
	c := len(matrix) - 1
	// d列
	d := len(matrix[0]) - 1
	// 由于是正方形矩阵，只需要判断行不越界，等同于判断列不越界
	for a < c {
		rotateEdge(matrix, a, b, c, d)
		a++
		b++
		c--
		d--
	}
}

// 当前需要转的圈的左上角和右下角
func rotateEdge(m [][]int, a, b, c, d int) {
	tmp := 0
	// 得到左上角右下角坐标，我们可以知道右上角和左下角的位置，这四个位置先旋转。这四个位置称为一个小组。
	// 旋转完之后，找下四个位置的小组再旋转
	for i := 0; i < d - b; i++ {
		tmp = m[a][b + i]
		m[a][b + i] = m[c - i][b]
		m[c - i][b] = m[c][d - i]
		m[c][d - i] = m[a + i][d]
		m[a + i][d] = tmp
	}
}

func printMatrix(matrix [][]int) {
	for i := 0; i != len(matrix); i++ {
		for j := 0; j != len(matrix[0]); j++ {
			fmt.Print(fmt.Sprintf("%d ", matrix[i][j]))
		}
		fmt.Println()
	}
}

//1 2 3 4
//5 6 7 8
//9 10 11 12
//13 14 15 16
//==============
//13 9 5 1
//14 10 6 2
//15 11 7 3
//16 12 8 4
func main() {
	matrix := [][]int{
		{ 1, 2, 3, 4 },
		{ 5, 6, 7, 8 },
		{ 9, 10, 11, 12 },
		{ 13, 14, 15, 16 },
	}
	printMatrix(matrix)
	rotate(matrix)
	fmt.Println("==============")
	printMatrix(matrix)
}
```

> 大量的矩阵变换都会涉及到一个宏观调度，不到万不得已，不要把自己陷入每个位置怎么变，扣每个位置的变化，会非常难