Skip to content

Commit 13e1675

Browse files
ThanhNITThanhNIT
authored
Added tasks 124-138
1 parent 76cd9ce commit 13e1675

File tree

16 files changed

+561
-0
lines changed

16 files changed

+561
-0
lines changed

‎LeetCodeNet.Tests/G0101_0200/S0124_binary_tree_maximum_path_sum/SolutionTest.cs

+20
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
namespace LeetCodeNet.G0101_0200.S0124_binary_tree_maximum_path_sum {
2+
3+
using System;
4+
using Xunit;
5+
using Com_github_leetcode;
6+
7+
public class SolutionTest {
8+
[Fact]
9+
public void MaxPathSum() {
10+
TreeNode treeNode = TreeNode.Create(new List<int?> {1, 2, 3});
11+
Assert.Equal(6, new Solution().MaxPathSum(treeNode));
12+
}
13+
14+
[Fact]
15+
public void MaxPathSum2() {
16+
TreeNode treeNode = TreeNode.Create(new List<int?> {-10, 9, 20, null, null, 15, 7});
17+
Assert.Equal(42, new Solution().MaxPathSum(treeNode));
18+
}
19+
}
20+
}

‎LeetCodeNet.Tests/G0101_0200/S0128_longest_consecutive_sequence/SolutionTest.cs

+17
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
namespace LeetCodeNet.G0101_0200.S0128_longest_consecutive_sequence {
2+
3+
using System;
4+
using Xunit;
5+
6+
public class SolutionTest {
7+
[Fact]
8+
public void LongestConsecutive() {
9+
Assert.Equal(4, new Solution().LongestConsecutive(new int[] {100, 4, 200, 1, 3, 2}));
10+
}
11+
12+
[Fact]
13+
public void LongestConsecutive2() {
14+
Assert.Equal(9, new Solution().LongestConsecutive(new int[] {0, 3, 7, 2, 5, 8, 4, 6, 0, 1}));
15+
}
16+
}
17+
}

‎LeetCodeNet.Tests/G0101_0200/S0131_palindrome_partitioning/SolutionTest.cs

+24
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
namespace LeetCodeNet.G0101_0200.S0131_palindrome_partitioning {
2+
3+
using System;
4+
using Xunit;
5+
6+
public class SolutionTest {
7+
[Fact]
8+
public void Partition() {
9+
Assert.Equal(
10+
new List<IList<string>> {
11+
new List<string> {"a", "a", "b"},
12+
new List<string> {"aa", "b"}
13+
},
14+
new Solution().Partition("aab"));
15+
}
16+
17+
[Fact]
18+
public void Partition2() {
19+
Assert.Equal(
20+
new List<IList<string>> {new List<string> {"a"}},
21+
new Solution().Partition("a"));
22+
}
23+
}
24+
}

‎LeetCodeNet.Tests/G0101_0200/S0136_single_number/SolutionTest.cs

+22
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
namespace LeetCodeNet.G0101_0200.S0136_single_number {
2+
3+
using System;
4+
using Xunit;
5+
6+
public class SolutionTest {
7+
[Fact]
8+
public void SingleNumber() {
9+
Assert.Equal(1, new Solution().SingleNumber(new int[] {2, 2, 1}));
10+
}
11+
12+
[Fact]
13+
public void SingleNumber2() {
14+
Assert.Equal(4, new Solution().SingleNumber(new int[] {4, 1, 2, 1, 2}));
15+
}
16+
17+
[Fact]
18+
public void SingleNumber3() {
19+
Assert.Equal(1, new Solution().SingleNumber(new int[] {1}));
20+
}
21+
}
22+
}

‎LeetCodeNet.Tests/G0101_0200/S0138_copy_list_with_random_pointer/SolutionTest.cs

+55
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
namespace LeetCodeNet.G0101_0200.S0138_copy_list_with_random_pointer {
2+
3+
using System;
4+
using Xunit;
5+
using LeetCodeNet.Com_github_leetcode;
6+
7+
public class SolutionTest {
8+
[Fact]
9+
public void CopyRandomList() {
10+
Node node7 = new Node(7);
11+
Node node13 = new Node(13);
12+
Node node11 = new Node(11);
13+
Node node10 = new Node(10);
14+
Node node1 = new Node(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+
new Solution().CopyRandomList(node7).ToString());
28+
}
29+
30+
[Fact]
31+
public void CopyRandomList2() {
32+
Node node1 = new Node(1);
33+
Node node2 = new Node(2);
34+
node1.next = node2;
35+
node1.random = node1;
36+
node2.next = null;
37+
node2.random = node2;
38+
Assert.Equal("[[1,1],[2,1]]", new Solution().CopyRandomList(node1).ToString());
39+
}
40+
41+
[Fact]
42+
public void CopyRandomList3() {
43+
Node node31 = new Node(3);
44+
Node node32 = new Node(3);
45+
Node node33 = new Node(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]]", new Solution().CopyRandomList(node31).ToString());
53+
}
54+
}
55+
}

