不能再拖，每天打卡2018

LC 44, C#, DP

public bool IsMatch(string s, string p) {
        
        if (string.IsNullOrEmpty(s) && string.IsNullOrEmpty(p))
            {
                return true;
            }

            int m = s.Length, n = p.Length;
            bool[,] dp = new bool[m + 1, n + 1];
            dp[0, 0] = true;

            for (int i = 0; i < n; i++)
            {
                if(p[i]!='*')
                {
                    break;
                }
                else
                {
                    dp[0, i + 1] = true;
                }
            }

            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (s[i] == p[j] || p[j] == '?')
                    {
                        dp[i + 1, j + 1] = dp[i, j];
                    }
                    else if (p[j] == '*')
                    {
                        dp[i + 1, j + 1] = dp[i+1, j]||dp[i,j+1];
                    }
                }
            }

            return dp[m, n];
    }


Python:
def isMatch(self, s, p):
        n1=len(s)
        n2=len(p)
        dp=[[False for i in range(n2+1)]for j in range(n1+1)]
        dp[0][0]=True

        for i in range(0,n2):
            if(p[i]!='*'):
                break
            else:
                dp[0][i+1]=True

        for i in range(0,n1):
            for j in range(0,n2):
                if(s[i]==p[j] or p[j]=='?'):
                    dp[i+1][j+1]=dp[i][j]
                elif(p[j]=='*'):
                    dp[i+1][j+1]=(dp[i+1][j] or dp[i][j+1])

        return dp[n1][n2]

LC 18, 4SUM, C#, Two pointer:
public IList<IList<int>> FourSum(int[] nums, int target) {
        
        IList<IList<int>> res = new List<IList<int>>();

            if(nums==null||nums.Length==0)
            {
                return res;
            }

            Array.Sort(nums);

            HashSet<List<int>> hset = new HashSet<List<int>>();

            for(int i=0;i<nums.Length-3;i++)
            {
                for(int j=i+1;j<nums.Length-2;j++)
                {
                    int left = j + 1, right = nums.Length - 1;
                    int sum = nums[i]+nums[j];

                    while(left<right)
                    {
                        if(sum+nums[left]+nums[right]>0)
                        {
                            right--;
                        }
                        else if(sum + nums[left] + nums[right]<0)
                        {
                            left++;
                        }
                        else
                        {
                            List<int> ls = new List<int>();
                            ls.Add(nums[i]);
                            ls.Add(nums[j]);
                            ls.Add(nums[left]);
                            ls.Add(nums[right]);

                            if(!hset.Contains(ls))
                            {
                                res.Add(ls);
                                hset.Add(ls);
                            }

                            left++;
                            right--;
                        }
                    }
                }
            }

            return res;
    }

LC15. 3Sum C#, Two pointer

public IList<IList<int>> ThreeSum(int[] nums)
        {
            IList<IList<int>> res = new List<IList<int>>();

            if(nums==null||nums.Length==0)
            {
                return res;
            }

            Array.Sort(nums);

            int n = nums.Length;

            for(int i=0;i<n-2;i++)
            {
                int begin = i + 1;
                int end = n - 1;

                // need to check if the first number is equal to the previous one to avoid count duplicate.
                if (i == 0 || nums[i] != nums[i - 1])
                {
                    while (begin < end)
                    {

                        if (nums[begin] + nums[end] + nums[i] == 0)
                        {
                            IList<int> ls = new List<int>();

                            ls.Add(nums[i]);
                            ls.Add(nums[begin]);
                            ls.Add(nums[end]);

                            //res.Add(new List<int>(ls));
                            res.Add(ls);

                            while (begin < end && nums[begin] == nums[begin + 1])
                            {
                                begin++;
                            }

                            while (begin < end && nums[end - 1] == nums[end])
                            {
                                end--;
                            }

                            begin++;
                        }
                        else if (nums[begin] + nums[end] + nums[i] > 0)
                        {
                            end--;
                        }
                        else
                        {
                            begin++;
                        }
                    }
                }
            }

            return res;
        }

LC 16. 3Sum Closest, TwoPointer, C#

public int ThreeSumClosest(int[] nums, int target)
        {
            if (nums == null || nums.Length == 0)
            {
                return 0;
            }

            Array.Sort(nums);

            int res = 0;
            int n = nums.Length;
            int min = int.MaxValue;

            for(int i=0;i<n-2;i++)
            {
                int begin = i + 1;
                int end = n - 1;

                while(begin<end)
                {
                    int s = nums[i] + nums[begin] + nums[end];
                    int distance = Math.Abs(s - target);
                    if (distance < min)
                    {
                        min = distance;
                        res = s;
                    }

                    if (s>target)
                    {
                        end--;
                    }
                    else
                    {
                        begin++;
                    }
                }
            }

            return res;
        }

LC20. Valid Parentheses, Stack, C#

public bool IsValid(string s) {
        
           if(string.IsNullOrEmpty(s))
            {
                return false;
            }

            Stack<char> st = new Stack<char>();
            int i = 0;

            while(i<s.Length)
            {
                if(s[i]=='('||s[i]=='['||s[i]=='{')
                {
                    st.Push(s[i]);
                }
                else if(s[i]==')')
                {
                    if(st.Count==0||st.Peek()!='(')
                    {
                        return false;
                    }

                    st.Pop();
                }
                else if(s[i]==']')
                {
                    if(st.Count == 0 || st.Peek()!='[')
                    {
                        return false;
                    }

                    st.Pop();
                }
                else if(s[i]=='}')
                {
                    if(st.Count == 0 || st.Peek()!='{')
                    {
                        return false;
                    }

                    st.Pop();
                }
                else
                {
                    return false;
                }

                i++;
            }
            
            if(st.Count==0&&i==s.Length)
            {
                return true;
            }

            return false;
    }

