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

Commit8ed511d

Browse files
committed
2 problems
1 parentb8dd7f9 commit8ed511d

File tree

3 files changed

+112
-0
lines changed

3 files changed

+112
-0
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -211,6 +211,8 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
211211
####[284. Peeking Iterator](https://github.com/hitzzc/go-leetcode/tree/master/peeking_iterator)
212212
####[287. Find the Duplicate Number](https://github.com/hitzzc/go-leetcode/tree/master/find_the_duplicate_number)
213213
####[290. Word Pattern](https://github.com/hitzzc/go-leetcode/tree/master/word_pattern)
214+
####[292. Nim Game](https://github.com/hitzzc/go-leetcode/tree/master/nim_game)
215+
####[295. Find Median from Data Stream](https://github.com/hitzzc/go-leetcode/tree/master/find_median_from_data_stream)
214216

215217

216218

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
#include<vector>
2+
#include<iostream>
3+
usingnamespacestd;
4+
5+
classHeap {
6+
private:
7+
vector<int> array;
8+
int (*compare) (int,int);
9+
voidadjust(int idx) {
10+
int largest = idx;
11+
if (2*idx+1 < array.size() &&compare(array[2*idx+1], array[idx]))
12+
largest =2*idx+1;
13+
if (2*idx+2 < array.size() &&compare(array[2*idx+2],array[largest]))
14+
largest =2*idx+2;
15+
if (largest != idx) {
16+
int tmp = array[idx];
17+
array[idx] = array[largest];
18+
array[largest] = tmp;
19+
adjust(largest);
20+
}
21+
return;
22+
}
23+
public:
24+
Heap(int (*compare) (int,int)): compare(compare) {}
25+
voidpush(int val) {
26+
array.push_back(val);
27+
for (int i = array.size()/2 -1; i >=0; --i){
28+
adjust(i);
29+
}
30+
}
31+
voidprint() {
32+
for (auto val: array)
33+
cout <<"print\t" << val << endl;
34+
}
35+
intpop() {
36+
int ret = array[0];
37+
array[0] = array.back();
38+
array.pop_back();
39+
adjust(0);
40+
return ret;
41+
}
42+
intempty() {
43+
return array.empty();
44+
}
45+
intsize() {
46+
return array.size();
47+
}
48+
inttop() {
49+
return array[0];
50+
}
51+
};
52+
53+
intmax(int i,int j) {
54+
if (i > j)returntrue;
55+
returnfalse;
56+
}
57+
58+
intmin(int i,int j) {
59+
if (i < j)returntrue;
60+
returnfalse;
61+
}
62+
63+
classMedianFinder {
64+
Heap max_heap;
65+
Heap min_heap;
66+
public:
67+
MedianFinder(): max_heap(Heap(max)), min_heap(Heap(min)){}
68+
// Adds a number into the data structure.
69+
voidaddNum(int num) {
70+
if (max_heap.empty() || num <= max_heap.top()) {
71+
max_heap.push(num);
72+
}else {
73+
min_heap.push(num);
74+
}
75+
if (max_heap.size() > min_heap.size()+1){
76+
int top = max_heap.pop();
77+
min_heap.push(top);
78+
}
79+
if (min_heap.size() > max_heap.size()) {
80+
int top = min_heap.pop();
81+
max_heap.push(top);
82+
}
83+
return;
84+
}
85+
86+
// Returns the median of current data stream
87+
doublefindMedian() {
88+
if (max_heap.size() == min_heap.size())
89+
return ((max_heap.top()+min_heap.top())/2.0);
90+
if (max_heap.size() > min_heap.size())
91+
return max_heap.top();
92+
return min_heap.top();
93+
}
94+
};
95+
96+
intmain() {
97+
MedianFinder finder;
98+
finder.addNum(-1);
99+
finder.addNum(-2);
100+
finder.addNum(-3);
101+
finder.addNum(-4);
102+
finder.addNum(-5);
103+
return0;
104+
}

‎nim_game/nim_game.cpp

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
classSolution {
2+
public:
3+
boolcanWinNim(int n) {
4+
return !(n%4 ==0);
5+
}
6+
};

0 commit comments

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