不能再拖，每天打卡2018

274. H-Index， C#， Hash

public int HIndex(int[] citations) {
        if(citations==null||citations.Length==0)
            {
                return 0;
            }

            int[] count = new int[citations.Length+1];

            foreach(int cit in citations)
            {
                if(cit>=citations.Length)
                {
                    count[citations.Length]++;
                }
                else
                {
                    count[cit]++;
                }
            }
            int c = 0;
            for(int i=citations.Length;i>=0;i--)
            {
                c+= count[i];
                if(c>=i)
                {
                    return i;
                }
            }

            return 0;
    }

275. H-Index II
public int hIndex(int[] citations) {
        
         if(citations==null||citations.length==0)
        {
            return 0;
        }
        
        int start = 0, end = citations.length-1;
        int length=citations.length;
        while (start + 1 < end) {
            int mid = start + (end-start)/2;
            if (citations[mid] == length-mid) {
                return length-mid;
            } else if (citations[mid] > length-mid) {
                end = mid;
            } else {
                start = mid;
            }
        }

        return 0;
    }

230. Kth Smallest Element in a BST, BST, C#,

public int KthSmallest(TreeNode root, int k) {
        if(root==null||k<=0)
            {
                return int.MinValue;
            }
            Stack<TreeNode> s = new Stack<TreeNode>();
            AddLeft(root,s);

            while(s.Count!=0)
            {
                TreeNode node = s.Pop();
                k--;

                if(k==0)
                {
                    return node.val;
                }

                if(node.right!=null)
                {
                    AddLeft(node.right,s);
                }
            }

            return int.MaxValue;
        }

        void AddLeft(TreeNode root, Stack<TreeNode> s)
        {
            while(root!=null)
            {
                s.Push(root);
                root = root.left;
            }
        }

LC # 416. Partition Equal Subset Sum, DP, C#

public bool CanPartition(int[] nums) {
      int total = 0;
            foreach (int num in nums)
            {
                total += num;
            }

            if (total % 2 != 0)
            {
                return false;
            }

            int max = total / 2;

            bool[] res = new bool[max+1];
            res[0] = true;

            for(int i=0;i<nums.Length;i++)
            {
                for(int j=max;j>=nums[i];j--)
                {
                    res[j] = res[j] || res[j - nums[i]];
                }
            }

            return res[max];
        }

LC#691. Stickers to Spell Word， C#， DP

public int MinStickers(string[] stickers, string target) {
       if(stickers==null||stickers.Length==0||string.IsNullOrEmpty(target))
            {
                return -1;
            }

            int len = stickers.Length;
            int[,] mp = new int[len, 26];
            Dictionary<string, int> dct = new Dictionary<string, int>();

            for(int i=0;i<len;i++)
            {
                for(int j=0;j<stickers[i].Length;j++)
                {
                    mp[i, stickers[i][j] - 'a']++;
                }
            }

            dct.Add("", 0);

            return GetMinStickers(mp, dct, target);
        }

        int GetMinStickers(int[,] mp, Dictionary<string,int> dp, string target)
        {
            if(dp.ContainsKey(target))
            {
                return dp[target];
            }

            int res = int.MaxValue;
            int[] cm = new int[26];
            int n = mp.GetLength(0);

            foreach(char c in target)
            {
                cm[c - 'a']++;
            }

            for(int i=0;i<n;i++)
            {
                if(mp[i,target[0]-'a']>0)
                {
                    StringBuilder sb = new StringBuilder();

                    for(int j=0;j<26;j++)
                    {
                        if(cm[j]>0)
                        {
                            for(int k=0;k<cm[j]-mp[i,j];k++)
                            {
                                sb.Append((char)(j + 'a'));
                            }
                        }
                    }

                    int next = GetMinStickers(mp, dp, sb.ToString());

                    if(next!=-1)
                    {
                        res = Math.Min(res, next + 1);
                    }
                }
            }

            if(res!=int.MaxValue)
            {
                if(!dp.ContainsKey(target))
                {
                    dp.Add(target, res);
                }
                else
                {
                    dp[target] = res;
                }
            }
            else
            {
                if (!dp.ContainsKey(target))
                {
                    dp.Add(target, -1);
                }
                else
                {
                    dp[target] = -1;
                }
            }

            return dp[target];
        }

