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

Commitb4b7ff4

Browse files
committed
Merge branch 'main' of github.com:sahasourav17/neetcode-leetcode
2 parentsbae51a2 +aa97117 commitb4b7ff4

File tree

60 files changed

+1938
-51
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

60 files changed

+1938
-51
lines changed

‎README.md

Lines changed: 39 additions & 39 deletions
Large diffs are not rendered by default.

‎c/0343-integer-break.c

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
intintegerBreak(intn) {
2+
if (n <=2) {
3+
return1;
4+
}
5+
6+
intmaxProducts[n+1];
7+
maxProducts[0]=0;
8+
maxProducts[1]=0;
9+
maxProducts[2]=1;
10+
11+
for (inti=3;i <=n;i++) {
12+
maxProducts[i]=0;
13+
for (intj=1;j <=i /2;j++) {
14+
maxProducts[i]=fmax(maxProducts[i],j* (i-j));
15+
maxProducts[i]=fmax(maxProducts[i],j*maxProducts[i-j]);
16+
}
17+
}
18+
19+
returnmaxProducts[n];
20+
}
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
intfindNumberOfLIS(int*nums,intnumsSize) {
2+
if (numsSize==0) {
3+
return0;
4+
}
5+
6+
intlengths[numsSize];
7+
intcounts[numsSize];
8+
intmax_length=1;
9+
intresult=0;
10+
11+
for (inti=0;i<numsSize;i++) {
12+
lengths[i]=1;
13+
counts[i]=1;
14+
for (intj=0;j<i;j++) {
15+
if (nums[i]>nums[j]) {
16+
if (lengths[j]+1>lengths[i]) {
17+
lengths[i]=lengths[j]+1;
18+
counts[i]=counts[j];
19+
}elseif (lengths[j]+1==lengths[i]) {
20+
counts[i]+=counts[j];
21+
}
22+
}
23+
}
24+
max_length=fmax(max_length,lengths[i]);
25+
}
26+
27+
for (inti=0;i<numsSize;i++) {
28+
if (lengths[i]==max_length) {
29+
result+=counts[i];
30+
}
31+
}
32+
33+
returnresult;
34+
}

‎c/0691-stickers-to-spell-word.c

