LeetCode解いた時の考え方
esakaLeetCodeで解いた問題の覚え書き色々
言語はGoでいつもやってる。
ホワイトボードコーディングを想定しているため
- 競プロやるときはいつもC++だけど、マクロ使いまくりなのでホワイトボードコーディングでできる自身がない
- Pythonはあまり好きじゃないし、慣れてない
- Goは普段業務や趣味でも触ってて、構文慣れてるので、競プロだと結構厳しい印象だけど、LeetCodeだとさほど困ることはない
esakaLRU-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
}
}
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)]
}