不能再拖，每天打卡2018

LC #63. Unique Paths, DP, C#

public int UniquePaths(int m, int n) {
        
            if (m < 1 || n < 1)
            {
                return 0;
            }

            int[,] res=new int[m,n];

            for (int i = 0; i < n; i++)
            {
                res[0, i] = 1;
            }

            for (int j = 0; j < m; j++)
            {
                res[j, 0] = 1;
            }

            for (int i = 1; i < m; i++)
            {
                for (int j = 1; j < n; j++)
                {
                    res[i, j] = res[i - 1, j] + res[i, j - 1];
                }
            }

            return res[m - 1, n - 1];
    }


LC #62. Unique Paths, DP, C#

public int UniquePathsWithObstacles(int[,] obstacleGrid) {
        
        if (obstacleGrid == null || obstacleGrid.Length == 0)
                return 0;

            int row = obstacleGrid.GetLength(0);
            int column = obstacleGrid.GetLength(1);
            int[,] dp = new int[row,column];

            for (int i = 0; i < row; i++)
            {
                if (obstacleGrid[i,0] == 0)
                {
                    if (i == 0 || dp[i - 1,0] == 1)
                        dp[i,0] = 1;
                    else
                        dp[i,0] = 0;
                }
                else
                    dp[i,0] = 0;
            }

            for (int j = 1; j < column; j++)
            {
                if (obstacleGrid[0,j] == 0 && dp[0,j - 1] == 1)
                    dp[0,j] = 1;
                else
                    dp[0,j] = 0;
            }

            for (int i = 1; i < row; i++)
            {
                for (int j = 1; j < column; j++)
                {
                    if (obstacleGrid[i,j] == 0)
                        dp[i,j] = dp[i - 1,j] + dp[i,j - 1];
                    else
                        dp[i,j] = 0;
                }
            }

            return dp[row - 1,column - 1];
    }

LC#64. Minimum Path Sum， DP, C#

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

            int m = grid.GetLength(0);
            int n = grid.GetLength(1);
            int[,] dp = new int[m, n];
            dp[0, 0] = grid[0, 0];

            for(int i=1;i<n;i++)
            {
                dp[0, i] = dp[0,i-1] + grid[0,i];
            }

            for(int i=1;i<m;i++)
            {
                dp[i, 0] = grid[i, 0] + dp[i - 1, 0];
            }

            for(int i=1;i<m;i++)
            {
                for(int j=1;j<n;j++)
                {
                    dp[i, j] = Math.Min(dp[i - 1, j], dp[i, j - 1]) + grid[i, j];
                }
            }

            return dp[m - 1, n - 1];
    }

LC# 805. Split Array With Same Average, Array. C#


if (A.Length == 1)
            {
                return false;
            }

            int sumA = 0;

            foreach (int a in A)
            {
                sumA += a;
            }

            Array.Sort(A);

            for (int lenOfB = 1; lenOfB <= A.Length / 2; lenOfB++)
            {
                if ((sumA * lenOfB) % A.Length == 0)
                {
                    if (CheckHelper(A, (sumA * lenOfB) / A.Length, lenOfB, 0))
                    {
                        return true;
                    }
                }
            }

            return false;
        }

        public bool CheckHelper(int[] A, int leftSum, int leftNum, int startIndex)
        {
            if (leftNum == 0)
            {
                return leftSum == 0;
            }

            if (A[startIndex] > leftSum / leftNum)
            {
                return false;
            }

            for (int i = startIndex; i < A.Length - leftNum + 1; i++)
            {
                if (i > startIndex && A[i] == A[i - 1])
                {
                    continue;
                }

                if (CheckHelper(A, leftSum - A[i], leftNum - 1, i + 1))
                {
                    return true;
                }
            }

            return false;
        }

LC# 69. Sqrt(x), BS, C#

public int MySqrt(int x) {
        
        if(x==0)
            {
                return 0;
            }

            long start = 1, end = x;
            long ans=0;

            while(start<=end)
            {
                long mid = start + (end - start) / 2;
                long s = mid * mid;

                if (s>x)
                {
                    end = mid-1;
                }
                else
                {
                    start = mid+1;
                    ans=mid;
                }
            }

            return (int)ans;
    }

LC#96. Unique Binary Search Trees, DP, C#

public int NumTrees(int n) {
        
        if(n<=0)
            {
                return 0;
            }

            int[] dp = new int[n+1];
            dp[0] = 1;
            dp[1] = 1;

            for(int i=2;i<=n;i++)
            {
                for(int j=1;j<=i;j++)
                {
                    dp[i] += dp[j - 1] * dp[i - j];
                }
            }

            return dp[n];
    }

楼主好棒！直截了当刷题。学习中。

另外为什么有的题即练C#又练Python？

LC#399. Evaluate Division, Graph, DFS

