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

Commit83feef3

Browse files
committed
[Function add]
1. Add leetcode solutions.
1 parent81b9209 commit83feef3

File tree

3 files changed

+428
-0
lines changed

3 files changed

+428
-0
lines changed
Lines changed: 116 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,116 @@
1+
##410. Split Array Largest Sum
2+
3+
###Question
4+
Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.
5+
6+
Note:
7+
If n is the length of array, assume the following constraints are satisfied:
8+
* 1 ≤ n ≤ 1000
9+
* 1 ≤ m ≤ min(50, n)
10+
11+
```
12+
Examples:
13+
14+
Input:
15+
nums = [7,2,5,10,8]
16+
m = 2
17+
18+
Output:
19+
18
20+
21+
Explanation:
22+
There are four ways to split nums into two subarrays.
23+
The best way is to split it into [7,2,5] and [10,8],
24+
where the largest sum among the two subarrays is only 18.
25+
```
26+
27+
28+
###Solutions:
29+
* Method 1: DP from top to bottom
30+
* dp[m][j] means the result from nums[0] to nums[j] into m divisions.
31+
* we have a index k, where 0 <= k < j.
32+
* dp[m][j] = min(max(dp[m - 1][k], sum[j] - sum[k]))
33+
![Imgur](https://i.imgur.com/dETKFm1.png)
34+
```Java
35+
classSolution {
36+
privateint[][] dp;
37+
privateint[] sum;
38+
publicintsplitArray(int[]nums,intm) {
39+
this.sum=newint[nums.length];
40+
sum[0]= nums[0];
41+
for(int i=1; i< nums.length; i++)
42+
sum[i]= sum[i-1]+ nums[i];
43+
dp=newint[m+1][nums.length];
44+
for(int[] d: dp)Arrays.fill(d,Integer.MAX_VALUE);
45+
return dfs(m, nums.length-1);
46+
}
47+
// Return the result from nums[0] to nums[j] divided into m parts.
48+
privateintdfs(intm,intj){
49+
if(m==1)return sum[j];
50+
if(m> j+1)returnInteger.MAX_VALUE;
51+
if(dp[m][j]!=Integer.MAX_VALUE)return dp[m][j];
52+
int res=Integer.MAX_VALUE;
53+
for(int k=0; k< j; k++){
54+
res=Math.min(res,Math.max(sum[j]- sum[k], dfs(m-1, k)));
55+
}
56+
return dp[m][j]= res;
57+
}
58+
}
59+
```
60+
61+
*Method2: from bottom to top
62+
```Java
63+
classSolution {
64+
publicintsplitArray(int[]nums,intm) {
65+
int[] sum=newint[nums.length];
66+
sum[0]= nums[0];
67+
for(int i=1; i< nums.length; i++) sum[i]= sum[i-1]+ nums[i];
68+
int[][] dp=newint[m+1][nums.length];
69+
for(int[] d: dp)Arrays.fill(d,Integer.MAX_VALUE);
70+
for(int i=0; i< nums.length; i++){
71+
dp[1][i]= sum[i];
72+
}
73+
for(int i=2; i<= m; i++){
74+
for(int j= i-1; j< nums.length; j++){
75+
for(int k=0; k< j; k++){
76+
dp[i][j]=Math.min(dp[i][j],Math.max(dp[i-1][k], sum[j]- sum[k]));
77+
}
78+
}
79+
}
80+
return dp[m][nums.length-1];
81+
}
82+
}
83+
```
84+
85+
*Method2:BinarySearch
86+
![Imgur](https://i.imgur.com/SEpy5br.png)
87+
```Java
88+
classSolution {
89+
publicintsplitArray(int[]nums,intm) {
90+
long r=0, l=0;
91+
for(int num: nums){
92+
l=Math.max(l, num);
93+
r+= num;
94+
}
95+
r++;
96+
while(l< r){
97+
long mid= l+ (r- l)/2;
98+
int count=1, temp=0;
99+
for(int i=0; i< nums.length; i++){
100+
if(temp+ nums[i]> mid){
101+
count++;
102+
temp= nums[i];
103+
}else{
104+
temp+= nums[i];
105+
}
106+
}
107+
if(count> m) l= mid+1;
108+
else r= mid;
109+
}
110+
return (int)l;
111+
}
112+
}
113+
```
114+
115+
###Reference
116+
1. [花花酱LeetCode410.SplitArrayLargestSum](http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-410-split-array-largest-sum/)

‎leetcode/460. LFU Cache.md

Lines changed: 206 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,206 @@
1+
##460. LFU Cache
2+
3+
###Question
4+
Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.
5+
6+
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
7+
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.
8+
9+
Follow up:
10+
* Could you do both operations in O(1) time complexity?
11+
12+
```
13+
Example:
14+
15+
LFUCache cache = new LFUCache( 2 /* capacity */ );
16+
17+
cache.put(1, 1);
18+
cache.put(2, 2);
19+
cache.get(1); // returns 1
20+
cache.put(3, 3); // evicts key 2
21+
cache.get(2); // returns -1 (not found)
22+
cache.get(3); // returns 3.
23+
cache.put(4, 4); // evicts key 1.
24+
cache.get(1); // returns -1 (not found)
25+
cache.get(3); // returns 3
26+
cache.get(4); // returns 4
27+
```
28+
29+
###Solutions:
30+
* Method 1: HashMap + PriorityQueue Both get and put are O(NlgN)
31+
* We create a class node, which saves the freq, tick, key and val.
32+
* We have a hashMap to save the key and Node.
33+
* We create a priorityQueue to to save the nodes, the comparator of the priorityQueue is
34+
1. if freq is not same, compare the freq.
35+
2. if freq is the same, we compare the tick.
36+
```Java
37+
classLFUCache {
38+
privatestaticfinalclassNode{
39+
int key, val;
40+
Node pre, next;
41+
int freq, tick;
42+
publicNode(intkey,intval,intfreq,inttick){
43+
this.key= key;
44+
this.val= val;
45+
this.freq= freq;
46+
this.tick= tick;
47+
}
48+
}
49+
privateMap<Integer,Node> map;
50+
privatePriorityQueue<Node> pq;
51+
privateint capacity;
52+
privateint size;
53+
privateint tick;
54+
publicLFUCache(intcapacity) {
55+
this.map=newHashMap<>();
56+
this.capacity= capacity;
57+
pq=newPriorityQueue<Node>((n1, n2)->{
58+
return n1.freq== n2.freq? n1.tick- n2.tick: n1.freq- n2.freq;
59+
});
60+
}
61+
publicintget(intkey) {
62+
if(!map.containsKey(key)|| capacity==0)return-1;
63+
Node node= map.get(key);
64+
pq.remove(node);
65+
node.freq++;
66+
node.tick= tick++;
67+
pq.offer(node);
68+
return node.val;
69+
}
70+
publicvoidput(intkey,intvalue) {
71+
if(capacity==0)return;
72+
Node node=null;
73+
if(map.containsKey(key)){
74+
node= map.get(key);
75+
node.val= value;
76+
pq.remove(node);
77+
map.remove(key);
78+
size--;
79+
}else{
80+
node=newNode(key, value,0, tick);
81+
}
82+
node.freq++;
83+
node.tick= tick++;
84+
map.put(key, node);
85+
if(size< capacity){
86+
pq.offer(node);
87+
size++;
88+
}else{
89+
Node lfu= pq.poll();
90+
map.remove(lfu.key);
91+
pq.offer(node);
92+
}
93+
}
94+
}
95+
/**
96+
* Your LFUCache object will be instantiated and called as such:
97+
* LFUCache obj = new LFUCache(capacity);
98+
* int param_1 = obj.get(key);
99+
* obj.put(key,value);
100+
*/
101+
```
102+
103+
*Method2:Two hashMap+ doubleLinkedList O(1)
104+
```Java
105+
classLFUCache {
106+
privatestaticfinalclassNode{
107+
int key, val, freq;
108+
Node pre, next;
109+
publicNode(intkey,intval){
110+
this.key= key;
111+
this.val= val;
112+
this.freq=1;
113+
}
114+
}
115+
privatestaticfinalclassDLLList{
116+
Node head, tail;
117+
int size;
118+
DLLList(){
119+
head=newNode(0,0);
120+
tail=newNode(0,0);
121+
head.next= tail;
122+
tail.pre= head;
123+
}
124+
125+
voidadd(Nodenode){
126+
head.next.pre= node;
127+
node.next= head.next;
128+
node.pre= head;
129+
head.next= node;
130+
size++;
131+
}
132+
voidremove(Nodenode){
133+
node.pre.next= node.next;
134+
node.next.pre= node.pre;
135+
size--;
136+
}
137+
NoderemoveLast(){
138+
if(size>0){
139+
Node node= tail.pre;
140+
remove(node);
141+
return node;
142+
}
143+
returnnull;
144+
}
145+
}
146+
privateMap<Integer,Node> map;
147+
privateMap<Integer,DLLList> countMap;
148+
privateint size;
149+
privateint capacity;
150+
privateint min;
151+
publicLFUCache(intcapacity) {
152+
this.capacity= capacity;
153+
this.map=newHashMap<>();
154+
this.countMap=newHashMap<>();
155+
}
156+
157+
publicintget(intkey) {
158+
if(!map.containsKey(key)|| size==0)return-1;
159+
Node node= map.get(key);
160+
update(node);
161+
return node.val;
162+
}
163+
164+
publicvoidput(intkey,intvalue) {
165+
if(capacity==0)return;
166+
Node node=null;
167+
if(map.containsKey(key)){
168+
node= map.get(key);
169+
node.val= value;
170+
update(node);
171+
}else{
172+
node=newNode(key, value);
173+
map.put(key, node);
174+
if(size== capacity){
175+
DLLList lastList= countMap.get(min);
176+
map.remove(lastList.removeLast().key);
177+
size--;
178+
}
179+
size++;
180+
min=1;
181+
DLLList newList= countMap.getOrDefault(node.freq,newDLLList());
182+
newList.add(node);
183+
countMap.put(node.freq, newList);
184+
}
185+
}
186+
privatevoidupdate(Nodenode){
187+
DLLList oldList= countMap.get(node.freq);
188+
oldList.remove(node);
189+
if(node.freq== min&& oldList.size==0) min++;
190+
node.freq++;
191+
DLLList newList= countMap.getOrDefault(node.freq,newDLLList());
192+
newList.add(node);
193+
countMap.put(node.freq, newList);
194+
}
195+
}
196+
197+
/**
198+
* Your LFUCache object will be instantiated and called as such:
199+
* LFUCache obj = new LFUCache(capacity);
200+
* int param_1 = obj.get(key);
201+
* obj.put(key,value);
202+
*/
203+
```
204+
205+
###Reference
206+
1. [花花酱LeetCode460.LFUCache](http://zxi.mytechroad.com/blog/hashtable/leetcode-460-lfu-cache/)

0 commit comments

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