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

Commit03c5b10

Browse files
authored
Merge branch 'neetcode-gh:main' into main
2 parents75af916 +793ea14 commit03c5b10

17 files changed

+607
-17
lines changed

‎README.md

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

‎c/199-Binary-Tree-Right-Side-View.c

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
/*
2+
Given a binary tree, return the right side view of it (the nodes which can
3+
be seen in front when looking from the right).
4+
Ex. 1 <-
5+
/ \
6+
2 3 <- -> [1, 3, 4]
7+
\ \
8+
5 4 <-
9+
10+
11+
The right side view is basically the last element at each level of the tree.
12+
So BFS is one way this problem can be solved.
13+
14+
The solution below uses recursion, where on reaching a new depth we add that
15+
node as the right view for that depth. We recursively visit the right child
16+
before the left child to get the right view.
17+
18+
Time: O(n)
19+
Space: O(n)
20+
*/
21+
22+
/**
23+
* Definition for a binary tree node.
24+
* struct TreeNode {
25+
* int val;
26+
* struct TreeNode *left;
27+
* struct TreeNode *right;
28+
* };
29+
*/
30+
31+
voiddfs(structTreeNode*root,int*result,int*returnSize,intdepth) {
32+
if (root==NULL)
33+
return;
34+
35+
// If a new depth is reached, add the node as right view for that depth
36+
if (*returnSize <=depth) {
37+
*returnSize+=1;
38+
result[depth]=root->val;
39+
}
40+
41+
// Visit the right child first then left child
42+
dfs(root->right,result,returnSize,depth+1);
43+
dfs(root->left,result,returnSize,depth+1);
44+
}
45+
46+
/**
47+
* Note: The returned array must be malloced, assume caller calls free().
48+
*/
49+
int*rightSideView(structTreeNode*root,int*returnSize) {
50+
// Size of result array depends on the depth of tree, which can be precomputed
51+
int*result= (int*)malloc(sizeof(int)*100);
52+
*returnSize=0;
53+
54+
dfs(root,result,returnSize,0);
55+
56+
returnresult;
57+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/*
2+
Given an m x n integers matrix, return the length of the longest increasing path in matrix.
3+
Time; O(n*m)
4+
Space; O(n*m)
5+
6+
*/
7+
8+
intmax(inta,intb) {
9+
returna>b?a:b;
10+
}
11+
12+
intdfs(int**matrix,int**dp,intn,intm,inti,intj) {
13+
if (dp[i][j]!=0)
14+
returndp[i][j];
15+
intcpt=0;
16+
if (i>0&&matrix[i-1][j]>matrix[i][j])
17+
cpt=max(cpt,dfs(matrix,dp,n,m,i-1,j));
18+
if (j>0&&matrix[i][j-1]>matrix[i][j])
19+
cpt=max(cpt,dfs(matrix,dp,n,m,i,j-1));
20+
if (i<(n-1)&&matrix[i+1][j]>matrix[i][j])
21+
cpt=max(cpt,dfs(matrix,dp,n,m,i+1,j));
22+
if (j<(m-1)&&matrix[i][j+1]>matrix[i][j])
23+
cpt=max(cpt,dfs(matrix,dp,n,m,i,j+1));
24+
dp[i][j]=cpt+1;
25+
returncpt+1;
26+
}
27+
28+
intlongestIncreasingPath(int**matrix,intmatrixSize,int*matrixColSize){
29+
int**dp=malloc(sizeof(int*)*matrixSize);
30+
intm=*matrixColSize,i,j;
31+
for (i=0;i<matrixSize;i++)
32+
dp[i]=calloc(m,sizeof(int));
33+
intans=0;
34+
for (i=0;i<matrixSize;i++) {
35+
for (j=0;j<m;j++) {
36+
ans=max(ans,dfs(matrix,dp,matrixSize,m,i,j));
37+
}
38+
}
39+
returnans;
40+
}

‎c/66-Plus-One.c

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
/*
2+
Given an integer array where the elements represent the digits of a number,
3+
return the resulting array when we add one to it.
4+
Ex. digits = [1,2,3] + 1 -> [1,2,4]
5+
6+
The length of the array after adding 1 will either remain the same or
7+
increase by 1. So we keep the size of the result array as n+1 during the
8+
start. We iterate from the last digit to the first digit backwards and
9+
keep track of the carry generated by the previous digit.
10+
11+
If there is a carry left at the end, the addition caused the length to
12+
increase, so we return the result. Else if there is no carry, the length
13+
remained constant, so we skip the first element of result and return.
14+
15+
Time: O(n)
16+
Space: O(n)
17+
*/
18+
19+
/**
20+
* Note: The returned array must be malloced, assume caller calls free().
21+
*/
22+
int*plusOne(int*digits,intdigitsSize,int*returnSize){
23+
24+
// Reserve the result with a digitsSize+1 size array
25+
int*result= (int*)malloc(sizeof(int)*(digitsSize+1));
26+
*returnSize=digitsSize+1;
27+
result[0]=1;
28+
29+
intcarry=1;
30+
for (inti=digitsSize;i>0;--i) {
31+
intsum=digits[i-1]+carry;
32+
carry=sum/10;
33+
sum=sum%10;
34+
35+
result[i]=sum;
36+
}
37+
38+
if (carry)
39+
returnresult;
40+
41+
// Skip the additional element which was reserved for carry
42+
*returnSize=digitsSize;
43+
returnresult+1;
44+
}

‎c/84. Largest Rectangle in Histogram

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
const int MAX_N = 1e5 + 5;
2+
struct Stack
3+
{
4+
int top;
5+
int capacity;
6+
int *array;
7+
};
8+
9+
struct Stack *createStack()
10+
{
11+
struct Stack *stack = (struct Stack *)malloc(sizeof(struct Stack));
12+
stack->capacity = MAX_N;
13+
stack->top = -1;
14+
stack->array = (int *)malloc(stack->capacity * sizeof(int));
15+
return stack;
16+
}
17+
18+
int isFull(struct Stack *stack)
19+
{
20+
return stack->top == stack->capacity - 1;
21+
}
22+
23+
int isEmpty(struct Stack *stack)
24+
{
25+
return stack->top == -1;
26+
}
27+
28+
void push(struct Stack *stack, int val)
29+
{
30+
if (isFull(stack))
31+
return;
32+
stack->array[++stack->top] = val;
33+
}
34+
35+
void pop(struct Stack *stack)
36+
{
37+
if (isEmpty(stack))
38+
return;
39+
--stack->top;
40+
}
41+
42+
int peek(struct Stack *stack)
43+
{
44+
if (isEmpty(stack))
45+
return INT_MIN;
46+
return stack->array[stack->top];
47+
}
48+
49+
int max(int num1, int num2)
50+
{
51+
return (num1 > num2) ? num1 : num2;
52+
}
53+
54+
int largestRectangleArea(int *heights, int heightsSize)
55+
{
56+
int ans = 0;
57+
struct Stack *st = createStack();
58+
for (int i = 0; i < heightsSize; i++)
59+
{
60+
while (!isEmpty(st) && heights[peek(st)] > heights[i])
61+
{
62+
int tp = peek(st);
63+
pop(st);
64+
int dist = (isEmpty(st) ? i : i - peek(st) - 1);
65+
ans = max(ans, dist * heights[tp]);
66+
}
67+
push(st, i);
68+
}
69+
while (!isEmpty(st))
70+
{
71+
int tp = peek(st);
72+
pop(st);
73+
int dist = (isEmpty(st) ? heightsSize : heightsSize - peek(st) - 1);
74+
ans = max(ans, dist * heights[tp]);
75+
}
76+
return ans;
77+
}

‎cpp/678-Valid-Parenthesis-String.cpp

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
classSolution {
2+
public:
3+
boolcheckValidString(string s) {
4+
int n = s.size();
5+
6+
int balanced =0;
7+
for(int i=0; i<n; i++) {
8+
if(s[i] =='(' || s[i] =='*')
9+
balanced++;
10+
else
11+
balanced--;
12+
13+
if(balanced <0)
14+
returnfalse;
15+
}
16+
17+
if(balanced ==0)
18+
returntrue;
19+
20+
balanced =0;
21+
for(int i=n-1; i>=0; i--) {
22+
if(s[i] ==')' || s[i] =='*')
23+
balanced++;
24+
else
25+
balanced--;
26+
27+
if(balanced <0)
28+
returnfalse;
29+
}
30+
31+
returntrue;
32+
}
33+
};

‎csharp/1094-Car-Pooling.cs

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
publicclassSolution{
2+
publicboolCarPooling(int[][]trips,intcapacity){
3+
vardictionary=newSortedDictionary<int,int>();
4+
5+
foreach(vartripintrips)
6+
{
7+
if(!dictionary.ContainsKey(trip[1]))dictionary[trip[1]]=0;
8+
if(!dictionary.ContainsKey(trip[2]))dictionary[trip[2]]=0;
9+
dictionary[trip[1]]+=trip[0];dictionary[trip[2]]-=trip[0];
10+
}
11+
intcurrentPassennger=0;
12+
foreach(varkeyvalindictionary)
13+
{
14+
currentPassennger+=keyval.Value;
15+
if(currentPassennger>capacity)returnfalse;
16+
}
17+
returntrue;
18+
}
19+
}

‎csharp/1905-Count-Sub-Islands.cs

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
publicclassSolution{
2+
publicintCountSubIslands(int[][]grid1,int[][]grid2)
3+
{
4+
intr=grid1.Length,c=grid1[0].Length,subIslands=0;
5+
for(inti=0;i<r;i++)
6+
{
7+
for(intj=0;j<c;j++)
8+
{
9+
if(grid2[i][j]==1&&DfsSubIsLand(grid1,grid2,i,j))
10+
{
11+
subIslands++;
12+
}
13+
}
14+
}
15+
returnsubIslands;
16+
}
17+
18+
privateboolDfsSubIsLand(int[][]grid1,int[][]grid2,intr,intc)
19+
{
20+
if(r<0||c<0||r>=grid2.Length||c>=grid2[r].Length||grid2[r][c]==0){returntrue;}
21+
22+
grid2[r][c]=0;
23+
boolstillASubIsland=true;
24+
stillASubIsland&=DfsSubIsLand(grid1,grid2,r-1,c);
25+
stillASubIsland&=DfsSubIsLand(grid1,grid2,r,c+1);
26+
stillASubIsland&=DfsSubIsLand(grid1,grid2,r+1,c);
27+
stillASubIsland&=DfsSubIsLand(grid1,grid2,r,c-1);
28+
returnstillASubIsland&&grid1[r][c]==1;
29+
}
30+
}

‎csharp/51-N-Queens.cs

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
publicclassSolution{
2+
publicIList<IList<string>>SolveNQueens(intn)
3+
{
4+
varresult=newList<IList<string>>();
5+
IList<StringBuilder>board=newList<StringBuilder>();
6+
for(inti=0;i<n;i++)
7+
{
8+
board.Add(newStringBuilder(n));
9+
board[i].Append('.',n);
10+
11+
}
12+
backtrackingNQueens(n,0,board,result,newHashSet<(inti,intj)>(),newHashSet<(inti,intj)>(),newHashSet<(inti,intj)>());
13+
returnresult;
14+
}
15+
16+
privatevoidbacktrackingNQueens(intn,introw,IList<StringBuilder>board,List<IList<string>>result,HashSet<(inti,intj)>col,HashSet<(inti,intj)>positiveDiag,HashSet<(inti,intj)>negativeDiag)
17+
{
18+
if(n==0)
19+
{
20+
result.Add(board.Select(s=>s.ToString()).ToList());
21+
return;
22+
}
23+
if(row==board.Count)return;
24+
25+
for(intc=0;c<board.Count;c++)
26+
{
27+
(inti,intj)column=(0,c);
28+
intm=Math.Min(row,c);
29+
(inti,intj)diag1=(row-m,c-m);
30+
m=Math.Min(row,board.Count-1-c);
31+
(inti,intj)diag2=(row-m,c+m);
32+
33+
if(col.Contains(column)||positiveDiag.Contains(diag1)||
34+
negativeDiag.Contains(diag2))continue;
35+
36+
col.Add(column);
37+
positiveDiag.Add(diag1);
38+
negativeDiag.Add(diag2);
39+
40+
41+
board[row][c]='Q';
42+
backtrackingNQueens(n-1,row+1,board,result,col,positiveDiag,negativeDiag);
43+
44+
board[row][c]='.';
45+
col.Remove(column);
46+
positiveDiag.Remove(diag1);
47+
negativeDiag.Remove(diag2);
48+
}
49+
}
50+
51+
}

‎csharp/695-Max-Area-of-Island.cs

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
publicclassSolution{
2+
publicintMaxAreaOfIsland(int[][]grid)
3+
{
4+
intr=grid.Length,c=grid[0].Length,area=0;
5+
6+
bool[,]visits=newbool[r,c];
7+
for(inti=0;i<r;i++)
8+
{
9+
for(intj=0;j<c;j++)
10+
{
11+
area=Math.Max(area,DFSMaxAreaOfIsland(i,j,grid,visits));
12+
}
13+
}
14+
15+
returnarea;
16+
}
17+
18+
privateintDFSMaxAreaOfIsland(introw,intcol,int[][]grid,bool[,]visits)
19+
{
20+
intm=grid.Length,n=grid[0].Length;
21+
if(row<0||row>=m||col<0||col>=n||visits[row,col]||grid[row][col]==0)
22+
return0;
23+
visits[row,col]=true;
24+
return(1+DFSMaxAreaOfIsland(row,col+1,grid,visits)+
25+
DFSMaxAreaOfIsland(row,col-1,grid,visits)+
26+
DFSMaxAreaOfIsland(row+1,col,grid,visits)+
27+
DFSMaxAreaOfIsland(row-1,col,grid,visits));
28+
}}

0 commit comments

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