Added tasks 139-148

ThanhNIT · web-flow · commit b324331736b3 · 2024-01-09T20:43:05.000+02:00
diff --git a/LeetCodeNet.Tests/G0101_0200/S0139_word_break/SolutionTest.cs b/LeetCodeNet.Tests/G0101_0200/S0139_word_break/SolutionTest.cs
@@ -0,0 +1,21 @@
+namespace LeetCodeNet.G0101_0200.S0139_word_break {
+
+using Xunit;
+
+public class SolutionTest {
+    [Fact]
+    public void WordBreak() {
+        Assert.True(new Solution().WordBreak("leetcode", new List<string> { "leet", "code" }));
+    }
+
+    [Fact]
+    public void WordBreak2() {
+        Assert.True(new Solution().WordBreak("applepenapple", new List<string> { "apple", "pen" }));
+    }
+
+    [Fact]
+    public void WordBreak3() {
+        Assert.False(new Solution().WordBreak("catsandog", new List<string> { "cats", "dog", "sand", "and", "cat" }));
+    }
+}
+}
diff --git a/LeetCodeNet.Tests/G0101_0200/S0141_linked_list_cycle/SolutionTest.cs b/LeetCodeNet.Tests/G0101_0200/S0141_linked_list_cycle/SolutionTest.cs
@@ -0,0 +1,31 @@
+namespace LeetCodeNet.G0101_0200.S0141_linked_list_cycle {
+
+using Xunit;
+using LeetCodeNet.Com_github_leetcode;
+
+public class SolutionTest {
+    [Fact]
+    public void HasCycle() {
+        ListNode listNode1 = new ListNode(3);
+        listNode1.next = new ListNode(2);
+        listNode1.next.next = new ListNode(0);
+        listNode1.next.next.next = new ListNode(-4);
+        listNode1.next.next.next.next = listNode1.next;
+        Assert.True(new Solution().HasCycle(listNode1));
+    }
+
+    [Fact]
+    public void HasCycle2() {
+        ListNode listNode1 = new ListNode(1);
+        listNode1.next = new ListNode(2);
+        listNode1.next.next = listNode1;
+        Assert.True(new Solution().HasCycle(listNode1));
+    }
+
+    [Fact]
+    public void HasCycle3() {
+        ListNode listNode1 = new ListNode(1);
+        Assert.False(new Solution().HasCycle(listNode1));
+    }
+}
+}
diff --git a/LeetCodeNet.Tests/G0101_0200/S0142_linked_list_cycle_ii/SolutionTest.cs b/LeetCodeNet.Tests/G0101_0200/S0142_linked_list_cycle_ii/SolutionTest.cs
@@ -0,0 +1,31 @@
+namespace LeetCodeNet.G0101_0200.S0142_linked_list_cycle_ii {
+
+using Xunit;
+using LeetCodeNet.Com_github_leetcode;
+
+public class SolutionTest {
+    [Fact]
+    public void DetectCycle() {
+        ListNode listNode1 = new ListNode(3);
+        listNode1.next = new ListNode(2);
+        listNode1.next.next = new ListNode(0);
+        listNode1.next.next.next = new ListNode(-4);
+        listNode1.next.next.next.next = listNode1.next;
+        Assert.True(new Solution().DetectCycle(listNode1) == listNode1.next);
+    }
+
+    [Fact]
+    public void DetectCycle2() {
+        ListNode listNode1 = new ListNode(1);
+        listNode1.next = new ListNode(2);
+        listNode1.next.next = listNode1;
+        Assert.True(new Solution().DetectCycle(listNode1) == listNode1);
+    }
+
+    [Fact]
+    public void DetectCycle3() {
+        ListNode listNode1 = new ListNode(1);
+        Assert.Equal(null, new Solution().DetectCycle(listNode1));
+    }
+}
+}
diff --git a/LeetCodeNet.Tests/G0101_0200/S0146_lru_cache/LRUCacheTest.cs b/LeetCodeNet.Tests/G0101_0200/S0146_lru_cache/LRUCacheTest.cs
@@ -0,0 +1,29 @@
+namespace LeetCodeNet.G0101_0200.S0146_lru_cache {
+
+using Xunit;
+
+public class LRUCacheTest {
+    [Fact]
+    public void LruCache() {
+        LRUCache lruCache = new LRUCache(2);
+        // cache is {1=1}
+        lruCache.Put(1, 1);
+        // cache is {1=1, 2=2}
+        lruCache.Put(2, 2);
+        // return 1
+        Assert.Equal(1, lruCache.Get(1));
+        // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
+        lruCache.Put(3, 3);
+        // returns -1 (not found)
+        Assert.Equal(-1, lruCache.Get(2));
+        // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
+        lruCache.Put(4, 4);
+        // return -1 (not found)
+        Assert.Equal(-1, lruCache.Get(1));
+        // return 3
+        Assert.Equal(3, lruCache.Get(3));
+        // return 4
+        Assert.Equal(4, lruCache.Get(4));
+    }
+}
+}
diff --git a/LeetCodeNet.Tests/G0101_0200/S0148_sort_list/SolutionTest.cs b/LeetCodeNet.Tests/G0101_0200/S0148_sort_list/SolutionTest.cs
@@ -0,0 +1,31 @@
+namespace LeetCodeNet.G0101_0200.S0148_sort_list {
+
+using Xunit;
+using LeetCodeNet.Com_github_leetcode;
+
+public class SolutionTest {
+    [Fact]
+    public void SortList() {
+        ListNode listNode1 = new ListNode(4);
+        listNode1.next = new ListNode(2);
+        listNode1.next.next = new ListNode(1);
+        listNode1.next.next.next = new ListNode(3);
+        Assert.Equal("1, 2, 3, 4", new Solution().SortList(listNode1).ToString());
+    }
+
+    [Fact]
+    public void SortList2() {
+        ListNode listNode1 = new ListNode(-1);
+        listNode1.next = new ListNode(5);
+        listNode1.next.next = new ListNode(3);
+        listNode1.next.next.next = new ListNode(4);
+        listNode1.next.next.next.next = new ListNode(0);
+        Assert.Equal("-1, 0, 3, 4, 5", new Solution().SortList(listNode1).ToString());
+    }
+
+    [Fact]
+    public void SortList3() {
+        Assert.Equal(null, new Solution().SortList(null));
+    }
+}
+}
diff --git a/LeetCodeNet/G0101_0200/S0139_word_break/Solution.cs b/LeetCodeNet/G0101_0200/S0139_word_break/Solution.cs
@@ -0,0 +1,34 @@
+namespace LeetCodeNet.G0101_0200.S0139_word_break {
+
+// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #String #Hash_Table
+// #Dynamic_Programming #Trie #Memoization #Algorithm_II_Day_15_Dynamic_Programming
+// #Dynamic_Programming_I_Day_9 #Udemy_Dynamic_Programming #Big_O_Time_O(M+max*N)_Space_O(M+N+max)
+// #2024_01_09_Time_64_ms_(98.44%)_Space_49.2_MB_(10.24%)
+
+public class Solution {
+    private Dictionary<string, bool> visited = new();
+    private HashSet<string>? set;
+
+    public bool WordBreak(string s, IList<string> wordDict) {
+        set = new HashSet<string>(wordDict);
+        return CheckWordBreak(s);
+    }
+
+    public bool CheckWordBreak(string s) {
+        if (visited.ContainsKey(s)) {
+            return visited[s];
+        }
+        if (set.Contains(s)) {
+            return true;
+        }
+        for (int i=0; i<s.Length; i++) {
+             if (set.Contains(s.Substring(0, i)) && CheckWordBreak(s.Substring(i))) {
+                 visited[s] = true;
+                 return true;
+             }
+        }
+       visited[s] = false;
+       return false;
+    }
+}   
+}
diff --git a/LeetCodeNet/G0101_0200/S0139_word_break/readme.md b/LeetCodeNet/G0101_0200/S0139_word_break/readme.md
@@ -0,0 +1,37 @@
+139\. Word Break
+
+Medium
+
+Given a string `s` and a dictionary of strings `wordDict`, return `true` if `s` can be segmented into a space-separated sequence of one or more dictionary words.
+
+**Note** that the same word in the dictionary may be reused multiple times in the segmentation.
+
+**Example 1:**
+
+**Input:** s = "leetcode", wordDict = ["leet","code"]
+
+**Output:** true
+
+**Explanation:** Return true because "leetcode" can be segmented as "leet code". 
+
+**Example 2:**
+
+**Input:** s = "applepenapple", wordDict = ["apple","pen"]
+
+**Output:** true
+
+**Explanation:** Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word. 
+
+**Example 3:**
+
+**Input:** s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
+
+**Output:** false 
+
+**Constraints:**
+
+*   `1 <= s.length <= 300`
+*   `1 <= wordDict.length <= 1000`
+*   `1 <= wordDict[i].length <= 20`
+*   `s` and `wordDict[i]` consist of only lowercase English letters.
+*   All the strings of `wordDict` are **unique**.
diff --git a/LeetCodeNet/G0101_0200/S0141_linked_list_cycle/Solution.cs b/LeetCodeNet/G0101_0200/S0141_linked_list_cycle/Solution.cs
@@ -0,0 +1,37 @@
+namespace LeetCodeNet.G0101_0200.S0141_linked_list_cycle {
+
+// #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Hash_Table #Two_Pointers #Linked_List
+// #Data_Structure_I_Day_7_Linked_List #Udemy_Linked_List #Big_O_Time_O(N)_Space_O(1)
+// #2024_01_09_Time_76_ms_(99.02%)_Space_46.5_MB_(16.05%)
+
+using LeetCodeNet.Com_github_leetcode;
+
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     public int val;
+ *     public ListNode next;
+ *     public ListNode(int x) {
+ *         val = x;
+ *         next = null;
+ *     }
+ * }
+ */
+public class Solution {
+    public bool HasCycle(ListNode head) {
+        if (head == null) {
+            return false;
+        }
+        ListNode fast = head.next;
+        ListNode slow = head;
+        while (fast != null && fast.next != null) {
+            if (fast == slow) {
+                return true;
+            }
+            fast = fast.next.next;
+            slow = slow.next;
+        }
+        return false;
+    }
+}
+}
diff --git a/LeetCodeNet/G0101_0200/S0141_linked_list_cycle/readme.md b/LeetCodeNet/G0101_0200/S0141_linked_list_cycle/readme.md
@@ -0,0 +1,47 @@
+141\. Linked List Cycle
+
+Easy
+
+Given `head`, the head of a linked list, determine if the linked list has a cycle in it.
+
+There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer. Internally, `pos` is used to denote the index of the node that tail's `next` pointer is connected to. **Note that `pos` is not passed as a parameter**.
+
+Return `true` _if there is a cycle in the linked list_. Otherwise, return `false`.
+
+**Example 1:**
+
+![](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png)
+
+**Input:** head = [3,2,0,-4], pos = 1
+
+**Output:** true
+
+**Explanation:** There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed). 
+
+**Example 2:**
+
+![](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png)
+
+**Input:** head = [1,2], pos = 0
+
+**Output:** true
+
+**Explanation:** There is a cycle in the linked list, where the tail connects to the 0th node. 
+
+**Example 3:**
+
+![](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test3.png)
+
+**Input:** head = [1], pos = -1
+
+**Output:** false
+
+**Explanation:** There is no cycle in the linked list. 
+
+**Constraints:**
+
+*   The number of the nodes in the list is in the range <code>[0, 10<sup>4</sup>]</code>.
+*   <code>-10<sup>5</sup> <= Node.val <= 10<sup>5</sup></code>
+*   `pos` is `-1` or a **valid index** in the linked-list.
+
+**Follow up:** Can you solve it using `O(1)` (i.e. constant) memory?
diff --git a/LeetCodeNet/G0101_0200/S0142_linked_list_cycle_ii/Solution.cs b/LeetCodeNet/G0101_0200/S0142_linked_list_cycle_ii/Solution.cs
@@ -0,0 +1,45 @@
+namespace LeetCodeNet.G0101_0200.S0142_linked_list_cycle_ii {
+
+// #Medium #Top_100_Liked_Questions #Hash_Table #Two_Pointers #Linked_List
+// #Data_Structure_II_Day_10_Linked_List #Level_1_Day_4_Linked_List #Udemy_Linked_List
+// #Big_O_Time_O(N)_Space_O(1) #2024_01_09_Time_72_ms_(94.58%)_Space_43.8_MB_(18.67%)
+
+using LeetCodeNet.Com_github_leetcode;
+
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     public int val;
+ *     public ListNode next;
+ *     public ListNode(int x) {
+ *         val = x;
+ *         next = null;
+ *     }
+ * }
+ */
+public class Solution {
+    public ListNode DetectCycle(ListNode head) {
+        if (head == null || head.next == null) {
+           return null;
+        }
+        ListNode slow = head;
+        ListNode fast = head;
+        while (fast != null && fast.next != null) {
+            fast = fast.next.next;
+            slow = slow.next;
+            if (slow == fast) {
+                break;
+            }
+        }
+        if (fast == null || fast.next == null) {
+            return null;
+        }
+        slow = head;
+        while (slow != fast) {
+            slow = slow.next;
+            fast = fast.next;
+        }
+        return slow;
+    }
+}
+}
diff --git a/LeetCodeNet/G0101_0200/S0142_linked_list_cycle_ii/readme.md b/LeetCodeNet/G0101_0200/S0142_linked_list_cycle_ii/readme.md
diff --git a/LeetCodeNet/G0101_0200/S0146_lru_cache/LRUCache.cs b/LeetCodeNet/G0101_0200/S0146_lru_cache/LRUCache.cs
diff --git a/LeetCodeNet/G0101_0200/S0146_lru_cache/readme.md b/LeetCodeNet/G0101_0200/S0146_lru_cache/readme.md
diff --git a/LeetCodeNet/G0101_0200/S0148_sort_list/Solution.cs b/LeetCodeNet/G0101_0200/S0148_sort_list/Solution.cs
diff --git a/LeetCodeNet/G0101_0200/S0148_sort_list/readme.md b/LeetCodeNet/G0101_0200/S0148_sort_list/readme.md
