Golang LeeCode练习题

# 算法重要概念

## 算法复杂度

算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。算法是大厂、外企面试的必备项，也是每个高级程序员的必备技能。针对同一问题，可以有很多种算法来解决，但不同的算法在效率和占用存储空间上的区别可能会很大。

那么，通过什么指标来衡量算法的优劣呢？其中，上面提到的效率可以用算法的时间复杂度来描述，而所占用的存储空间可以用算法的空间复杂度来描述。

- 时间复杂度：用于评估执行程序所消耗的时间，可以估算出程序对处理器的使用程度。

- 空间复杂度：用于评估执行程序所占用的内存空间，可以估算出程序对计算机内存的使用程度。

在实践中或面试中，我们不仅要能够写出具体的算法来，还要了解算法的时间复杂度和空间复杂度，这样才能够评估出算法的优劣。当时间复杂度和空间复杂度无法同时满足时，还需要从中选取一个平衡点。

一个算法通常存在最好、平均、最坏三种情况，我们一般关注的是最坏情况。最坏情况是算法运行时间的上界，对于某些算法来说，最坏情况出现的比较频繁，也意味着平均情况和最坏情况一样差。

通常，时间复杂度要比空间复杂度更容易出问题，更多研究的是时间复杂度，面试中如果没有特殊说明，讲的也是时间复杂度。

# 一、时间复杂度

时间复杂度的全称是**渐进时间复杂度**，算法的时间复杂度是用大写的“`O`”来表示的，比如：`O(1)`，`O(n)`，`O(logn)`，`O(nlogn)`，`O(n²)` 等，表示算法的执行时间与数据规模之间的增长关系。

>这种时间复杂度表示法并不能真正反应一个算法的执行时间，反应的只是一个趋势，所以我们在分析复杂度的时候要关注“变”，忽略“不变”。

变指的是变量，也就是**一段代码的执行时间是随着变量的变化而变化的**，而不变指的是常量，也就是不论我的变量如何改变，执行时间都不会改变。

----------

## O(1) 常数阶

0(1) 复杂度算法也称之为常数阶算法。这里的 1 是用来代指常量，也就是说这个算法的效率是固定的，无论你的数据量如何变化，效率都一样，这种复杂度也是最优的一种算法。
```go
func calc() int {
	a := 1
	b := 2
	c := 3
	return a + b + c
}
```

上面的示例中不论有多少行代码，时间复杂度都是属于常数阶。

换言之：只要代码不存在循环，递归等循环类调用，不论代码有多少行，其复杂度都是常数阶。

---------------

## O(n) 线性阶

O(n) 复杂度算法也称之为线性阶。

```go
// 时间复杂度O(n)
func printValue(n int) {
	a:=0
	for i := 0; i < n; i++ {
		fmt.Println(i,a)
	}
}
```

我们假设每一行代码的执行时间是 T，那么上面这段代码的执行复杂度是 `T+n*T`，也就是 `(n+1)T`

而在算法中有一个原则，那就是常量可以被忽略，所以就得到了 nT，换成大 O 表示法就是 `O(n)`。

>这只是一个简略的计算过程，忽略每行代码执行时间可能不一致的情况

算法中的复杂度反应的只是一个趋势，这里 O(n) 反应的就是一个趋势，也就是随着 n 的变化，算法的执行时间是会降低的。

---------------

## O(n²) 平方阶

双层循环就是平方阶，同理，三层循环就是立方阶，**k 次循环就是 k 次方阶**。

```go
// 时间复杂度O(n的3次方)
func cycle(a int) {
	n := 0
	for i := 0; i < a; i++ {
		for j := i; j < a; j++ {
			for k := j; k < a; k++ {
				n = i + j + k
			}
		}
	}
	fmt.Println(n)
}
```

---------------

## O(logn) 对数阶

