LeetCodeで解いた問題の覚え書き色々

言語はGoでいつもやってる。
ホワイトボードコーディングを想定しているため

競プロやるときはいつもC++だけど、マクロ使いまくりなのでホワイトボードコーディングでできる自身がない
Pythonはあまり好きじゃないし、慣れてない
Goは普段業務や趣味でも触ってて、構文慣れてるので、競プロだと結構厳しい印象だけど、LeetCodeだとさほど困ることはない

esaka

LRU-Cacheの解法覚え書き

有名な？LRU Cache問題を解いた

問題文概略

以下のレシーバーをもつLRUCache構造体を作成せよ

LRUCache(int capacity) : 与えられたcapacityでLRUCacheを構築する.
int get(int key) : 与えられたkeyが存在する場合はkeyと対応する値を返却する、存在しない場合は-1を返す
void put(int key, int value) : keyが既に存在する場合は値を更新する、存在しない場合は新しくkey-valのペアを追加する。またこの際capacityを超える場合は、もっとも使用頻度が低いキーを削除する

使用頻度が低いは、LRUCacheに入ってるkeyのうちもっとも古く操作(put or get)されたものをさす

追加課題

get, putともにO(1)で実装できるか？

考えたこと

とりあえず、mapを使うのは確定
問題は使用頻度の管理方法,　もっとも古いのを1つ持っておくだけではだめ、その古いのが操作された際に、次に古いのを使わないといけない。

では、すべてのkey-valの使用順序を配列などで管理するとする。
これも難しい.例えば以下のようなLRU Cacheの状態があったとする、配列の先頭ほど古く、末尾ほど最近使われたとする

[(1, 5), (3, 5), (4, 0), (11, 2)]

これでget(3)を呼ぶとする、すると配列は次のように変更される

[(1, 5), (4, 0), (11, 2), (3, 5)]

インデックス1にあった要素を末尾に移動し、インデックス1以降にあった要素を1つづつ前にずらしている
これは配列が苦手な操作、最悪計算量がO(N)かかってしまう。
一応できるけど、get, putのたびにこれをやるのは非効率すぎる。

ではどうするか、こういう操作が得意なContainerで双方向連結リストがある

先程の配列を双方向連結リストで表現してみる

(key: 1, val: 5, 前の要素のkey: nil, 次の要素のkey: 3) -> (key: 3, val: 5, 前の要素のkey: 1, 次の要素のkey: 4) -> (key: 4, val: 0, 前の要素のkey: 3 次の要素のkey: 11) -> (key: 11, val: 2, 前の要素のkey: 4, 次の要素のkey: nil)

先程と同じようにget(3)をしたら, 要素をそれぞれ次のように変えていく

(key: 1, val: 5, 前の要素のkey: nil, 次の要素のkey: 3) => (key: 1, val: 5, 前の要素のkey: nil, 次の要素のkey: 4)
(key: 3, val: 5, 前の要素のkey: 1, 次の要素のkey: 4) => key: 3, val: 5, 前の要素のkey: 11, 次の要素のkey: nil)
(key: 4, val: 0, 前の要素のkey: 3 次の要素のkey: 11) => (key: 4, val: 0, 前の要素のkey: 1, 次の要素のkey: 11)
(key: 11, val: 2, 前の要素のkey: 4, 次の要素のkey: nil) => (key: 11, val: 2, 前の要素のkey: 4, 次の要素のkey: 5)

この例だと全てのノードを更新してるように見えるが、実際は操作対象のノードの前の要素・次の要素へのポインタ, 操作対象の前のノードの次の要素へのポインタ, 操作対象の次のノードの前の要素へのポインタ, 最新ノードの次の要素へのポインタの4ノードの操作で済む

これならO(1)で処理できる。あとはこれらの双方向連結リストの先頭(一番使用頻度が低いkey-val)とkeyが指定された際に対応するノードのポインタを返せるようにkeyをkey, valをノードへのポインタとするmapの2つをフィールドとして持てば実現できる

最終的な実装は以下(ちょっと無駄は多いかも)

// doubly-linked list
type DoublyLinkedList struct {
    Val int
    Prev *DoublyLinkedList
    Next *DoublyLinkedList
}


