Week 15 @ 2025 算法周记【随机 + 队列】

1 随机
- 1.1 LC 382. Linked List Random Node 链表随机节点
- 1.2 LC 398. Random Pick Index
2 队列
- 2.1 LC 933. Number of Recent Calls
- 2.2 LC 622. Design Circular Queue 设计循环队列

随机

LC 382. Linked List Random Node 链表随机节点

https://leetcode.com/problems/linked-list-random-node/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
type Solution struct {
    head *ListNode
}


func Constructor(head *ListNode) Solution {
    return Solution {
        head: head,
    }
}


func (this *Solution) GetRandom() int {
    v := -1

    i := 0
    for h := this.head; h != nil; h = h.Next {
        i++

        if rand.Intn(i) == 0 {
            v = h.Val
        }
    }

    return v
}


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

LC 398. Random Pick Index

https://leetcode.com/problems/random-pick-index/

预处理

type Solution struct {
    numsMap map[int][]int
}


func Constructor(nums []int) Solution {
    numsMap := make(map[int][]int, len(nums))

    for i, v := range nums {
        numsMap[v] = append(numsMap[v], i)
    }

    return Solution {
        numsMap: numsMap,
    }
}


func (this *Solution) Pick(target int) (result int) {
    indexes := this.numsMap[target]

    return indexes[rand.Intn(len(indexes))]
}


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

水塘抽样（TLE）

type Solution struct {
    nums []int
}


func Constructor(nums []int) Solution {
    return Solution {
        nums: nums,
    }
}


func (this *Solution) Pick(target int) (result int) {
    k := 0
    for i, v := range this.nums {
        if v != target {
            continue
        }
        k++

        if rand.Intn(k) == 0 {
            result = i
        }
    }

    return
}


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

队列

LC 933. Number of Recent Calls

https://leetcode.com/problems/number-of-recent-calls/description/

type RecentCounter struct {
    requests []int
}


func Constructor() RecentCounter {
    return RecentCounter {
        requests: []int{},
    }
}


func (this *RecentCounter) Ping(t int) int {
    this.requests = append(this.requests, t)

    start := 0
    for i := 0; i < len(this.requests); i++ {
        if this.requests[i] < t - 3000 {
            start = i+1
        }
    }

    this.requests = this.requests[start:]
    return len(this.requests)
}


/**
 * Your RecentCounter object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Ping(t);
 */

进一步强化「队列」属性

type RecentCounter struct {
    requests []int
}


func Constructor() RecentCounter {
    return RecentCounter {
        requests: []int{},
    }
}


func (this *RecentCounter) Ping(t int) int {
    this.requests = append(this.requests, t)

    for this.requests[0] < t - 3000 {
        this.requests = this.requests[1:]
    }

    return len(this.requests)
}


/**
 * Your RecentCounter object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Ping(t);
 */

LC 622. Design Circular Queue 设计循环队列

https://leetcode.com/problems/design-circular-queue/description/

type MyCircularQueue struct {
    els []int
    head int
    n int
    maxN int
}


func Constructor(k int) MyCircularQueue {
    return MyCircularQueue {
        els: make([]int, k),
        head: -1,
        n: 0,
        maxN: k,
    }
}


func (this *MyCircularQueue) EnQueue(value int) bool {
    if this.n == this.maxN {
        return false
    }

    if this.n == 0 {
        this.head = 0
        this.els[0] = value
        this.n = 1
        return true
    }

    nextIndex := (this.head + this.n) % this.maxN
    this.els[nextIndex] = value
    this.n++

    return true
}


func (this *MyCircularQueue) DeQueue() bool {
    if this.n == 0 {
        return false
    }

    this.n--
    this.head = (this.head + 1) % this.maxN
    return true
}


func (this *MyCircularQueue) Front() int {
    if this.n == 0 {
        return -1
    }

    return this.els[this.head]
}

func (this *MyCircularQueue) Rear() int {
    if this.n == 0 {
        return -1
    }


    i := (this.head + this.n - 1) % this.maxN

    return this.els[i]
}


