Skip to content

Commit c9fe0ea

Browse files
6boris6boris
committed
add 146 solution
1 parent c35405a commit c9fe0ea

File tree

5 files changed

+183
-1
lines changed

5 files changed

+183
-1
lines changed

‎SUMMARY-LIST.md

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,28 @@
11
# SUMMARY-LIST
22

33

4+
- Link List
5+
- [19. Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)
6+
- [83. Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list)
7+
- [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list)
8+
- [92. Reverse Linked List II](https://leetcode.com/problems/reverse-linked-list-ii)
9+
- [61. Rotate List](https://leetcode.com/problems/rotate-list)
10+
- [143. Reorder List](https://leetcode.com/problems/reorder-list)
11+
- [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists)
12+
- [160. Intersection of Two Linked Lists](https://leetcode.com/problems/intersection-of-two-linked-lists)
13+
- [141. Linked List Cycle](https://leetcode.com/problems/intersection-of-two-linked-lists)
14+
- [147. Insertion Sort List](https://leetcode.com/problems/intersection-of-two-linked-lists)
15+
- [142. Linked List Cycle II](https://leetcode.com/problems/intersection-of-two-linked-lists)
16+
- [148. Sort List](https://leetcode.com/problems/intersection-of-two-linked-lists)
17+
- [146. LRU Cache 7](https://leetcode.com/problems/intersection-of-two-linked-lists)
18+
19+
- DFS
20+
21+
- Tree
22+
23+
- DP
24+
25+
- QUEUE/STACK
26+
27+
- Hash
28+

‎src/0146.LRU-Cache/README.md

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
# [146. LRU Cache][title]
2+
3+
## Description
4+
5+
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
6+
7+
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
8+
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
9+
10+
**Example 1:**
11+
12+
```
13+
Input: a = "11", b = "1"
14+
Output: "100"
15+
```
16+
17+
**Example 2:**
18+
19+
```
20+
Input: a = "1010", b = "1011"
21+
Output: "10101"
22+
```
23+
24+
**Tags:** Math, String
25+
26+
## 题意
27+
> 设计LRU
28+
29+
## 题解
30+
31+
### 思路1
32+
> 。。。。
33+
34+
```go
35+
36+
```
37+
38+
### 思路2
39+
> 思路2
40+
```go
41+
42+
```
43+
44+
## 结语
45+
46+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
47+
48+
[title]: https://leetcode.com/problems/two-sum/description/
49+
[me]: https://github.com/kylesliu/awesome-golang-leetcode

‎src/0146.LRU-Cache/Solution.go

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package Solution
2+
3+
import (
4+
"container/list"
5+
"fmt"
6+
)
7+
8+
type LRUCache struct {
9+
Capacity int
10+
Data *list.List
11+
//*list.List
12+
}
13+
14+
func Constructor(capacity int) LRUCache {
15+
lru := LRUCache{
16+
Capacity: capacity,
17+
Data: list.New(),
18+
}
19+
return lru
20+
}
21+
22+
func (this *LRUCache) Get(key int) int {
23+
for e := this.Data.Front(); e != nil; e = e.Next() {
24+
25+
//fmt.Println(key, e.Value.(list.Element).Value.(map[int]int)[key])
26+
27+
if v, ok := e.Value.(list.Element).Value.(map[int]int)[key]; ok {
28+
this.Data.MoveBefore(e, this.Data.Front())
29+
return v
30+
}
31+
}
32+
return -1
33+
}
34+
35+
func (this *LRUCache) Put(key int, value int) {
36+
this.Data.PushFront(
37+
list.Element{
38+
Value: map[int]int{key: value},
39+
},
40+
)
41+
if this.Data.Len() > this.Capacity {
42+
this.Data.Remove(this.Data.Back())
43+
}
44+
}
45+
46+
func (this *LRUCache) Print() {
47+
for e := this.Data.Front(); e != nil; e = e.Next() {
48+
fmt.Println(e.Value.(list.Element).Value.(map[int]int))
49+
}
50+
}

‎src/0146.LRU-Cache/Solution_test.go

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package Solution
2+
3+
import (
4+
"fmt"
5+
"reflect"
6+
"strconv"
7+
"testing"
8+
)
9+
10+
func TestSolution(t *testing.T) {
11+
// 测试用例
12+
cases := []struct {
13+
name string
14+
inputs int
15+
expect bool
16+
}{
17+
{"TestCase", 1, true},
18+
{"TestCase", 1, true},
19+
{"TestCase", 1, false},
20+
}
21+
22+
// 开始测试
23+
for i, c := range cases {
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+
34+
func TestConstructor(t *testing.T) {
35+
lru := Constructor(2)
36+
fmt.Println(lru.Get(2))
37+
38+
lru.Put(2, 6)
39+
fmt.Println(lru.Get(1))
40+
41+
lru.Put(1, 5)
42+
lru.Put(1, 2)
43+
lru.Print()
44+
45+
fmt.Println(lru.Get(1))
46+
fmt.Println(lru.Get(2))
47+
48+
}
49+
50+
// 压力测试
51+
func BenchmarkSolution(b *testing.B) {
52+
53+
}
54+
55+
// 使用案列
56+
func ExampleSolution() {
57+
58+
}

‎src/0322.Coin-Change/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -31,7 +31,7 @@ Output: -1
3131

3232
### 动态规划
3333
> 状态表示：
34-
- dp[i]表示凑出 ii 价值的钱，最少需要多少个硬币。
34+
- dp[i]表示凑出 i 价值的钱，最少需要多少个硬币。
3535
- 第i种硬币 dp[i] = min(dp[i], min(dp[i - coins[i]] ) + 1)
3636

3737
```go

0 commit comments

Comments
 (0)