抽五星卡概率

单抽抽中五星的概率

• 就是 p = 0.006，这是最基础的。

字符串相加

解题思路：将两个字符串表示的数字看作是按位排列的数字，从低位（字符串末尾）开始逐位相加，同时考虑进位情况，就如同我们在纸上进行竖式加法运算一样。

package main

import (
	"fmt"
)

// 字符串相加
func addStrings(num1, num2 string) string {
	i, j := len(num1)-1, len(num2)-1 // 指向 num1 和 num2 的最后一位（即最低位）。
	carry := 0                       // 初始化进位为 0
	result := []byte{}               // 结果字符串使用 []byte 存储，最后再转换成字符串。
	// 只要有任一数字还有未处理的位，或仍有 carry（进位），就继续循环。
	for i >= 0 || j >= 0 || carry > 0 {
		var x, y int

		if i >= 0 {
			x = int(num1[i] - '0')
			i--
		}
		if j >= 0 {
			y = int(num2[j] - '0')     // num1[i] - '0' 是将字符 '3' 转为数字 3
			j--
		}

		sum := x + y + carry
		result = append([]byte{byte(sum%10 + '0')}, result...)
		carry = sum / 10           // 是进位（如 8+7=15，写下 5，进位 1）
	}

	return string(result)
}

func main() {
	a := "123"
	b := "456"
	fmt.Println("结果：", addStrings(a, b))  
}

给一个整数，求其二进制1的个数，负数取补码

func hammingWeight(n uint32) int {
	count := 0
	for n != 0 {
		n &= n - 1 // 每次消掉最右边的 1
		count++
	}
	return count
}
/*
n      = 1100
n - 1  = 1011
n & n-1= 1000   // 去掉了最右边的 

n      = 1000
n - 1  = 0111
n & n-1= 0000   // 再次去掉了最右边的 1
*/

给定链表 1 -> 2 -> ... -> n-1 -> n，使用 O(1) 空间复杂度使其变为 1 -> n -> 2 -> n-1 -> ...

解决思路：

Step 1：使用快慢指针找到链表中点

将链表一分为二。

Step 2：反转链表后半部分

从中点之后反转链表，使其从 n -> n-1 -> ...

Step 3：合并两个链表

交替合并 前半部分（1->2->3） 和 后半部分（n->n-1->...）

type ListNode struct {
    Val  int
    Next *ListNode
}

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }

    // Step 1: 找到中间节点（快慢指针）
    slow, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    // Step 2: 反转后半部分
    second := reverseList(slow.Next)
    slow.Next = nil // 断开前后链表

    // Step 3: 合并两个链表
    first := head
    for second != nil {
        tmp1 := first.Next
        tmp2 := second.Next

        first.Next = second
        second.Next = tmp1

        first = tmp1
        second = tmp2
    }
}

// 反转链表
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    for head != nil {
        next := head.Next
        head.Next = prev
        prev = head
        head = next
    }
    return prev
}

讲一下二叉树最近公共父节点算法

给定一棵二叉树和两个节点 p 和 q，找到它们的最近公共祖先（Lowest Common Ancestor）。

最近公共祖先是指：在二叉树中同时拥有 p 和 q 作为后代的最深节点（注意，一个节点可以是它自己的祖先）。

给定二叉树：

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

• p = 5, q = 1 → 最近公共祖先是 3。
• p = 5, q = 4 → 最近公共祖先是 5。

算法核心思想（递归解法）

我们从根节点出发，递归查找 p 和 q 的位置：

1. 如果当前节点是 p 或 q，直接返回该节点。
2. 在左子树中递归查找 p 和 q。
3. 在右子树中递归查找 p 和 q。
4. 如果左子树和右子树都找到了，那当前节点就是最近公共祖先。
5. 如果只有一边找到了，就返回找到的那个。

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    // 情况 1：遇到空节点或等于 p、q 之一，直接返回
    if root == nil || root == p || root == q {
        return root
    }

    // 情况 2：递归查找左右子树
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    // 情况 3：p 和 q 分别在左右子树，当前节点是 LCA
    if left != nil && right != nil {
        return root
    }

    // 情况 4：p 和 q 都在同一侧，往那一侧返回
    if left != nil {
        return left
    }
    return right
}

快乐数，每一位平方求和，循环操作是否可以变为1

快乐数的定义如下：