Python：
def minStickers(self, stickers, target):
        res=0
        n = len(stickers)
        mp=[[0 for i in range(n)] for j in range(26)]
        hm={}

        for i in range(0,n-1):
            for j in stickers[i]:
                d=ord(j)-ord('a')
                mp[i][d]+=1

        hm[""]=0

        return self.getMinStickers(mp,hm,target)

    def getMinStickers(self,mp,hm,target):
        if(hm[target]):
            return hm[target]

        res=float("inf")
        cm=[0 for i in range(26)]
        n=mp.length

        for c in target:
            cm[ord(c)-ord('a')]+=1

        for i in range(0,n-1):
            if(mp[i][target[0]-'a']>0):
                sb=""
                for j in range(0,25):
                    if(cm[j]>0):
                        for k in range(0,cm[j]-mp[i][j]):
                            sb.join(chr(j+ord('a')))
                next=self.getMinStickers(mp,hm,sb)

                if(next!=-1):
                    res=min(res,next+1)

        hm[target]=res

        return hm[target]

今天没有刷题，看了一点Machine Learning的东西和这边文章https://medium.com/the-mission/do-these-things-after-6-p-m-and-your-life-will-never-be-the-same-1dcc545664dc 。

LC# 329. Longest Increasing Path in a Matrix, DFS, C#

public int LongestIncreasingPath(int[,] matrix) {
     if(matrix==null||matrix.Length==0)
            {
                return 0;
            }

            int m = matrix.GetLength(0);
            int n = matrix.GetLength(1);
            int[,] cache = new int[m, n];
            int max = 1;
            for(int i=0;i<m;i++)
            {
                for(int j=0;j<n;j++)
                {
                    int len = GetLongestPathDFS(matrix, i, j, cache);
                    max = Math.Max(len, max);
                }
            }

            return max;
        }

        int GetLongestPathDFS(int[,] matrix,int i,int j,int[,] cache)
        {
            if(cache[i,j]!=0)
            {
                return cache[i, j];
            }

            int m = matrix.GetLength(0);
            int n = matrix.GetLength(1);
            int[,] units = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
            int max = 1;

            for(int k=0;k<units.GetLength(0);k++)
            {
                int x = i + units[k,0];
                int y = j + units[k, 1];

                if(x<0||x>=m||y<0||y>=n||matrix[x,y]<=matrix[i,j])
                {
                    continue;
                }

                int len = 1 + GetLongestPathDFS(matrix, x, y, cache);
                max = Math.Max(len, max);
            }

            cache[i, j] = max;
            return cache[i, j];
        }

LC# 515. Find Largest Value in Each Tree Row, DFS, C#

public IList<int> LargestValues(TreeNode root) {
        
         IList<int> res = new List<int>();

            if (root == null)
            {
                return res;
            }

            lvDfsHelper(root, 0, res);

            return res;
        }

        void lvDfsHelper(TreeNode root,int depth,IList<int> ls)
        {
            if(root==null)
            {
                return;
            }

            if(ls.Count==depth)
            {
                ls.Add(root.val);
            }
            else
            {
                ls[depth] = Math.Max(ls[depth], root.val);
            }

            lvDfsHelper(root.left, depth + 1, ls);
            lvDfsHelper(root.right, depth + 1, ls);
        }

今天刷了最新Contest的816~819，Contest时间内只做出了前3道题

今天研究了Union Find, LC#130,128,200,547!

继续研究UnionFind， LC # 721,737