Leetcode专项学习计划：LeetCode热题100

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

func longestConsecutive(nums []int) int {
    numSet := map[int]bool{}
    for _, num := range nums {
       numSet[num] = true
    }
    maxLen := 0
    for num := range numSet {
       if !numSet[num-1] {
          curNum := num
          curLen := 1
          for numSet[curNum+1] {  // 一直找从num开始的所有连续数字
             curNum++
             curLen++
          }
          if maxLen < curLen {
             maxLen = curLen
          }
       }
    }
    return maxLen
}

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

func groupAnagrams(strs []string) [][]string {
    strMap := make(map[string][]string) // 存字母异位词
    for _, str := range strs {
       s := []byte(str)
       sort.Slice(s, func(i, j int) bool {
          return s[i] < s[j]
       })
       sortedS := string(s)
       strMap[sortedS] = append(strMap[sortedS], str)
    }
    res := make([][]string, len(strMap)) // 最后的返回值
    i := 0
    for _, strSlice := range strMap {
       res[i] = strSlice
       i++
    }
    return res
}

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

func groupAnagrams(strs []string) [][]string {
    map01 := make(map[[26]int][]string)
    for _, str := range strs {
       byteCount := [26]int{}
       for _, byte := range str {
          byteCount[byte-'a']++ // 存放每个字母出现的次数
       }
       map01[byteCount] = append(map01[byteCount], str)
    }
    res := make([][]string, len(map01))
    i := 0
    for _, strSlice := range map01 { // 将map中的value转移到res切片中
       res[i] = strSlice
       i++
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func maxArea(height []int) int {
	// 左右双指针，取左右高度较矮的作为高度
	n := len(height)
	realH, largestArea := 0, 0
	for l := 0; l < n; l++ {
		for r := n - 1; r >= 0; r-- {
			realH = min(height[l], height[r])
			largestArea = max(largestArea, realH*(r-l))
		}
	}
	return largestArea
}

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

func maxArea(height []int) int {
    maxVal, realH := 0, 0
    n := len(height)
    l, r := 0, n-1
    for l < r {
       realH = min(height[l], height[r])
       if (r-l)*realH > maxVal {
          maxVal = (r - l) * realH
       }
       if height[l] <= height[r] {
          l++
       } else {
          r--
       }
    }
    return maxVal
}

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

func findAnagrams(s string, p string) []int {
    res := make([]int, 0)
    lenP := len(p)
    pChars := [26]byte{}
    for _, pStr := range p {
       pChars[pStr-'a']++
    }
    for i := range s {
       sChars := [26]byte{}
       if i+lenP > len(s) {
          break
       }
       for _, sStr := range s[i : i+lenP] { // 判断滑动窗口中的字符串是否合法
          sChars[sStr-'a']++
       }
       if sChars == pChars {
          res = append(res, i)
       }
    }
    return res
}

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

func findAnagrams(s string, p string) []int {
    if len(s) < len(p) { // 剪枝
       return nil
    }
    res := make([]int, 0)
    lenP := len(p)
    pChars, sChars := [26]byte{}, [26]byte{}
    for i, pStr := range p {
       pChars[pStr-'a']++
       sChars[s[i]-'a']++
    }
    if sChars == pChars {
       res = append(res, 0)
    }
    for i := 0; i < len(s)-lenP; i++ { // 滑动窗口的移动过程，i是移除滑动窗口的位置
       sChars[s[i]-'a']--      // 移出
       sChars[s[i+lenP]-'a']++ // 移入
       if sChars == pChars {
          res = append(res, i+1) // 加入到res的应该是i+1，而不是i
       }
    }
    return res
}

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

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
       return intervals[i][0] < intervals[j][0]
    })
    res := make([][]int, 1)
    res[0] = intervals[0]
    for i := 1; i < len(intervals); i++ {
       if intervals[i][0] <= res[len(res)-1][1] { // 存在重叠。注意这里比较的右区间位置是res[len(res)-1][1]，而不是intervals[i-1][0]（这里很关键）
          rightIndex := max(intervals[i][1], res[len(res)-1][1])  
          res[len(res)-1][1] = rightIndex // 更新右区间的值
       } else {
          res = append(res, intervals[i])
       }
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func rotate(nums []int, k int) {
	n := len(nums)
	k = k % n
	for k > 0 {
		temp := nums[n-1]
		for i := n - 1; i >= 1; i-- {
			nums[i] = nums[i-1]
		}
		nums[0] = temp
		k--
	}
}

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

func rotate(nums []int, k int) {
    reverse := func(nums []int) {
       l, r := 0, len(nums)-1
       for l < r {
          nums[l], nums[r] = nums[r], nums[l]
          l++
          r--
       }
    }
    reverse(nums)
    reverse(nums[:k])
    reverse(nums[k:])
}

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

func productExceptSelf(nums []int) []int {
    pre, post := 1, 1
    res := make([]int, len(nums))
    for i := 0; i < len(nums); i++ {
       res[i] = pre
       pre *= nums[i]
    }
    for j := len(nums) - 1; j >= 0; j-- {
       res[j] *= post
       post *= nums[j]
    }
    return res
}

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

func spiralOrder(matrix [][]int) []int {
    // 遍历matrix数组的每一条边
    m := len(matrix)
    n := len(matrix[0])
    res := make([]int, m*n)
    count := 0 // 遍历过的元素数量
    i, j, startX, offset := 0, 0, 0, 1
    for c := 0; c < max(m, n)/2; c++ { // c表示圈数
       i, j = startX, startX
       for ; j < n-offset; j++ { // 每条边不包含最后一个元素
          if count == m*n {
             return res
          }
          res[count] = matrix[i][j]
          count++
       }
       for ; i < m-offset; i++ {
          if count == m*n {
             return res
          }
          res[count] = matrix[i][j]
          count++

       }
       for ; j > startX; j-- {
          if count == m*n {
             return res
          }
          res[count] = matrix[i][j]
          count++
       }
       for ; i > startX; i-- {
          if count == m*n {
             return res
          }
          res[count] = matrix[i][j]
          count++
       }
       offset++
       startX++
    }
    if count == m*n-1 { // 最中心的位置如果没有遍历到，则最后再赋值
       res[count] = matrix[m/2][n/2]
    }
    return res
}

 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
27
28
29

func searchMatrix(matrix [][]int, target int) bool {
	m := len(matrix)
	n := len(matrix[0])
	colLeft, colRight := 0, m-1
	for colLeft <= colRight {
		colMid := colLeft + (colRight-colLeft)>>1
		if target == matrix[colMid][0] {
			return true
		} else if target < matrix[colMid][0] {  // 只有target小的时候才能二分
			colRight = colMid - 1
		} else {
			break
		}
	}
	for i := colLeft; i <= colRight; i++ {
		rowLeft, rowRight := 0, n-1
		for rowLeft <= rowRight {
			rowMid := rowLeft + (rowRight-rowLeft)>>1
			if target == matrix[i][rowMid] {
				return true
			} else if target > matrix[i][rowMid] {
				rowLeft = rowMid + 1
			} else {
				rowRight = rowMid - 1
			}
		}
	}
	return false
}

 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

type MinStack struct {
    stack    []int
    minStack []int
}
func Constructor() MinStack {
    return MinStack{
       stack:    []int{},
       minStack: []int{math.MaxInt},
    }
}
func (this *MinStack) Push(val int) {
    this.stack = append(this.stack, val)
    minTop := this.minStack[len(this.minStack)-1]
    this.minStack = append(this.minStack, min(minTop, val))
}
func (this *MinStack) Pop() {
    this.stack = this.stack[:len(this.stack)-1]
    this.minStack = this.minStack[:len(this.minStack)-1]
}
func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}
func (this *MinStack) GetMin() int {
    return this.minStack[len(this.minStack)-1]
}

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

