# go-projects-leetcode

**Repository Path**: daizhangyuan/go-projects-leetcode

## Basic Information

- **Project Name**: go-projects-leetcode
- **Description**: leetcode刷题
- **Primary Language**: Go
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-05-18
- **Last Updated**: 2024-06-04

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数组

## 二分查找

### 思想

对于有序的序列，查找target。设立左指针`left`，右指针`right`，`mid=(left+right)/2`,每次查找都比较nums[mid]和target的大小，如中间的值小于target，则说明target只能在右半部分出现，反之只可能在左半部分出现，一直重复之前操作，直到找到target或者left=right；因为每次都是除2，所以时间复杂度是O（log~2~N），最差的时间复杂度是当序列是倒序的时候，这个时间复杂度是O(n)；

~~~go
func halfSearch(nums []int, target int) int {
	left, right := 0, len(nums)-1
	var mid = 0
	for left <= right {
		mid = (left+right)/2
		if nums[mid] == target {
			return mid
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}
~~~

> b站上有一个关于二分查找的模版。

~~~go
func halfSearch2(nums []int, target int) int {
	left, right := -1, len(nums)
	for (left + 1) != right {
		mid := (left + right) / 2
		if nums[mid] == target {
			return mid
		} else if nums[mid] < target {
			left = mid
		} else {
			right = mid
		}
	}
	return -1
}
~~~

>例子：1 2 3 5 5 5 8 9
>
>1、找到第一个">="的元素
>
>2、找到最后一个"<5"的元素
>
>3、找到第一个">5"的元素
>
>4、找到最后一个"<=5"的元素

![image-20220801110618763](/Users/dzy/Library/Application Support/typora-user-images/image-20220801110618763.png)

二分查找步骤：

l = -1， r = N

初始：l 指向蓝色区域，r 指向红色区域；

循环：l、r快速向蓝红边界逼近，**保持l、r颜色不改变**；

结束：l、r刚好指向蓝红边界；

伪代码：

<img src="/Users/dzy/Library/Application Support/typora-user-images/image-20220801111504781.png" alt="image-20220801111504781" style="zoom:50%;" />

### 相关题目

#### 35.[搜素插入位置](https://leetcode-cn.com/problems/search-insert-position)

题目描述：给定一个**排序数组**和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

> 解题思路：二分查找

如果目标值不存在数组中，与二分查找返回-1不同的是需要返回这个目标值将呗顺序插入的位置，这个位置可以是0也可以是n，故可以先判断这个目标值和数组最后一个元素的大小，若是目标值比较大，则直接返回n，和判断目标值和数组第一个元素，若是目标值较小，则直接返回0。剩余的情况则说明目标值肯定在第0个元素和第n-1个元素之间，故该题可转化为寻找第一个大于target值的元素下标，然后将target插入到该位置。

~~~go
func searchInsert(nums []int, target int) int {
    if nums[0] > target {
        return 0
    }
    if nums[len(nums)-1] < target {
        return len(nums)
    }
	left, right := -1, len(nums)
	for (left + 1) != right {
		mid := (left + right) / 2
		if nums[mid] == target {
			return mid
		} else if nums[mid] < target {
			left = mid
		} else {
			right = mid
		}
	}
    // 未找到target时返回被插入的位置
	return right
}
~~~

#### 34.[在排序数组中查找第一个和最后一个位置](https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array)

题目描述：给定一个按照**升序排列**的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

> 解题思路：二分查找

找出目标值target在数组的开始位置，即找第一个大于等于target；结束为止，即找最后一个小于等于target的元素；

~~~go
func searchRange(nums []int, target int) []int  {
	var result []int  // 返回数组 
	var leftIdex = -1
	var rightIdex = -1
	leftIdex = binarySearchLeft(nums, target)  // 寻找左边界:找到第一个 >=5，返回r
	rightIdex = binarySearchRight(nums, target) // 寻找右边界：找到最后一个 <=5，返回l
	if leftIdex <= rightIdex && rightIdex < len(nums) && nums[leftIdex] == target && nums[rightIdex] == target {
		result = []int{leftIdex, rightIdex}
	} else {
		result = []int{-1, -1}
	}
	return result
}
func binarySearchLeft(nums []int, target int) int {
	left, right := -1, len(nums)
	var mid = 0
	for (left+1) != right {
		mid = (left + right) / 2
		if nums[mid] >= target {
			right = mid
		} else {
			left = mid
		}
	}
	return right
}
func binarySearchRight(nums []int, target int) int {
	left, right := -1, len(nums)
	var mid = 0
	for (left+1) != right {
		mid = (left + right) / 2
		if nums[mid] <= target {
			left = mid
		} else {
			right = mid
		}
	}
	return left
}
~~~

#### 69.[X的平方根](https://leetcode-cn.com/problems/sqrtx)

题目描述：给你一个非负整数 `x` ，计算并返回 `x` 的**算术平方根** 。由于返回类型是整数，结果只保留**整数部分**，小数部分将被 **舍去 。**

> 解题思路：二分查找

正确解法：对于给定的非负整数，进行范围为【1，x】的二分查找，如果 mid * mid 小于等于x，则 left = mid；反之，right = mid。

~~~go
func mySqrt(x int) int {
	if x == 0 {
		return 0
	}
	if x == 1 {
		return 1
	}
	left, right := -1, x
	for (left + 1) != right {
		mid := (left + right) / 2
		if mid * mid <= x {
			left = mid
		} else {
			right = mid
		}
	}
	return left
}
~~~

~~~go
// 如果是重新申请内存保存为数组的话，会有分配内存的错误
func mySqrt2(x int) int {
	if x == 0 || x == 1 {
		return x
	}
	var nums = make([]int, x)  // 会有分配内存的错误
	// nums = []int{1,2,3,4,5,6,7,8}
	for i := 0; i < x; i++ {
		nums[i] = i+1
	}
	fmt.Println(nums)
	left, right := -1, len(nums)
	for left + 1 < right {
		mid := (left + right) / 2
		if nums[mid] * nums[mid] <= x{
			left = mid
		}
		if nums[mid] * nums[mid] > x {
			right = mid
		}
	}
	return nums[left]
}
~~~

#### 367.[有效的完全平方数](https://leetcode-cn.com/problems/valid-perfect-square)

> 二分查找

~~~go
func isPerfectSquare(num int) bool {
	if num == 1 {
		return true
	}
	left, right := -1, num
	for (left + 1) != right {
		mid := (left + right) / 2
		if mid * mid == num {
			return true
		} else if mid * mid < num {
			left = mid
		} else {
			right = mid
		}
	}
	return false
}
~~~

#### 33、搜索旋转排序数组

题目描述：整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

>解题思路：二分查找。
>
>数组元素无重复。举个例子大概可以分为两类：1 2 3 4 5 6 7
>
>旋转数组之后数组可分为两个部分:[left,mid] && [mid+1, right]，其中肯定有一个部分是有序的，我们根据有序的部分确定target在不在这个部分。
>
>1）第一类：2 3 4 5 6 7 1；nums[left] <= nums[mid]，此时前半部分有序，在有序的部分来判断target在哪个部分，如果 nums[left] <= target < nums[mid]，说明target在前半部分，否则在后半部分；
>
>2）第二类：6 7 1 2 3 4 5；nums[left] > nums[mid]，此时后半部分有序，在有序的部分来判断target在哪一个部分，如果nums[mid] < target <= nums[right]，说明target在后半部分，否则在前半部分。

~~~go
/** 
* @Description: 数组元素互不相同
* @param nums
* @param target
* @return int
**/
func search2(nums []int, target int) int {
	if len(nums) == 1 {
		if nums[0] == target {
			return 0
		} else {
			return -1
		}
	}
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)>>1
		if nums[mid] == target {
			return mid
		}
		// 如果前半部分有序
		// 不可以删去等于的情况是因为可能left==mid，重合了，此时若是没有nums[left]==nums[mid]会陷入死循环
		if nums[left] <= nums[mid] {
			// 判断target是在哪一个部分
			// 因为是左闭右闭区间，且target < nums[mid]，所以right= mid-1
			// 如果right=mid的话，说明target可以等于nums[mid]，与if条件不符；
			if nums[left] <= target && target < nums[mid] {
				// 如果target在前半部分
				right = mid - 1
			} else {
				// target在后半部分
				left = mid + 1
			}
		} else if nums[left] > nums[mid] {
			// 如果后半部分有序
			// 如果target在后半部分
			if nums[mid] < target && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}
	return -1
}
~~~

#### 81、搜索旋转排序数组||

题目描述：已知存在一个按非降序排列的整数数组 nums ，**数组中的值不必互不相同**。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-in-rotated-sorted-array-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

>二分查找注意的问题：
>
>1）循环的结束条件；
>
>2）满足性质的条件确定；
>
>3）边界条件的确定；
>
>具体问题具体分析，不能套模版。

~~~go
func search(nums []int, target int) bool {
	if len(nums) == 1 {
		if nums[0] == target {
			return true
		} else {
			return false
		}
	}
	// 数值可能是相同的
	left, right := 0, len(nums)-1
	// 左闭右闭
	for left <= right {
		mid := left + (right-left)>>1
		if nums[mid] == target {
			return true
		}
		if nums[left] == nums[mid] {
			left++
			continue
		}
		// 前半部分有序
		if nums[left] < nums[mid] {
			// target在前半部分
			if nums[mid] > target && nums[left] <= target {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			// 后半部分有序
			// target在后半部分
			if nums[mid] < target && nums[right] >= target {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}
	return false
}
~~~

~~~go
func search(nums []int, target int) bool {
	if len(nums) == 1 {
		if nums[0] == target {
			return true
		} else {
			return false
		}
	}
	// 如果数组元素是不重复的话，可以根据有序的部分确定如何更改二分查找的上下界
	left, right := 0, len(nums)-1
	// 等于的情况等会再考虑
	for left <= right {
		mid := left + (right-left)>>1
		if nums[mid] == target {
			return true
		}
		// 说明[left,mid]这个区间都是相同的数，此时只需要跳过
		if nums[left] == nums[mid] {
			left++
			continue
		}
		// 如果前半部分是单调不递减的
		if nums[left] < nums[mid] {
			// 再判断target在哪一个部分
			// 如果target在前半部分
			if nums[left] <= target && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid
			}
		} else if nums[left] > nums[mid] {
			// 后半部分是单调不递减的
			// 如果target在后半部分
			if nums[mid] < target && target <= nums[right] {
				left = mid + 1
			} else {
				// 如果target在前半部分
				right = mid
			}
		}
	}
	return false
}
~~~

#### 153、寻找旋转排序数组中的最小值

题目描述：已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

**给你一个元素值 互不相同 的数组 nums** ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

>

~~~go
func findMin(nums []int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right-left)>>1
		if nums[mid] > nums[right] {
			left = mid + 1
		} else if nums[mid] < nums[right] {
			right = mid
		}
	}
	return nums[left]
}

~~~

~~~go
func findMin2(nums []int) int {
	// 先用nums[0]与nums[mid]比较，判断是哪一个部分是有序的
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right - left) >> 1
		// 如果左边有序
		if nums[left] <= nums[mid] {
			if nums[left] < nums[right] {
				// 收缩左区间
				right = mid
			} else {
				left = mid + 1
			}
		} else {
			// 如果右边有序
			if nums[mid] < nums[right] {
				// 收缩左区间
				right = mid
			} else {
				// 收缩右区间
				left = mid
			}
		}
	}
	return nums[left]
}
~~~