func (this *MyCircularQueue) IsEmpty() bool {
    return this.n == 0
}


func (this *MyCircularQueue) IsFull() bool {
    return this.n == this.maxN
}


/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * obj := Constructor(k);
 * param_1 := obj.EnQueue(value);
 * param_2 := obj.DeQueue();
 * param_3 := obj.Front();
 * param_4 := obj.Rear();
 * param_5 := obj.IsEmpty();
 * param_6 := obj.IsFull();
 */

同时记录 first & last

import "errors"

// 底层用数组实现队列
type ArrayQueue[E any] struct {
    size  int
    data  []E
    first int
    last  int
}

const INIT_CAP = 2

func NewArrayQueue[E any](initCap int) *ArrayQueue[E] {
    return &ArrayQueue[E]{
        size:  0,
        data:  make([]E, initCap),
        first: 0,
        last:  0,
    }
}

func NewArrayQueueDefault[E any]() *ArrayQueue[E] {
    // 不传参数，默认大小为 INIT_CAP
    return NewArrayQueue[E](INIT_CAP)
}

// 增
func (q *ArrayQueue[E]) Enqueue(e E) {
    if q.size == len(q.data) {
        q.resize(q.size * 2)
    }

    q.data[q.last] = e
    q.last++
    if q.last == len(q.data) {
        q.last = 0
    }

    q.size++
}

// 删
func (q *ArrayQueue[E]) Dequeue() (E, error) {
    if q.isEmpty() {
        var zero E
        return zero, errors.New("no such element")
    }

    if q.size == len(q.data)/4 {
        q.resize(len(q.data) / 2)
    }

    oldVal := q.data[q.first]
    var zero E
    q.data[q.first] = zero
    q.first++
    if q.first == len(q.data) {
        q.first = 0
    }

    q.size--
    return oldVal, nil
}

func (q *ArrayQueue[E]) resize(newCap int) {
    temp := make([]E, newCap)

    // first ----- last
    // --- last    first ---
    for i := 0; i < q.size; i++ {
        temp[i] = q.data[(q.first+i)%len(q.data)]
    }

    q.first = 0
    q.last = q.size
    q.data = temp
}

// 查
func (q *ArrayQueue[E]) PeekFirst() (E, error) {
    if q.isEmpty() {
        var zero E
        return zero, errors.New("no such element")
    }
    return q.data[q.first], nil
}

func (q *ArrayQueue[E]) PeekLast() (E, error) {
    if q.isEmpty() {
        var zero E
        return zero, errors.New("no such element")
    }
    if q.last == 0 {
        return q.data[len(q.data)-1], nil
    }
    return q.data[q.last-1], nil
}

func (q *ArrayQueue[E]) Size() int {
    return q.size
}

func (q *ArrayQueue[E]) isEmpty() bool {
    return q.size == 0
}

type MyCircularQueue struct {
    q      *ArrayQueue[int]
    maxCap int
}

func Constructor(k int) MyCircularQueue {
    return MyCircularQueue{
        q:      NewArrayQueue[int](k),
        maxCap: k,
    }
}

func (cq *MyCircularQueue) EnQueue(value int) bool {
    if cq.q.Size() == cq.maxCap {
        return false
    }
    cq.q.Enqueue(value)
    return true
}

func (cq *MyCircularQueue) DeQueue() bool {
    if cq.q.isEmpty() {
        return false
    }
    _, _ = cq.q.Dequeue()
    return true
}

func (cq *MyCircularQueue) Front() int {
    if cq.q.isEmpty() {
        return -1
    }
    val, _ := cq.q.PeekFirst()
    return val
}

func (cq *MyCircularQueue) Rear() int {
    if cq.q.isEmpty() {
        return -1
    }
    val, _ := cq.q.PeekLast()
    return val
}

func (cq *MyCircularQueue) IsEmpty() bool {
    return cq.q.isEmpty()
}

func (cq *MyCircularQueue) IsFull() bool {
    return cq.q.Size() == cq.maxCap
}