Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitc194647

Browse files
committed
update 146 Solution.go
1 parent58bb452 commitc194647

File tree

7 files changed

+64
-2534
lines changed

7 files changed

+64
-2534
lines changed

‎leetcode/1-100/0072.Edit-Distance/Solution.go‎

Lines changed: 0 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,5 @@
11
package Solution
22

3-
import"fmt"
4-
53
/*
64
设状态为dp[i][j],表示A[0,i]与B[0,j]的最小编辑距离，对应形式分别为str1c,str2d
75
如果c==d,f[i][j]=f[i-1][j-1]
@@ -41,13 +39,6 @@ func minDistance(word1 string, word2 string) int {
4139
returndp[m][n]
4240
}
4341

44-
funcPrint(arr [][]int) {
45-
fori:=0;i<len(arr);i++ {
46-
fmt.Println(arr[i])
47-
}
48-
fmt.Println()
49-
}
50-
5142
funcmin(x,yint)int {
5243
ifx>y {
5344
returny
Lines changed: 64 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -1,50 +1,82 @@
11
package Solution
22

3-
import (
4-
"container/list"
5-
"fmt"
6-
)
7-
83
typeLRUCachestruct {
9-
Capacityint
10-
Data*list.List
11-
//*list.List
4+
sizeint
5+
capacityint
6+
cachemap[int]*DLinkedNode
7+
head,tail*DLinkedNode
8+
}
9+
10+
typeDLinkedNodestruct {
11+
key,valueint
12+
prev,next*DLinkedNode
13+
}
14+
15+
funcinitDLinkedNode(key,valueint)*DLinkedNode {
16+
return&DLinkedNode{
17+
key:key,
18+
value:value,
19+
}
1220
}
1321

1422
funcConstructor(capacityint)LRUCache {
15-
lru:=LRUCache{
16-
Capacity:capacity,
17-
Data:list.New(),
23+
l:=LRUCache{
24+
cache:map[int]*DLinkedNode{},
25+
head:initDLinkedNode(0,0),
26+
tail:initDLinkedNode(0,0),
27+
capacity:capacity,
1828
}
19-
returnlru
29+
l.head.next=l.tail
30+
l.tail.prev=l.head
31+
returnl
2032
}
2133

2234
func (this*LRUCache)Get(keyint)int {
23-
fore:=this.Data.Front();e!=nil;e=e.Next() {
24-
25-
//fmt.Println(key, e.Value.(list.Element).Value.(map[int]int)[key])
26-
27-
ifv,ok:=e.Value.(list.Element).Value.(map[int]int)[key];ok {
28-
this.Data.MoveBefore(e,this.Data.Front())
29-
returnv
30-
}
35+
if_,ok:=this.cache[key];!ok {
36+
return-1
3137
}
32-
return-1
38+
node:=this.cache[key]
39+
this.moveToHead(node)
40+
returnnode.value
3341
}
3442

3543
func (this*LRUCache)Put(keyint,valueint) {
36-
this.Data.PushFront(
37-
list.Element{
38-
Value:map[int]int{key:value},
39-
},
40-
)
41-
ifthis.Data.Len()>this.Capacity {
42-
this.Data.Remove(this.Data.Back())
44+
if_,ok:=this.cache[key];!ok {
45+
node:=initDLinkedNode(key,value)
46+
this.cache[key]=node
47+
this.addToHead(node)
48+
this.size++
49+
ifthis.size>this.capacity {
50+
removed:=this.removeTail()
51+
delete(this.cache,removed.key)
52+
this.size--
53+
}
54+
}else {
55+
node:=this.cache[key]
56+
node.value=value
57+
this.moveToHead(node)
4358
}
4459
}
4560

46-
func (this*LRUCache)Print() {
47-
fore:=this.Data.Front();e!=nil;e=e.Next() {
48-
fmt.Println(e.Value.(list.Element).Value.(map[int]int))
49-
}
61+
func (this*LRUCache)addToHead(node*DLinkedNode) {
62+
node.prev=this.head
63+
node.next=this.head.next
64+
this.head.next.prev=node
65+
this.head.next=node
66+
}
67+
68+
func (this*LRUCache)removeNode(node*DLinkedNode) {
69+
node.prev.next=node.next
70+
node.next.prev=node.prev
71+
}
72+
73+
func (this*LRUCache)moveToHead(node*DLinkedNode) {
74+
this.removeNode(node)
75+
this.addToHead(node)
76+
}
77+
78+
func (this*LRUCache)removeTail()*DLinkedNode {
79+
node:=this.tail.prev
80+
this.removeNode(node)
81+
returnnode
5082
}

‎leetcode/101-200/0146.LRU-Cache/Solution_test.go‎

Lines changed: 0 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -2,35 +2,9 @@ package Solution
22

33
import (
44
"fmt"
5-
"reflect"
6-
"strconv"
75
"testing"
86
)
97

10-
funcTestSolution(t*testing.T) {
11-
//测试用例
12-
cases:= []struct {
13-
namestring
14-
inputsint
15-
expectbool
16-
}{
17-
{"TestCase",1,true},
18-
{"TestCase",1,true},
19-
{"TestCase",1,false},
20-
}
21-
22-
//开始测试
23-
fori,c:=rangecases {
24-
t.Run(c.name+" "+strconv.Itoa(i),func(t*testing.T) {
25-
got:=Constructor(c.inputs)
26-
if!reflect.DeepEqual(got,c.expect) {
27-
//t.Fatalf("expected: %v, but got: %v, with inputs: %v",
28-
//c.expect, got, c.inputs)
29-
}
30-
})
31-
}
32-
}
33-
348
funcTestConstructor(t*testing.T) {
359
lru:=Constructor(2)
3610
fmt.Println(lru.Get(2))
@@ -40,19 +14,8 @@ func TestConstructor(t *testing.T) {
4014

4115
lru.Put(1,5)
4216
lru.Put(1,2)
43-
lru.Print()
4417

4518
fmt.Println(lru.Get(1))
4619
fmt.Println(lru.Get(2))
4720

4821
}
49-
50-
//压力测试
51-
funcBenchmarkSolution(b*testing.B) {
52-
53-
}
54-
55-
//使用案列
56-
funcExampleSolution() {
57-
58-
}
-10.6 KB
Binary file not shown.
-4.58 KB
Binary file not shown.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp