算法与数据结构

[wxb]

算法与数据结构

[wxb]

《我的第一本算法书》

[wxb]

2-2 冒泡算法

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”这一操作的算法。

在这个过程中，数字会像泡泡一样，慢慢从右往左“浮”到序列的顶端，所以这个算法才被称为“冒泡排序”​。

// BubbleSort 升序冒泡排序
func BubbleSort(arr []int) {
	// 边界处理：空数组或单元素数组无需排序
	if len(arr) <= 1 {
		return
	}

	length := len(arr)
	// 新增：交换标志位，标记本轮是否发生交换
	var swapped bool

	for i := 0; i < length; i++ {
		swapped = false // 每轮开始前重置为false
		for j := length - 1; j > i; j-- {
			if arr[j] < arr[j-1] {
				arr[j], arr[j-1] = arr[j-1], arr[j]
				swapped = true // 发生交换，标记为true
			}
		}
		// 新增：本轮无交换，说明数组已完全有序，直接退出
		if !swapped {
			break
		}
	}
}

[wxb]

2-3 选择排序

选择排序就是重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”这一操作的算法。

结合线性查找每次内部循环找出最大（DESC）或最小（ASC）值，然后与最左侧位置交换

• 第一版

func sortWithAsc(arr []int) {

	for i := 0; i < len(arr); i++ {
		for j := i + 1; j < len(arr); j++ {
			if arr[i] > arr[j] {
				arr[i], arr[j] = arr[j], arr[i]
			}
		}
	}
}

问题: 每发现一个更小的元素就立即交换，导致交换次数过多（理想的选择排序应该先找到最小值的索引，遍历完待排序区后只做一次交换）。

• 第二版

// SelectionSortAsc 对整型数组进行升序选择排序
// 选择排序核心：每轮从待排序区找到最小值的索引，仅做一次交换
func SelectionSortAsc(arr []int) {
	// 鲁棒性处理：空数组或单元素数组无需排序，直接返回
	if len(arr) <= 1 {
		return
	}

	arrLen := len(arr)
	// 外层循环：划分已排序区(0~i-1)和待排序区(i~arrLen-1)
	for i := 0; i < arrLen-1; i++ { // 优化：只需遍历到arrLen-1，最后一个元素自然有序
		minIdx := i // 初始化最小值索引为待排序区第一个元素

		// 内层循环：遍历待排序区，找到最小值的索引
		for j := i + 1; j < arrLen; j++ {
			if arr[j] < arr[minIdx] {
				minIdx = j // 更新最小值索引，不立即交换
			}
		}

		// 优化：仅当最小值索引不等于i时，才交换（避免无意义的自我交换）
		if minIdx != i {
			arr[i], arr[minIdx] = arr[minIdx], arr[i]
		}
	}
}

[wxb]

2-4 插入排序

插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上。

// InsertSortAsc 对整型数组进行升序插入排序
// 插入排序核心：从右侧的未排序区域内取出一个数据，将它插入到已排序区域内合适的位置上
func InsertSortAsc(arr []int) {

	arrLen := len(arr)
	if arrLen <= 1 {
		return
	}

	// i从1开始，已排序区域长度默认是i（i=1时已排序长度1，i=2时已排序长度2，和你的sortedLen完全同步）
	for i := 1; i < arrLen; i++ {
		insertVal := arr[i] // 暂存待插入元素，避免多次交换
		j := i - 1          // 已排序区域的最后一个元素索引
		// 比insertVal大的元素统一后移，无需交换
		for j >= 0 && arr[j] > insertVal {
			arr[j+1] = arr[j] // 单赋值操作，比交换轻量
			j--
		}
		arr[j+1] = insertVal // 插入到最终位置
	}
}

[wxb]

《漫画算法：小灰的算法之旅》

[wxb]

《大话数据结构》

[wxb]

面试算法

[wxb]

链表中环的长度

核心思路：先用快慢指针确定有环，然后从相遇点开始，走一圈计算环的长度

// 计算环的长度
func getCycleLength(head *ListNode) int {
	if head == nil || head.Next == nil {
		return 0
	}

	slow, fast := head, head

	// 找到相遇点
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next

		if slow == fast {
			// 从相遇点开始，走一圈计算长度
			length := 1
			current := slow.Next
			for current != slow {
				length++
				current = current.Next
			}
			return length
		}
	}

	return 0
}

[wxb]

链表的中间节点

核心思想
快慢指针：快指针走 2 步，慢指针走 1 步，快指针到尾时，慢指针在中间。

// 找到链表的中间节点
func findMiddle(head *ListNode) *ListNode {
    // 边界情况
    if head == nil {
        return nil
    }
    
    slow, fast := head, head
    
    // 快指针走2步，慢指针走1步
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    return slow // 慢指针指向中间节点
}

[wxb]

链表删除倒数第 N 个节点

核心思路：让快指针先移动 n 步，然后快慢指针同步移动，快指针到尾时，慢指针指向倒数第 n+1 个节点，直接删除其后节点。

// 删除倒数第 N 个节点
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	// 使用虚拟头节点，处理删除头节点的情况
	dummy := &ListNode{Value: "", Next: head}
	slow, fast := dummy, dummy

	// 快指针先走n步
	for i := 0; i < n; i++ {
		fast = fast.Next
	}

	// 快慢指针同时移动，直到快指针走到末尾
	for fast.Next != nil {
		slow = slow.Next
		fast = fast.Next
	}

	// 删除节点
	slow.Next = slow.Next.Next

	return dummy.Next
}

[wxb]

找出给定字符串中不含有重复字符的 最长 子串 的长度

核心思路: 维护一个 “滑动窗口”，窗口内的子串保证无重复字符，通过哈希表记录字符的最新位置，动态调整窗口的起始位置：

func lengthOfLongestSubstring(s string) int {
    // 哈希表存储字符最后出现的位置
    lastOccurred := make(map[byte]int)
    maxLen := 0   // 最长无重复子串长度
    left := 0     // 窗口左边界

    // 右指针遍历字符串
    for right := 0; right < len(s); right++ {
  	  c := s[right]
  	  // 若字符已出现且在当前窗口内，移动左指针到重复位置的下一位
  	  if pos, exists := lastOccurred[c]; exists && pos >= left {
  		  left = pos + 1
  	  }
  	  // 更新字符最后出现的位置
  	  lastOccurred[c] = right
  	  // 计算当前窗口长度，更新最大长度
  	  currentLen := right - left + 1
  	  if currentLen > maxLen {
  		  maxLen = currentLen
  	  }
    }
    return maxLen
}

[wxb]

找出s1字符串的任何排列是否存在于s2字符串中

问题示例：

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
 
示例 1：
输入：s1 = "abb" s2 = "eidbabooo"
输出：true
解释：s2 包含 s1 的排列之一 ("bab").
示例 2：
输入：s1= "abb" s2 = "eidbboaoo"
输出：false

---

核心思路：

• 方案一（排序 + 滑动窗口对比）：既然 s1 的排列是 “字符种类和数量不变”，那把 s1 排序后，只要 s2 中存在一个长度等于 s1 的子串，排序后和 s1 排序结果完全一致，就返回 true。

  package main
  
  import (
      "fmt"
      "sort"
      "strings"
  )
  
  func checkInclusion(s1 string, s2 string) bool {
      n1, n2 := len(s1), len(s2)
      if n1 > n2 {
    	  return false // s1 比 s2 长，直接不可能
      }
  
      // 1. 把 s1 排序（转成切片排序后再转回字符串）
      sortedS1 := sortString(s1)
  
      // 2. 滑动窗口：遍历 s2 所有长度为 n1 的子串
      for i := 0; i <= n2-n1; i++ {
    	  // 切出当前窗口的子串（s2[i:i+n1]）
    	  subStr := s2[i : i+n1]
    	  // 子串排序后和 sortedS1 对比
    	  if sortString(subStr) == sortedS1 {
    		  return true
    	  }
      }
  
      return false
  }
  
  // 辅助函数：把字符串排序（比如 "bab"→"abb"）
  func sortString(s string) string {
      // 字符串转 rune 切片（支持中文，这里虽然用不到，但更通用）
      runes := []rune(s)
      // 排序切片
      sort.Slice(runes, func(i, j int) bool {
    	  return runes[i] < runes[j]
      })
      // 转回字符串
      return string(runes)
  }
  
  func main() {
      fmt.Println(checkInclusion("abb", "eidbabooo")) // 输出 true
      fmt.Println(checkInclusion("abb", "eidbboaoo")) // 输出 false
      fmt.Println(checkInclusion("a", "ab"))          // 输出 true
  }