func searchRange(nums []int, target int) []int {
    // 返回target最左侧的位置
    binarySearch := func(nums []int, target int) int {
       l, r := 0, len(nums)-1
       for l <= r {
          mid := l + (r-l)>>1
          if target > nums[mid] {
             l = mid + 1
          } else {
             r = mid - 1
          }
       }
       return l
    }
    left := binarySearch(nums, target)
    right := binarySearch(nums, target+1) - 1
    if left == len(nums) || nums[left] != target { // 可能存在数组中没有找到target的情况
       return []int{-1, -1}
    }
    return []int{left, right}
}

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

func majorityElement(nums []int) int {
    candidate, count := 0, 0
    for _, num := range nums {
       if count == 0 {
          candidate = num
       }
       if num == candidate {
          count++
       } else {
          count--
       }
    }
    return candidate
}

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

func sortColors(nums []int) {
    countTarget := 0
    var swap func(nums []int, target int)
    swap = func(nums []int, target int) { // 需要把target放到数组最前面
       countTarget = 0
       for i := 0; i < len(nums); i++ {
          if nums[i] == target {
             nums[countTarget], nums[i] = nums[i], nums[countTarget]
             countTarget++
          }
       }
    }
    swap(nums, 0)
    swap(nums[countTarget:], 1)
}

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