#### 154、寻找旋转排序数组中的最小值||

题目描述：已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

**给你一个可能存在 重复 元素值的数组 nums** ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

~~~go
func findMin(nums []int) int {
	// 与153题不同在于会有重复元素
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right-left)>>1
		if nums[mid] > nums[right] {
			left = mid + 1
		} else if nums[mid] < nums[right] {
			right = mid
		} else if nums[mid] == nums[right] {
			right--
		}
	}
	return nums[left]
}
~~~

~~~go
func findMin(nums []int) int {
	// 对于最后一个数组元素x，最小值a右侧的值小于等于x，最小值a左侧的值大于等于x
	// 判断 mid 对应的元素值是在最小值的左半部分还是右半部分
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right-left) >> 1
		if nums[mid] == nums[right] {
			right--
			continue
		}
		if nums[mid] < nums[right] {
			right = mid
		} else if nums[mid] > nums[right]{
			//
			left = mid + 1
		}
	}
	return nums[left]
}
~~~



## 滑动窗口

### 思想

来源：https://programmercarl.com/0209（代码随想录）

不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

主要确定如下三点：

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

### 相关题目

209.[长度最小的子数组](https://leetcode-cn.com/problems/minimum-size-subarray-sum/)

> 方法一：暴力解法，两重循环遍历

~~~go
/*
思路：暴力解法，两重循环遍历
 */
func minSubArrayLen(target int, nums []int) int {
	var result = math.MaxInt32
	for i := 0; i < len(nums); i++ {
		sum := 0
		for j := i; j < len(nums); j++ {
			sum += nums[j]
			if sum >= target {
				result = min(result, j - i + 1)
				break
			}
		}
	}
	if result ==  math.MaxInt32 {
		return 0
	}
	return result
}
func min(x int, y int) int {
	if x < y {
		return x
	}
	return y
}
~~~

> 方法二：滑动窗口

left和right指针，left用来缩小窗口，right用来增大窗口；
只要子数组sum和小于target，则right指针往右移，直到子数组和 sum >= target，因为数组的值都为正整数，故不需再往右遍历；
此时需要的是缩小窗口，删去left对应的值直到 sum < target；如果删去left对应的值sum仍然大于等于target，则更新子数组长度；

~~~go
func minSubArrayLen2(target int, nums []int) int {
	var result = math.MaxInt32
	var left = 0
	var right = 0
	sum := 0
	for right < len(nums) {
		sum += nums[right]
		for sum >= target {
			result = min(result, right-left+1)
			sum -= nums[left]
			left++  // 子数组和大于等于target时缩小窗口
		}
		right++  // 子数组和小于target时往右扩大窗口
	}
	if result == math.MaxInt32 {
		return 0
	}
	return result
}
~~~

[904.水果成篮](https://leetcode-cn.com/problems/fruit-into-baskets/)

~~~go
func totalFruit(fruits []int) int {
	if len(fruits)  <= 2 {
		return len(fruits)
	}
	left, right := 0, 0
	result, count := 2, 0
	hashMap := map[int]int{}
	for ; right < len(fruits); right++{
		hashMap[fruits[right]]++  // 入篮
		if hashMap[fruits[right]] == 1 {  // 如果是第一次入篮
			count++
		}
		for count > 2 {
			hashMap[fruits[left]]--
			if hashMap[fruits[left]] == 0 {
				delete(hashMap, fruits[left])
				count--
			}
			left++
		}
		result = max(result, right - left + 1)
	}
	return result
}
func max(x int, y int) int {
	if x > y {
		return x
	}
	return y
}
~~~

[76.最小覆盖子串](https://leetcode-cn.com/problems/minimum-window-substring/)



~~~go
func minWindow(s string, t string) string {
	// 创建两个哈希表保存字符串s和字符串t出现的字符个数
	hs, ht := map[byte]int{}, map[byte]int{}
	for i := 0; i < len(t); i++ {  // 存储字符串t中的每个字符的个数
		//fmt.Printf("%c",t[i])
		ht[t[i]]++
	}
	var res = ""  // 保存返回的结果字符串
	var count = 0  // 记录当前窗口中符合字符串t的字符个数
	left, right := 0, 0  // 遍历指针，right扩展窗口，left收缩窗口
	for ;right < len(s);right++ {
		// 加入窗口
		hs[s[right]]++
		// 如果s[right]的个数小于字符串t中对应字符的个数，不满足字符串s覆盖字符串t的题意，必须加入窗口，计数加一
		if hs[s[right]] <= ht[s[right]] {
			count++
		}
		/*
		进行窗口的收缩：如果s中left对应的字符个数已经大于t中对应的字符个数，说明可以删除left对应元素来满足最小的条件
		 */
		for left <= right && hs[s[left]] > ht[s[left]] {
			hs[s[left]]--
			left++
		}
		if count == len(t) {
			if res == "" || (right - left + 1) < len(res) {  // 更新
				res = s[left: right+1]
			}
		}
	}
	return res
}
~~~



## 排序算法

### 冒泡排序

~~~go
func sortmaoPao(nums []int) {
	length := len(nums)
	for i := 0; i < length-1; i++ {  // 执行的趟数
		for j := 1; j < length; j++ {  // 比较的次数
			if nums[j] < nums[j-1] {
				nums[j], nums[j-1] = nums[j-1], nums[j]
			}
		}
	}
}
~~~

### 插入排序

~~~go
/*
插入排序：将未排序的元素依次插入到前面已排序的位置
 */
func insert(nums []int, i int)  {
	var key = nums[i]
	for ; nums[i-1] > key; i-- {
		nums[i] = nums[i-1]
		if i == 0 {
			break
		}
	}
	nums[i] = key
}
~~~

### 选择排序

~~~go
// 选择排序：选取当前的最大值和当前的最后一个数交换
func findMaxPosit (nums []int, n int) int {
	max := nums[0]
	position := 0
	for i := 0; i < n; i++ {
		if nums[i] > max {
			max = nums[i]
			position = i
		}
	}
	return position
}
func selectionSort(nums []int)  {
	for i := len(nums); i > 1; i--{
		position := findMaxPosit(nums, i)
		temp := nums[i-1]
		nums[i-1] = nums[position]
		nums[position] = temp
	}
}
~~~

### 快速排序

~~~go
/*
quickSort：思想是找到基准值的在数组中的下标
 */
func getIndex(nums []int, slow int, fast int) int {
	var temp = nums[slow] // 保存基准值
	for slow < fast {
		// 当队尾元素大于基准值时，right指针往左移，从右往左遍历
		for slow < fast && temp <= nums[fast] {
			fast--
		}
		// 当队尾元素小于基准值时，将队尾元素的值赋值给队首元素，并开始从左往后遍历
		nums[slow] = nums[fast]
		// 当队首元素小于基准值时，left指针往右移
		for slow < fast && temp >= nums[slow] {
			slow++
		}
		// 将队首元素赋值给队尾元素
		nums[fast] = nums[slow]
	}
	nums[slow] = temp
	return slow
}
func quickSort(nums []int, left int, right int )  {
	if left < right {
		index := getIndex(nums, left, right)
		quickSort(nums, left, index-1)
		quickSort(nums, index+1, right)
	}
}
~~~

### 堆排序

~~~go
// 堆排序：完全二叉树
// 堆调整: 调整为父节点的值大于子节点
func heapify(nums []int, n int, i int)  {  // n 表示节点数， i 表示需要调整的节点下标
	if i >= n {
		return
	}
	child1, child2 := 2 * i + 1, 2 * i + 2
	max := i  // 记录较大值的下标
	if child1 < n && nums[child1] > nums[max] {
		max = child1
	}
	if child2 < n && nums[child2] > nums[max] {
		max = child2
	}
	if max != i {
		nums[i], nums[max] = nums[max], nums[i]
		heapify(nums, n, max)  // 调整之后下标为max的子树可能不满足堆的定义，需要进行调整
	}
}
// 建堆
func buildHeap(nums []int, n int)  {  // n 表示完全二叉树的节点个数
	var lastNode = n - 1  // 最后一个节点下标
	var parent = (lastNode + 1) / 2  // 最后一个节点的父节点下标
	for i := parent; i >= 0; i-- {
		heapify(nums, n, i)
	}
}
// 排序
func heapSort(nums []int, n int)  {
	buildHeap(nums, n)
	for i := n - 1; i >= 0; i-- {
		nums[i], nums[0] = nums[0], nums[i]  // 将根节点与当前最后一个节点交换
		heapify(nums, i , 0)
	}
}
~~~

### 归并排序

#### 归并算法思想

1、分解（Divide）：将 n 个元素分成含 n/2 个元素的子序列；

2、解决（Solve）：用合并排序法对两个子序列递归的排序；

3、合并（merge）：合并两个已经排好序的子序列；

#### 实现逻辑

1、迭代法

- 申请空间，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排好序的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤3直到某一指针到达序列尾；
- 将另一序列剩下的所有元素 直接复制到合并序列尾；

2、递归法

- 将序列没相邻两个数字进行归并操作，形成floor(n/2)，排序后每个序列包含两个元素；
- 将上述需序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素；
- 重复步骤2，直到所有元素排序完毕；

~~~go
// 归并排序
// 递归划分
func mergeSort(nums []int, result []int, left int, right int) {
	// 如果只有一个元素，则停止划分
	if left < right {
		mid := (left + right) / 2
		mergeSort(nums, result, left, mid)
		mergeSort(nums, result, mid+1, right)
		merge(nums, result, left, mid, right)
	}
}
// 合并
func merge(nums []int, result []int, left int, mid int, right int) {
	i, j, k := left, mid+1, left  // 遍历指针，依次为左半部分第一个元素，右半部分第一个元素，存放排序后的元素下标
	for ; i <= mid && j <= right; k++ {  //
		if nums[i] < nums[j] {
			result[k] = nums[i]
			i++
		} else {
			result[k] = nums[j]
			j++
		}
	}
	for i <= mid {
		result[k] = nums[i]
		i++
	}
	for j <= right {
		result[k] = nums[j]
		j++
	}
	for left <= right {
		nums[left] = result[left]
		left++
	}
}
~~~

### 计数排序

> 计数排序思想：关键字排序，与其他排序不同，不是比较排序。申请一个计数数组，遍历原数组计数，然后再遍历计数数组，将对应的值写入到数组中就可以完成排序了。

~~~go
/**
* @Description: 计数排序
* @param nums
* @return []int
**/
func countSort(nums []int) []int {

	// 1、找出待排序的数组中最大和最小的元素
	maxNum := maxNumber(nums)
	//minNum := minNumber(nums)
	// 2、统计数组中每个值为 i 的元素出现的次数，存入数组count的第 i 项
	bucketLen := maxNum + 1
	bucket := make([]int, bucketLen)
	sortedIndex := 0
	for i := 0; i < len(nums); i++ {
		bucket[nums[i]]++
	}
	// 3、对所有的计数累加（从count中的第一个元素开始，每一项和前一项相加）
	for j := 0; j < bucketLen; j++ {
		for bucket[j] > 0 {
			// 4、反向填充目标数组：将每个元素 i 放在新数组的第count(i)项，每放一个元素就将count(i)减去1
			nums[sortedIndex] = j
			sortedIndex += 1
			bucket[j]--
		}
	}
	return nums
}
func maxNumber(nums []int) int{
	maxNum := nums[0]
	for i := 1; i < len(nums); i++ {
		if nums[i] > maxNum {
			maxNum = nums[i]
		}
	}
	return maxNum
}
~~~

>上述的排序，会造成不稳定。在排序中加入累加数组，然后对原数组从右往左遍历，这样得到排序后的数组是稳定的。

~~~go
func countSort2(nums []int) []int {
	var res = make([]int, len(nums))
	// 1、找出待排序的数组中最大和最小的元素
	maxNum := maxNumber(nums)
	// 2、统计数组中每个值为 i 的元素出现的次数，存入数组count的第 i 项
	bucketLen := maxNum + 1
	count := make([]int, bucketLen)
	for i := 0; i < len(nums); i++ {
		count[nums[i]]++
	}
	// 3、累加数组，目的是为了使排序稳定，其中count[i]保留的就是原数组元素值的下标减1
	// 比如：原来count[3,5,2]，原数组：nums[0,0,2,2,1,1,0,1,1,1]，累加数组count[3,8,10]
	// 将原数组从后往前遍历，遍历第一个1时，下标为：count[1]-1 = 7，然后直接将 1 放到下标为7的位置上,遍历第二个1时，下标为：count[1]-1=6
	for i := 1; i < len(count); i++ {
		count[i] += count[i-1]
	}
	// 4、将原数组的元素放到正确的位置上
	for i := len(nums)-1; i >= 0; i-- {
		res[count[nums[i]]-1] = nums[i]
		count[nums[i]]--
	}
	return res
}
~~~

### 基数排序

>思想：按照每一位排序

~~~go
func radixSort(arr []int) []int {
	// 获取数组的最大值
	max := getMax(arr)
	// 数组中最大值决定了循环次数，101 循环三次
	for bit := 1; max/bit > 0; bit *= 10 {
		arr = bitSort(arr, bit)
		fmt.Println("[DEBUG bit]\t", bit)
		fmt.Println("[DEBUG arr]\t", arr)
	}
	return arr
}

//
// 对指定的位进行排序
// bit 可取 1，10，100 等值
//
func bitSort(arr []int, bit int) []int {
	n := len(arr)
	// 各个位的相同的数统计到 bitCounts[] 中
	bitCounts := make([]int, 10)
	// 得到每个数的某一位数
	for i := 0; i < n; i++ {
		num := (arr[i] / bit) % 10
		bitCounts[num]++
	}
	fmt.Println("------------")
	fmt.Println(bitCounts)
	// 计数排序，累加
	for i := 1; i < 10; i++ {
		fmt.Printf("%d\t%d\t",bitCounts[i],bitCounts[i-1])
		fmt.Print("\n")
		bitCounts[i] += bitCounts[i-1]
	}
	fmt.Println(bitCounts)
	fmt.Println("++++++++++")
	tmp := make([]int, 10)
	// 按照某位进行排序
	for i := n - 1; i >= 0; i-- {
		num := (arr[i] / bit) % 10
		tmp[bitCounts[num]-1] = arr[i]
		bitCounts[num]--
	}
	fmt.Println(tmp)
	// 复制，减少空间复杂度
	for i := 0; i < n; i++ {
		arr[i] = tmp[i]
	}
	return arr
}
// 获取数组中最大的值
func getMax(arr []int) (max int) {
	max = arr[0]
	for _, v := range arr {
		if max < v {
			max = v
		}
	}
	return
}
~~~



## 模拟行为

### 59.螺旋矩阵||

题目描述：给你一个正整数 `n` ，生成一个包含 `1` 到 `n2` 所有元素，且元素按顺时针顺序螺旋排列的 `n x n` 正方形矩阵 `matrix` 。

> 思想：设立上下左右边界，然后按照从左到右、从上到下、从右往左、从下到上的顺序依次往数组里面填充数值

~~~go
func generateMatrix(n int) [][]int {
	var result = make([][]int,n)
	for i := 0; i < n; i++ {  // 创建二维切片
		result[i] = make([]int, n)
	}
	left, right, top, bottom := 0, n-1, 0, n-1
	var num = 1
	var end = n * n
	for num <= end {
		// 从左到右
		for i := left; i <= right; i++ {
			result[top][i] = num
			num++
		}
		top++
		// 从上到下
		for i := top; i <= bottom; i++ {
			result[i][right] = num
			num++
		}
		right--
		// 从右往左
		for i := right; i >= left; i-- {
			result[bottom][i] = num
			num++
		}
		bottom--
		// 从下到上
		for i := bottom; i >= top; i-- {
			result[i][left] = num
			num++
		}
		left++
	}
	return result
}

~~~

## 常用数组技巧

### 元素作为数组索引

#### 442.数组中重复的数据



#### 448.找到所有数组中消失的数字

题目描述：给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

> 解题思路：申请额外空间

具体：申请一个大小为n+1的数组temp，先将tem[i]全部置为0，遍历nums数组，将temp[nums[i]]置为1，表示nums[i]元素出现过，最后再遍历temp数组，将所有temp[i]==0的下标i放入result中，temp中的 i 就是num数组中的元素值。

~~~go
func findDisappearedNumbers(nums []int) []int {
	var result []int
	var temp = make([]int, len(nums)+1)
	for i := 1; i < len(temp); i++ {
		temp[i] = 0
	}
	for i := range nums {
		temp[nums[i]] = 1
	}
	for i := 1; i < len(temp); i++ {
		if temp[i] == 0 {
			result = append(result, i)
		}
	}
	return result
}
~~~

#### 1002.查找共用字符

题目描述：

给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。只有小写字母。

> 解题思路：hash表

具体过程：用hash保存每个字符串中字符的出现字数。如下图所示，最后再取每一列的最小值。

![1002.查找常用字符.png](https://pic.leetcode-cn.com/1632105856-qqFVxc-image.png)

~~~shell
/**
* @Description: 用数组返回字符串数组共用的字符
* @param words
* @return []string
**/
func commonChars(words []string) []string {
	var result []string
	// 用第一个字符串给hash初始化,保存第一个字符串的字符次数
	hashtable := make([]int, 26)
	for i := 0; i < len(hashtable); i++ {
		hashtable[i] = 0
	}
	// words[0] 第一个字符串
	for i := 0; i < len(words[0]); i++ {
		hashtable[words[0][i]-97]++
		//fmt.Println(hashtable[words[0][i]-97])
	}
	//fmt.Println("----------------------")
	//fmt.Println(hashtable)
	// 统计除第一个字符串外字符的出现频率
	otherhashtable := make([]int, 26)
	for i := 0; i < len(otherhashtable); i++ {
		otherhashtable[i] = 0
	}
	for j := 1; j < len(words); j++ {
		for i := 0; i < len(otherhashtable); i++ {
			otherhashtable[i] = 0
		}
		// 其他字符串
		otherwords := words[j]
		for k := 0; k < len(otherwords); k++ {
			otherhashtable[otherwords[k]-97]++
			//fmt.Println(otherhashtable[otherwords[k]-97])
		}
		//fmt.Printf("%s字符串", words[j])
		//fmt.Println()
		//fmt.Println("+++++++++++++++++++++++++++")
		//fmt.Println(otherhashtable)
		// 更新hash，保证hash里统计26个字符在所有字符串里出现的最小次数
		for i := 0; i < 26; i++ {
			hashtable[i] = min(hashtable[i], otherhashtable[i])
		}
	}
	//fmt.Println("=============================")
	//fmt.Println(hashtable)
	// 将hash统计的字符次数，转成输出形式
	for i := 0; i < 26; i++ {
		for hashtable[i] != 0 {
			result = append(result, string(i+97))
			hashtable[i]--
		}
	}
	return result
}
func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}
~~~

## 二维数组

#### 36、有效的数独

题目描述：

请你判断一个 `9 x 9` 的数独是否有效。

> 解题思路：1）判断每行是否出现一次；2）判断每列是否出现一次；3）判断每个box是否出现一次。难点在于如何判断`board[i][j]`是在哪一个box；

~~~go
func isValidSudoku(board [][]byte) bool {
	// 判断是否出现
	var rows, columns [9][9]int
	var boxes [9][9]int
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			rows[i][j] = 0
			columns[i][j] = 0
			boxes[i][j] = 0
		}
	}
	for i, row := range board {
		for j, c := range row {
			if c == '.' {
				continue
			}
			var currNumber = c - '1'
			if rows[i][currNumber] != 0 {
				return false
			}
			if columns[j][currNumber] != 0 {
				return false
			}
			if boxes[j/3+(i/3)*3][currNumber] != 0 {
				return false
			}
			rows[i][currNumber] = 1
			columns[j][currNumber] = 1
			boxes[j/3+(i/3)*3][currNumber] = 1
		}
	}
	return true
}
~~~

#### 48、旋转图像

题目描述：给定一个 *n* × *n* 的二维矩阵 `matrix` 表示一个图像。请你将图像顺时针旋转 90 度。

> 解题思路：利用额外数组

~~~go
func rotate(matrix [][]int) {
	var length = len(matrix)
	tmp := make([][]int, length)
	for i := range tmp {
		tmp[i] = make([]int, length)
	}
	for i, row := range matrix {
		for j, v := range row {
			tmp[j][length-1-i] = v
		}
	}
	copy(matrix, tmp) // 拷贝 tmp 矩阵每行的引用
}
~~~

> 解题思路：利用翻转

~~~go
func rotate(matrix [][]int) {
	var length = len(matrix)
    // 水平翻转
	for i := 0; i < length/2; i++ {
		matrix[i], matrix[length-1-i] = matrix[length-1-i], matrix[i]
	}
    // 对角线翻转
	for i := 0; i < length; i++ {
		for j := 0; j < i; j++ {
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
		}
	}
}
~~~

#### 59.螺旋矩阵

题目描述：

>解题思路1：按层模拟。定义一个返回的二维数组，然后按顺序往里面填充元素

~~~go
func generateMatrix(n int) [][]int {
    result := make([][]int, n)
	for i := range result {
		result[i] = make([]int, n)
	}
    k := 1
    // 设立上下左右边界
    top := 0
    bottom := n - 1
    left := 0
    right := n - 1
    // 没有到达边界的时候
    for k <= n*n {
        // 从左到右
        for i := left; i <= right; i++ {
            result[top][i] = k
            k++
        }
        top++
        // 从上到下
        for i := top; i <= bottom; i++ {
            result[i][right] = k
            k++
        }
        right--
       
        // 从右往左
        for i := right; i >= left; i-- {
            result[bottom][i] = k
            k++
        }
        bottom--
        // 从下到上
        for i := bottom; i >= top; i-- {
            result[i][left] = k
            k++
        }
        left++
        
    }
    fmt.Println(result)
    return result
}
~~~

## day05

### 两数相加

#### 989、数组形式的整数加法

题目描述：整数的 数组形式  num 是按照从左到右的顺序表示其数字的数组。

- 例如，对于 num = 1321 ，数组形式是 [1,3,2,1] 。

给定 num ，整数的 数组形式 ，和整数 k ，返回 整数 num + k 的 数组形式 。

**示例 1：**

```
输入：num = [1,2,0,0], k = 34
输出：[1,2,3,4]
解释：1200 + 34 = 1234
```

> 解题思路：按位模拟相加

~~~go
func addToArrayForm2(num []int, k int) []int {
	var res []int
	// 进位
	carry := 0
	sum := 0
	for i := len(num) - 1; i >= 0 || k > 0 || carry != 0; i-- {
		x := 0
		y := 0
		// 防止出现i小于0，但carry不等于0和k>0的情况报错
		if i >= 0 {
			x = num[i]
		}
		if k > 0 {
			y = k % 10
			k = k / 10
		}
		sum = x + y + carry
		// 得到相加末尾的余数
		result := sum % 10
		// 得到进位
		carry = sum / 10
		res = append(res, result)
	}
	// 逆置
	reverse(res)
	return res
}
func reverse(num []int) {
	for i, n := 0, len(num); i < n/2; i++ {
		num[i], num[n-1-i] = num[n-1-i], num[i]
	}
}
~~~

#### 415、字符串相加

题目描述：给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

> 解题思路：按位模拟相加

~~~go
func addStrings(num1 string, num2 string) string {
	m := len(num1)
	n := len(num2)
	carry := 0 // 进位
	res := ""
	for i, j := m-1, n-1; i >= 0 || j >= 0 || carry != 0; i, j = i-1, j-1 {
		var x, y = 0, 0
		if i >= 0 {
			x = int(num1[i] - '0')
		}
		if j >= 0 {
			y = int(num2[j] - '0')
		}
		tmp := x + y + carry
		carry = tmp / 10
		result := tmp % 10
        res = strconv.Itoa(result) + res
	}
	return res
}
~~~

#### 67、二进制求和

题目描述：

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 **非空** 字符串且只包含数字 `1` 和 `0`。

>解题思路： 按位模拟相加

~~~go
func addBinary(a string, b string) string {
    // 逢二进一
    carry := 0  // 进位
    m := len(a)
    n := len(b)
    res := ""  // 返回的字符数组
    for i,j := m-1, n-1; i >= 0 || j >=0 || carry != 0; i, j = i-1, j-1 {
        x := 0
        y := 0
        tmp := 0
        if i >= 0 {
            x = int(a[i] - '0')
        }
        if j >= 0 {
            y = int(b[j] - '0')
        }
        tmp = x + y + carry
        carry = tmp / 2
        res = strconv.Itoa(tmp%2) + res
    }
    return res
}
~~~

#### 总结

> 前三道相加的题目，都是一个模版，有一个进位表示变量，从后向前遍历数组，不管是整数数组还是字符数组，在不为空的情况下进行相加，用一个sum变量表示相加的结果，用sum%10表示当次存储的结果，sum/10表示进位的大小，然后再将每次循环的结果连起来，得到结果。

### 2、剑指offer.求1+2+3+...+n

题目描述：求 `1+2+...+n` ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

>解题思路：逻辑运算符的短路性质，例如：&&。对于A && B这个表达式，如果 A 表达式返回false，那么A  && B确定为False，此时不会去执行表达式 B，同理，对于逻辑运算符||，对于 A || B这个表达式，如果A 表达式返回True，那么A || B 已经确定为True，此时不会再执行表达式B。
>
>利用短路性质，将递归的出口看作 A && B 表达式中的A部分，递归的主体函数看作 B 部分。如果不是递归出口，则返回 True，并继续执行 B 的部分，否则递归结束。

~~~go
func sumNums(n int) int {
    ans := 0
    var sum func(int) bool
    sum = func(n int) bool {
        ans += n
        return n > 0 && sum(n-1)
    }
    sum(n)
    return ans
}
~~~

### 66、加一

题目描述：

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

>解题思路：加一只存在两种情况：1）除9之外的数字加一；2）数字9。加一得十进一位，个位数为0，加法运算如不出现进位就算运算结束，进位也只可能是一。
>
>只需要循环判断有没有进位，直到没有进位后退出循环返回结果。
>
>特殊情况类似于99，999之类的数字，循环到最后也需要进位，此时需要手动进位，申请多之前多一位的数组长度，首元素赋值为1.

~~~go
func plusOne(digits []int) []int {
	n := len(digits)
	for i := n - 1; i >= 0; i-- {
		digits[i]++
		digits[i] = digits[i] % 10
		// 加1不为0或者进位不为0返回结果
		if digits[i] != 0 {
			return digits
		}
	}
	// 特殊情况，99，999之类的
	digits = make([]int, n+1)
	digits[0] = 1
	return digits
}
~~~

### 43、字符串相乘

题目描述：

给定两个以字符串形式表示的非负整数 `num1` 和 `num2`，返回 `num1` 和 `num2` 的乘积，它们的乘积也表示为字符串形式。

>方法一：字符串相加

~~~go
func multiply(num1 string, num2 string) string {
	if num1 == "0" || num2 == "0" {
		return "0"
	}
	// num1是被乘数，num2是乘数
	m := len(num1)
	n := len(num2)
	ans := "0"
	// 乘数的每一位都与被乘数相乘
	for i := n - 1; i >= 0; i-- {
		// 进位
		carry := 0
		currAns := ""
		// 对当前位补0
		for j := n - 1; j > i; j-- {
			currAns += "0"
		}
		x := int(num2[i] - '0')
		// 与被乘数相乘
		for j := m - 1; j >= 0; j-- {
			y := int(num1[j] - '0')
			product := x*y + carry
			result := product % 10
			carry = product / 10
			currAns = strconv.Itoa(result) + currAns
		}
		for ; carry != 0; carry /= 10 {
			currAns = strconv.Itoa(carry%10) + currAns
		}
		ans = addStrings(ans, currAns)
	}
	return ans
}
// 字符串相加
func addStrings(num1 string, num2 string) string {
	m := len(num1)
	n := len(num2)
	carry := 0 // 进位
	res := ""
	for i, j := m-1, n-1; i >= 0 || j >= 0 || carry != 0; i, j = i-1, j-1 {
		var x, y = 0, 0
		if i >= 0 {
			x = int(num1[i] - '0')
		}
		if j >= 0 {
			y = int(num2[j] - '0')
		}
		tmp := x + y + carry
		carry = tmp / 10
		result := tmp % 10
		res = strconv.Itoa(result) + res
	}
	return res
}

~~~

时间复杂度：O（m*n）,因为有很多字符串拼接的过程，所以时间效率不高。

>方法二：乘法规律。两个数相乘，最后的结果长度小于两个数的长度之和；第 i 位和第 j 位相乘，结果应该是 i + j + 1， 进位是 i + j；

~~~go
func multiply(num1 string, num2 string) string {
	if num1 == "0" || num2 == "0" {
		return "0"
	}
	m := len(num1)
	n := len(num2)
	ans := ""
	var res = make([]int, m + n)
	for i := m - 1; i >= 0; i-- {
		x := int(num1[i] - '0')
		for j := n - 1; j >= 0; j-- {
			y := int(num2[j] - '0')
			sum := res[i+j+1] + x*y
			res[i+j+1] = sum % 10
            // 进位的位置
			res[i+j] += sum / 10
		}
	}
	// 对结果的处理
	for i := 0; i < len(res); i++ {
		if i == 0 && res[i] == 0 {
			continue
		}
		ans += strconv.Itoa(res[i])
	}
	return ans
}
~~~

### 7、整数反转

题目描述：

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。

**假设环境不允许存储 64 位整数（有符号或无符号）。**

>方法一：取余，分别将取余的结果存入到字符数组中，再转化为int。
>
>具体：分为大于0和小于0的情况，小于0的情况需要返回的时候注意一下。

~~~go
// 取余
func reverse(x int) int {
	var res = ""
	if x == 0 || x == 1 {
		return x
	}
	if x > 0 {
		for x != 0 {
			result := x % 10
			x /= 10
			res += strconv.Itoa(result)
		}
		i, _ := strconv.Atoi(res)
		if i > math.MaxInt32 {
			return 0
		}
		return i
	} else {
		x = -x
		for x != 0 {
			result := x % 10
			x /= 10
			res += strconv.Itoa(result)
		}
		i, _ := strconv.Atoi(res)
		if -i < math.MinInt32 {
			return 0
		} else {
			return -i
		}
	}
}
~~~

>方法二：取余优化，不在拼接字符串，且需要在最大整数的前一位判断是否溢出。

~~~go
func reverse2(x int) int {
	res := 0
	for x != 0 {
		tmp := x % 10
		// 判断溢出
		if res > math.MaxInt32/10 || res < math.MinInt32/10 {
			return 0
		}
		res = res*10 + tmp
		x /= 10
	}
	return res
}
~~~

### 9、回文数

题目描述：

给你一个整数 `x` ，如果 `x` 是一个回文整数，返回 `true` ；否则，返回 `false` 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

>解题思路：
>
>

~~~go
~~~



### 8、字符串转换整数

题目描述：



## day06

### 29、两数相除

题目描述：

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

>解题思路一：将除法转化为减法问题。

~~~go
func divide2(dividend int, divisor int) int {
	// abs(math.MinInt32) = math.MinInt32 = -2147483648
	if dividend == math.MinInt32 && divisor == -1 {
		return math.MaxInt32
	}
	res := 0
	sign := 1
	if (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0) {
		sign = -1
	}
	dividend = abs(dividend)
	divisor = abs(divisor)
	for dividend >= divisor {
		dividend -= divisor
		res++
	}
	return sign * res
}
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
// 时间复杂度是O(n)，n 是最大值2147483648  --》 10 ^ 10，会超时。
~~~

>解题思路：对解法一优化，解法一中是一个个的减去除数，但是我们可以成倍的减去除数。
>
>越界问题只要对除数是 1 和 -1 单独讨论。
>
>以11除以3为例。11除以3，结果是大于1的，将结果翻倍得到2，再将3翻倍得到6；11除以6得到结果还是大于1，将结果翻倍得到4，再将6翻倍；此时11除以12是小于1的，意味着结果肯定是在2与4之间，将11减去6得到5，再用5除以3，得到大于1的结果，形成了一个递归，递归结束是最后除以3是小于1的；

~~~go
func divide(dividend int, divisor int) int {
	res := 0
	if dividend == 0 {
		return 0
	}
	if divisor == 1 {
		return dividend
	}
	sign := 1
	if (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0) {
		sign = -1
	}
	if dividend < 0 {
		dividend = -dividend
	}
	if divisor < 0 {
		divisor = -divisor
	}
	res = div(dividend, divisor)
	if sign > 0 {
		if res > math.MaxInt32 {
			return math.MaxInt32
		} else {
			return res
		}
	}
	return -res
}

func div(a int, b int) int {
	if a < b {
		return 0
	}
	count := 1
	var tb = b
	for tb+tb <= a {
		count += count
		tb = tb + tb
	}
	return count + div(a-tb, b)
}
~~~

~~~go
// 边界问题处理和对减法代替除法思想的优化：之前减法是一个个的减，现在是成倍的减去，例如减3，减3+3，减6+6，减12+12...
// 时间复杂度是O(logn * logn)，
func divide3(dividend int, divisor int) int {
	// abs(math.MinInt32) = math.MinInt32 = -2147483648
	if dividend == math.MinInt32 && divisor == -1 {
		return math.MaxInt32
	}
	sign := 1
	if (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0) {
		sign = -1
	}
	// 防止32位最小整数做绝对值之后溢出，故全转为负数；10 / 3 == (-10) / (-3)
	if dividend > 0 {
		dividend = -dividend
	}
	if divisor > 0 {
		divisor = -divisor
	}
	res := 0
	for dividend <= divisor {
		value := divisor
		k := 1
		// 0xc0000000是最小整数的一半
		for (value >= 0xc0000000) && (dividend <= value+value) {
			value += value
			k += k
		}
		dividend -= value
		res += k
	}
	return sign * res
}
~~~

> 方法三：位运算。

~~~go
// 再优化：位移操作。从31位一直到0，此时时间复杂度为O(31),也就是O(1)，难点在于如何处理边界，divisor为最小整数时
func divide4(dividend int, divisor int) int {
	// abs(math.MinInt32) = math.MinInt32 = -2147483648
	if dividend == math.MinInt32 && divisor == -1 {
		return math.MaxInt32
	}
	sign := 1
	if (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0) {
		sign = -1
	}
	res := 0
	dividend = abs(dividend)
	divisor = abs(divisor)
	for i := 31; i >= 0; i-- {
		// 首先右移是为了确保不越界，因为如果是 divisor左移很可能会造成越界
		// 其次无符号右移是为了将最小整数 -2147483648 当作 2147483648
		a := uint32(dividend) >> i
		// 这里为什么是 a - divisor >= 0 而不是 a >= divisor，是因为如果 divisor = 2147483648，那么 a >= divisor
		//永远是true，但是 a-divisor >= 0 为 false ;
		if int(a)-divisor >= 0 {
			dividend -= divisor << i
			res += 1 << i
		}
	}
	return sign * res
}

~~~

### 136、只出现一次的数

题目描述：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

> 解题思路：利用题目信息，只有一个元素只出现1次，其余均出现2次，利用异或运算满足交换律和结合律的性质，两个相同数异或是0，任何数与0异或是本身，那么只有1个数出现1次，其余都是出现2次的情况下，异或最后的结果是那个只出现一次的数。

~~~go
func singleNumber2(nums []int) int {
	single := 0
	for _, x := range nums {
		single ^= x
	}
	return single
}
~~~

### 260、只出现一次的数字|||

题目描述：

给定一个整数数组 `nums`，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 **任意顺序** 返回答案。

>方法一：利用额外空间

~~~go
func singleNumber(nums []int) []int {
	var res []int
	freq := map[int]int{}
	for _, x := range nums {
		freq[x]++
	}
	for num, count := range freq {
		if count == 1 {
			res = append(res, num)
		}
	}
	return res
}
~~~

> 方法二：利用位运算将数组分为两类，只出现1次的两个元素恰好分别属于不同的类中，对两个类中的元素进行异或运算，分别得到的就是只出现1次的元素。
>
> 异或运算的性质：1）如果异或结果的某一位为1，说明进行异或运算的两个数在这一位肯定是不相同的。比如：3 ^ 5，011 ^ 101 = 110。

~~~go
func singleNumber(nums []int) []int {
	res := 0
	// 得到两个只出现一次元素的异或值
	for _, num := range nums {
		res = res ^ num
	}
	// 取得异或值的最后一位1。异或值的某一位为1，代表着这两个数在这一位不一样
	mask := res & (-res)
	// 分组
	ans := make([]int, 2)
	for _, num := range nums {
		if (num & mask) != 0 {
			ans[0] ^= num
		} else {
			ans[1] ^= num
		}
	}
	return ans
}
~~~

### 477、汉明距离总和

题目描述：

两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。

给你一个整数数组 nums，请你计算并返回 nums 中任意两个数之间 汉明距离的总和 。

> 方法一：暴力解法。

~~~go
func totalHammingDistance(nums []int) int {
	ans := 0
	// 超时
	for i := 0; i < len(nums)-1; i++ {
		for j := i + 1; j < len(nums); j++ {
			ans += hammingDistance(nums[i], nums[j])
		}
	}
	return ans
}

// 两个整数之间的汉明距离
func hammingDistance(a int, b int) int {
	ans := 0
	// 异或运算：相同为0，不相同为1。将异或后的结果每一位和 1 进行与运算，得到不相同的个数
	// 遍历检查 x ^ y的最低位，如果最低位是1，那么结果+1，然后令s整体右移一位，最低位被舍去，直到 s = 0 为止；
	for s := a ^ b; s > 0; s >>= 1 {
		ans += s & 1
	}
	return ans
}
~~~

> 方法二：位运算。汉明距离是两数二进制表示中不同位的个数，同时每位的统计是互相独立的。
>
> 对于某一个nums[i]，我们只关心在nums中有多少个数的第 x 位与其不同，不关心具体是哪些数与其不同，所以可以用1个集合统计出nums中所有数的第x位中0的个数，另外一个集合统计第 x 位中 1 的个数，那么对于nums[i]来说，它的汉明距离就是两个集合的数相乘。

~~~go
func totalHammingDistance2(nums []int) int {
	ans := 0
	tmp := make([]int, 2)
	for i := 31; i >= 0; i-- {
		tmp[0] = 0
		tmp[1] = 0
		for _, x := range nums {
			// 取得第i位的值
			if ((x >> i) & 1) == 0 {
				tmp[0]++
			} else {
				tmp[1]++
			}
		}
		ans += tmp[0] * tmp[1]
	}
	return ans
}


~~~



## day07

### 排序算法回顾

1、时间复杂度为O(n^2)：冒泡排序、选择排序、插入排序；  时间复杂度为O(n^3/2)：希尔排序

- 1）插入排序性能最好、其次是选择排序、冒泡排序性能最差；
- 2）选择排序不是稳定的排序算法；
- 3）插入排序是最好的选择；

2、时间复杂度O(nlogn)：归并排序、快速排序

- 1）快速排序复杂度最坏情况下是O(n^2)，所以合理选择分区点；
- 2）归并排序在任何情况下的时间复杂度都是O(nlogn)；
- 3）归并排序的空间复杂度是O(n)，快速空间复杂度是O(logn)；
- 4）快速排序是不稳定的，归并是稳定的；

3、时间复杂度O(n)：桶排序、计数排序、基数排序

- 桶排序：桶与桶之间有序、元素均匀的划分到桶中；
- 计数排序：应用在数据范围不大的场景；
- 基数排序：排序数据可以分割出独立的 “位” ，而且每一位的数据范围不能太大；

#### 分治算法思想

### 75、颜色分类

题目描述：给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

>解题思路：

~~~go
func sortColors(nums []int)  {
	count := make([]int, 3)
	for _, x := range nums {
		if x == 0 {
			count[0]++
		} else if x == 1 {
			count[1]++
		} else {
			count[2]++
		}
	}
	k := 0
	for count[0] != 0 {
		nums[k] = 0
		count[0]--
		k++
	}
	for count[1] != 0 {
		nums[k] = 1
		count[1]--
		k++
	}
	for count[2] != 0 {
		nums[k] = 2
		count[2]--
		k++
	}
}
~~~

### 164、最大间距

题目描述：给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。

您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-gap
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

>思想：基数排序

~~~go
func maximumGap2(nums []int) int {
	radixSort(nums)
	maxDiff := 0
	for i := 1; i < len(nums); i++ {
		tmpDiff := nums[i]-nums[i-1]
		if tmpDiff > maxDiff {
			maxDiff = tmpDiff
		}
	}
	return maxDiff
}
~~~

## day08



## day09



## day10

### 单调栈

单调栈是指栈中的元素必须按照升序排列或者降序排列的栈；

#### 单调栈应用

> 1、找出数组中右边第一个比我小的元素

~~~go
/*
   题目：找出数组中右边第一个比我小的元素
   一个整数数组 nums，找到每个元素：右边第一个比我小的下标位置，没有则用 -1 表示。
   输入：[5, 2]
   输出：[1, -1]

   解释：
       因为元素 5 的右边离我最近且比我小的位置应该是 nums[1]，
       最后一个元素 2 右边没有比 2 小的元素，所以应该输出 -1。
*/

func findFirstRightSmaller(nums []int) []int {
	n := len(nums)
	// 结果数组
	ans := make([]int, n)
	// 栈，存储的是下标（索引）
	var stack []int
	for i := 0; i < n; i++ {
		x := nums[i]
		// 如果栈不为空，且遍历的元素小于栈顶的元素，说明找到了右边第一个小于栈顶元素的值，此时需要更新ans；
		// 此栈为单调递增栈
		// 拿到栈顶元素，也就是索引值
		for len(stack) > 0 && x < nums[stack[len(stack)-1]] {
			// 更新ans
			ans[stack[len(stack)-1]] = i
			// 出栈
			stack = stack[:len(stack)-1]
		}
		// 不管怎样，都需要先压栈，将当前遍历的下标入栈
		stack = append(stack, i)
	}
	// 如果遍历结束但是栈不为空，说明不存在右边第一个小于的元素，此时将栈顶元素在ans中置为-1
	for len(stack) > 0 {
		// 更新ans
		ans[stack[len(stack)-1]] = -1
		// 出栈
		stack = stack[:len(stack)-1]
	}
	return ans
}

~~~

![image-20221009113800523](/Users/dzy/Library/Application Support/typora-user-images/image-20221009113800523.png)

> 2、找出数组中左边第一个比我小的元素

~~~go
/**
* @Description:
   题目：找出数组中左边离我最近比我小的元素
   一个整数数组 nums，找到每个元素：左边第一个比我小的下标位置，没有则用 -1 表示。
   输入：[1, 2]
   输出：[-1, 0]

   解释：
       因为元素 2 的左边离我最近且比我小的位置应该是 nums[0]，
       第一个元素 1 左边没有比 1 小的元素，所以应该输出 -1。
* @param nums
* @return []int
**/
func findLeftLastSmaller(nums []int) []int {
	var stack []int
	var ans = make([]int, len(nums))
	for i := len(nums) - 1; i >= 0; i-- {
		for len(stack) > 0 && nums[i] < nums[stack[len(stack)-1]] {
			ans[stack[len(stack)-1]] = i
			stack = stack[:len(stack)-1]
		}
		// 入栈
		stack = append(stack, i)
	}
	for len(stack) > 0 {
		// 更新ans
		ans[stack[len(stack)-1]] = -1
		// 出栈
		stack = stack[:len(stack)-1]
	}
	return ans
}
~~~



# 链表

## 单链表的基本操作

### 单链表初始化

~~~go
// 定义单链表结构体
type Node struct {
    data int  // 数据域
	next *Node  // 指针域，指向下一个节点
}
type List struct {
	length   int //储存链表的长度
	headNode *Node
}
/*单链表的初始化
1、生成新结点作为头结点，用头指针指向头结点
2、头结点的指针域置空
*/
func InitList() *List {
	//即构造一个空的单链表L(包含头指针)
	node := new(Node)
	L := new(List)
	L.headNode = node
	return L
}


~~~

### 头插法

~~~go
func (list *List) AddElemFromHead(v int) {
	node := &Node{data: v}
	if list.IsNull() {  // 处理空表的插入，否则会导致一个空的头结点后移
		list.headNode = node
		list.length++
		return
	}
	node.next = list.headNode
	list.headNode = node
	list.length++
	return
}
~~~

### 尾插法

~~~go
func (list *List) AddElemFromTail(v int) {
	node := &Node{data: v}  // 新建一个数据域为v的Node节点
	p := list.headNode
	if list.IsNull() {  // 如果此时是空链表，即只有一个空的头节点，直接让头节点的指针指向要插入的节点
		p.next = node
	} else {
		for p.next != nil {
			p = p.next
		}
	}
	p.next = node   // 让最后一个节点的指针指向将要插入的元素
	node.next = nil // 将插入的元素指针域置为空
	list.length++
}
~~~

### 删除指定位置的元素

~~~go
func (list * List) DeleteElemIndex(i int) {
	p := list.headNode
	if i <= 0 || i > list.length {  // i=0表示头节点
		fmt.Println("删除位置不合法")
	} else if i == 1 {  // 删除第一个节点
		list.headNode = p.next
	} else {
		for j := 1; j < i-1; j++ {  // 找到删除位置的前一个位置
			p = p.next
		}
		p.next = p.next.next
	}
	list.length--
}
~~~

### 删除指定值

~~~go
func (list *List) DeleteElem(v int) {
	p := list.headNode
	if p.data == v {
		list.headNode = p.next
		fmt.Println("ok")
	} else {
		for p.next != nil { //
			if p.next.data == v {
				p.next = p.next.next
				return
			}
		}
	}
	return
}
~~~

### 查找是否包含指定值

~~~go
func (list *List)havaElem(v int)  bool {
	p := list.headNode
	for p != nil {  // current node not nil
		if p.data == v {
			return true
		}
		p = p.next
	}
	return false
}
~~~

### 查找指定位置元素的值

~~~go
func (list *List)havaIndexElem(index int) int {
	p := list.headNode  // 初始值为头节点
	if index <= 0 || index > list.length {
		fmt.Print("输入的值违法")
		return 0
	}
	for j := 1; j < index; j++ {
		p = p.next
	}
	return p.data
}
~~~

### 遍历链表所有结点

~~~go
func (list *List) getAllElem()  {
	if !list.IsNull() {
		p := list.headNode
		for p != nil {
			fmt.Println(p.data)
			p = p.next
		}
	}
	return
}
~~~

## 移除元素

### 230.链表移除元素

题目来源：https://leetcode-cn.com/problems/remove-linked-list-elements/

~~~go
// 方式一：在原链表上进行删除
func removeElements(head *ListNode, val int) *ListNode {
	// 如果要移除的节点是头节点
	for head != nil && head.Val == val {
		head = head.Next
	}
	if head == nil {
		return nil
	}
	p := head
	for p.Next != nil {
		if p.Next.Val == val {
			p.Next = p.Next.Next
		} else {
			p = p.Next
		}
	}
	return head
}
// 方式二：构造虚拟节点
func removeElements2(head *ListNode, val int) *ListNode {
	pVir := &ListNode{}  // 创建一个虚拟节点
	pVir.Next = head
	pIndex := pVir  // 遍历指针
	for pIndex != nil && pIndex.Next != nil {  // 当前节点不为空且有下一个节点
		if pIndex.Next.Val == val {
			pIndex.Next = pIndex.Next.Next
		} else {
			pIndex = pIndex.Next
		}
	}
	return pVir.Next
}
~~~

## 翻转链表

题目来源：https://leetcode-cn.com/problems/reverse-linked-list/

题目描述：给你单链表的头节点 `head` ，请你反转链表，并返回反转后的链表。

**示例 1：**

![img](https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg)

>解题思路：

~~~go
func reverseList(head *ListNode) *ListNode {
	// 利用双指针进行指针逆向
	var prev *ListNode = nil
	curr := head
	// 保存当前节点的下一个指针
	var tempNext *ListNode = nil
	for curr != nil {  // 当前节点不为空
		tempNext = curr.Next  // 将下个节点先保存
		curr.Next = prev  // 指针逆向
		prev = curr  // prev指针后移
		curr = tempNext  // curr指针后移
	}
	return prev
}
~~~



~~~go
// 递归实现
func reverseList2(head *ListNode) *ListNode {
	// 递归结束条件:如果只有0个节点或者1个节点
	if head == nil || head.Next == nil {
		return head
	}
	// 递归的递过程
	p := reverseList2(head.Next)
	// 归过程
	head.Next.Next = head
	head.Next = nil
	return p
}
~~~



## 两两交换链表中的节点

题目来源：https://leetcode-cn.com/problems/swap-nodes-in-pairs/

题目描述：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

**示例 1：**

![img](https://assets.leetcode.com/uploads/2020/10/03/swap_ex1.jpg)

> 解题思路：

~~~go
func swapPairs(head *common.ListNode) *common.ListNode {
	// 先创建一个虚拟节点
	virnode := &common.ListNode{}
	virnode.Next = head  // 将虚拟节点指向头节点
	curr := virnode
	for curr.Next != nil && curr.Next.Next != nil {

		temp1 := curr.Next  // 临时保存节点
		temp2 := curr.Next.Next.Next  // 临时保存节点

		// 步骤
		curr.Next = curr.Next.Next
		curr.Next.Next = temp1
		curr.Next.Next.Next = temp2

		curr = curr.Next.Next

	}
	return virnode.Next
}
~~~



## 删除链表倒数的第K个节点

题目来源：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

题目描述：

给你一个链表，删除链表的倒数第 `n` 个结点，并且返回链表的头结点。

**示例 1：**

![img](https://assets.leetcode.com/uploads/2020/10/03/remove_ex1.jpg)

> 方法一：双指针

~~~go
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	// 构造虚拟节点，保持删除的一致性
	virhead := &ListNode{}
	virhead.Next = head
	// 删除第N个节点，可以设立双指针i和j，j与i指向的节点相差N个节点，直到j遍历到链表末尾，
	// 此时要删除的节点就是i指向节点的下一个节点
	i := virhead
	j := head
	count := 0
	for count < n {
		j = j.Next
		count++
	}
	for j != nil {
		i = i.Next
		j = j.Next
	}
	// 删除
	i.Next = i.Next.Next
	return virhead.Next
}
~~~

> 方式二：计算链表长度

~~~go
func removeNthFromEnd2(head *ListNode, n int) *ListNode {
	// 构造虚拟节点，保持删除的一致性
	virhead := &ListNode{}
	virhead.Next = head
	p := head
	lenght := 0
	for p != nil {
		lenght++
		p = p.Next
	}
	count := 0
	for p = virhead; p.Next != nil;  {
		if count < lenght - n {
			p = p.Next
			count++
		} else {
			break
		}
	}
	p.Next = p.Next.Next
	return virhead.Next
}
~~~

## 环形链表||

题目来源：https://leetcode-cn.com/problems/linked-list-cycle-ii/

题目描述：给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

![img](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png)

> 方式一：利用hash表

利用hash表，遍历的时候判断hash表中是不是出现过，出现过则返回；

~~~go
func detectCycle(head *ListNode) *ListNode {
	tempMap := make(map[*ListNode]int)
	p := head
	for p != nil {
		if _, ok := tempMap[p]; ok {
			return p
		}
		tempMap[p] = 1
		p = p.Next
	}
	return nil
}
~~~

> 方式二：快慢指针

有快慢指针fast、slow，在后面的遍历中，快指针fast每次走两步，慢指针每次走一步，若是链表中存在环的话，则快指针肯定会追上慢指针。

为何慢指针第一圈走不完一定会和快指针相遇? 可以认为快指针和慢指针是相对运动的，假设慢指针的速度是 1节点/秒，快指针的速度是 2节点/秒，当以慢指针为参考系的话（即慢指针静止），快指针的移动速度就是 1节点/秒，所以肯定会相遇。

为什么在第一圈就会相遇呢？ 设环的长度为 L，当慢指针刚进入环时，慢指针需要走 L 步(即 L 秒)才能走完一圈，此时快指针距离慢指针的最大距离为 L-1，我们再次以慢指针为参考系，如上所说，快指针在按照1节点/秒的速度在追赶慢指针，所以肯定能在 L 秒内追赶到慢指针。

![fig1](https://assets.leetcode-cn.com/solution-static/142/142_fig1.png)

设从链表头部到入环处的距离为a，*slow* 指针进入环后，又走了 b 的距离与 fast 相遇，则此时 fast 指针已经在环中走了 n 圈，fast 指针走的距离总共为 a + （b+c）n + b，slow指针走的距离为：a+b，而fast指针的距离始终是slow指针的两倍，故 a + （b+c）n + b = 2（a+b），也就是：a = （n-1）（b+c） + c。当发现
slow与fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow每次向后移动一个位置。最终，它们会在入环点相遇。

~~~go
func detectCycle(head *ListNode) *ListNode {
	fast, slow := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {  // 快慢指针相遇
			for slow != head {  // a = (n-1)(b+c) + c
				slow = slow.Next
				head = head.Next
			}
			return  head
		}
	}
	return nil
}
~~~

# 双指针法

## 同向指针

### 27、移除元素

给你一个数组 `nums` 和一个值 `val`，你需要 **[原地](https://baike.baidu.com/item/原地算法)** 移除所有数值等于 `val` 的元素，并返回移除后数组的新长度。

>解题思路：原地移除等于val的元素，只需要在遍历的时候判断是否等于val，等于的话就不管，不想等就保存起来；

~~~go
func removeElement(nums []int, val int) int {
    i := 0  // 保存不等于val的元素下标/个数
    for j := 0; j < len(nums); j++ {
        if nums[j] != val {
            nums[i] = nums[j]
            i++
        }
    }
    return i
}
~~~

### 26.移除重复元素

给你一个 **升序排列** 的数组 `nums` ，请你**[ 原地](http://baike.baidu.com/item/原地算法)** 删除重复出现的元素，使每个元素 **只出现一次** ，返回删除后数组的新长度。元素的 **相对顺序** 应该保持 **一致** 。

>解题思路：
>
>1、设立遍历数组指针 j ；不重复元素指针 i ；
>
>2、遍历数组，若是前一个数不等于后一个数相等，则将元素赋值给 i 指向的空间，反之不处理；
>
>3、最后前 i 个元素是不重复的数字；

~~~go
func removeDuplicates(nums []int) int {
    i := 0
    j := 1
    for ;j < len(nums);j++ {
        if nums[j-1] != nums[j] {
            i++
            nums[i] = nums[j]
        }
    }
    return i+1
}
~~~

### 80.移除重复元素||

给你一个有序数组 `nums` ，请你**[ 原地](http://baike.baidu.com/item/原地算法)** 删除重复出现的元素，使每个元素 **最多出现两次** ，返回删除后数组的新长度。

> 解题思路：
>
> 1、将整个数组分为有效数和待定数，待定数需要判断是否是有效数；
>
> 2、先将数组前两个数加入有效数，i 指针
>
> 3、从两个数之后遍历数组，对待定数与前两个数做判断是否相等，不相等则放入有效数中，相反不处理 j++；

~~~go
/**
* @Description:给定一个有序数组，原地删除元素，使每个元素最多出现2次
* @param nums
* @return int
**/
func removeDuplicates(nums []int) int {
	// k表示每个元素需要出现的次数
	var process func(k int) int
	process = func(k int) int {
		i := 0
		for _, x := range nums {
			// i < k：表示如果是前两个数，直接默认为有效值
			if i < k || nums[i-k] != x {
				nums[i] = x
				i++
			}
		}
		return i
	}
	return process(2)
}

~~~

### 26和80题目总结

> 26和80是同一类的题目，可以总结为保存出现 k 次的元素；
>
> 1、将整个数组分为有效数和待定数，待定数需要判断是否是有效数；
>
> 2、将前 k 个元素放入有效数中；
>
> 3、对于k个元素之后的数组元素，进行遍历，若是与前k个元素不等于，则放入有效数中，反之不处理；

### 283.移动零

给定一个数组 `nums`，编写一个函数将所有 `0` 移动到数组的末尾，同时保持非零元素的相对顺序。

> 解题思路：设立循环遍历指针 i 和不等于0的元素指针 j，在遍历数组的时候，只要发现不等于0的元素都赋值到下标 j 指向的空间，然后 j++；遍历完成之后，将 [j,length-1]全部置为0；

~~~go
func moveZeroes(nums []int) {
	i := 0 // 循环遍历指针
	j := 0 // 不等于0元素指针
	for ; i < len(nums); i++ {
		if nums[i] != 0 {
			nums[j] = nums[i]
			j++
		}
	}
	fmt.Println(j)
	for k := j; k < len(nums); k++ {
		nums[k] = 0
	}
	fmt.Println(nums)
}

~~~

### 总结

>这四道题都是同向双指针，一个循环遍历指针 i ，一个保存留下来元素的指针 j ；遍历数组，根据需要留下来的条件进行判断，符合条件就保存，至此前 j 个元素都是符合要求的；

## 对撞指针

### 11.盛水最多的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

>解题思路：对撞指针。
>
>1、盛水的容量等于（j - i）* min（height[i],height[j]），容量的初始值先设为0，i = 0，j = length - 1， 因为这个时候 j - i 是最大的。
>
>2、遍历数组，将当次遍历的结果与max比较，若是这次结果较大，则max更新，然后从height小的那一边继续遍历；
>
>3、若是当前遍历结果小于max，则还是从height小的那一边继续遍历；
>
>4、直到 i == j，退出循环；

~~~go
func maxArea(height []int) int {
    i := 0
    j := len(height)-1
    max := 0
    for ;i < j; {
        temp := (j - i) * min(height[i],height[j])
        if temp > max {
            max = temp  // 是新的max
            if height[i] > height[j] {
                j--
            } else {
                i++
            }
        } else {
            if height[i] > height[j] {
                j--
            } else {
                i++
            }
        }
    }
    return max
}
func min(x int, y int) int {
    if x > y {
        return y
    }
    return x
}
~~~

### 125.验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

>解题思路：对撞指针。
>
>1、两个指针，一个头指针，一个尾指针，判断这两个指针指向的元素是否相等，相等则继续往中间走，反之则肯定不是回文串；

~~~go
/**对撞指针
* @Description:给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
* @param s
* @return bool
**/
func isPalindrome(s string) bool {
	s = strings.ToLower(s) // 变成小写
	// fmt.Println(s)
	i := 0
	j := len(s) - 1
	for i < j {
		// 跳过空格
		for i < j && !isAlNum(s[i]) {
			i++
		}
		for i < j && !isAlNum(s[j]) {
			j--
		}
		// 判断是否相等
		if s[i] != s[j] {
			return false
		} else {
			i++
			j--
		}
	}
	return true
}
// 只包括字母和数字
func isAlNum(ch byte) bool {
	return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9')
}
~~~

### 344、反转字符串

题目来源：https://leetcode.cn/problems/reverse-string/

题目描述：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

>解题思路：双指针

设立 i，j 指针，i 指向字符数组首元素，j 指向字符数组数组末尾元素，当 i < j 时，执行循环：

- 交换 s[i] 和 s[j]；
- 然后 i++，j--；

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

### 对撞指针总结

>对撞指针是指一个指针在数组开头，一个指针在数组末尾，然后慢慢逼近中间，直到两个指针相遇，则退出循环。

# 动态规划

## 基本思想

动态规划的核心就是记住已经解决过的子问题的解。

动态规划算法的两种形式：

（1）自顶向下；

（2）自底向上；

### 自顶向下的备忘录法

备忘录法就是利用空间保存之前计算过的值。

~~~java
public static int Fibonacci(int n)
{
		if(n<=0)
			return n;
		int []Memo=new int[n+1];		
		for(int i=0;i<=n;i++)
			Memo[i]=-1;
		return fib(n, Memo);
	}
	public static int fib(int n,int []Memo)
	{
		
		if(Memo[n]!=-1)
			return Memo[n];
	//如果已经求出了fib（n）的值直接返回，否则将求出的值保存在Memo备忘录中。				
		if(n<=2)
			Memo[n]=1;
		
		else Memo[n]=fib( n-1,Memo)+fib(n-2,Memo);	
		
		return Memo[n];
	}

~~~

### 自底向上的动态规划

先计算子问题，再由子问题计算父问题。

~~~java
public static int fib(int n)
{
		if(n<=0)
			return n;
		int []Memo=new int[n+1];
		Memo[0]=0;
		Memo[1]=1;
		for(int i=2;i<=n;i++)
		{
			Memo[i]=Memo[i-1]+Memo[i-2];
		}		
		return Memo[n];
}

~~~

~~~java
public static int fib(int n)
	{
		if(n<=1)
			return n;
		
		int Memo_i_2=0;
		int Memo_i_1=1;
		int Memo_i=1;
		for(int i=2;i<=n;i++)
		{
			Memo_i=Memo_i_2+Memo_i_1;
			Memo_i_2=Memo_i_1;
			Memo_i_1=Memo_i;
		}		
		return Memo_i;
	}
~~~

## 案例