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

Commit096b9de

Browse files
authored
Merge pull requestneetcode-gh#1098 from ThBlitz/main
Add C solutions for 417-Pacific-Atlantic-Water-Flow and 703-Kth-Largest-Element-In-A-Stream
2 parents4c8784e +61ea277 commit096b9de

File tree

2 files changed

+228
-0
lines changed

2 files changed

+228
-0
lines changed

‎c/417-Pacific-Atlantic-Waterflow.c

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
2+
3+
/**
4+
* Return an array of arrays of size *returnSize.
5+
* The sizes of the arrays are returned as *returnColumnSizes array.
6+
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
7+
*/
8+
9+
intdirections[4][2]= {{0,1}, {0,-1}, {1,0}, {-1,0}};
10+
boolpacific_reach[200][200];
11+
boolatlantic_reach[200][200];
12+
13+
voidresetSet(boolset[200][200]) {
14+
for (inti=0;i<200;i++) {
15+
for (intj=0;j<200;j++) {
16+
set[i][j]= false;
17+
}
18+
}
19+
}
20+
21+
voiddfs(introw,intcol,boolset[200][200],int**heights,introws,intcols) {
22+
set[row][col]= true;
23+
inta=0;
24+
intb=0;
25+
for (inti=0;i<4;i++) {
26+
a=directions[i][0]+row;
27+
b=directions[i][1]+col;
28+
if ((a >=0)&& (a<rows)&& (b >=0)&& (b<cols)&& (!set[a][b])) {
29+
if (heights[a][b] >=heights[row][col]) {
30+
dfs(a,b,set,heights,rows,cols);
31+
}
32+
}
33+
}
34+
}
35+
36+
int**pacificAtlantic(int**heights,intheightsSize,int*heightsColSize,int*returnSize,int**returnColumnSizes) {
37+
38+
introws=heightsSize;
39+
intcols=heightsColSize[0];
40+
41+
resetSet(pacific_reach);
42+
resetSet(atlantic_reach);
43+
44+
for (introw=0;row<rows;row++) {
45+
dfs(row,0,pacific_reach,heights,rows,cols);
46+
dfs(row,cols-1,atlantic_reach,heights,rows,cols);
47+
}
48+
for (intcol=0;col<cols;col++) {
49+
dfs(0,col,pacific_reach,heights,rows,cols);
50+
dfs(rows-1,col,atlantic_reach,heights,rows,cols);
51+
}
52+
53+
intres=0;
54+
for (introw=0;row<rows;row++) {
55+
for (intcol=0;col<cols;col++) {
56+
if ((pacific_reach[row][col]== true)&& (atlantic_reach[row][col]== true)) {
57+
res+=1;
58+
}
59+
}
60+
}
61+
62+
*returnSize=res;
63+
returnColumnSizes[0]= (int*)malloc(res*sizeof(int));
64+
for (inti=0;i<res;i++) {
65+
returnColumnSizes[0][i]=2;
66+
}
67+
68+
int**results= (int**)malloc(res*sizeof(int*));
69+
res=0;
70+
for (introw=0;row<rows;row++) {
71+
for (intcol=0;col<cols;col++) {
72+
if ((pacific_reach[row][col]== true)&& (atlantic_reach[row][col]== true)) {
73+
int*buffer= (int*)malloc(2*sizeof(int));
74+
buffer[0]=row;
75+
buffer[1]=col;
76+
results[res]=buffer;
77+
res+=1;
78+
}
79+
}
80+
}
81+
82+
returnresults;
83+
}
Lines changed: 145 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,145 @@
1+
2+
structheap {
3+
int*array;
4+
intlen;
5+
intmax_len;
6+
bool (*append)(structheap*self,intval);
7+
int (*pop)(structheap*self);
8+
};
9+
10+
boolheap_insert(structheap*,int);
11+
intheap_pop(structheap*);
12+
13+
structheap*Heap(intmax_len) {
14+
int*array= (int*)malloc(max_len*sizeof(int));
15+
structheap*heap= (structheap*)malloc(sizeof(structheap));
16+
heap->array=array;
17+
heap->max_len=max_len;
18+
heap->len=0;
19+
heap->append=heap_insert;
20+
heap->pop=heap_pop;
21+
returnheap;
22+
}
23+
24+
intheap_parent(intindex) {
25+
return (index-1) /2;
26+
}
27+
28+
intheap_left(intindex) {
29+
return2*index+1;
30+
}
31+
32+
intheap_right(intindex) {
33+
return2*index+2;
34+
}
35+
36+
voidheap_swap(structheap*heap,intparent,intindex) {
37+
inttemp=heap->array[index];
38+
heap->array[index]=heap->array[parent];
39+
heap->array[parent]=temp;
40+
}
41+
42+
voidheap_heapify(structheap*heap,intindex) {
43+
if (index!=0) {
44+
intparent=heap_parent(index);
45+
if (heap->array[parent]>heap->array[index]) {
46+
heap_swap(heap,parent,index);
47+
heap_heapify(heap,parent);
48+
}
49+
}
50+
}
51+
52+
boolheap_insert(structheap*heap,intval) {
53+
54+
if (heap->len==heap->max_len) {
55+
return false;
56+
}
57+
heap->array[heap->len]=val;
58+
heap_heapify(heap,heap->len);
59+
heap->len+=1;
60+
return true;
61+
}
62+
63+
boolheap_has_left(structheap*heap,intindex) {
64+
returnheap_left(index)<heap->len;
65+
}
66+
67+
boolheap_has_right(structheap*heap,intindex) {
68+
returnheap_right(index)<heap->len;
69+
}
70+
71+
voidheap_heapify_reverse(structheap*heap,intindex) {
72+
73+
intleft=heap_left(index);
74+
intright=heap_right(index);
75+
intminimum=index;
76+
if (heap_has_left(heap,index)&& (heap->array[left]<heap->array[minimum])) {
77+
minimum=left;
78+
}
79+
if (heap_has_right(heap,index)&& (heap->array[right]<heap->array[minimum])) {
80+
minimum=right;
81+
}
82+
if (minimum!=index) {
83+
heap_swap(heap,index,minimum);
84+
heap_heapify_reverse(heap,minimum);
85+
}
86+
}
87+
88+
intheap_pop(structheap*heap) {
89+
if (heap->len==0) {
90+
returnNULL;
91+
}
92+
intval=heap->array[0];
93+
heap->len-=1;
94+
heap->array[0]=heap->array[heap->len];
95+
if (heap->len>1) {
96+
heap_heapify_reverse(heap,0);
97+
}
98+
returnval;
99+
}
100+
101+
voidheap_free(structheap*heap) {
102+
free(heap->array);
103+
free(heap);
104+
}
105+
106+
typedefstruct {
107+
structheap*heap;
108+
intk;
109+
}KthLargest;
110+
111+
112+
KthLargest*kthLargestCreate(intk,int*nums,intnumsSize) {
113+
114+
KthLargest*self=malloc(sizeof(KthLargest));
115+
self->heap=Heap(numsSize+2);
116+
self->k=k;
117+
for (inti=0;i<numsSize;i++) {
118+
self->heap->append(self->heap,nums[i]);
119+
}
120+
while (self->heap->len>k) {
121+
self->heap->pop(self->heap);
122+
}
123+
returnself;
124+
}
125+
126+
intkthLargestAdd(KthLargest*obj,intval) {
127+
obj->heap->append(obj->heap,val);
128+
if (obj->heap->len>obj->k) {
129+
obj->heap->pop(obj->heap);
130+
}
131+
returnobj->heap->array[0];
132+
}
133+
134+
voidkthLargestFree(KthLargest*obj) {
135+
heap_free(obj->heap);
136+
free(obj);
137+
}
138+
139+
/**
140+
* Your KthLargest struct will be instantiated and called as such:
141+
* KthLargest* obj = kthLargestCreate(k, nums, numsSize);
142+
* int param_1 = kthLargestAdd(obj, val);
143+
144+
* kthLargestFree(obj);
145+
*/

0 commit comments

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