func trap(height []int) int {
	n := len(height)
	left, right := make([]int, n), make([]int, n)
	left[0], right[n-1] = height[0], height[n-1]
	for i := 1; i < n; i++ {
		left[i] = max(left[i-1], height[i])
	}
	for i := n - 2; i >= 0; i-- {
		right[i] = max(right[i+1], height[i])
	}
	sum := 0
	for i, h := range height {
		sum += min(left[i], right[i]) - h
	}
	return sum
}

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

func trap(height []int) int {
    n := len(height)
    l, r := 0, n-1
    lMax, rMax, sum := 0, 0, 0
    for l < r {
       lMax = max(lMax, height[l]) // 遍历过程中，更新lMax和rMax的值
       rMax = max(rMax, height[r])
       if lMax < rMax { // 如果lMax更小，则决定桶高度的就是lMax，计算lMax与height[l]的差值，加入到sum中，并右移l指针
          sum += lMax - height[l]
          l++
       } else { // 反之，rMax更小，决定桶高度的就是rMax
          sum += rMax - height[r]
          r--
       }
    }
    return sum
}

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

func subarraySum(nums []int, k int) int {
	count := 0
	preSum := make([]int, len(nums)+1)
	preSum[0] = 0
	for i, num := range nums { // 构建前缀和数组
		preSum[i+1] = preSum[i] + num
	}
	for i := 0; i < len(preSum); i++ { // i遍历preSum的每个位置，j遍历i后面的每个位置
		for j := i + 1; j < len(preSum); j++ {
			if preSum[j]-preSum[i] == k {
				count++
			}
		}
	}
	return count
}

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

func subarraySum(nums []int, k int) int {
    preSum := 0
    count := 0
    preSumMap := make(map[int]int, 1) // key为前缀和，value为该前缀和出现的次数
    preSumMap[0] = 1                  // 前缀和为0至少出现了1次（这里的初始化很重要）
    for _, num := range nums {
       // 计算当前的前缀和，由于后一个位置的前缀和可以由前一个位置得到，而所有的前缀和都保存到了map中，
       // 所以，这里只需要一个不断迭代的变量就可以了，不需要一个前缀和数组
       preSum += num
       if preSumCount, exist := preSumMap[preSum-k]; exist { // 找到了满足条件的前缀和
          count += preSumCount
       }
       preSumMap[preSum]++
    }
    return count
}

 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
27
28
29
30

func maxSlidingWindow(nums []int, k int) []int {
	queue := make([]int, 1)
	queue[0] = nums[0]
	push := func(num int) {
		if len(queue) == 0 || num < queue[len(queue)-1] {
			queue = append(queue, num)
		} else {
			for len(queue) > 0 && num > queue[len(queue)-1] { // 把前面小于num的元素全部删除
				queue = queue[:len(queue)-1]
			}
			queue = append(queue, num)
		}
	}
	pop := func(num int) {
		if num == queue[0] {
			queue = queue[1:]
		}
	}
	res := make([]int, len(nums)-k+1)
	for i := 1; i <= k-1; i++ { // 先把前k个元素加入到队列中
		push(nums[i])
	}
	res[0] = queue[0]
	for i := k; i < len(nums); i++ {
		pop(nums[i-k])
		push(nums[i])
		res[i-k+1] = queue[0]
	}
	return res
}

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40

