- Link List

-[19. Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)

-[83. Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list)

-[206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list)

-[92. Reverse Linked List II](https://leetcode.com/problems/reverse-linked-list-ii)

-[61. Rotate List](https://leetcode.com/problems/rotate-list)

-[143. Reorder List](https://leetcode.com/problems/reorder-list)

-[21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists)

-[160. Intersection of Two Linked Lists](https://leetcode.com/problems/intersection-of-two-linked-lists)

-[141. Linked List Cycle](https://leetcode.com/problems/intersection-of-two-linked-lists)

-[147. Insertion Sort List](https://leetcode.com/problems/intersection-of-two-linked-lists)

-[142. Linked List Cycle II](https://leetcode.com/problems/intersection-of-two-linked-lists)

-[148. Sort List](https://leetcode.com/problems/intersection-of-two-linked-lists)

-[146. LRU Cache 7](https://leetcode.com/problems/intersection-of-two-linked-lists)

- DFS

- Tree

- DP

- QUEUE/STACK

- Hash

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

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.

**Example 1:**

**Example 2:**

**Tags:** Math, String

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]

[title]:https://leetcode.com/problems/two-sum/description/

[me]:https://github.com/kylesliu/awesome-golang-leetcode

package Solution

import (

)

typeLRUCachestruct {

Data*list.List

}

funcConstructor(capacityint)LRUCache {

lru:=LRUCache{

Capacity:capacity,

Data:list.New(),

}

}

func (this*LRUCache)Get(keyint)int {

fore:=this.Data.Front();e!=nil;e=e.Next() {

ifv,ok:=e.Value.(list.Element).Value.(map[int]int)[key];ok {

this.Data.MoveBefore(e,this.Data.Front())

}

}

}

func (this*LRUCache)Put(keyint,valueint) {

this.Data.PushFront(

list.Element{

Value:map[int]int{key:value},

},

)

ifthis.Data.Len()>this.Capacity {

this.Data.Remove(this.Data.Back())

}

}

func (this*LRUCache)Print() {

fore:=this.Data.Front();e!=nil;e=e.Next() {

fmt.Println(e.Value.(list.Element).Value.(map[int]int))

}

}

package Solution

import (

)

funcTestSolution(t*testing.T) {

cases:= []struct {

}{

{"TestCase",1,true},

{"TestCase",1,true},

{"TestCase",1,false},

}

fori,c:=rangecases {

t.Run(c.name+" "+strconv.Itoa(i),func(t*testing.T) {

got:=Constructor(c.inputs)

if!reflect.DeepEqual(got,c.expect) {

t.Fatalf("expected: %v, but got: %v, with inputs: %v",

c.expect,got,c.inputs)

}

})

}

}

funcTestConstructor(t*testing.T) {

lru:=Constructor(2)

fmt.Println(lru.Get(2))

lru.Put(2,6)

fmt.Println(lru.Get(1))

lru.Put(1,5)

lru.Put(1,2)

lru.Print()

fmt.Println(lru.Get(1))

fmt.Println(lru.Get(2))

}

funcBenchmarkSolution(b*testing.B) {

}

funcExampleSolution() {

}

- dp[i]表示凑出ii 价值的钱，最少需要多少个硬币。

- dp[i]表示凑出i 价值的钱，最少需要多少个硬币。

- 第i种硬币 dp[i] = min(dp[i], min(dp[i - coins[i]] ) + 1)