O(logn) 也称之为对数阶，对数阶也很常见，像二分查找，二叉树之类的问题中会见到比较多的对数阶复杂度，但是对数阶也是比较难理解的一种算法复杂度。

```go
func logarithm(n int) {
	i := 0
	for i >= n {
		i = 2 * n
	}
}
```

这段代码最关键就是要分析出 for 循环中到底循环了多少次，我们观察这个循环，发现 i 并不是逐一递增，而是不断的翻倍：**1->2->4->8->16->32->64** 一直到等于或者大于 n 为止才会结束

所以我们得到了这样的一个公式：
```
2^x=n
```

也就是我们只要计算出 x 的值，就得到了循环次数，而根据高中的数学知识我们可以得到 `x=log2n`（2是底数）

所以根据上面线性阶的分析方法，我们省略常量，就得到了示例中的算法复杂度为 `O(log2n)`。

同样的分析方式，下面的例子，我们可以很快的分析出复杂度就为 O(log3n)：

```go
func logarithm(n int) {
	i := 0
	for i >= n {
		i = 3 * n
	}
}
```

上面得到的 log3n 我们可以再做进一步的转换：`log3n=log32 * log2n`

而 log32（注意这几个地方的 3 是底数） 是一个常量，常量可以省略，所以也就得到了：
```
O(log3n)=O(log2n)
```
同样的道理，不论底数是多少，其实最终都可以转化成和 O(log2n) 相等，正因为如此，为了方便，我们算法中通常就会省略底数，直接写作 O(logn)。

>上面的数学公式大家如果忘了或者看不懂也没关系，只要记住不论对数的底数是多少，我们都算作 O(logn)
而对于一个算法的复杂度是否是对数阶，还有一个简易的判断方法：
当循环中下标以指定倍数形式衰减，那么这就是一个对数阶。

---------------

## O(nlogn) 线性对数阶
如果理解了上面的对数阶，那么这种线性对数阶就非常好理解了，只需要在对数阶的算法中再嵌一层循环就是线性对数阶：

```go
func logarithm2(n int) {
	for i := 0; i < 10; i++ {
		j := 1
		for j < n {
			j = j * 2
		}
	}
}
```
-------

分析了前面这些最常用的时间复杂度，其实我们可以得到以下规律：

1. 只要是常量级别，不论多大，效率都是一样的。

2. 分析一段代码的时间复杂度，只需要分析执行次数最多的一段代码。

3. 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

# 二、其他复杂度

除了上面常用的复杂度之外，另外还有指数阶，阶层阶，根号阶等，这些接触的相对会较少，不做赘述。

# 三、组合式复杂度分析
前面我们分析的都是只有一段代码比较复杂的情况下得到的复杂度结果，那么假如一个算法中，有多段代码都比较复杂呢？这时候复杂度该如何分析？

## 取最大复杂度作为整个算法复杂度

示例如下：
```go
func print1(n int)  {
	for i := 0; i < 100; i++ {
		fmt.Println(i)
	}

for k := 0; k < n; k++ {
		fmt.Println(k)
	}

for j := 0; j < n; j++ {
		for i := 0; i < n+1; i++ {
			fmt.Println(j+i)
		}
	}
}
```

这个例子中有三个循环，首先第一个，是一个常量，那么根据前面的结论，不论这个常量是多大，都属于常量级，所以第一个循环中的复杂度为 O(1)，第二个和第三个循环我们前面也分析过，复杂度分别为 O(n) 和 O(n²)。

也就是这一段代码中有三段代码产生了三种不同复杂度，而且这三个复杂度可以很明显得到的大小关系为：
`O(1)<O(n)<O(n²)`，像这种在同一个算法中有明确大小关系的，就可以直接取最大值作为这个算法的复杂度，所以这个例子中算法的复杂度就是`O(n²)`。

## 取多个复杂度之和作为整个算法复杂度