对一个正整数进行如下操作：

1. 将其每一位数字取出平方后相加，得到一个新的数字；
2. 不断重复这个过程；
3. 如果最终结果是 1，则这个数是快乐数；
4. 如果陷入循环，永远无法得到 1，则不是快乐数。

19 → 1^2 + 9^2 = 82  
82 → 8^2 + 2^2 = 68  
68 → 6^2 + 8^2 = 100  
100 → 1^2 + 0^2 + 0^2 = 1  快乐数

核心思想：循环检测

因为可能出现“无限循环”，我们需要判断是否进入了之前出现过的数字循环。可以用：

• Set（map[int]bool） 存储出现过的数字，如果重复了 → 说明进入循环。
• 或者用“快慢指针”检测循环（类 Floyd 判圈算法）

func isHappy(n int) bool {
    seen := make(map[int]bool)

    for n != 1 && !seen[n] {
        seen[n] = true
        n = digitSquareSum(n)
    }

    return n == 1
}

// 计算一个数字的每一位的平方和
func digitSquareSum(n int) int {
    sum := 0
    for n > 0 {
        digit := n % 10
        sum += digit * digit
        n /= 10
    }
    return sum
}

无重复字符的最长子串

核心解题思路：滑动窗口 + 哈希表

我们使用一个 滑动窗口 来记录当前无重复字符的子串，并利用一个 哈希表（map）来记录每个字符最后出现的位置。

解题步骤：

1. 定义两个指针 left 和 right 表示窗口的左右边界；
2. 遍历字符串 s：
3. 如果当前字符曾在 left 右边出现过，就将 left 移到上次重复字符的下一个位置；
4. 更新当前字符的最新位置；
5. 更新最长子串长度 maxLen = max(maxLen, right - left + 1)。

举例说明

字符串：abcabcbb

• 窗口变化如下：
• a → ab → abc → 遇到 a，left 移动 → bca → bcab → bca → cab → ab → b
• 最长无重复子串是 abc，长度为 3

func lengthOfLongestSubstring(s string) int {
    lastIndex := make(map[byte]int) // 存储字符最后出现位置
    maxLen := 0
    left := 0

    for right := 0; right < len(s); right++ {
        ch := s[right]
        if idx, ok := lastIndex[ch]; ok && idx >= left {
            // 重复字符在当前窗口内，移动 left
            left = idx + 1
        }

        // 更新字符位置
        lastIndex[ch] = right

        // 更新最长长度
        if right-left+1 > maxLen {
            maxLen = right - left + 1
        }
    }

    return maxLen
}

复杂度分析

最长回文字符串

中心扩展法原理

一个回文串从“中间”向两边对称展开，因此我们可以以每个字符为中心进行扩展检查。

需要注意：回文串有奇数中心（如 "aba"）和偶数中心（如 "abba"）两种情况。

输入: "babad"
输出: "bab" 或 "aba"

输入: "cbbd"
输出: "bb"

func longestPalindrome(s string) string {
    if len(s) < 2 {
        return s
    }

    start, end := 0, 0

    for i := 0; i < len(s); i++ {
        len1 := expandAroundCenter(s, i, i)     // 奇数中心
        len2 := expandAroundCenter(s, i, i+1)   // 偶数中心
        maxLen := max(len1, len2)

        if maxLen > end-start {
            start = i - (maxLen-1)/2
            end = i + maxLen/2
        }
    }

    return s[start : end+1]
}

