1 栈
- 1.2 随机
  - 1.2.1 LC 528. Random Pick with Weight 按权重随机选择
  - 1.2.2 LC 870. Advantage Shuffle 优势洗牌
  - 1.2.3 LC 384. 打乱数组

栈

LC 895. Maximum Frequency Stack 最大频率栈

https://leetcode.com/problems/maximum-frequency-stack/description/

type FreqStack struct {
    maxFreq int
    valToFreq map[int]int
    freqToVals map[int][]int
}


func Constructor() FreqStack {
    return FreqStack{
        maxFreq: 0,
        valToFreq: map[int]int{},
        freqToVals: map[int][]int{},
    }
}


func (this *FreqStack) Push(val int)  {
    freq := this.valToFreq[val] + 1
    this.valToFreq[val] = freq
    this.freqToVals[freq] = append(this.freqToVals[freq], val)
    if freq > this.maxFreq {
        this.maxFreq = freq
    }
}


func (this *FreqStack) Pop() int {
    val := pop(this.freqToVals, this.maxFreq)
    this.valToFreq[val]--
    if this.valToFreq[val] == 0 {
        delete(this.valToFreq, val)
    }
    if len(this.freqToVals[this.maxFreq]) == 0 {
        delete(this.freqToVals, this.maxFreq)
        this.maxFreq--
    }
    return val
}

func pop(m map[int][]int, k int) int {
    arr := m[k]

    n := len(arr)
    v := arr[n-1]
    arr = arr[:n-1]

    m[k] = arr

    return v
}

/**
 * Your FreqStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * param_2 := obj.Pop();
 */

LC 232. Implement Queue using Stacks 用栈实现队列

https://leetcode.com/problems/implement-queue-using-stacks/description/

type MyQueue struct {
    s1 []int
    s2 []int
}


func Constructor() MyQueue {
    return MyQueue{}
}


func (this *MyQueue) Push(x int)  {
    this.s1 = append(this.s1, x)
}


func (this *MyQueue) Pop() int {
    this.transform()
    return pop(&this.s2)
}


func (this *MyQueue) Peek() int {
    this.transform()
    return this.s2[len(this.s2) - 1]
}

func (this *MyQueue) transform() {
    if len(this.s2) == 0 {
        for len(this.s1) != 0 {
            val := pop(&this.s1)
            this.s2 = append(this.s2, val)
        }
    }
}

func (this *MyQueue) Empty() bool {
    return len(this.s1) == 0 && len(this.s2) == 0 
}

func pop(arr *[]int) int {
    n := len(*arr)
    val := (*arr)[n-1]
    *arr = (*arr)[:n-1]
    return val
}


/**
 * Your MyQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Peek();
 * param_4 := obj.Empty();
 */

LCR 125. 图书整理 II

https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/description/

type CQueue struct {
    s1 []int
    s2 []int
}


func Constructor() CQueue {
    return CQueue{}
}


func (this *CQueue) AppendTail(value int)  {
    this.s1 = append(this.s1, value)
}


func (this *CQueue) DeleteHead() int {
    this.transform()

    if len(this.s2) == 0 {
        return -1
    }
    
    return pop(&this.s2)
}

func (this *CQueue) transform() {
    if len(this.s2) == 0 {
        for len(this.s1) != 0 {
            val := pop(&this.s1)
            this.s2 = append(this.s2, val)
        }
    }
}

func pop(arr *[]int) int {
    n := len(*arr)
    val := (*arr)[n-1]
    *arr = (*arr)[:n-1]
    return val
}

/**
 * Your CQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AppendTail(value);
 * param_2 := obj.DeleteHead();
 */

随机

LC 528. Random Pick with Weight 按权重随机选择

https://leetcode.com/problems/random-pick-with-weight/description/

type Solution struct {
    total int
    preSum []int
}


func Constructor(w []int) Solution {
    preSum := make([]int, len(w))
    preSum[0] = w[0]

    for i := 1; i < len(w); i++ {
        preSum[i] = preSum[i-1] + w[i]
    }

    total := preSum[len(w) - 1]

    return Solution {
        total: total,
        preSum: preSum,
    }
}


func (this *Solution) PickIndex() int {
    return sort.SearchInts(this.preSum, this.rand())
}

func (this *Solution) rand() int {
    return rand.Intn(this.total) + 1
}


/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(w);
 * param_1 := obj.PickIndex();
 */

LC 870. Advantage Shuffle 优势洗牌

https://leetcode.com/problems/advantage-shuffle/

func advantageCount(nums1 []int, nums2 []int) []int {
    n := len(nums2)
    sort.Ints(nums1)

    q2 := make([]el, n)
    for i, v := range nums2 {
        q2[i] = el{v, i}
    }
    sort.Slice(q2, func(i, j int) bool {
        return q2[i].val > q2[j].val
    })

    result := make([]int, n)
    for _, vv := range q2 {
        i, v := vv.index, vv.val

        if nums1[len(nums1)-1] > v {
            result[i] = nums1[len(nums1)-1]
            nums1 = nums1[:len(nums1)-1]
        } else {
            result[i] = nums1[0]
            nums1 = nums1[1:]
        }
    }

    return result
}

type el struct {
    val int
    index int
}

LC 384. 打乱数组

https://leetcode.com/problems/shuffle-an-array/description/

type Solution struct {
    nums []int
    original []int
}


func Constructor(nums []int) Solution {
    return Solution {
        nums: nums,
        original: append([]int(nil), nums...),
    }
}


func (this *Solution) Reset() []int {
    copy(this.nums, this.original)

    return this.nums
}


func (this *Solution) Shuffle() []int {
    nums := this.nums

    for i := 0; i < len(nums); i++ {
        j := i + rand.Intn(len(nums)-i)

        nums[i], nums[j] = nums[j], nums[i]
    }

    return nums
}


/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.Reset();
 * param_2 := obj.Shuffle();
 */

知识库

Week 14 @ 2025 算法周记【栈 + 随机】

栈

LC 895. Maximum Frequency Stack 最大频率栈

LC 232. Implement Queue using Stacks 用栈实现队列

LCR 125. 图书整理 II

随机

LC 528. Random Pick with Weight 按权重随机选择

LC 870. Advantage Shuffle 优势洗牌

LC 384. 打乱数组

Related content