‎LeetCodeNet/Com_github_leetcode/Node.cs

+57
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
namespace LeetCodeNet.Com_github_leetcode {
2+
3+
public class Node {
4+
public int val;
5+
public Node next;
6+
public Node random;
7+
8+
public Node() {
9+
this.val = 0;
10+
}
11+
12+
public Node(int val) {
13+
this.val = val;
14+
}
15+
16+
public Node(int val, Node next, Node random) {
17+
this.val = val;
18+
this.next = next;
19+
this.random = random;
20+
}
21+
22+
public override string ToString() {
23+
List<string> result = new List<string>{};
24+
List<string> result2 = new List<string> {
25+
val.ToString()
26+
};
27+
if (random == null) {
28+
result2.Add("null");
29+
} else {
30+
result2.Add(random.val.ToString());
31+
}
32+
string result2String = "[" + string.Join(",", result2) + "]";
33+
result.Add(result2String);
34+
Node curr = next;
35+
while (curr != null) {
36+
List<string> result3 = new List<string> {
37+
curr.val.ToString()
38+
};
39+
if (curr.random == null) {
40+
result3.Add("null");
41+
} else {
42+
int randomIndex = 0;
43+
Node curr2 = this;
44+
while (curr2.next != null && curr2 != curr.random) {
45+
randomIndex += 1;
46+
curr2 = curr2.next;
47+
}
48+
result3.Add(randomIndex.ToString());
49+
}
50+
string result3String = "[" + string.Join(",", result3) + "]";
51+
result.Add(result3String);
52+
curr = curr.next;
53+
}
54+
return "[" + string.Join(",", result) + "]";
55+
}
56+
}
57+
}

‎LeetCodeNet/G0101_0200/S0124_binary_tree_maximum_path_sum/Solution.cs

+44
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
namespace LeetCodeNet.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+
using LeetCodeNet.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+
public class Solution {
23+
private int max = int.MinValue;
24+
25+
private int Helper(TreeNode root) {
26+
if (root == null) {
27+
return 0;
28+
}
29+
// to avoid the -ve values in left side we will compare them with 0
30+
int left = Math.Max(0, Helper(root.left));
31+
int right = Math.Max(0, Helper(root.right));
32+
int current = (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+
public int MaxPathSum(TreeNode root) {
40+
Helper(root);
41+
return max;
42+
}
43+
}
44+
}

‎LeetCodeNet/G0101_0200/S0124_binary_tree_maximum_path_sum/readme.md

+34
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`

‎LeetCodeNet/G0101_0200/S0128_longest_consecutive_sequence/Solution.cs

+29
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
namespace LeetCodeNet.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+
public class Solution {
7+
public int LongestConsecutive(int[] nums) {
8+
if (nums.Length == 0) {
9+
return 0;
10+
}
11+
Array.Sort(nums);
12+
int max = int.MinValue;
13+
int thsMax = 1;
14+
for (int i = 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+
return Math.Max(max, thsMax);
27+
}
28+
}
29+
}

‎LeetCodeNet/G0101_0200/S0128_longest_consecutive_sequence/readme.md

+26
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>

‎LeetCodeNet/G0101_0200/S0131_palindrome_partitioning/Solution.cs

+36
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
namespace LeetCodeNet.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+
public class Solution {
8+
public IList<IList<string>> Partition(string s) {
9+
IList<IList<string>> res = new List<IList<string>>();
10+
Backtracking(res, new List<string>(), s, 0);
11+
return res;
12+
}
13+
14+
private void Backtracking(IList<IList<string>> res, IList<string> currArr, string s, int start) {
15+
if (start == s.Length) {
16+
res.Add(new List<string>(currArr));
17+
}
18+
for (int end = 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+
private bool IsPanlindrome(string s, int start, int end) {
29+
while (start < end && s[start] == s[end]) {
30+
start++;
31+
end--;
32+
}
33+
return start >= end;
34+
}
35+
}
36+
}

0 commit comments

Comments
 (0)