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

Commit6a3e3fd

Browse files
authored
Added tasks 84-101
1 parentbbe5057 commit6a3e3fd

File tree

15 files changed

+442
-0
lines changed

15 files changed

+442
-0
lines changed
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
namespaceLeetCodeNet.G0001_0100.S0084_largest_rectangle_in_histogram{
2+
3+
usingXunit;
4+
5+
publicclassSolutionTest{
6+
[Fact]
7+
publicvoidLargestRectangleArea(){
8+
Assert.Equal(10,newSolution().LargestRectangleArea(newint[]{2,1,5,6,2,3}));
9+
}
10+
11+
[Fact]
12+
publicvoidLargestRectangleArea2(){
13+
Assert.Equal(4,newSolution().LargestRectangleArea(newint[]{2,4}));
14+
}
15+
}
16+
}
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
namespaceLeetCodeNet.G0001_0100.S0094_binary_tree_inorder_traversal{
2+
3+
usingXunit;
4+
usingLeetCodeNet.Com_github_leetcode;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidInorderTraversal(){
9+
TreeNodetreeNode=newTreeNode(1);
10+
TreeNodetreeNode2=newTreeNode(2);
11+
treeNode.right=treeNode2;
12+
treeNode2.left=newTreeNode(3);
13+
Assert.Equal(newList<int>{1,3,2},newSolution().InorderTraversal(treeNode));
14+
}
15+
16+
[Fact]
17+
publicvoidInorderTraversal2(){
18+
Assert.Equal(newList<int>{},newSolution().InorderTraversal(null));
19+
}
20+
21+
[Fact]
22+
publicvoidInorderTraversal3(){
23+
Assert.Equal(newList<int>{1},newSolution().InorderTraversal(newTreeNode(1)));
24+
}
25+
}
26+
}
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
namespaceLeetCodeNet.G0001_0100.S0096_unique_binary_search_trees{
2+
3+
usingXunit;
4+
5+
publicclassSolutionTest{
6+
[Fact]
7+
publicvoidNumTrees(){
8+
Assert.Equal(5,newSolution().NumTrees(3));
9+
}
10+
11+
[Fact]
12+
publicvoidNumTrees2(){
13+
Assert.Equal(1,newSolution().NumTrees(1));
14+
}
15+
}
16+
}
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
namespaceLeetCodeNet.G0001_0100.S0098_validate_binary_search_tree{
2+
3+
usingXunit;
4+
usingLeetCodeNet.Com_github_leetcode;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidIsValidBST(){
9+
TreeNodetreeNode=newTreeNode(2);
10+
treeNode.left=newTreeNode(1);
11+
treeNode.right=newTreeNode(3);
12+
Assert.True(newSolution().IsValidBST(treeNode));
13+
}
14+
15+
[Fact]
16+
publicvoidIsValidBST2(){
17+
TreeNodetreeNode=newTreeNode(5);
18+
treeNode.left=newTreeNode(1);
19+
TreeNodetreeNode2=newTreeNode(4);
20+
treeNode2.left=newTreeNode(3);
21+
treeNode2.right=newTreeNode(6);
22+
treeNode.right=treeNode2;
23+
Assert.False(newSolution().IsValidBST(treeNode));
24+
}
25+
}
26+
}
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
namespaceLeetCodeNet.G0101_0200.S0101_symmetric_tree{
2+
3+
usingXunit;
4+
usingLeetCodeNet.Com_github_leetcode;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidIsSymmetric(){
9+
TreeNodetreeNode=newTreeNode(1);
10+
treeNode.left=newTreeNode(2);
11+
treeNode.right=newTreeNode(2);
12+
treeNode.left.left=newTreeNode(3);
13+
treeNode.left.right=newTreeNode(4);
14+
treeNode.right.left=newTreeNode(4);
15+
treeNode.right.right=newTreeNode(3);
16+
Assert.True(newSolution().IsSymmetric(treeNode));
17+
}
18+
19+
[Fact]
20+
publicvoidIsSymmetric2(){
21+
TreeNodetreeNode=newTreeNode(1);
22+
treeNode.left=newTreeNode(2);
23+
treeNode.right=newTreeNode(2);
24+
treeNode.left.right=newTreeNode(3);
25+
treeNode.right.right=newTreeNode(3);
26+
Assert.False(newSolution().IsSymmetric(treeNode));
27+
}
28+
}
29+
}
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
namespaceLeetCodeNet.G0001_0100.S0084_largest_rectangle_in_histogram{
2+
3+
// #Hard #Top_100_Liked_Questions #Top_Interview_Questions #Array #Stack #Monotonic_Stack
4+
// #Big_O_Time_O(n_log_n)_Space_O(log_n) #2024_01_08_Time_304_ms_(30.92%)_Space_52.4_MB_(29.92%)
5+
6+
publicclassSolution{
7+
publicintLargestRectangleArea(int[]heights){
8+
intmaxArea=0,i=0;
9+
Stack<int>stack=newStack<int>();
10+
while(i<=heights.Length){
11+
varcurrHeight=i==heights.Length?0:heights[i];
12+
if(!stack.Any()||currHeight>=heights[stack.Peek()]){
13+
stack.Push(i);
14+
i++;
15+
}
16+
else{
17+
intindex=stack.Pop();
18+
intheight=heights[index];
19+
intwidth=(!stack.Any())?i:(i-1)-stack.Peek();
20+
maxArea=Math.Max(maxArea,height*width);
21+
}
22+
}
23+
returnmaxArea;
24+
}
25+
}
26+
}
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
84\. Largest Rectangle in Histogram
2+
3+
Hard
4+
5+
Given an array of integers`heights` representing the histogram's bar height where the width of each bar is`1`, return_the area of the largest rectangle in the histogram_.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg)
10+
11+
**Input:** heights =[2,1,5,6,2,3]
12+
13+
**Output:** 10
14+
15+
**Explanation:** The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.
16+
17+
**Example 2:**
18+
19+
![](https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg)
20+
21+
**Input:** heights =[2,4]
22+
23+
**Output:** 4
24+
25+
**Constraints:**
26+
27+
* <code>1 <= heights.length <= 10<sup>5</sup></code>
28+
* <code>0 <= heights[i] <= 10<sup>4</sup></code>
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
namespaceLeetCodeNet.G0001_0100.S0094_binary_tree_inorder_traversal{
2+
3+
// #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Depth_First_Search #Tree #Binary_Tree
4+
// #Stack #Data_Structure_I_Day_10_Tree #Udemy_Tree_Stack_Queue #Big_O_Time_O(n)_Space_O(n)
5+
// #2024_01_08_Time_90_ms_(99.30%)_Space_45.5_MB_(6.37%)
6+
7+
usingLeetCodeNet.Com_github_leetcode;
8+
9+
/**
10+
* Definition for a binary tree node.
11+
* public class TreeNode {
12+
* public int val;
13+
* public TreeNode left;
14+
* public TreeNode right;
15+
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
16+
* this.val = val;
17+
* this.left = left;
18+
* this.right = right;
19+
* }
20+
* }
21+
*/
22+
publicclassSolution{
23+
publicIList<int>InorderTraversal(TreeNoderoot){
24+
if(root==null){
25+
returnnewList<int>();
26+
}
27+
varanswer=newList<int>();
28+
InorderTraversal(root,answer);
29+
returnanswer;
30+
}
31+
32+
privatevoidInorderTraversal(TreeNoderoot,IList<int>answer){
33+
if(root==null){
34+
return;
35+
}
36+
if(root.left!=null){
37+
InorderTraversal(root.left,answer);
38+
}
39+
answer.Add((int)root.val);
40+
if(root.right!=null){
41+
InorderTraversal(root.right,answer);
42+
}
43+
}
44+
}
45+
}
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
94\. Binary Tree Inorder Traversal
2+
3+
Easy
4+
5+
Given the`root` of a binary tree, return_the inorder traversal of its nodes' values_.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg)
10+
11+
**Input:** root =[1,null,2,3]
12+
13+
**Output:**[1,3,2]
14+
15+
**Example 2:**
16+
17+
**Input:** root =[]
18+
19+
**Output:**[]
20+
21+
**Example 3:**
22+
23+
**Input:** root =[1]
24+
25+
**Output:**[1]
26+
27+
**Example 4:**
28+
29+
![](https://assets.leetcode.com/uploads/2020/09/15/inorder_5.jpg)
30+
31+
**Input:** root =[1,2]
32+
33+
**Output:**[2,1]
34+
35+
**Example 5:**
36+
37+
![](https://assets.leetcode.com/uploads/2020/09/15/inorder_4.jpg)
38+
39+
**Input:** root =[1,null,2]
40+
41+
**Output:**[1,2]
42+
43+
**Constraints:**
44+
45+
* The number of nodes in the tree is in the range`[0, 100]`.
46+
*`-100 <= Node.val <= 100`
47+
48+
**Follow up:** Recursive solution is trivial, could you do it iteratively?
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
namespaceLeetCodeNet.G0001_0100.S0096_unique_binary_search_trees{
2+
3+
// #Medium #Top_100_Liked_Questions #Dynamic_Programming #Math #Tree #Binary_Tree
4+
// #Binary_Search_Tree #Dynamic_Programming_I_Day_11 #Big_O_Time_O(n)_Space_O(1)
5+
// #2024_01_08_Time_13_ms_(98.48%)_Space_26.2_MB_(88.64%)
6+
7+
publicclassSolution{
8+
publicintNumTrees(intn){
9+
longresult=1;
10+
for(inti=0;i<n;i++){
11+
result*=2L*n-i;
12+
result/=i+1;
13+
}
14+
result/=n+1;
15+
return(int)result;
16+
}
17+
}
18+
}
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
96\. Unique Binary Search Trees
2+
3+
Medium
4+
5+
Given an integer`n`, return_the number of structurally unique**BST'**s (binary search trees) which has exactly_`n`_nodes of unique values from_`1`_to_`n`.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg)
10+
11+
**Input:** n = 3
12+
13+
**Output:** 5
14+
15+
**Example 2:**
16+
17+
**Input:** n = 1
18+
19+
**Output:** 1
20+
21+
**Constraints:**
22+
23+
*`1 <= n <= 19`
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
namespaceLeetCodeNet.G0001_0100.S0098_validate_binary_search_tree{
2+
3+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Depth_First_Search #Tree #Binary_Tree
4+
// #Binary_Search_Tree #Data_Structure_I_Day_14_Tree #Level_1_Day_8_Binary_Search_Tree
5+
// #Udemy_Tree_Stack_Queue #Big_O_Time_O(N)_Space_O(log(N))
6+
// #2024_01_08_Time_75_ms_(97.31%)_Space_45.3_MB_(19.73%)
7+
8+
usingLeetCodeNet.Com_github_leetcode;
9+
10+
/**
11+
* Definition for a binary tree node.
12+
* public class TreeNode {
13+
* public int val;
14+
* public TreeNode left;
15+
* public TreeNode right;
16+
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
17+
* this.val = val;
18+
* this.left = left;
19+
* this.right = right;
20+
* }
21+
* }
22+
*/
23+
publicclassSolution{
24+
publicboolIsValidBST(TreeNoderoot){
25+
returnSolve(root,long.MinValue,long.MaxValue);
26+
}
27+
// we will send a valid range and check whether the root lies in the range
28+
// and update the range for the subtrees
29+
privateboolSolve(TreeNoderoot,longleft,longright){
30+
if(root==null){
31+
returntrue;
32+
}
33+
if(root.val<=left||root.val>=right){
34+
returnfalse;
35+
}
36+
returnSolve(root.left,left,(long)root.val)&&Solve(root.right,(long)root.val,right);
37+
}
38+
}
39+
}
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
98\. Validate Binary Search Tree
2+
3+
Medium
4+
5+
Given the`root` of a binary tree,_determine if it is a valid binary search tree (BST)_.
6+
7+
A**valid BST** is defined as follows:
8+
9+
* The left subtree of a node contains only nodes with keys**less than** the node's key.
10+
* The right subtree of a node contains only nodes with keys**greater than** the node's key.
11+
* Both the left and right subtrees must also be binary search trees.
12+
13+
**Example 1:**
14+
15+
![](https://assets.leetcode.com/uploads/2020/12/01/tree1.jpg)
16+
17+
**Input:** root =[2,1,3]
18+
19+
**Output:** true
20+
21+
**Example 2:**
22+
23+
![](https://assets.leetcode.com/uploads/2020/12/01/tree2.jpg)
24+
25+
**Input:** root =[5,1,4,null,null,3,6]
26+
27+
**Output:** false
28+
29+
**Explanation:** The root node's value is 5 but its right child's value is 4.
30+
31+
**Constraints:**
32+
33+
* The number of nodes in the tree is in the range <code>[1, 10<sup>4</sup>]</code>.
34+
* <code>-2<sup>31</sup> <= Node.val <= 2<sup>31</sup> - 1</code>

0 commit comments

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