示例如下：
```go
func print2(n,m int) {
	for i := 0; i < 100; i++ {
		fmt.Println(i)
	}

for k := 0; k < n; k++ {
		fmt.Println(k)
	}

for j := 0; j < m; j++ {
		fmt.Println(j)
	}
}
```

这个例子我们同样对三段循环分别分析可以分别得到如下复杂度：O(1)，O(m)，O(n)。这时候我们只能知道 O(1) 最小可以忽略，但是后面两个无法却无法确定大小，所以这时候我们需要取两段循环复杂度之和来作为算法的复杂度，所以可以得到这个例子的算法复杂度为：`O(m+n)`。

# 时间复杂度类型

上面分析的时间复杂度都是比较简单的，实际算法中可能会比示例中复杂的多，而且我们示例中只要是循环都是无脑循环，也就是一定从头循环到尾，然而实际中我们有时候并不需要从头循环到尾，可能中途就会结束循环，所以我们根据实际情况，又可以将时间复杂度从以下四个方面来进一步分析：

- 最好时间复杂度
- 最坏时间复杂度
- 平均时间复杂度
- 均摊时间复杂度

这四种类型的时间复杂度在这里只会介绍前面三种，因为第四种比较复杂，而且使用场景也非常有限，因为在绝大部分情况我们只需要分析最坏复杂度就行，也就是假设循环全部执行完毕场景下的时间复杂度。

## 最好时间复杂度
我们通过一个例子来理解下最好时间复杂度：

```go
func print3(nums []int) int {
	if nums == nil || len(nums) == 0 {
		return -1
	}
	for i := 0; i < len(nums); i++ {
		if nums[i] == 0 {
			return -1
		}
	}
	return -1
}
```

这个方法就是在一个指定数组中找到指定元素的下标，找不到就返回 -1，这个方法比较简单，应该比较好理解。

这个方法中的循环体，如果找到元素，那么就直接返回，这就会有一个现象，那就是这个循环体到底会循环多少次是不确定的，可能是 1 次，也可能是 n（假设数组的长度）次，

所以假如要找的元素就在数组中的第一个位置，那么循环一次就找到了，这个算法的复杂度就是 O(1)，这就是最好情况时间复杂度。

## 最坏时间复杂度

数组中不存在目标元素，或者说最后一个值才是需要的目标元素，那么就必须循环完整个数组，时间复杂度就是 O(n)，也就是最坏时间复杂度。

## 平均时间复杂度
最好时间复杂度和最坏时间复杂度毕竟只有特殊情况才会发生，概率还是相对较小，所以需要有一个平均时间复杂度。

为了便于分析，假设一个元素在数组和不在数组中的概率都为 1/2，假如在数组中，那么又假设元素出现在每个位置的概率也是一样的，也就是每个位置出现元素的概率为： 1/n。

所以最终得到的平均时间复杂度应该等于元素在数组中和元素不在数组中两种情况相加。

**元素在数组中的复杂度**

元素在数组中的概率为 1/2，在每个位置出现的概率也为 1/n。

假如元素出现在第一个位置，复杂度为 1*(1/2n)；
假如元素出现在第二个位置，复杂度为 2 * (1/2n)，

最终得到当前场景下时间复杂度为：1*(1/2n) + 2 * (1/2n) + ... + n*(1/2n)=`(n+1)/4`。

**元素不在数组中的复杂度**

已经假定元素不在数组中的概率为 1/2，所以当前场景下的时间复杂度为：`n * (1/2)`，因为元素不在数组中，那么这个算法必然会将整个循环执行完毕，也就循环是 n 次。

最后我们把两种情况的复杂度之和相加就得到了平均时间复杂度：

```
(n+1)/4 + n/2 = (3n+1)/4
```

最终我们将常数类的系数忽略掉，就得到了平均时间复杂度为 O(n)。

## 均摊时间复杂度

均摊时间复杂度的算法需要使用摊还分析法，计算方式相对有点复杂，而且使用场景很有限，本文就不做过多介绍了。