不能再拖，每天打卡2018

lc797 (C#)
DFS:
public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {

            IList<IList<int>> res = new List<IList<int>>();
            List<int> ls = new List<int>();

            ls.Add(0);
            AllPathsSourceTargetHelper(graph, 0, ls, res);

            return res;
        }

        void AllPathsSourceTargetHelper(int[][] graph,int node,List<int> ls, IList<IList<int>> res)
        {
            if(node==graph.GetLength(0)-1)
            {
                res.Add(new List<int>(ls));
                return;
            }

            foreach(int nextNode in graph[node])
            {
                ls.Add(nextNode);
                AllPathsSourceTargetHelper(graph, nextNode, ls, res);
                ls.RemoveAt(ls.Count - 1);
            }
        }
}

BFS:

public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {
        
            IList<IList<int>> res = new List<IList<int>>();
            Queue<List<int>> q = new Queue<List<int>>();
            List<int> list = new List<int>();
            list.Add(0);

            q.Enqueue(new List<int>(list));

            while(q.Count!=0)
            {
                List<int> ls = q.Dequeue();

                if(ls.Last()==graph.GetLength(0)-1)
                {
                    res.Add(new List<int>(ls));
                }
                else
                {
                    int next = ls.Last();
                    foreach (int nexNode in graph[next])
                    {
                        List<int> nextList = new List<int>(ls);
                        nextList.Add(nexNode);
                        q.Enqueue(nextList);
                    }
                }
            }

            return res;
    }

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

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

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

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]

LC #802. Find Eventual Safe States,Topological Sort,DFS, C#


//Topological Sort
        public IList<int> EventualSafeNodes(int[][] graph)
        {
            List<int> res = new List<int>();

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

            List<int> ls = new List<int>();
            int n = graph.GetLength(0);
            int[] outDegree = new int[n];
            Dictionary<int, HashSet<int>> dct = new Dictionary<int, HashSet<int>>();

            for (int i = 0; i < n; i++)
            {
                outDegree[i] = graph[i].Length;

                if (outDegree[i] == 0)
                {
                    res.Add(i);
                    ls.Add(i);
                }
                else
                {
                    foreach (int t in graph[i])
                    {
                        if (!dct.ContainsKey(t))
                        {
                            dct.Add(t, new HashSet<int>());
                        }

                        dct[t].Add(i);
                    }
                }
            }

            while (ls.Count > 0)
            {
                int c = ls[0];

                if (dct.ContainsKey(c))
                {
                    foreach (int v in dct[c])
                    {
                        outDegree[v]--;

                        if (outDegree[v] == 0)
                        {
                            res.Add(v);
                            ls.Add(v);
                        }
                    }
                }

                ls.RemoveAt(0);
            }

            res.Sort();

            return res;
        }


        //DFS
        public IList<int> EventualSafeNodes(int[][] graph)
        {
            List<int> res = new List<int>();

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

            int n = graph.GetLength(0);
            int[] visited = new int[n];

            for (int i=0;i<n;i++)
            {
                //judge if it is not an circle, return true if not an circle, return false if it is an circle
                if (DFSHelper(graph,i,visited))
                {
                    res.Add(i);
                }
            }

            return res;
        }

        bool DFSHelper(int[][] graph,int index,int[] visited)
        {
            if(visited[index]>0)
            {
                return visited[index] == 2;
            }

            visited[index] = 1;

            foreach(int nb in graph[index])
            {
                if (visited[nb] == 1 || (visited[nb] == 0 && !DFSHelper(graph, nb, visited)))
                {
                    return false;
                }
            }

            visited[index] = 2;

            return true;
        }

