栈

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();
 */