Lines changed: 267 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,267 @@
1+
#defineMIN 5
2+
3+
typedefstructmyInstance {
4+
intindex;
5+
intcount;
6+
}Instance;
7+
8+
typedefstructmyList {
9+
intsize;
10+
intmaxSize;
11+
Instance*data;
12+
}InstanceList;
13+
14+
// Function to clean up allocated memory
15+
voidcleanup(InstanceList**mapping,int**stickerSignatures,intsignatureSize) {
16+
// Clean up the memory used for mapping
17+
for (inti=0;i<26;i++) {
18+
InstanceList*current=mapping[i];
19+
if (current!=NULL) {
20+
if (current->data!=NULL) {
21+
free(current->data);
22+
}
23+
free(current);
24+
}
25+
}
26+
27+
// Clean up the memory used for sticker signatures
28+
for (inti=0;i<signatureSize;i++) {
29+
if (stickerSignatures[i]!=NULL) {
30+
free(stickerSignatures[i]);
31+
}
32+
}
33+
}
34+
35+
// Hash function to map a character to an index
36+
inthashFunction(charc) {
37+
returnc-'a';
38+
}
39+
40+
// Initialize the signature for a word (count of each letter)
41+
voidinitializeSignature(char*word,int*signature) {
42+
for (inti=0;i<26;i++) {
43+
signature[i]=0;
44+
}
45+
46+
for (char*c=word;*c!='\0';c++) {
47+
signature[hashFunction(*c)]++;
48+
}
49+
}
50+
51+
// Preprocess stickers and filter out dominated ones
52+
intpreprocessStickers(char**stickers,intstickersSize,
53+
int**stickerSignatures,char**workingStickers,constintconst*targetSignature) {
54+
for (inti=0;i<stickersSize;i++) {
55+
workingStickers[i]=stickers[i];
56+
stickerSignatures[i]= (int*)malloc(sizeof(int)*26);
57+
58+
for (intj=0;j<26;j++) {
59+
stickerSignatures[i][j]=0;
60+
}
61+
62+
for (char*c=stickers[i];*c!='\0';c++) {
63+
intindex=hashFunction(*c);
64+
65+
if (targetSignature[index]>0) {
66+
stickerSignatures[i][index]++;
67+
}
68+
}
69+
}
70+
71+
intremaining=stickersSize;
72+
73+
for (inti=0;i<remaining;i++) {
74+
for (intj=0;j<remaining;j++) {
75+
if (i==j||workingStickers[j]==NULL) {
76+
continue;
77+
}
78+
79+
intdominated=1;
80+
81+
for (intk=0;k<26;k++) {
82+
if (stickerSignatures[i][k]>stickerSignatures[j][k]) {
83+
dominated=0;
84+
break;
85+
}
86+
}
87+
88+
if (dominated) {
89+
free(stickerSignatures[i]);
90+
stickerSignatures[i]=NULL;
91+
workingStickers[i]=NULL;
92+
remaining--;
93+
94+
if (i<remaining) {
95+
stickerSignatures[i]=stickerSignatures[remaining];
96+
workingStickers[i]=workingStickers[remaining];
97+
stickerSignatures[remaining]=NULL;
98+
workingStickers[remaining]=NULL;
99+
i--;
100+
}
101+
102+
break;
103+
}
104+
}
105+
}
106+
107+
returnremaining;
108+
}
109+
110+
// Create a hash table to map characters to stickers
111+
intmakeHashTable(char**stickers,intstickersSize,char*target,InstanceList**mapping) {
112+
for (inti=0;i<26;i++) {
113+
mapping[i]=NULL;
114+
}
115+
116+
for (char*c=target;*c!='\0';c++) {
117+
intindex=hashFunction(*c);
118+
119+
if (mapping[index]==NULL) {
120+
mapping[index]= (InstanceList*)malloc(sizeof(InstanceList));
121+
mapping[index]->data=NULL;
122+
}
123+
}
124+
125+
for (inti=0;i<stickersSize;i++) {
126+
for (char*c=stickers[i];*c!='\0';c++) {
127+
intindex=hashFunction(*c);
128+
129+
if (mapping[index]!=NULL) {
130+
InstanceList*spot=mapping[index];
131+
132+
if (spot->data!=NULL&&spot->size>0
133+
&&spot->data[spot->size-1].index==i) {
134+
spot->data[spot->size-1].count++;
135+
continue;
136+
}
137+
138+
if (spot->data==NULL) {
139+
spot->data= (Instance*)malloc(sizeof(Instance)*MIN);
140+
spot->size=0;
141+
spot->maxSize=MIN;
142+
}elseif (spot->size==spot->maxSize) {
143+
spot->maxSize *=2;
144+
spot->data=realloc(spot->data,sizeof(Instance)*spot->maxSize);
145+
}
146+
147+
spot->data[spot->size].index=i;
148+
spot->data[spot->size].count=1;
149+
spot->size++;
150+
}
151+
}
152+
}
153+
154+
return0;
155+
}
156+
157+
// Find the index with the minimum size in mapping
158+
intminIndex(InstanceList**mapping,int*targetSignature) {
159+
intindex=-1;
160+
161+
for (inti=0;i<26;i++) {
162+
if (targetSignature[i]>0&& (index==-1||mapping[i]->size<mapping[index]->size)) {
163+
index=i;
164+
}
165+
}
166+
167+
returnindex;
168+
}
169+
170+
// Recursive search function to find the minimum stickers required
171+
voidsearch(InstanceList**mapping,int**stickerSignatures,int*targetSignature,intdepth,int*maxDepth) {
172+
if (depth >=*maxDepth&&*maxDepth>0) {
173+
return;
174+
}
175+
176+
intminLetter=minIndex(mapping,targetSignature);
177+
178+
if (minLetter<0) {
179+
if (*maxDepth==0||depth<*maxDepth) {
180+
*maxDepth=depth;
181+
}
182+
183+
return;
184+
}
185+
186+
for (intoption=0;option<mapping[minLetter]->size;option++) {
187+
intindex=mapping[minLetter]->data[option].index;
188+
189+
for (inti=0;i<26;i++) {
190+
targetSignature[i]-=stickerSignatures[index][i];
191+
}
192+
193+
search(mapping,stickerSignatures,targetSignature,depth+1,maxDepth);
194+
195+
for (inti=0;i<26;i++) {
196+
targetSignature[i]+=stickerSignatures[index][i];
197+
}
198+
}
199+
200+
return;
201+
}
202+
203+
// Main function to calculate the minimum stickers required
204+
intminStickers(char**stickers,intstickersSize,char*target) {
205+
inttargetSignature[26];
206+
initializeSignature(target,targetSignature);
207+
int*stickerSignatures[stickersSize];
208+
char*workingStickers[stickersSize];
209+
intdomainSize=preprocessStickers(stickers,stickersSize,stickerSignatures,workingStickers,targetSignature);
210+
InstanceList*mapping[26];
211+
makeHashTable(workingStickers,domainSize,target,mapping);
212+
213+
for (inti=0;i<26;i++) {
214+
if (mapping[i]!=NULL&&mapping[i]->data==NULL) {
215+
cleanup(mapping,stickerSignatures,domainSize);
216+
return-1;
217+
}
218+
}
219+
220+
intmaxDepth=0;
221+
search(mapping,stickerSignatures,targetSignature,0,&maxDepth);
222+
cleanup(mapping,stickerSignatures,domainSize);
223+
returnmaxDepth;
224+
}
225+
226+
// Alternative Solution
227+
228+
// int solve(int mask, char **stickers, char *target, int n, int m, int *dp) {
229+
// if (mask == (1 << m) - 1) {
230+
// return 0;
231+
// }
232+
// if (dp[mask] != -1) {
233+
// return dp[mask];
234+
// }
235+
// int ans = 1e9;
236+
// for (int i = 0; i < n; i++) {
237+
// int freq[26] = {0};
238+
// for (int j = 0; stickers[i][j] != '\0'; j++) {
239+
// freq[stickers[i][j] - 'a']++;
240+
// }
241+
// int new_mask = 0;
242+
// for (int j = 0; j < m; j++) {
243+
// if ((1 << j) & mask) continue;
244+
// if (freq[target[j] - 'a']) {
245+
// freq[target[j] - 'a']--;
246+
// new_mask |= (1 << j);
247+
// }
248+
// }
249+
// if (new_mask != 0) {
250+
// int temp = 1 + solve(new_mask | mask, stickers, target, n, m, dp);
251+
// ans = (temp < ans) ? temp : ans;
252+
// }
253+
// }
254+
// return dp[mask] = ans;
255+
// }
256+
257+
// int minStickers(char **stickers, int stickersSize, char *target) {
258+
// int mask = 0;
259+
// int n = stickersSize, m = strlen(target);
260+
// int *dp = (int *)malloc((1 << m) * sizeof(int));
261+
// for (int i = 0; i < (1 << m); i++) {
262+
// dp[i] = -1;
263+
// }
264+
// int ans = solve(mask, stickers, target, n, m, dp);
265+
// free(dp);
266+
// return (ans == 1e9) ? -1 : ans;
267+
// }