func expandAroundCenter(s string, left, right int) int {
    for left >= 0 && right < len(s) && s[left] == s[right] {
        left--
        right++
    }
    return right - left - 1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

轮转数组

给定一个数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

三次反转法思路

举例：[1,2,3,4,5,6,7]，k=3

1. 反转整个数组：[7,6,5,4,3,2,1]
2. 反转前 k 个元素：[5,6,7,4,3,2,1]
3. 反转后 n-k 个元素：[5,6,7,1,2,3,4]

这样我们完成了右旋转！

func rotate(nums []int, k int) {
    n := len(nums)
    k = k % n // 防止 k > n

    reverse(nums, 0, n-1)
    reverse(nums, 0, k-1)
    reverse(nums, k, n-1)
}

func reverse(nums []int, start, end int) {
    for start < end {
        nums[start], nums[end] = nums[end], nums[start]
        start++
        end--
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

最小覆盖子串

给你两个字符串 s 和 t，返回 s 中最短的子串，它包含了 t 中的所有字符（包括重复字符）。如果不存在这样的子串，返回空字符串 ""。

输入: s = "ADOBECODEBANC", t = "ABC"
输出: "BANC"

滑动窗口 + 哈希表计数

• 我们要找到一个最小的窗口 window，使得其中包含 t 所有字符（可以乱序）。
• 用两个哈希表：
• need：统计 t 中每个字符出现的次数。
• window：当前滑动窗口中每个字符出现的次数。
• 用两个指针 left 和 right 表示窗口的左右边界。
• 用一个变量 valid 表示有多少个字符的出现次数满足 need 要求。

func minWindow(s string, t string) string {
    if len(s) == 0 || len(t) == 0 {
        return ""
    }

    need := make(map[byte]int)
    window := make(map[byte]int)

    for i := 0; i < len(t); i++ {
        need[t[i]]++
    }

    left, right := 0, 0
    valid := 0
    start := 0
    minLen := len(s) + 1

    for right < len(s) {
        c := s[right]
        right++

        if need[c] > 0 {
            window[c]++
            if window[c] == need[c] {
                valid++
            }
        }

        // 所有字符都满足了
        for valid == len(need) {
            // 更新最小子串
            if right-left < minLen {
                start = left
                minLen = right - left
            }

            d := s[left]
            left++

            if need[d] > 0 {
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
        }
    }

    if minLen == len(s)+1 {
        return ""
    }
    return s[start : start+minLen]
}

时间复杂度分析

• 时间复杂度：O(n)，其中 n 是 s 的长度，每个字符最多进出窗口一次。
• 空间复杂度：O(|t|)，用于记录字符频次的哈希表。

两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

示例：

输入：1 -> 2 -> 3 -> 4
输出：2 -> 1 -> 4 -> 3

要求：

• 你不能仅仅改变节点内部的值，而是需要实际交换节点

迭代（Dummy Node 方式）

• 用 dummy 节点简化头节点交换
• 每次迭代交换 first 和 second 两个节点
• 更新前后指针保持链表连接

func swapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    prev := dummy

    for head != nil && head.Next != nil {
        first := head
        second := head.Next

        // 交换
        prev.Next = second
        first.Next = second.Next
        second.Next = first

        // 移动指针
        prev = first
        head = first.Next
    }

    return dummy.Next
}

时间复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

在只有 3 种数的 1000 个数中快速排序（荷兰国旗问题）

数组中只包含三种元素，例如：0, 1, 2（或 'red', 'white', 'blue'），你要对其排序（按数值大小或颜色顺序）。

三指针一次遍历法（荷兰国旗）

只用一趟遍历，使用三个指针将数组分成：

• [0, low)：放置的是第 1 类（如 0）
• [low, mid)：是第 2 类（如 1）
• [high+1, end]：是第 3 类（如 2）

func sortColors(nums []int) {
    low, mid, high := 0, 0, len(nums)-1

    for mid <= high {
        switch nums[mid] {
        case 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low++
            mid++
        case 1:
            mid++
        case 2:
            nums[mid], nums[high] = nums[high], nums[mid]
            high--
        }
    }
}

时间复杂度：

• 一趟遍历 O(n)
• 空间 O(1)

长度为奇数的数组中快速找到中位数

给你一个长度为奇数的数组，找其中的第 k 小数（k = n/2），即中位数
不能用完整排序（O(n log n)）
要求 O(n) 时间复杂度

快排的变种 - 快速选择（QuickSelect）

QuickSelect 是基于快速排序的 partition 思想，每次只递归需要的那一边。

func findMedian(nums []int) int {
    k := len(nums) / 2
    return quickSelect(nums, 0, len(nums)-1, k)
}

func quickSelect(nums []int, left, right, k int) int {
    if left == right {
        return nums[left]
    }

    pivot := nums[right]
    i := left
    for j := left; j < right; j++ {
        if nums[j] < pivot {
            nums[i], nums[j] = nums[j], nums[i]
            i++
        }
    }
    nums[i], nums[right] = nums[right], nums[i]

    if i == k {
        return nums[i]
    } else if i < k {
        return quickSelect(nums, i+1, right, k)
    } else {
        return quickSelect(nums, left, i-1, k)
    }
}

时间复杂度：

• 平均时间复杂度：O(n)
• 最坏情况：O(n^2)（但可优化为 O(n) 使用随机化 pivot）

乘积最大子数组（Maximum Product Subarray

给你一个整数数组 nums，请你找出数组中乘积最大的连续子数组（至少包含一个数），并返回该子数组所对应的乘积。

输入: nums = [2,3,-2,4]
状态变化：
i=0: max=2, min=2
i=1: max=6, min=3
i=2: max=-2, min=-12
i=3: max=4, min=-48
最大值是 6

返回 6

动态规划（DP）

核心思想：

由于乘法中负负得正，且可能存在 0，因此我们需要在每一步记录：

• 当前最大乘积 maxProd
• 当前最小乘积 minProd

它们在遇到负数时可能发生翻转，因此每一步都要：

maxProd[i] = max(nums[i], nums[i]*maxProd[i-1], nums[i]*minProd[i-1])
minProd[i] = min(nums[i], nums[i]*maxProd[i-1], nums[i]*minProd[i-1])

然后更新结果为历史最大乘积。

func maxProduct(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    maxProd, minProd := nums[0], nums[0]
    result := nums[0]

    for i := 1; i < len(nums); i++ {
        cur := nums[i]

        tempMax := max(cur, maxProd*cur, minProd*cur)
        tempMin := min(cur, maxProd*cur, minProd*cur)

        maxProd = tempMax
        minProd = tempMin

        result = max(result, maxProd)
    }

    return result
}

func max(a, b, c int) int {
    if a > b {
        if a > c {
            return a
        }
        return c
    }
    if b > c {
        return b
    }
    return c
}

func min(a, b, c int) int {
    if a < b {
        if a < c {
            return a
        }
        return c
    }
    if b < c {
        return b
    }
    return c
}

时间 & 空间复杂度

• 时间复杂度：O(n) —— 只需一次遍历
• 空间复杂度：O(1) —— 常量空间记录 max/min

区间合并（Merge Intervals）

给定多个区间 [[start1, end1], [start2, end2], ...]，请将所有有交集的区间合并，输出合并后的非重叠区间列表。

示例：

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]

解题思路：排序 + 遍历合并（贪心）

先按照每个区间的起点 start 升序排序

1. 使用一个 merged 列表维护合并结果
2. 遍历每个区间：
3. 如果当前区间的起点 start 大于 merged 最后一个区间的 end，则没有重叠，直接添加
4. 否则，更新 merged 最后一个区间的 end 为 max(end, 当前end)，表示合并

import "sort"

func merge(intervals [][]int) [][]int {
    if len(intervals) == 0 {
        return [][]int{}
    }

    // Step 1: 按起始位置排序
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    merged := [][]int{}
    merged = append(merged, intervals[0])

    for i := 1; i < len(intervals); i++ {
        last := merged[len(merged)-1]
        curr := intervals[i]

        if curr[0] <= last[1] {
            // 有重叠，合并区间
            last[1] = max(last[1], curr[1])
            merged[len(merged)-1] = last
        } else {
            // 无重叠，直接添加
            merged = append(merged, curr)
        }
    }

    return merged
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

时间与空间复杂度

应用场景拓展

• 日程冲突检测（如会议时间）
• 合并 IP 区段、时间段、资源段等
• 线段树/区间树中的预处理优化

单链表删除重复元素

给定一个 无序的单链表，删除所有重复元素，使每个元素只出现一次。

输入: 1 -> 2 -> 3 -> 2 -> 4 -> 1
输出: 3 -> 4

思路：

1. 第一次遍历，用 map[int]int 统计每个值出现的次数。
2. 第二次遍历，构造一个新链表，只保留出现次数为 1 的节点。

func deleteDuplicatesUnsorted(head *ListNode) *ListNode {
    freq := make(map[int]int)
    for curr := head; curr != nil; curr = curr.Next {
        freq[curr.Val]++
    }

    dummy := &ListNode{Next: head}
    prev := dummy
    curr := head

    for curr != nil {
        if freq[curr.Val] > 1 {
            prev.Next = curr.Next // 删除
        } else {
            prev = curr
        }
        curr = curr.Next
    }

    return dummy.Next
}

复杂度分析

时间复杂度O(n)

空间复杂度O(n)（哈希表）