type LRUCache struct {
    capacity int
    cacheVal map[int]int
    index map[int]*DoublyLinkedList
    top *DoublyLinkedList
    tail *DoublyLinkedList
}


func Constructor(capacity int) LRUCache {
    return LRUCache{capacity, map[int]int{}, map[int]*DoublyLinkedList{}, nil, nil}
}


func (this *LRUCache) Get(key int) int {
    if v, ok := this.cacheVal[key]; ok {
        // update index
        this.updateIndex(key)
        return v
    } else {
        return -1
    }
}


func (this *LRUCache) Put(key int, value int)  {
    if _, ok := this.cacheVal[key]; ok {
        // update index
        this.updateIndex(key)
        // update val
        this.cacheVal[key] = value
    } else {
        this.cacheVal[key] = value
        if len(this.cacheVal) == 1 {
            this.top = &DoublyLinkedList{key, nil, nil}
            this.tail = this.top
            this.index[key] = this.top
        } else {
            tmpTail := &DoublyLinkedList{key, this.tail, nil}
            this.tail.Next = tmpTail
            this.tail = tmpTail
            this.index[key] = tmpTail
        }

        // tmpTail := &DoublyLinkedList{key, this.tail, nil}
        // this.tail = tmpTail
        // do evict if capcity over
        if len(this.cacheVal) > this.capacity {
            delete(this.cacheVal, this.top.Val)
            delete(this.index, this.top.Val)
            this.top = this.top.Next
        }
    }
}

func (this *LRUCache) updateIndex(key int) {
    now := this.index[key]
    if now == this.tail {
        // do nothing
        return
    }

    if now == this.top {
        this.top = now.Next
        this.top.Prev = nil
        now.Next = nil
        this.tail.Next = now
        now.Prev = this.tail
        this.tail = now
    } else {
        prev := now.Prev
        next := now.Next
        prev.Next = next
        next.Prev = prev


        this.tail.Next = now
        now.Prev = this.tail
        now.Next = nil
        this.tail = now
    }
}

esaka

Count of Smaller Numbers After Selfを解く

30分ほど考えてもナイーブな2重ループしか思いつかなかった。

HARDなんですよね。。

解説を探しながら解いてみる