‎c/1035-uncrossed-lines.c

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
intmaxUncrossedLines(int*nums1,intnums1Size,int*nums2,intnums2Size) {
2+
intdp[nums1Size+1][nums2Size+1];
3+
4+
for (inti=0;i <=nums1Size;i++) {
5+
for (intj=0;j <=nums2Size;j++) {
6+
if (i==0||j==0)
7+
dp[i][j]=0;
8+
elseif (nums1[i-1]==nums2[j-1])
9+
dp[i][j]=dp[i-1][j-1]+1;
10+
else
11+
dp[i][j]=fmax(dp[i-1][j],dp[i][j-1]);
12+
}
13+
}
14+
15+
returndp[nums1Size][nums2Size];
16+
}

‎c/1137-n-th-tribonacci-number.c

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
inttribonacci(intn) {
2+
if (n==0)
3+
return0;
4+
elseif (n==1||n==2)
5+
return1;
6+
7+
inttrib[n+1];
8+
trib[0]=0;
9+
trib[1]=1;
10+
trib[2]=1;
11+
12+
for (inti=3;i <=n;i++) {
13+
trib[i]=trib[i-1]+trib[i-2]+trib[i-3];
14+
}
15+
16+
returntrib[n];
17+
}
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
long longmostPoints(int**questions,intquestionsSize,int*questionsColSize) {
2+
intn=questionsSize;
3+
long long*dp= (long long*)malloc((n+1)*sizeof(long long));
4+
5+
for (inti=0;i <=n;i++) {
6+
dp[i]=0;
7+
}
8+
9+
for (inti=n-1;i >=0;i--) {
10+
intpoints=questions[i][0];
11+
intjump=questions[i][1];
12+
dp[i]= (points+dp[(jump+i+1)<n ? (jump+i+1) :n])>dp[i+1] ? (points+dp[(jump+i+1)<n ? (jump+i+1) :n]) :dp[i+1];
13+
}
14+
15+
long longresult=dp[0];
16+
free(dp);
17+
returnresult;
18+
}

0 commit comments

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