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

Commit68f33b5

Browse files
authored
Sri hari: Batch-8/Added Articles/Neetcode-ALL (#4318)
* Batch-8/Neetcode-ALL/Added-articles* Batch-8/Neetcode-ALL/Added-articles* Batch-8/Neetcode-ALL/Added-articles* Batch-8/Neetcode-ALL/Added-articles* Batch-8/Neetcode-ALL/Added-articles* Batch-8/Neetcode-ALL/Added-articles
1 parentd8f0d05 commit68f33b5

13 files changed

+4406
-3
lines changed

‎articles/convert-bst-to-greater-tree.md‎

Lines changed: 157 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -155,6 +155,45 @@ class Solution {
155155
}
156156
```
157157

158+
```csharp
159+
/**
160+
* Definition for a binary tree node.
161+
* public class TreeNode {
162+
* public int val;
163+
* public TreeNode left;
164+
* public TreeNode right;
165+
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
166+
* this.val = val;
167+
* this.left = left;
168+
* this.right = right;
169+
* }
170+
* }
171+
*/
172+
publicclassSolution {
173+
publicTreeNodeConvertBST(TreeNoderoot) {
174+
intGetSum(TreeNodenode) {
175+
if (node==null)return0;
176+
returnnode.val+GetSum(node.left)+GetSum(node.right);
177+
}
178+
179+
inttotalSum=GetSum(root);
180+
181+
voidDfs(TreeNodenode) {
182+
if (node==null)return;
183+
184+
Dfs(node.left);
185+
inttmp=node.val;
186+
node.val=totalSum;
187+
totalSum-=tmp;
188+
Dfs(node.right);
189+
}
190+
191+
Dfs(root);
192+
returnroot;
193+
}
194+
}
195+
```
196+
158197
::tabs-end
159198

160199
###Time & Space Complexity
@@ -299,6 +338,40 @@ class Solution {
299338
}
300339
```
301340

341+
```csharp
342+
/**
343+
* Definition for a binary tree node.
344+
* public class TreeNode {
345+
* public int val;
346+
* public TreeNode left;
347+
* public TreeNode right;
348+
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
349+
* this.val = val;
350+
* this.left = left;
351+
* this.right = right;
352+
* }
353+
* }
354+
*/
355+
publicclassSolution {
356+
publicTreeNodeConvertBST(TreeNoderoot) {
357+
intcurSum=0;
358+
359+
voidDfs(TreeNodenode) {
360+
if (node==null)return;
361+
362+
Dfs(node.right);
363+
inttmp=node.val;
364+
node.val+=curSum;
365+
curSum+=tmp;
366+
Dfs(node.left);
367+
}
368+
369+
Dfs(root);
370+
returnroot;
371+
}
372+
}
373+
```
374+
302375
::tabs-end
303376

304377
###Time & Space Complexity
@@ -448,6 +521,43 @@ class Solution {
448521
}
449522
```
450523

524+
```csharp
525+
/**
526+
* Definition for a binary tree node.
527+
* public class TreeNode {
528+
* public int val;
529+
* public TreeNode left;
530+
* public TreeNode right;
531+
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
532+
* this.val = val;
533+
* this.left = left;
534+
* this.right = right;
535+
* }
536+
* }
537+
*/
538+
publicclassSolution {
539+
publicTreeNodeConvertBST(TreeNoderoot) {
540+
intcurSum=0;
541+
Stack<TreeNode>stack=newStack<TreeNode>();
542+
TreeNodenode=root;
543+
544+
while (stack.Count>0||node!=null) {
545+
while (node!=null) {
546+
stack.Push(node);
547+
node=node.right;
548+
}
549+
550+
node=stack.Pop();
551+
curSum+=node.val;
552+
node.val=curSum;
553+
node=node.left;
554+
}
555+
556+
returnroot;
557+
}
558+
}
559+
```
560+
451561
::tabs-end
452562

453563
###Time & Space Complexity
@@ -635,6 +745,53 @@ class Solution {
635745
}
636746
```
637747

748+
```csharp
749+
/**
750+
* Definition for a binary tree node.
751+
* public class TreeNode {
752+
* public int val;
753+
* public TreeNode left;
754+
* public TreeNode right;
755+
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
756+
* this.val = val;
757+
* this.left = left;
758+
* this.right = right;
759+
* }
760+
* }
761+
*/
762+
publicclassSolution {
763+
publicTreeNodeConvertBST(TreeNoderoot) {
764+
intcurSum=0;
765+
TreeNodecur=root;
766+
767+
while (cur!=null) {
768+
if (cur.right!=null) {
769+
TreeNodeprev=cur.right;
770+
while (prev.left!=null&&prev.left!=cur) {
771+
prev=prev.left;
772+
}
773+
774+
if (prev.left==null) {
775+
prev.left=cur;
776+
cur=cur.right;
777+
}else {
778+
prev.left=null;
779+
curSum+=cur.val;
780+
cur.val=curSum;
781+
cur=cur.left;
782+
}
783+
}else {
784+
curSum+=cur.val;
785+
cur.val=curSum;
786+
cur=cur.left;
787+
}
788+
}
789+
790+
returnroot;
791+
}
792+
}
793+
```
794+
638795
::tabs-end
639796

640797
###Time & Space Complexity

‎articles/find-the-index-of-the-first-occurrence-in-a-string.md‎

Lines changed: 148 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -80,6 +80,27 @@ class Solution {
8080
}
8181
```
8282

83+
```csharp
84+
publicclassSolution {
85+
publicintStrStr(stringhaystack,stringneedle) {
86+
intn=haystack.Length,m=needle.Length;
87+
for (inti=0;i<=n-m;i++) {
88+
intj=0;
89+
while (j<m) {
90+
if (haystack[i+j]!=needle[j]) {
91+
break;
92+
}
93+
j++;
94+
}
95+
if (j==m) {
96+
returni;
97+
}
98+
}
99+
return-1;
100+
}
101+
}
102+
```
103+
83104
::tabs-end
84105

85106
###Time & Space Complexity
@@ -274,6 +295,52 @@ class Solution {
274295
}
275296
```
276297

298+
```csharp
299+
publicclassSolution {
300+
publicintStrStr(stringhaystack,stringneedle) {
301+
if (needle=="")return0;
302+
303+
int[]lps=newint[needle.Length];
304+
intprevLPS=0,i=1;
305+
306+
while (i<needle.Length) {
307+
if (needle[i]==needle[prevLPS]) {
308+
lps[i]=prevLPS+1;
309+
prevLPS++;
310+
i++;
311+
}elseif (prevLPS==0) {
312+
lps[i]=0;
313+
i++;
314+
}else {
315+
prevLPS=lps[prevLPS-1];
316+
}
317+
}
318+
319+
i=0;
320+
intj=0;
321+
322+
while (i<haystack.Length) {
323+
if (haystack[i]==needle[j]) {
324+
i++;
325+
j++;
326+
}else {
327+
if (j==0) {
328+
i++;
329+
}else {
330+
j=lps[j-1];
331+
}
332+
}
333+
334+
if (j==needle.Length) {
335+
returni-needle.Length;
336+
}
337+
}
338+
339+
return-1;
340+
}
341+
}
342+
```
343+
277344
::tabs-end
278345

279346
###Time & Space Complexity
@@ -423,6 +490,41 @@ class Solution {
423490
}
424491
```
425492

493+
```csharp
494+
publicclassSolution {
495+
publicintStrStr(stringhaystack,stringneedle) {
496+
if (string.IsNullOrEmpty(needle))return0;
497+
498+
strings=needle+"$"+haystack;
499+
intn=s.Length;
500+
int[]z=newint[n];
501+
intl=0,r=0;
502+
503+
for (inti=1;i<n;i++) {
504+
if (i<=r) {
505+
z[i]=Math.Min(r-i+1,z[i-l]);
506+
}
507+
while (i+z[i]<n&&s[z[i]]==s[i+z[i]]) {
508+
z[i]++;
509+
}
510+
if (i+z[i]-1>r) {
511+
l=i;
512+
r=i+z[i]-1;
513+
}
514+
}
515+
516+
intm=needle.Length;
517+
for (inti=m+1;i<n;i++) {
518+
if (z[i]==m) {
519+
returni-m-1;
520+
}
521+
}
522+
523+
return-1;
524+
}
525+
}
526+
```
527+
426528
::tabs-end
427529

428530
###Time & Space Complexity
@@ -623,6 +725,52 @@ class Solution {
623725
}
624726
```
625727

728+
```csharp
729+
publicclassSolution {
730+
publicintStrStr(stringhaystack,stringneedle) {
731+
if (string.IsNullOrEmpty(needle))return0;
732+
733+
intbase1=31,mod1=768258391;
734+
intbase2=37,mod2=685683731;
735+
736+
intn=haystack.Length,m=needle.Length;
737+
if (m>n)return-1;
738+
739+
longpower1=1,power2=1;
740+
for (inti=0;i<m;i++) {
741+
power1= (power1*base1)%mod1;
742+
power2= (power2*base2)%mod2;
743+
}
744+
745+
longneedleHash1=0,needleHash2=0;
746+
longhaystackHash1=0,haystackHash2=0;
747+
748+
for (inti=0;i<m;i++) {
749+
needleHash1= (needleHash1*base1+needle[i])%mod1;
750+
needleHash2= (needleHash2*base2+needle[i])%mod2;
751+
haystackHash1= (haystackHash1*base1+haystack[i])%mod1;
752+
haystackHash2= (haystackHash2*base2+haystack[i])%mod2;
753+
}
754+
755+
for (inti=0;i<=n-m;i++) {
756+
if (haystackHash1==needleHash1&&haystackHash2==needleHash2) {
757+
returni;
758+
}
759+
760+
if (i+m<n) {
761+
haystackHash1= (haystackHash1*base1-haystack[i]*power1+haystack[i+m])%mod1;
762+
haystackHash2= (haystackHash2*base2-haystack[i]*power2+haystack[i+m])%mod2;
763+
764+
if (haystackHash1<0)haystackHash1+=mod1;
765+
if (haystackHash2<0)haystackHash2+=mod2;
766+
}
767+
}
768+
769+
return-1;
770+
}
771+
}
772+
```
773+
626774
::tabs-end
627775

628776
###Time & Space Complexity

0 commit comments

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