LC794 (C#)

yunliang2014 发表于 2018-3-18 10:34
LC794 (C#)

public bool ValidTicTacToeGood(string[] board)
        {
            if (board == null || board.Length != 3 || board[0].Length != 3)
            {
                return false;
            }

            int moveX = 0;
            bool xWin = false;
            bool oWin = false;
            int[] rows = new int[3];
            int[] cols = new int[3];
            int diag = 0, antidiag = 0;

            for(int i=0;i<3;i++)
            {
                for(int j=0;j<3;j++)
                {
                    if(board[i][j]=='X')
                    {
                        moveX++;
                        rows[i]++;
                        cols[j]++;

                        if(i==j)
                        {
                            diag++;
                        }

                        if(i+j==2)
                        {
                            antidiag++;
                        }
                    }
                    else if(board[i][j] == 'O')
                    {
                        moveX--;
                        rows[i]--;
                        cols[j]--;

                        if (i == j)
                        {
                            diag--;
                        }

                        if (i + j == 2)
                        {
                            antidiag--;
                        }
                    }
                }
            }

            xWin = rows[0] == 3 || rows[1] == 3 || rows[2] == 3 || cols[0] == 3 || cols[1] == 3 || cols[2] == 3 || diag == 3 || antidiag == 3;
            oWin= rows[0] == -3 || rows[1] == -3 || rows[2] == -3 || cols[0] == -3 || cols[1] == -3 || cols[2] == -3 || diag == -3 || antidiag == -3;

            if((xWin&&moveX==0)||(oWin&&moveX==1))
            {
                return false;
            }

            return (moveX == 0 || moveX == 1) && (!xWin || !oWin);
        }

LC 4 (C#)

public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        
        if((nums1==null||nums1.Length==0)&&(nums2==null&&nums2.Length==0))
            {
                return -1;
            }

            int len1 = nums1.Length, len2 = nums2.Length;

            if(len1>len2)
            {
                return FindMedianSortedArrays(nums2, nums1);
            }

            int m = (len1 + len2 - 1) / 2;
            int left = 0, right = Math.Min(m, len1);

            while(left<right)
            {
                int midA = (left + right) / 2;
                int midB = m - midA;

                if(nums1[midA]<nums2[midB])
                {
                    left = midA + 1;
                }
                else
                {
                    right = midA;
                }
            }

            double a = Math.Max(left>0 ? nums1[left-1]:int.MinValue,m-left>=0?nums2[m-left]:int.MinValue);
            double b = Math.Min(left < len1 ? nums1[left] : int.MaxValue, m - left+1 < len2 ? nums2[m - left + 1] : int.MaxValue);

            if((len1+len2)%2!=0)
            {
                return a;
            }
            else
            {
                return (a + b) / 2;
            }
    }

LC 5: C#, DP

public string LongestPalindrome(string s) {
        
        if(string.IsNullOrEmpty(s))
            {
                return string.Empty;
            }

            int n = s.Length;
            bool[,] dp = new bool[n, n];
            string res = s.Substring(0, 1);

            for(int i=0;i<n;i++)
            {
                dp[i, i] = true;

                for(int j=0;j<i;j++)
                {
                    if(s[i]==s[j]&&(i-j<2||dp[i-1,j+1]))
                    {
                        dp[i, j] = true;
                    }

                    if(dp[i, j]&&i-j>=res.Length)
                    {
                        res = s.Substring(j, i - j + 1);
                    }
                }
            }

            return res;
    }

LC516, C#, DP

if(string.IsNullOrEmpty(s))
            {
                return 0;
            }

            int n = s.Length;
            int[,] dp = new int[n, n];

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

                for(int j=i-1;j>=0;j--)
                {
                    if(s[i]==s[j])
                    {
                        if(i-j<2)
                        {
                            dp[i, j] = 2;
                        }
                        else
                        {
                            dp[i, j] = dp[i - 1, j + 1] + 2;
                        }
                    }
                    else
                    {
                        dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j + 1]);
                    }
                }
            }

            return dp[n - 1, 0];

可以可以！！加油！

LC 649, DP, C#

public int CountSubstrings(string s)
        {
            if(string.IsNullOrEmpty(s))
            {
                return 0;
            }

            int n = s.Length;
            bool[,] dp = new bool[n, n];
            int count = 0;

            for(int i=0;i<n;i++)
            {
                dp[i, i] = true;
                count++;

                for(int j=0;j<i;j++)
                {
                    if(s[i]==s[j])
                    {
                        if(i-j<2||dp[i-1,j+1])
                        {
                            dp[i, j] = true;
                            count++;
                        }
                    }
                }
            }

            return count;
        }

LC 10, 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]=='*'&&i>0)
                {
                    dp[0,i + 1] = dp[0,i - 1];
                }
            }

            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]=='*'&&j>0)
                    {
                        if(s[i]!=p[j-1]&&p[j-1]!='.')
                        {
                            dp[i + 1, j + 1] = dp[i + 1, j - 1];
                        }
                        else
                        {
                            dp[i + 1, j + 1] = dp[i + 1, j] || dp[i + 1, j - 1] || dp[i, j + 1];
                        }
                    }
                }
            }

            return dp[m, n];
    }

yunliang2014 发表于 2018-3-19 14:32
LC 10, C#,DP

public bool IsMatch(string s, string p) {

是双向DP