栈、队列、优先队列、双端队列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func isValid(s string) bool {
	cache := map[int]int{
		')': '(',
		'}': '{',
		']': '[',
	}
	var array []int
	for _, right := range s {
		if len(array) == 0 {
			array = append(array, int(right))
			continue
		}
		left, ok := cache[int(right)]
		if !ok {
			array = append(array, int(right))
		} else {
			if array[len(array)-1] != left {
				return false
			}
			array = array[:len(array)-1]
		}
	}
	return len(array) == 0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func largestRectangleArea(heights []int) int {
	var area int
	stack := make([]int, 0)
	stack = append(stack, -1)
	// 预防特殊情况，无法触发计算 ，如：[2, 4]
	heights = append(heights, 0)
	for right := 0; right < len(heights); right++ {
		for len(stack) > 1 && heights[stack[len(stack)-1]] > heights[right] {
			// 当前需要计算的height的index
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			// 左下标
			left := stack[len(stack)-1]
			area = maxArea(area, (right-left-1)*heights[top])
		}
		stack = append(stack, right)
	}
	return area
}

func maxArea(x, y int) int {
	if x > y {
		return x
	}
	return y
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func maxSlidingWindow(nums []int, k int) []int {
	if nums == nil {
		return []int{}
	}
	window, res := []int{}, []int{}
	for index, value := range nums {
		// 判断滑动窗口中已保存的最大下标和当前循环到的小标是否大于k，如果大于k需要滑动删除最左
		if index >= k && window[0] <= index-k {
			window = window[1:]
		}
		for len(window) > 0 && nums[window[len(window)-1]] <= value {
			window = window[:len(window)-1]
		}
		window = append(window, index)
		if index >= k-1 {
			res = append(res, nums[window[0]])
		}
	}
	return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func removeDuplicates(nums []int) int {
	if len(nums) <= 1 {
		return len(nums)
	}
	// 快、慢下标
	slow, fast := 0, 1
	for fast < len(nums) {
		// 如果slow 和 fast不相等，那么slow下个元素赋值fast，不然是相等的，那么fast继续前进
		if nums[slow] != nums[fast] {
			slow++
			nums[slow] = nums[fast]
		}
		fast++
	}
	return slow + 1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func rotate(nums []int, k int) {
	if len(nums) == 0 || k == 0 {
		return
	}
	// 防止k大于len(nums)造成数组溢出
	k %= len(nums)
	// 翻转整个数组
	reverseArray(0, len(nums)-1, nums)
	// 翻转前k个元素
	reverseArray(0, k-1, nums)
	// 翻转k后面的元素
	reverseArray(k, len(nums)-1, nums)
}

func reverseArray(left, right int, nums []int) {
	for left < right {
		leftValue := nums[left]
		nums[left] = nums[right]
		nums[right] = leftValue
		left++
		right--
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	head := &ListNode{}
	newList := &ListNode{Next: head}

	for l1 != nil && l2 != nil {
		if l1.Val > l2.Val {
			head.Next = l2
			head = l2
			l2 = l2.Next
		} else {
			head.Next = l1
			head = l1
			l1 = l1.Next
		}
	}

	if l1 != nil {
		head.Next = l1
	} else if l2 != nil {
		head.Next = l2
	}
	return newList.Next.Next
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func merge(nums1 []int, m int, nums2 []int, n int) {
	// 倒插方式比较简单好理解
	// 最后的永远是最大的，所以来比较每个nums里面递减的值，然后放到nums1里面就行了
	for inBack := n + m - 1; inBack >= 0; inBack-- {
		// n 为0，递减完毕，直接返回
		if n == 0 {
			break
		}
		// 保证m>0的前提下，如果s1 > s2，那么inBack下标放s1的值，反之亦然，同时注意m和n的下标要递减
		if m > 0 && nums1[m-1] > nums2[n-1] {
			nums1[inBack] = nums1[m-1]
			m--
		} else {
			nums1[inBack] = nums2[n-1]
			n--
		}
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func plusOne(digits []int) []int {
	// 为0直接返回1
	if len(digits) == 0 {
		return []int{1}
	}

	for i := len(digits) - 1; i >= 0; i-- {
		// 不为9不用进1，直接返回
		if digits[i] != 9 {
			digits[i] += 1
			return digits
		}
		digits[i] = 0
	}
	// 最低位如果为9那么低位变1
	return append([]int{1}, digits...)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func isAnagram(s string, t string) bool {
	if len(s) != len(t) {
		return false
	}
	// 简易hash表
	// 不包含大写，所以能缩小范围到26（通过-a的方式）
	var a [26]int
	var b [26]int
	for _, c := range s {
		a[c-'a']++
	}
	for _, c := range t {
		b[c-'a']++
	}
	return a == b
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func groupAnagrams(strs []string) [][]string {
	// 没大写字母，压缩到26个数组
	cache := make(map[[26]int][]string)
	for _, str := range strs {
		var key [26]int
		// 一个循环下来，将相应的字母的计数保存到相应的数组位
		for _, c := range str {
			key[c-'a']++
		}
		// 整个key数组就是map的key，然后将相同key的str append起来
		cache[key] = append(cache[key], str)
	}

	var res [][]string
	// 遍历返回即可
	for _, strings := range cache {
		res = append(res, strings)
	}
	return res
}