LC 21. Merge Two Sorted Lists, LinkedList,

public ListNode MergeTwoLists(ListNode l1, ListNode l2)
        {
            if(l1==null)
            {
                return l2;
            }

            if(l2==null)
            {
                return l1;
            }

            ListNode fakeHead = new ListNode(0);
            ListNode p = fakeHead; ;

            while (l1!=null&&l2!=null)
            {
                if(l1.val<=l2.val)
                {
                    p.next = l1;
                    l1 = l1.next;
                }
                else
                {
                    p.next = l2;
                    l2 = l2.next;
                }

                if(fakeHead.next==null)
                {
                    fakeHead.next = p;
                }

                p = p.next;
            }

            if (l1 != null)
            {
                p.next = l1;
            }
            else if(l2!=null)
            {
                p.next = l2;
            }

            return fakeHead.next;
        }

LC#22. Generate Parentheses, DFS, C#

public IList<string> GenerateParenthesis(int n) {
       List<String> res = new List<string>();

            if (n <= 0)
                return res;

            String item ="";

            doGenerateParenthesis(n, n, res, item);

            return res;
        }

        private void doGenerateParenthesis(int left, int right, List<string> res, String str)
        {
            if (left > right)
                return;

            if (left == 0 && right == 0)
            {
                res.Add(str);
                return;
            }

            if (right > 0)
                doGenerateParenthesis(left, right - 1, res, str + ")");

            if (left > 0)
                doGenerateParenthesis(left - 1, right, res, str + "(");
        }

LC# 23. Merge k Sorted Lists, Two Pointer, LinkedList, C#

Method1:
public ListNode MergeKLists(ListNode[] lists)
        {
            if (lists == null || lists.Length == 0)
            {
                return null;
            }

            if (lists.Length < 2)
            {
                return lists[0];
            }

            int n = lists.Length;
            int end = n - 1;

            while (end > 0)
            {
                int begin = 0;

                while (begin < end)
                {
                    lists[begin] = MergeTwoLists(lists[begin], lists[end]);
                    begin++;
                    end--;
                }
            }

            return lists[0];
        }

public ListNode MergeTwoLists(ListNode l1, ListNode l2)
        {
            if (l1 == null)
            {
                return l2;
            }

            if (l2 == null)
            {
                return l1;
            }

            ListNode fakeHead = new ListNode(0);
            ListNode p = fakeHead; ;

            while (l1 != null && l2 != null)
            {
                if (l1.val <= l2.val)
                {
                    p.next = l1;
                    l1 = l1.next;
                }
                else
                {
                    p.next = l2;
                    l2 = l2.next;
                }

                if (fakeHead.next == null)
                {
                    fakeHead.next = p;
                }

                p = p.next;
            }

            if (l1 != null)
            {
                p.next = l1;
            }
            else if (l2 != null)
            {
                p.next = l2;
            }

            return fakeHead.next;
        }

Method2:

public ListNode MergeKLists(ListNode[] lists)
        {
            if (lists == null || lists.Length == 0)
            {
                return null;
            }

            return Partion(lists, 0, lists.Length - 1);
        }

        ListNode Partion(ListNode[] lists, int begin,int end)
        {
            if(begin==end)
            {
                return lists[0];
            }

            if(begin<end)
            {
                int mid = (begin + end) / 2;
                ListNode l1 = Partion(lists, begin, mid);
                ListNode l2 = Partion(lists, mid + 1, end);

                return MergeTwoLists(l1, l2);
            }

            return null;
        }

LC #32. Longest Valid Parentheses, Stack, C#

public int LongestValidParentheses(string s) {
      
       if(s==null||s.Length<2)
            {
                return 0;
            }

            int max = 0;
            Stack<int> st = new Stack<int>();
            int last = -1;

            for(int i=0;i<s.Length;i++)
            {
                if(s[i]=='(')
                {
                    st.Push(i);
                }
                else if(st.Count==0)
                {
                    last = i;
                }
                else
                {
                    st.Pop();

                    if(st.Count==0)
                    {
                        max = Math.Max(max, i - last);
                    }
                    else
                    {
                        max = Math.Max(max, i - st.Peek());
                    }
                }
            }

            return max;
    }

LC#33. Search in Rotated Sorted Array, BS, C#

public int Search(int[] nums, int target) {
        
        if(nums==null||nums.Length==0)
            {
                return -1;
            }

            int n = nums.Length;
            int left = 0, right = n - 1;

            while (left <= right)
            {
                int mid = (right + left) / 2;

                if (nums[mid] == target)
                {
                    return mid;
                }
               
                if (nums[mid] >nums[right])
                {
                    if (nums[mid] > target&&target>=nums[left])
                    {
                        right = mid - 1;
                    }
                    else
                    {
                        left = mid + 1;
                    }
                }
                else
                {
                    if (nums[mid] <target&&target<=nums[right])
                    {
                        left = mid + 1;
                    }
                    else
                    {
                        right = mid - 1;
                    }
                }
            }

            return -1;
    }