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

Commit13e1675

Browse files
authored
Added tasks 124-138
1 parent76cd9ce commit13e1675

File tree

16 files changed

+561
-0
lines changed

16 files changed

+561
-0
lines changed
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
namespaceLeetCodeNet.G0101_0200.S0124_binary_tree_maximum_path_sum{
2+
3+
usingSystem;
4+
usingXunit;
5+
usingCom_github_leetcode;
6+
7+
publicclassSolutionTest{
8+
[Fact]
9+
publicvoidMaxPathSum(){
10+
TreeNodetreeNode=TreeNode.Create(newList<int?>{1,2,3});
11+
Assert.Equal(6,newSolution().MaxPathSum(treeNode));
12+
}
13+
14+
[Fact]
15+
publicvoidMaxPathSum2(){
16+
TreeNodetreeNode=TreeNode.Create(newList<int?>{-10,9,20,null,null,15,7});
17+
Assert.Equal(42,newSolution().MaxPathSum(treeNode));
18+
}
19+
}
20+
}
Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
namespaceLeetCodeNet.G0101_0200.S0128_longest_consecutive_sequence{
2+
3+
usingSystem;
4+
usingXunit;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidLongestConsecutive(){
9+
Assert.Equal(4,newSolution().LongestConsecutive(newint[]{100,4,200,1,3,2}));
10+
}
11+
12+
[Fact]
13+
publicvoidLongestConsecutive2(){
14+
Assert.Equal(9,newSolution().LongestConsecutive(newint[]{0,3,7,2,5,8,4,6,0,1}));
15+
}
16+
}
17+
}
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
namespaceLeetCodeNet.G0101_0200.S0131_palindrome_partitioning{
2+
3+
usingSystem;
4+
usingXunit;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidPartition(){
9+
Assert.Equal(
10+
newList<IList<string>>{
11+
newList<string>{"a","a","b"},
12+
newList<string>{"aa","b"}
13+
},
14+
newSolution().Partition("aab"));
15+
}
16+
17+
[Fact]
18+
publicvoidPartition2(){
19+
Assert.Equal(
20+
newList<IList<string>>{newList<string>{"a"}},
21+
newSolution().Partition("a"));
22+
}
23+
}
24+
}
Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
namespaceLeetCodeNet.G0101_0200.S0136_single_number{
2+
3+
usingSystem;
4+
usingXunit;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidSingleNumber(){
9+
Assert.Equal(1,newSolution().SingleNumber(newint[]{2,2,1}));
10+
}
11+
12+
[Fact]
13+
publicvoidSingleNumber2(){
14+
Assert.Equal(4,newSolution().SingleNumber(newint[]{4,1,2,1,2}));
15+
}
16+
17+
[Fact]
18+
publicvoidSingleNumber3(){
19+
Assert.Equal(1,newSolution().SingleNumber(newint[]{1}));
20+
}
21+
}
22+
}
Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
namespaceLeetCodeNet.G0101_0200.S0138_copy_list_with_random_pointer{
2+
3+
usingSystem;
4+
usingXunit;
5+
usingLeetCodeNet.Com_github_leetcode;
6+
7+
publicclassSolutionTest{
8+
[Fact]
9+
publicvoidCopyRandomList(){
10+
Nodenode7=newNode(7);
11+
Nodenode13=newNode(13);
12+
Nodenode11=newNode(11);
13+
Nodenode10=newNode(10);
14+
Nodenode1=newNode(1);
15+
node7.next=node13;
16+
node13.next=node11;
17+
node11.next=node10;
18+
node10.next=node1;
19+
node1.next=null;
20+
node7.random=null;
21+
node13.random=node7;
22+
node11.random=node1;
23+
node10.random=node11;
24+
node1.random=node7;
25+
Assert.Equal(
26+
"[[7,null],[13,0],[11,4],[10,2],[1,0]]",
27+
newSolution().CopyRandomList(node7).ToString());
28+
}
29+
30+
[Fact]
31+
publicvoidCopyRandomList2(){
32+
Nodenode1=newNode(1);
33+
Nodenode2=newNode(2);
34+
node1.next=node2;
35+
node1.random=node1;
36+
node2.next=null;
37+
node2.random=node2;
38+
Assert.Equal("[[1,1],[2,1]]",newSolution().CopyRandomList(node1).ToString());
39+
}
40+
41+
[Fact]
42+
publicvoidCopyRandomList3(){
43+
Nodenode31=newNode(3);
44+
Nodenode32=newNode(3);
45+
Nodenode33=newNode(3);
46+
node31.next=node32;
47+
node31.random=null;
48+
node32.next=node33;
49+
node32.random=node31;
50+
node33.next=null;
51+
node33.random=null;
52+
Assert.Equal("[[3,null],[3,0],[3,null]]",newSolution().CopyRandomList(node31).ToString());
53+
}
54+
}
55+
}
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
namespaceLeetCodeNet.Com_github_leetcode{
2+
3+
publicclassNode{
4+
publicintval;
5+
publicNodenext;
6+
publicNoderandom;
7+
8+
publicNode(){
9+
this.val=0;
10+
}
11+
12+
publicNode(intval){
13+
this.val=val;
14+
}
15+
16+
publicNode(intval,Nodenext,Noderandom){
17+
this.val=val;
18+
this.next=next;
19+
this.random=random;
20+
}
21+
22+
publicoverridestringToString(){
23+
List<string>result=newList<string>{};
24+
List<string>result2=newList<string>{
25+
val.ToString()
26+
};
27+
if(random==null){
28+
result2.Add("null");
29+
}else{
30+
result2.Add(random.val.ToString());
31+
}
32+
stringresult2String="["+string.Join(",",result2)+"]";
33+
result.Add(result2String);
34+
Nodecurr=next;
35+
while(curr!=null){
36+
List<string>result3=newList<string>{
37+
curr.val.ToString()
38+
};
39+
if(curr.random==null){
40+
result3.Add("null");
41+
}else{
42+
intrandomIndex=0;
43+
Nodecurr2=this;
44+
while(curr2.next!=null&&curr2!=curr.random){
45+
randomIndex+=1;
46+
curr2=curr2.next;
47+
}
48+
result3.Add(randomIndex.ToString());
49+
}
50+
stringresult3String="["+string.Join(",",result3)+"]";
51+
result.Add(result3String);
52+
curr=curr.next;
53+
}
54+
return"["+string.Join(",",result)+"]";
55+
}
56+
}
57+
}
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
namespaceLeetCodeNet.G0101_0200.S0124_binary_tree_maximum_path_sum{
2+
3+
// #Hard #Top_100_Liked_Questions #Top_Interview_Questions #Dynamic_Programming #Depth_First_Search
4+
// #Tree #Binary_Tree #Udemy_Tree_Stack_Queue #Big_O_Time_O(N)_Space_O(N)
5+
// #2024_01_09_Time_85_ms_(91.69%)_Space_47.6_MB_(23.52%)
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+
privateintmax=int.MinValue;
24+
25+
privateintHelper(TreeNoderoot){
26+
if(root==null){
27+
return0;
28+
}
29+
// to avoid the -ve values in left side we will compare them with 0
30+
intleft=Math.Max(0,Helper(root.left));
31+
intright=Math.Max(0,Helper(root.right));
32+
intcurrent=(int)(root.val+left+right);
33+
if(current>max){
34+
max=current;
35+
}
36+
return(int)(root.val+Math.Max(left,right));
37+
}
38+
39+
publicintMaxPathSum(TreeNoderoot){
40+
Helper(root);
41+
returnmax;
42+
}
43+
}
44+
}
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
124\. Binary Tree Maximum Path Sum
2+
3+
Hard
4+
5+
A**path** in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence**at most once**. Note that the path does not need to pass through the root.
6+
7+
The**path sum** of a path is the sum of the node's values in the path.
8+
9+
Given the`root` of a binary tree, return_the maximum**path sum** of any**non-empty** path_.
10+
11+
**Example 1:**
12+
13+
![](https://assets.leetcode.com/uploads/2020/10/13/exx1.jpg)
14+
15+
**Input:** root =[1,2,3]
16+
17+
**Output:** 6
18+
19+
**Explanation:** The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
20+
21+
**Example 2:**
22+
23+
![](https://assets.leetcode.com/uploads/2020/10/13/exx2.jpg)
24+
25+
**Input:** root =[-10,9,20,null,null,15,7]
26+
27+
**Output:** 42
28+
29+
**Explanation:** The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
30+
31+
**Constraints:**
32+
33+
* The number of nodes in the tree is in the range <code>[1, 3 * 10<sup>4</sup>]</code>.
34+
*`-1000 <= Node.val <= 1000`
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
namespaceLeetCodeNet.G0101_0200.S0128_longest_consecutive_sequence{
2+
3+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Hash_Table #Union_Find
4+
// #Big_O_Time_O(N_log_N)_Space_O(1) #2024_01_09_Time_201_ms_(61.50%)_Space_61.2_MB_(52.89%)
5+
6+
publicclassSolution{
7+
publicintLongestConsecutive(int[]nums){
8+
if(nums.Length==0){
9+
return0;
10+
}
11+
Array.Sort(nums);
12+
intmax=int.MinValue;
13+
intthsMax=1;
14+
for(inti=0;i<nums.Length-1;i++){
15+
if(nums[i+1]==nums[i]+1){
16+
thsMax+=1;
17+
continue;
18+
}
19+
if(nums[i+1]==nums[i]){
20+
continue;
21+
}
22+
// Start of a new Sequene
23+
max=Math.Max(max,thsMax);
24+
thsMax=1;
25+
}
26+
returnMath.Max(max,thsMax);
27+
}
28+
}
29+
}
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
128\. Longest Consecutive Sequence
2+
3+
Medium
4+
5+
Given an unsorted array of integers`nums`, return_the length of the longest consecutive elements sequence._
6+
7+
You must write an algorithm that runs in`O(n)` time.
8+
9+
**Example 1:**
10+
11+
**Input:** nums =[100,4,200,1,3,2]
12+
13+
**Output:** 4
14+
15+
**Explanation:** The longest consecutive elements sequence is`[1, 2, 3, 4]`. Therefore its length is 4.
16+
17+
**Example 2:**
18+
19+
**Input:** nums =[0,3,7,2,5,8,4,6,0,1]
20+
21+
**Output:** 9
22+
23+
**Constraints:**
24+
25+
* <code>0 <= nums.length <= 10<sup>5</sup></code>
26+
* <code>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup></code>
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
namespaceLeetCodeNet.G0101_0200.S0131_palindrome_partitioning{
2+
3+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #String #Dynamic_Programming
4+
// #Backtracking #Big_O_Time_O(N*2^N)_Space_O(2^N*N)
5+
// #2024_01_09_Time_677_ms_(38.30%)_Space_148_MB_(5.53%)
6+
7+
publicclassSolution{
8+
publicIList<IList<string>>Partition(strings){
9+
IList<IList<string>>res=newList<IList<string>>();
10+
Backtracking(res,newList<string>(),s,0);
11+
returnres;
12+
}
13+
14+
privatevoidBacktracking(IList<IList<string>>res,IList<string>currArr,strings,intstart){
15+
if(start==s.Length){
16+
res.Add(newList<string>(currArr));
17+
}
18+
for(intend=start;end<s.Length;end++){
19+
if(!IsPanlindrome(s,start,end)){
20+
continue;
21+
}
22+
currArr.Add(s.Substring(start,end-start+1));
23+
Backtracking(res,currArr,s,end+1);
24+
currArr.RemoveAt(currArr.Count-1);
25+
}
26+
}
27+
28+
privateboolIsPanlindrome(strings,intstart,intend){
29+
while(start<end&&s[start]==s[end]){
30+
start++;
31+
end--;
32+
}
33+
returnstart>=end;
34+
}
35+
}
36+
}

0 commit comments

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