代码随想录：基础算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func bubbleSort(arr []int) {
	length := len(arr)
	for i := 0; i < length-1; i++ { // i控制排序的轮数（每轮让1个元素有序）
		for j := 0; j < length-i-1; j++ { // j控制实际参与排序的元素（每轮减少1个元素）
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func selectionSort(arr []int) {
    for i := 0; i < len(arr)-1; i++ {
       minIndex := i
       for j := i + 1; j < len(arr); j++ {
          if arr[j] < arr[minIndex] {
             minIndex = j
          }
       }
       arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func insertionSort(arr []int) {
    for i := 0; i < len(arr)-1; i++ {
       currentVal := arr[i+1]
       insertIndex := i
       for insertIndex >= 0 && currentVal < arr[insertIndex] {
          arr[insertIndex+1] = arr[insertIndex]
          insertIndex--
       }
       arr[insertIndex+1] = currentVal
    }
}

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

func partition(arr []int, left, right int) int {
    pivot := arr[right]
    i := left - 1 // i指向左边小于pivot元素集合中的最后一个元素
    for j := left; j < right; j++ {
       if arr[j] <= pivot {
          i++
          arr[i], arr[j] = arr[j], arr[i]
       }
    }
    arr[i+1], arr[right] = arr[right], arr[i+1] // 把pivot放在“中间”的位置
    return i + 1                                // i+1就是pivot的位置下标
}

func quickSort(arr []int, left, right int) {
    if left < right {
       pivotIndex := partition(arr, left, right)
       quickSort(arr, left, pivotIndex-1)
       quickSort(arr, pivotIndex+1, right)
    }
}

 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

func mergeSort(arr, help []int, left, right int) {
    // 递归的出口：left>=right
    if left < right {
       middleIndex := left + (right-left)>>1      // 求中点下标
       mergeSort(arr, help, left, middleIndex)    // 左边排序
       mergeSort(arr, help, middleIndex+1, right) // 右边排序
       merge(arr, help, middleIndex, left, right) // 合并左右的数组
    }
}

func merge(arr, help []int, middleIndex, left, right int) {
    p1 := left
    p2 := middleIndex + 1
    i := left
    for ; p1 <= middleIndex && p2 <= right; i++ {
       if arr[p1] <= arr[p2] {
          help[i] = arr[p1]
          p1++
       } else {
          help[i] = arr[p2]
          p2++
       }
    }
    for ; p1 <= middleIndex; i++ {
       help[i] = arr[p1]
       p1++
    }
    for ; p2 <= right; i++ {
       help[i] = arr[p2]
       p2++
    }
    for j := left; j <= right; j++ {
       arr[j] = help[j]
    }
}

 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 main() {
    arr := []int{9, 2, 5, 1, 3, 7, 6, 4, 8}
    fmt.Println("原始数组:", arr)
    heapSort(arr)
    fmt.Println("排序后数组:", arr)
}

// 调整堆
func heapify(arr []int, n, i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2

    // 如果左子节点大于根节点，则更新最大值索引
    if left < n && arr[left] > arr[largest] {
       largest = left
    }

    // 如果右子节点大于根节点，则更新最大值索引
    // 注意加上 right < n 的条件限制，因为堆最多n个元素
    if right < n && arr[right] > arr[largest] {
       largest = right
    }

    // 如果最大值不是根节点，则交换根节点和最大值，然后继续调整堆
    if largest != i {
       arr[i], arr[largest] = arr[largest], arr[i]
       heapify(arr, n, largest) // 对 largest 位置再次堆化
    }
}

// 堆排序
func heapSort(arr []int) {
    n := len(arr)

    // 构建最大堆
    for i := n/2 - 1; i >= 0; i-- { // 从最后一个非叶子节点（下标为n/2-1）开始，因为在heapify要比较i位置元素和它左右孩子元素的大小
       heapify(arr, n, i)
    }

    // 逐个将最大值（根节点）移到数组末尾，并调整堆
    for i := n - 1; i >= 0; i-- {
       arr[0], arr[i] = arr[i], arr[0] // 此时 arr[0]是最大的元素，将其和数组中的最后一个元素交换，然后再对0位置进行堆化
       heapify(arr, i, 0)              // 注意这里的第二个参数为i
    }
}

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

func search(nums []int, target int) int {
    left := 0
    right := len(nums) - 1
    for left <= right { // 注意区间的开闭，这里采用左闭右闭区间
       middle := left + (right-left)>>1
       if target == nums[middle] {
          return middle
       }
       if target < nums[middle] {
          right = middle - 1
       } else {
          left = middle + 1
       }
    }
    return -1
}

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

func removeElement(nums []int, val int) int {
    // 使用快慢指针的思想
    // 快指针fast遍历数组，慢指针slow指向符合要求的数组集合的最后一个元素。
    // 当fast指向的元素不等于val时，把该值赋给slow指向的位置，然后slow加1。
    fast := 0
    slow := -1
    for ; fast < len(nums); fast++ {
       if nums[fast] != val {
          slow++
          nums[slow] = nums[fast]
       }
    }
    return slow + 1
}

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

func sortedSquares(nums []int) []int {
    left := 0
    right := len(nums) - 1
    help := make([]int, len(nums))
    for i := len(nums) - 1; left <= right; i-- {
       if nums[right]*nums[right] >= nums[left]*nums[left] {
          help[i] = nums[right] * nums[right]
          right--
       } else {
          help[i] = nums[left] * nums[left]
          left++
       }
    }
    return help
}

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

func minSubArrayLen(target int, nums []int) int {
    left := 0
    right := 0
    minLen := math.MaxInt
    sum := 0
    exist := false
    for right = 0; right < len(nums); right++ {
       sum += nums[right]
       for sum >= target { // 当满足条件时，移动left指针（这个过程是循环移动的，所以这里要用for）
          exist = true
          minLen = min(minLen, right-left+1)
          sum -= nums[left]
          left++
       }
    }
    if !exist {
       return 0
    }
    return minLen
}

 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

func main() {
    n := 4
    r := generateMatrix(n)
    fmt.Println(r)
}

func generateMatrix(n int) [][]int {
    // 创建n*n的切片，学会这种写法
    matrix := make([][]int, n)
    for i := range matrix {
       matrix[i] = make([]int, n)
    }
    count := 1
    var (
       i      = 0 // 行
       j      = 0 // 列
       c      = 0 // 圈数
       startX = 0 // 代表第几层循环
       offset = 1 // 第1圈，offset=1
    )
    for c = 0; c < n/2; c++ {
       for j = startX; j < n-offset; j++ { // 第1条边，y坐标变化
          matrix[c][j] = count
          count++
       }
       for i = startX; i < n-offset; i++ { // 第2条边，x坐标变化
          matrix[i][j] = count
          count++
       }
       for ; j > startX; j-- { // 第3条边，y坐标变化
          matrix[i][j] = count
          count++
       }
       for ; i > startX; i-- { // 第4条边，x坐标变化
          matrix[i][j] = count
          count++
       }
       startX++
       offset++
    }
    if n%2 != 0 { // 如果n为奇数，中心位置单独处理
       matrix[startX][startX] = count
    }
    return matrix
}

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

func reverseList(head *ListNode) *ListNode {
	var pre *ListNode // 定义一个pre，作为虚拟头结点
	cur := head
	var temp *ListNode
	for cur != nil {
		temp = cur.Next // 记录原来的下一个结点
		cur.Next = pre
		pre = cur
		cur = temp
	}
	return pre
}

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

func swapPairs(head *ListNode) *ListNode {
    pre := &ListNode{0, head}
    pre.Next = head // 添加一个虚拟头结点，指向真正的头结点
    var temp, temp1 *ListNode
    cur := pre // cur最开始指向pre

    if head.Next == nil || head.Next.Next == nil {
       return head
    }

    for cur.Next != nil && cur.Next.Next != nil {
       temp = cur.Next
       temp1 = cur.Next.Next.Next
       cur.Next = cur.Next.Next
       cur.Next.Next = temp
       cur.Next.Next.Next = temp1
       cur = cur.Next.Next
    }
    return pre.Next
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil { // 确定递归出口
		return head
	}
	next := head.Next           // 先记录第2个结点
	head.Next = swapPairs(next.Next) // 第1个结点指向第3个结点
	next.Next = head            // 第2个结点指向第1个结点

	return next
}

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

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    pre := &ListNode{0, head}
    pre.Next = head
    fast := head
    slow := head
    if head == nil || head.Next == nil {
       return nil
    }
    for i := 0; i < n; i++ { // 快指针先移动n步
       fast = fast.Next
    }
    for fast != nil { // 三个指针同时移动
       pre = pre.Next
       slow = slow.Next
       fast = fast.Next
    }
    pre.Next = pre.Next.Next // 删除slow位置的结点
    return pre.Next
}

 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

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    listA := headA
    listB := headB
    var lenA, lenB int
    for listA != nil {
       listA = listA.Next
       lenA++
    }
    for listB != nil {
       listB = listB.Next
       lenB++
    }
    listA = headA
    listB = headB

    n := lenDiff(lenA, lenB)

    if lenA > lenB { // 将长的链表先移动n步
       for i := 0; i < n; i++ {
          listA = listA.Next
       }
    } else {
       for i := 0; i < n; i++ {
          listB = listB.Next
       }
    }
    for i := 0; i < min(lenA, lenB); i++ {
       if listA == listB {
          return listA
       }
       listA = listA.Next
       listB = listB.Next
    }
    return nil
}

func lenDiff(lenA, lenB int) int {
    n := lenA - lenB
    if n < 0 {
       return -n
    }
    return n
}

 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

// 方法1：map实现
func detectCycle1(head *ListNode) *ListNode {
    cur := head
    nodeMap := make(map[*ListNode]struct{}) // 保存已经遍历过的结点到map中
    if head == nil || head.Next == nil {
       return nil
    }
    for cur != nil {
       if _, exist := nodeMap[cur]; exist {
          return cur
       }
       nodeMap[cur] = struct{}{}
       cur = cur.Next
    }
    return nil
}

// 方法2：快慢指针
func detectCycle(head *ListNode) *ListNode {
    slow := head
    fast := head
    var meet *ListNode // 默认为nil
    fmt.Println(meet)
    if head == nil || head.Next == nil || head.Next.Next == nil {
       return nil
    }
    for fast != nil && fast.Next != nil {
       slow = slow.Next // 这里一定要先移动，在判断slow是否等于fast，因为初始时slow是等于fast的。
       fast = fast.Next.Next
       if slow == fast { // 找到相遇结点
          meet = slow
          break
       }
    }
    slow = head // slow从head出发，meet从相遇点出发
    for meet != nil {
       if slow == meet { // slow和meet相遇点即为环入口
          return slow
       }
       meet = meet.Next
       slow = slow.Next
    }
    return nil
}

 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
47
48

// 2024.04.03 自己写的版本，需要创建两个hashmap
func isAnagram00(s string, t string) bool {
    charCountS := make(map[rune]int)
    charCountT := make(map[rune]int)

    for _, v := range s {
       if _, exist := charCountS[v]; exist {
          charCountS[v]++
       } else {
          charCountS[v] = 1
       }
    }
    for _, v := range t {
       if _, exist := charCountT[v]; exist {
          charCountT[v]++
       } else {
          charCountT[v] = 1
       }
    }
    return maps.Equal(charCountS, charCountT)
}

// 方法2：同一个hashmap，一个做加法，一个做减
func isAnagram(s string, t string) bool {
    charCountS := make(map[rune]int) // 定义一个hashmap，key为字符，value为字符出现的次数

    for _, v := range s {
       if _, exist := charCountS[v]; exist {
          charCountS[v]++ // 做加法
       } else { // 不存在时，初始化为1
          charCountS[v] = 1
       }
    }

    for _, v := range t {
       if _, exist := charCountS[v]; !exist { // s的hashset中不存在该字符，直接退出
          return false
       } else {
          charCountS[v]-- // 做减法
       }
    }
    for _, v := range charCountS {
       if v != 0 {
          return false
       }
    }
    return true
}

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

func intersection(nums1 []int, nums2 []int) []int {
    result := make([]int, 0)
    nums1Map := make(map[int]struct{})
    commonMap := make(map[int]struct{})
    for _, v := range nums1 {
       if _, exist := nums1Map[v]; !exist { // 不存在，写入map
          nums1Map[v] = struct{}{}
       }
    }
    for _, v := range nums2 {
       if _, exist := nums1Map[v]; exist {
          commonMap[v] = struct{}{}
       }
    }
    for k := range commonMap {
       result = append(result, k)
    }
    return result
}

 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 main() {
    r := isHappy(20)
    fmt.Println(r)
}

func isHappy(n int) bool {
    sumsMap := make(map[int]struct{})
    bitNum := 0 // 每位的数字
    num := n
    sum := 0
    for {
       sum = 0
       for num != 0 {
          bitNum = num % 10
          sum += bitNum * bitNum
          num = num / 10
       }
       if _, exist := sumsMap[sum]; exist {
          fmt.Println(sum)
          return false
       }
       if sum == 1 {
          return true
       }
       sumsMap[sum] = struct{}{}
       fmt.Println(sum)
       num = sum
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)
    for i, v := range nums {
       if mapValue, exist := numMap[target-v]; exist {
          return []int{i, mapValue}
       }
       numMap[v] = i
    }
    return nil
}

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

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    count := 0
    sum1 := 0
    sum1Map := make(map[int]int)
    for _, v1 := range nums1 {
       for _, v2 := range nums2 {
          sum1 = v1 + v2
          if _, exist := sum1Map[sum1]; !exist {
             sum1Map[sum1] = 1
          } else {
             sum1Map[sum1]++
          }
       }
    }
    for _, v3 := range nums3 {
       for _, v4 := range nums4 {
          if _, exist := sum1Map[-v3-v4]; exist {
             count += sum1Map[-v3-v4] // 这里的计数很关键，第二组每出现一次符合条件的，就应该加上前面map中存的次数
          }
       }
    }
    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

func canConstruct(ransomNote string, magazine string) bool {
    runeMap := make(map[rune]int)
    for _, v := range magazine {
       if _, exist := runeMap[v]; !exist {
          runeMap[v] = 1
       } else {
          runeMap[v]++
       }
    }
    for _, v := range ransomNote {
       if _, exist := runeMap[v]; !exist {
          return false
       } else {
          runeMap[v]--
       }
    }
    for _, v := range runeMap {
       if v < 0 {
          return false
       }
    }
    return true
}

 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

// map的key不能是slice，但可以是array
func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    valuesMap := make(map[[3]int]struct{}) // key为值组合而成的数组
    result := make([][]int, 0)
    for i := 0; i < len(nums); i++ { // 固定一个数
       left := i + 1 // 双指针
       right := len(nums) - 1
       for left < right {
          if nums[i]+nums[left]+nums[right] == 0 {
             target := []int{nums[i], nums[left], nums[right]}
             if _, exist := valuesMap[[3]int(target)]; !exist { // 将map的key设置为数组类型，判断是否该组合是否出现过
                valuesMap[[3]int(target)] = struct{}{}
                result = append(result, target)
             }
             left++
          } else if nums[i]+nums[left]+nums[right] < 0 { // 小于0，右移left指针
             left++
          } else { // 大于0，左移right指针
             right--
          }
       }
    }
    return result
}