public double[] CalcEquation(string[,] equations, double[] values, string[,] queries) {
        if(equations==null||values==null||queries==null||equations.Length==0||values.Length==0||queries.Length==0)
            {
                return (new double[0]);
            }

            int n = queries.GetLength(0);
            double[] res = new double[n];
            Dictionary<string, List<string>> strDct = new Dictionary<string, List<string>>();
            Dictionary<string, List<double>> valDct = new Dictionary<string, List<double>>();

            for(int i=0;i<equations.GetLength(0);i++)
            {
                string str1 = equations[i, 0];
                string str2 = equations[i, 1];

                if(!strDct.ContainsKey(str1))
                {
                    strDct.Add(str1, new List<string>());
                    valDct.Add(str1, new List<double>());
                }

                if(!strDct.ContainsKey(str2))
                {
                    strDct.Add(str2, new List<string>());
                    valDct.Add(str2, new List<double>());
                }

                strDct[str1].Add(str2);
                strDct[str2].Add(str1);
                valDct[str1].Add(values[i]);
                valDct[str2].Add(1 / values[i]);
            }

            for(int i=0;i<n;i++)
            {
                res[i] = DFSHelper(queries[i, 0], queries[i, 1], strDct, valDct, new HashSet<string>(), 1.0);

                if (res[i] == 0.0)
                {
                    res[i] = -1;
                }
            }

            return res;
        }

        double DFSHelper(string start, string end, Dictionary<string, List<string>> strDct, Dictionary<string,List<double>> valuesDct,HashSet<string> hs, double value)
        {
            if(hs.Contains(start))
            {
                return 0.0;
            }

            if(!strDct.ContainsKey(start))
            {
                return 0.0;
            }

            if(start.Equals(end))
            {
                return value;
            }

            hs.Add(start);

            List<string> strList = strDct[start];
            List<double> valueList = valuesDct[start];
            double tmp = 0.0;
            for (int i=0;i<strList.Count;i++)
            {
                 tmp= DFSHelper(strList[i], end, strDct, valuesDct, hs, value * valueList[i]);

                if(tmp!=0.0)
                {
                    break;
                }
            }

            hs.Remove(start);
            return tmp;
        }
}

jamesleborn 发表于 2018-3-30 16:21
楼主好棒！直截了当刷题。学习中。

另外为什么有的题即练C#又练Python？

现在Python这么流行，不学习不行了。工作中也需要用Python处理一些数据！

LC#811. Subdomain Visit Count, HashTable, C#

public IList<string> SubdomainVisits(string[] cpdomains)
        {
            IList<string> res = new List<string>();

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

            Dictionary<string, int> dct = new Dictionary<string, int>();

            foreach(string cpdomain in cpdomains)
            {
                string[] cps = cpdomain.Split(' ');
                int count = int.Parse(cps[0]);
                string domainStr = cps[1];

                if (dct.ContainsKey(domainStr))
                {
                    dct[domainStr] += count;
                }
                else
                {
                    dct.Add(domainStr, count);
                }

                while (domainStr.IndexOf('.')>0)
                {
                    int index = domainStr.IndexOf('.');
                    domainStr = domainStr.Substring(index + 1);

                    if (dct.ContainsKey(domainStr))
                    {
                        dct[domainStr] += count;
                    }
                    else
                    {
                        dct.Add(domainStr, count);
                    }
                }
            }

            foreach(string key in dct.Keys)
            {
                res.Add(dct[key].ToString() + " " + key);
            }

            return res;
        }

LC#116. Populating Next Right Pointers in Each Node, Java, BT, BFS

public void connect(TreeLinkNode root) {
        
        if(root==null)
        {
            return;
        }
        
        TreeLinkNode levelStart=root;
        
        while(levelStart!=null)
        {
            TreeLinkNode cur=levelStart;
            
            while(cur!=null)
            {
                if(cur.left!=null)
                {
                    cur.left.next=cur.right;
                }
                    
                if(cur.right!=null && cur.next!=null)
                {
                    cur.right.next=cur.next.left;
                }
               
                cur=cur.next;
            }
            
            levelStart=levelStart.left;
        }
    }

LC#117. Populating Next Right Pointers in Each Node II, Java, BT, BFS

public void connect(TreeLinkNode root) {
      
        if(root==null)
       {
           return;
       }
      
      
        Queue<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();  
        Queue<TreeLinkNode> nextQueue = new LinkedList<TreeLinkNode>();  
        queue.add(root);  
        TreeLinkNode left = null;  
        
        while (!queue.isEmpty())
        {  
            TreeLinkNode node = queue.poll();  
            
            if (left != null)
            {  
                left.next = node;  
            }  
            
            left = node;
            
            if (node.left != null)
            {  
                nextQueue.add(node.left);  
            }
            
            if (node.right != null)
            {  
                nextQueue.add(node.right);  
            }
            
            if (queue.isEmpty())
            {  
                Queue<TreeLinkNode> temp = queue;  
                queue = nextQueue;  
                nextQueue = temp;  
                left = null;  
            }  
        }  
    }