不能再拖，每天打卡2018

LC # 39. Combination Sum, DFS, C#

public IList<IList<int>> CombinationSum(int[] candidates, int target) {
            
            IList<IList<int>> res = new List<IList<int>>();

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

            Array.Sort(candidates);

            DoCombinationSum(candidates, 0, target, new List<int>(), res);

            return res;
        }

        void DoCombinationSum(int[] candidates, int sIndex, int target, List<int> ls, IList<IList<int>> res )
        {
            if(target<0)
            {
                return;
            }

            if(target==0)
            {
                res.Add(new List<int>(ls));
                return;
            }

            for(int i=sIndex;i<candidates.Length;i++)
            {
                ls.Add(candidates[i]);
                DoCombinationSum(candidates, i, target - candidates[i], ls, res);
                ls.RemoveAt(ls.Count - 1);
            }
        }

LC #216. Combination Sum III, DFS, C#

public IList<IList<int>> CombinationSum3(int k, int n) {
        IList<IList<int>> res = new List<IList<int>>();

            if(k<=0||n<=0)
            {
                return res;
            }

            DoCominationSum3(1, k, n, new List<int>(), res);

            return res;
        }

        void DoCominationSum3(int start, int k, int target, List<int> ls, IList<IList<int>> res)
        {
            if(target<0)
            {
                return;
            }

            if(target==0&&k==0)
            {
                res.Add(new List<int>(ls));
                return;
            }

            for(int i=start;i<=9;i++)
            {
                ls.Add(i);
                DoCominationSum3(i + 1, k - 1, target - i, ls, res);
                ls.RemoveAt(ls.Count - 1);
            }
        }

LC #46. Permutations, 47. Permutations II backtracking

public IList<IList<int>> Permute(int[] nums) {
        IList<IList<int>> res = new List<IList<int>>();
            
            if(nums==null||nums.Length==0)
            {
                return res;
            }

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

            DoPermutation(nums, 0, ls, res,new bool[nums.Length]);

            return res;
        }

        void DoPermutation(int[] nums, int count, List<int> item, IList<IList<int>> res, bool[] used)
        {
            if (count == nums.Length)
            {
                res.Add(new List<int>(item));
                return;
            }

            for (int i = 0; i < nums.Length; i++)
            {
                if (!used[i])
                {
                    item.Add(nums[i]);
                    used[i] = true;
                    DoPermutation(nums, count + 1, item, res,used);
                    used[i] = false;
                    item.RemoveAt(item.Count - 1);
                }
            }
        }

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

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

            List<int> ls = new List<int>();
            bool[] used = new bool[nums.Length];

            DoPermutationUnique(nums, 0, ls, res,used);

            return res;
        }

        void DoPermutationUnique(int[] nums, int count, List<int> item, IList<IList<int>> res, bool[] used)
        {
            if (count == nums.Length)
            {
                res.Add(new List<int>(item));
                return;
            }

            for (int i = 0; i < nums.Length; i++)
            {
                if (used[i]||(i>0&&nums[i]==nums[i-1]&&!used[i-1]))
                {
                    continue;
                }

                item.Add(nums[i]);
                used[i] = true;
                DoPermutationUnique(nums, count + 1, item, res, used);
                used[i] = false;
                item.RemoveAt(item.Count - 1);
            }
        }

LC#54. Spiral Matrix, C#, Array,

public IList<int> SpiralOrder(int[,] matrix) {
        
        IList<int> resList = new List<int>();

            if(matrix==null||matrix.Length==0)
            {
                return resList;
            }

            int m = matrix.GetLength(0);
            int n = matrix.GetLength(1);
            int startRow = 0, endRow = m - 1;
            int startColumn = 0, endColumn = n - 1;

            while(startRow<=endRow&&startColumn<=endColumn)
            {
                for (int i = startColumn; i <=endColumn; i++)
                {
                    resList.Add(matrix[startRow, i]);
                }

                startRow++;

                for (int i = startRow; i <= endRow; i++)
                {
                    resList.Add(matrix[i, endColumn]);
                }

                endColumn--;

                if(startRow<=endRow)
                {
                    for (int i = endColumn; i >= startColumn; i--)
                    {
                        resList.Add(matrix[endRow, i]);
                    }
                }

                endRow--;

                if(startColumn<=endColumn)
                {
                    for (int i = endRow; i >= startRow; i--)
                    {
                        resList.Add(matrix[i, startColumn]);
                    }
                }

                startColumn++;
            }

            return resList;
        }

LC#55. Jump Game, Greedy, C#

public bool CanJump(int[] nums) {
        
        if(nums==null||nums.Length==0)
            {
                return true;
            }

            int len = nums.Length;
            int max = 0;

            for(int i=0;i<=max&&i<len;i++)
            {
                if(i+nums[i]>max)
                {
                    max = nums[i] + i;
                }
            }

            return max >= len - 1;
    }

LC #45. Jump Game II, Greedy, C#

public int Jump(int[] nums) {
        
         if (nums == null || nums.Length < 2)
            {
                return 0;
            }

            int steps = 0;
            int reach = 0;
            int nextmax = 0;
            int i = 0;

            
            while(i<=reach)
            {
                while(i<=reach)
                {
                    if(nextmax<i+nums[i])
                    {
                        nextmax = i + nums[i];
                    }

                    if(nextmax>=nums.Length-1)
                    {
                        return steps+1;
                    }
                    
                    i++;
                }
                steps++;
                reach = nextmax;
            }

            return 0;
    }

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;
        }

yunliang2014 发表于 2018-3-25 15:27
LC #802. Find Eventual Safe States,Topological Sort,DFS, C#

This is about Graph

LC#804. Unique Morse Code Words, HashMap, C#

public int UniqueMorseRepresentations(string[] words)
        {
            HashSet<string> hashSet = new HashSet<string>();
            foreach (string w in words)
            {
                hashSet.Add(GetCode(w));
            }

            return hashSet.Count;
        }

        private string GetCode(string w)
        {
            string[] morseCode = { ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.",
                "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.." };

            StringBuilder sb= new StringBuilder();
            foreach (char c in w)
            {
                sb.Append(morseCode[c - 'a']);
            }
            return sb.ToString();
        }

LC# 806. Number of Lines To Write String, Array, C#

public int[] NumberOfLines(int[] widths, string S)
        {
            int[] res = new int[2];

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

            int n = S.Length;
            int units = 0;
            int lines = 1;
            int width = 0;

            for(int i=0;i<n;i++)
            {
                width= widths[S[i] - 'a'];
               
                if(width+units>100)
                {
                    lines += 1;
                    units = width;
                }
                else
                {
                    units += width;
                }
            }

            res[0] = lines;
            res[1] = units;
            return res;
        }

LC# 807. Max Increase to Keep City Skyline, Matrix, Array, C#


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

            int res = 0;
            int m = grid.GetLength(0);
            int n = grid[0].Length;
            int[] rowMaxes = new int[m];
            int[] colMaxes = new int[n];

            for(int i=0;i<m;i++)
            {
                for(int j=0;j<n;j++)
                {
                    if(rowMaxes[i]<grid[i][j])
                    {
                        rowMaxes[i] = grid[i][j];
                    }
                }
            }

            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    if(colMaxes[i]<grid[j][i])
                    {
                        colMaxes[i] = grid[j][i];
                    }
                }
            }

            for(int i=0;i<m;i++)
            {
                for(int j=0;j<n;j++)
                {
                    res += Math.Min(rowMaxes[i], colMaxes[j]) - grid[i][j];
                }
            }

            return res;
    }