func minWindow(s string, t string) string {
    if len(s) < len(t) {
       return ""
    }
    tMap, sMap := make(map[byte]int), make(map[byte]int)
    for i := 0; i < len(t); i++ {
       tMap[t[i]]++
    }
    l, r, start, minLen, count := 0, 0, 0, len(s)+1, 0
    for r < len(s) {
       if tMap[s[r]] == 0 { // r位置的元素在tMap中不存在
          r++
          continue
       }
       if sMap[s[r]] < tMap[s[r]] {
          count++
       }
       sMap[s[r]]++
       r++
       for count == len(t) { // 这是一个循环的过程
          if r-l < minLen {
             minLen = r - l // 记录start后面到r的距离，不用加1
             start = l
          }
          if tMap[s[l]] == 0 { // 滑动窗口最左侧的元素不在t中
             l++
             continue
          }
          if sMap[s[l]] == tMap[s[l]] {
             count--
          }
          sMap[s[l]]--
          l++
       }
    }
    if minLen == len(s)+1 { // 如果最小长度还为初始值，说明没有符合条件的子串
       return ""
    }
    return s[start : start+minLen]
}

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

func firstMissingPositive(nums []int) int {
    n := len(nums)
    for i := 0; i < n; i++ {
       for nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i]-1] {
          nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i] // 交换两个位置的值
       }
    }
    for i := 0; i < len(nums); i++ {
       if nums[i] != i+1 {
          return i + 1
       }
    }
    return n + 1
}

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

func setZeroes(matrix [][]int) {
    m := len(matrix)
    n := len(matrix[0])
    col_zero, row_zero := false, false // 记录第0列个第0行是否存在0
    for i := 0; i < m; i++ {
       if matrix[i][0] == 0 {
          col_zero = true
          break
       }
    }
    for j := 0; j < n; j++ {
       if matrix[0][j] == 0 {
          row_zero = true
          break
       }
    }
    for i := 1; i < m; i++ {
       for j := 1; j < n; j++ {
          if matrix[i][j] == 0 {
             matrix[i][0] = 0
             matrix[0][j] = 0
          }
       }
    }
    for i := 1; i < m; i++ {
       for j := 1; j < n; j++ {
          if matrix[i][0] == 0 || matrix[0][j] == 0 {
             matrix[i][j] = 0
          }
       }
    }
    if col_zero {
       for i := 0; i < m; i++ {
          matrix[i][0] = 0
       }
    }
    if row_zero {
       for j := 0; j < n; j++ {
          matrix[0][j] = 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
27
28
29
30
31

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    oldL1 := l1  // 指向最初l1的头结点，用于最后返回
    addFlag := 0 // 进位值
    var pre1 *ListNode
    for l1 != nil && l2 != nil {
       temp := l1.Val + l2.Val + addFlag // 注意这里要用temp临时保存计算的值，因为l1.Val的值在这里会被修改，所以后面求进位值时，不能使用l1.Val + l2.Val + addFlag（此时l1.Val的值已经发生了变化）
       l1.Val = temp % 10
       addFlag = temp / 10
       pre1 = l1
       l1 = l1.Next
       l2 = l2.Next
    }
    if l1 == nil {
       pre1.Next = l2
       l1 = l2
    }
    for l1 != nil {
       temp := l1.Val + addFlag
       l1.Val = temp % 10
       addFlag = temp / 10
       if addFlag == 0 { // 如果没有进位值了，就可以不用再进行计算了
          break
       }
       pre1 = l1
       l1 = l1.Next
    }
    if addFlag == 1 {
       pre1.Next = &ListNode{1, nil}
    }
    return oldL1
}

 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
27

func reverseKGroup(head *ListNode, k int) *ListNode {
    if head == nil || k == 1 {
       return head
    }
    curLen := 0
    curHead := head
    for curHead != nil {
       curLen++
       curHead = curHead.Next
    }
    if curLen < k { // 判断当前链表长度是否大于等于k
       return head
    }
    reversedHead, nextHead := reverseK(head, k)
    head.Next = reverseKGroup(nextHead, k) // 递归地处理剩余的链表，head的next为翻转之后的头结点，这样就把链表连接起来了
    return reversedHead                    // 向上层返回翻转之后的头结点
}
func reverseK(head *ListNode, k int) (*ListNode, *ListNode) {
    var pre *ListNode
    for i := 0; i < k; i++ {
       temp := head.Next
       head.Next = pre
       pre = head
       head = temp
    }
    return pre, head // 返回翻转之后的头结点和下一个需要翻转的头结点
}