アプローチ1: 二分探索木を使う (コーナーケースでTLEする）

これを参考にした

ポイントは以下

インデックス末尾から見ていく
二分探索木を構築する
木のノードには値と右・左へのリンクのほか、そのノードの値より小さいノード数を記録する

インデックス末尾から見ていく

これにより、あるインデックスでの値を確認した時点で、それまでに確認した値の中で、確認中の値より小さい個数を探せばいいと言える
(その後の値が、結果に影響しないようになる)

木のノードには値と右・左へのリンクのほか、そのノードの値より小さいノード数を記録する

この値を保持することで、例えばあるノードAの右側に新しくノードBが配置される（ノードAより大きい値）時、ノードBの以降のインデックスかつノードBより小さい値は、1(ノードA自身) + ノードAより小さい値　という感じで即座に出せる

コード

type BTNode struct {
    Val int
    LessThan int
    Right *BTNode
    Left *BTNode
}

func Insert(root *BTNode, val, index, sum int, result []int) *BTNode {
    if root == nil {
        result[index] = sum
        return &BTNode{
            Val: val,
            LessThan: 0,
            Right: nil,
            Left: nil,
        }
    }
    
    if val < root.Val {
        root.LessThan++
        root.Left = Insert(root.Left, val, index, sum, result)
    } else {
        if val != root.Val {
            root.Right = Insert(root.Right, val, index, sum + root.LessThan + 1, result)
        } else {
            root.Right = Insert(root.Right, val, index, sum + root.LessThan, result)
        }
    }
    
    return root
    
}


func countSmaller(nums []int) []int {
    var root *BTNode
    root = nil
    
    if len(nums) == 0 {
        return []int{}
    }
    
    result := make([]int, len(nums))
    
    for i := len(nums)-1 ; i >= 0 ; i-- {
        root = Insert(root, nums[i], i, 0, result)
    }
    
    return result
}

コーナケースだと間に合わない

二分木の一般的な問題だけど、処理時間は木の深さに依存する。木が完全二分木になっていれば目的の値までの到達はlogNで済むが、以下のようなコーナーケースの場合

[1,2,3,4,5,6,7,8.....99999, 100000]
[100000,99999,.....5,4,3,2,1]

ただの一直線のリストみたいになるので、目的の値までの到達がNになって、最終的な計算量もN^2になる。
実際、LeetCodeでもこのコーナケースがあって落ちる

アプローチ2: マージソートの応用

これだといいらしい
マージソートは計算量がN logN でこの中の処理で追加処理をしてあげることで、数が求めれる。具体的に見てみる

入力例をマージソートしたのは以下のようになる

分解して、マージしていく際に以下を行う

今見ている値の組み合わせの中でのインデックスのマージ前とマージ後を比較する
マージ後が右側に移動していれば、移動した分だけ、元々右側にいた値が自分より小さかったと言える。

実際に図示するとこんな感じ

コードはマージソートのコードとして以下のページを参考にした

ほとんど一緒（構造体スライスを使っている以外は）で、マージ部分だけ以下のようにして、今回のマージでの移動分を加算するようにしている。

func merge(left, right []*Node) []*Node {
    ret := []*Node{}
    //allIndecies := len(left) + len(right) - 1
    rightStart := len(left)
    
    nowIndex := 0
    
    for len(left) > 0 && len(right) > 0 {
        var x *Node
        if right[0].val >= left[0].val {
            x, left = left[0], left[1:]
            // Do Check
            addMoveSize(x, nowIndex, 0)
        } else {
            x, right = right[0], right[1:]
            // Do Check
            addMoveSize(x, nowIndex, rightStart)
        }
        ret = append(ret, x)
        nowIndex++
    }
...


func addMoveSize(node *Node, moveTo int, addIndex int) {
    node.nowIndex += addIndex
    if node.nowIndex < moveTo {
        ans[node.originalIndex] += moveTo-node.nowIndex
    }
    node.nowIndex = moveTo
}

コード全文

type Node struct {
    originalIndex int
    nowIndex int
    val int
}

var ans = make([]int, 100000+5)

func addMoveSize(node *Node, moveTo int, addIndex int) {
    node.nowIndex += addIndex
    if node.nowIndex < moveTo {
        ans[node.originalIndex] += moveTo-node.nowIndex
    }
    node.nowIndex = moveTo
}

func merge(left, right []*Node) []*Node {
    ret := []*Node{}
    //allIndecies := len(left) + len(right) - 1
    rightStart := len(left)
    
    nowIndex := 0
    
    for len(left) > 0 && len(right) > 0 {
        var x *Node
        if right[0].val >= left[0].val {
            x, left = left[0], left[1:]
            // Do Check
            addMoveSize(x, nowIndex, 0)
        } else {
            x, right = right[0], right[1:]
            // Do Check
            addMoveSize(x, nowIndex, rightStart)
        }
        ret = append(ret, x)
        nowIndex++
    }
    
    for len(left) > 0 {
        var x *Node
        x, left = left[0], left[1:]
        addMoveSize(x, nowIndex, 0)
        ret = append(ret, x)
        nowIndex++
    }
    
    for len(right) > 0 {
        var x *Node
        x, right = right[0], right[1:]
        addMoveSize(x, nowIndex, rightStart)
        ret = append(ret, x)
        nowIndex++
    }       
    return ret
} 

func sort(left, right []*Node) []*Node {
    if len(left) > 1 {
        l, r := split(left)
        left = sort(l, r)
    }
    if len(right) > 1 {
        l, r := split(right)
        right = sort(l, r)
    }
    
    ret := merge(left, right)
    return ret
}

func split(arr []*Node) (l, r []*Node) {
    l = arr[:len(arr)/2]
    r = arr[len(arr)/2:]
    return
}

func MergeSort(arr []*Node) {
    l, r := split(arr)
    sort(l, r)
}

func countSmaller(nums []int) []int {
    // 初期化, テストケース毎に共有されるので
    for i := range ans {
        ans[i] = 0
    }
    nodeNums := make([]*Node, len(nums))
    for i, v := range nums {
        nodeNums[i] = &Node{
            originalIndex: i,
            nowIndex: 0,
            val: v,
        }
    }
    MergeSort(nodeNums)
    
    return ans[:len(nums)]
}

このスクラップは2021/05/13にクローズされました