Merge pull request #289 from hellomrsun/master

hellomrsun · web-flow · commit 56e1745d414a · 2020-10-17T19:46:55.000+02:00
Add C# solutions
diff --git a/October-LeetCoding-Challenge/04-Remove-Covered-Intervals/Remove-Covered-Intervals.cs b/October-LeetCoding-Challenge/04-Remove-Covered-Intervals/Remove-Covered-Intervals.cs
@@ -0,0 +1,14 @@
+public class Solution {
+    public int RemoveCoveredIntervals(int[][] intervals) {
+        Array.Sort(intervals, (x, y) => x[0]==y[0] ? y[1]-x[1] : x[0]-y[0]);
+        int count = 0;
+        int curr = 0;
+        foreach(int[] interval in intervals){
+            if(curr < interval[1]){
+                curr = interval[1];
+                count++;
+            }
+        }
+        return count;
+    }
+}
diff --git a/October-LeetCoding-Challenge/12-Buddy-Strings/Buddy-Strings.cs b/October-LeetCoding-Challenge/12-Buddy-Strings/Buddy-Strings.cs
@@ -0,0 +1,22 @@
+public class Solution {
+    public bool BuddyStrings(string A, string B) {
+        if((A == null && B != null) || (A != null && B == null)) return false;
+        if(A.Length != B.Length) return false;
+        int diffCount = 0;
+        int a = -1, b = -1;
+        bool canSwitch = false;
+        int[] count = new int[26];
+
+        for(int i=0; i<A.Length; i++){
+			if(++count[A[i] - 'a'] >= 2) canSwitch = true;
+            
+            if(A[i] != B[i])
+            {
+                diffCount++;
+                if (a == -1)  a = i;
+                else if (b == -1)  b = i;
+            }
+        }
+        return (diffCount == 0 && canSwitch) || (diffCount == 2 && A[a] == B[b] && A[b] == B[a]);
+    }
+}
diff --git a/October-LeetCoding-Challenge/14-House-Robber-II/House-Robber-II.cs b/October-LeetCoding-Challenge/14-House-Robber-II/House-Robber-II.cs
@@ -0,0 +1,18 @@
+public class Solution {
+    public int Rob(int[] nums) {
+        if(nums == null || nums.Length == 0) return 0;
+        if(nums.Length == 1) return nums[0];
+
+        return Math.Max(rob(nums, 1, nums.Length-1), rob(nums, 0, nums.Length-2));
+    }
+    
+    private int rob(int[] nums, int lo, int hi){
+        int include = 0, exclude = 0;
+        for(int x=lo; x<=hi; x++){
+            int i=include, e=exclude;
+            include = e + nums[x];
+            exclude = Math.Max(i, e);
+        }
+        return Math.Max(include, exclude);
+    }
+}
diff --git a/October-LeetCoding-Challenge/15-Rotate-Array/Rotate-Array.cs b/October-LeetCoding-Challenge/15-Rotate-Array/Rotate-Array.cs
@@ -0,0 +1,23 @@
+public class Solution {
+    public void Rotate(int[] nums, int k) {
+        if(nums == null || nums.Length < 2) return;
+        var length = nums.Length;
+        int n = k % length;
+        //Reverse left part
+        Reverse(nums, 0, length - 1 - n);
+        //Reverse right part
+        Reverse(nums, length - n, length-1);
+        //Reverse whole array
+        Reverse(nums, 0, length-1);
+    }
+    private void Reverse(int[] nums, int b, int e){
+        int tmp = 0;
+        while(b < e){
+            tmp = nums[b];
+            nums[b] = nums[e];
+            nums[e] = tmp;
+            b++;
+            e--;
+        }
+    }
+}
diff --git a/October-LeetCoding-Challenge/16-Search-a-2D-Matrix/Search-a-2D-Matrix.cs b/October-LeetCoding-Challenge/16-Search-a-2D-Matrix/Search-a-2D-Matrix.cs
@@ -0,0 +1,47 @@
+public class Solution {
+    public bool SearchMatrix(int[][] matrix, int target)
+    {
+        if (matrix == null || matrix.Length == 0) return false;
+        var levelLen = matrix[0].Length;
+        if(levelLen == 0) return false;    
+
+        bool result = false;
+        for (int i = 0; i <= matrix.Length-1; i++)
+        {
+            if (target <= matrix[i][levelLen - 1])
+            {
+                return BinarySearch(target, matrix[i]);
+            }
+        }
+
+        return false;
+    }
+
+    private bool BinarySearch(int target, int[] nums)
+    {
+        int lo = 0, hi = nums.Length - 1;
+        int mid = 0;
+        while (lo <= hi)
+        {
+            mid = lo + (hi - lo) / 2;
+
+            if (nums[mid] > target)
+            {
+                hi = mid-1;
+            }
+            else if (nums[mid] < target)
+            {
+                lo = mid+1;
+            }
+            else if (nums[mid] == target)
+            {
+                return true;
+            }
+            else
+            {
+                return false;
+            }
+        }
+        return false;
+    }
+}
diff --git a/October-LeetCoding-Challenge/17-Repeated-DNA-Sequences/Repeated-DNA-Sequences.cs b/October-LeetCoding-Challenge/17-Repeated-DNA-Sequences/Repeated-DNA-Sequences.cs
@@ -0,0 +1,14 @@
+public class Solution {
+    public IList<string> FindRepeatedDnaSequences(string s) {
+        if(s == null || s.Length == 0) return new List<string>();
+        var seen = new HashSet<string>();
+        var repeated = new HashSet<string>();
+        for(int i=0; i<s.Length-9; i++){
+            string curr = s.Substring(i, 10);
+            if(!seen.Add(curr)){
+                repeated.Add(curr);
+            }
+        }
+        return new List<string>(repeated);
+    }
+}
diff --git a/README.md b/README.md
@@ -9,7 +9,7 @@ Click [here](https://leetcode.com/explore/challenge/card/october-leetcoding-chal
 Solutions in various programming languages are provided. Enjoy it.
 
 1. [Number of Recent Calls](https://github.com/AlgoStudyGroup/Leetcode/tree/master/October-LeetCoding-Challenge/01-Number-of-Recent-Calls) : Queue
-
+4. [Remove Covered Intervals](https://github.com/AlgoStudyGroup/Leetcode/tree/master/October-LeetCoding-Challenge/04-Remove-Covered-Intervals)
 
 ## September LeetCoding Challenge
 Click [here](https://leetcode.com/explore/challenge/card/september-leetcoding-challenge) for problem descriptions.
