不能再拖，每天打卡2018

LC# 200. Number of Islands， DFS, C#

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

            int m = grid.GetLength(0);
            int n = grid.GetLength(1);
            int count = 0;

            for(int i=0;i<m;i++)
            {
                for(int j=0;j<n;j++)
                {
                    if(grid[i,j]=='1')
                    {
                        NumIslandsHelper(grid, i, j, m, n);
                        count++;
                    }
                }
            }

            return count;
        }

        void NumIslandsHelper(char[,] grid, int i,int j,int m, int n)
        {
            if(i<0||i>=m||j<0||j>=n||grid[i,j]=='0')
            {
                return;
            }

            grid[i, j] = '0';

            NumIslandsHelper(grid, i - 1, j, m, n);
            NumIslandsHelper(grid, i + 1, j, m, n);
            NumIslandsHelper(grid, i, j - 1, m, n);
            NumIslandsHelper(grid, i, j + 1, m, n);
        }

LC#199. Binary Tree Right Side View, C#, DFS

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

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

            GetResults(root, res, 0);

            return res;
        }

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

            if(res.Count==depth)
            {
                res.Add(root.val);
            }

            GetResults(root.right, res, depth+1);
            GetResults(root.left, res, depth+1);
        }

LC#133. Clone Graph, C#, Graph

BFS

public UndirectedGraphNode CloneGraph(UndirectedGraphNode node) {
        
        if(node==null)
            {
                return null;
            }

            Dictionary<UndirectedGraphNode, UndirectedGraphNode> dct = new Dictionary<UndirectedGraphNode, UndirectedGraphNode>();
            Queue<UndirectedGraphNode> q = new Queue<UndirectedGraphNode>();

            dct.Add(node, new UndirectedGraphNode(node.label));
            q.Enqueue(node);

            while(q.Count!=0)
            {
                UndirectedGraphNode gn = q.Dequeue();

                foreach(UndirectedGraphNode g in gn.neighbors)
                {
                    if(!dct.ContainsKey(g))
                    {
                        dct.Add(g, new UndirectedGraphNode(g.label));
                        q.Enqueue(g);
                    }

                    dct[gn].neighbors.Add(dct[g]);
                }
            }

            return dct[node];
    }
DFS

public UndirectedGraphNode CloneGraph(UndirectedGraphNode node) {
        
        return CloneHelper(node,new Dictionary<UndirectedGraphNode,UndirectedGraphNode>());
    }
   
     public UndirectedGraphNode CloneHelper(UndirectedGraphNode node, Dictionary<UndirectedGraphNode,UndirectedGraphNode> dct)
        {
            if(node==null)
            {
                return node;
            }

            if(dct.ContainsKey(node))
            {
                return dct[node];
            }

            UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
            dct.Add(node, newNode);

            foreach(UndirectedGraphNode unode in node.neighbors)
            {
                newNode.neighbors.Add(CloneHelper(unode, dct));
            }

            return newNode;
        }

今天看了一条微信说，要烙印在这里卧底，有人发了面经被取消了Offer，不知道在这里贴代码会不会也有影响，所以今天就说一下今天做了那几道题，以后代码还是放在GitHub上吧！

今天做了买股票的几道题，121，122，123，188，319，714. 都是动归加贪心！

LC#127. Word Ladder, BFS, C#

public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
        
        if (beginWord == null || endWord == null || beginWord.Length != endWord.Length)
            {
                return 0;
            }

            HashSet<string> dct = new HashSet<string>();
            foreach(string s in wordList)
            {
                dct.Add(s);
            }

            Queue<string> sq = new Queue<string>();
            Queue<int> dq = new Queue<int>();
            sq.Enqueue(beginWord);
            dq.Enqueue(1);

            while (sq.Count != 0)
            {
                string tmp = sq.Dequeue();
                int currDistance = dq.Dequeue();

                if (tmp.Equals(endWord))
                {
                    return currDistance;
                }

                for (int i = 0; i < tmp.Length; i++)
                {
                    for (char c = 'a'; c <= 'z'; c++)
                    {
                        if (tmp[i] != c)
                        {
                            char[] ch = tmp.ToCharArray();
                            ch[i] = c;
                            string newStr = new string(ch);

                            if (dct.Contains(newStr))
                            {
                                sq.Enqueue(newStr);
                                dq.Enqueue(currDistance + 1);
                                dct.Remove(newStr);
                            }
                        }
                    }
                }
            }

            return 0;
    }

LC# 39. Combination Sum, DFS, Backtracking, 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#289. Game of Life, BFS, C#

public void GameOfLife(int[,] board) {
        
        if (board == null || board.Length == 0)
            {
                return;
            }

            int m = board.GetLength(0);
            int n = board.GetLength(1);

            int[] dx = { -1, -1, -1, 0, 1, 1, 1, 0 };
            int[] dy = { -1, 0, 1, -1, -1, 0, 1, 1 };

            for(int i=0;i<m;i++)
            {
                for(int j=0;j<n;j++)
                {
                    int lives = 0;
                    for(int k=0;k<8;k++)
                    {
                        int x = i + dx[k];
                        int y = j + dy[k];

                        if(x>=0&&x<m&&y>=0&&y<n)
                        {
                            lives += board[x, y] & 1;
                        }
                    }

                    if(board[i,j]==1&&lives>=2&&lives<=3)
                    {
                        board[i, j] = 3;
                    }
                    else if(board[i,j]==0&&lives==3)
                    {
                        board[i, j] = 2;
                    }
                }
            }

            for(int i=0;i<m;i++)
            {
                for(int j=0;j<n;j++)
                {
                    board[i, j] >>= 1;
                }
            }
    }

LC#421. Maximum XOR of Two Numbers in an Array, Bit Manipulation, C#,Hash

public int FindMaximumXOR(int[] nums) {
        
         int max = 0, mask = 0;

            for(int i=31;i>=0;i--)
            {
                mask |= (1 << i);
                HashSet<int> set = new HashSet<int>();
                foreach(int num in nums)
                {
                    set.Add(num & mask);
                }

                int tmp = max | (1 << i);

                foreach(int pre in set)
                {
                    if(set.Contains(tmp^pre))
                    {
                        max = tmp;
                    }
                }
            }

            return max;
    }

LC#784. Letter Case Permutation

Python：
def letterCasePermutation(self, S):
        res = ['']
        for ch in S:
            if ch.isalpha():
                res = [i+j for i in res for j in [ch.upper(), ch.lower()]]
            else:
                res = [i+ch for i in res]
        return res

C#
public IList<string> LetterCasePermutation(string S) {
        IList<string> res = new List<string>();

            if (string.IsNullOrEmpty(S))
            {
                res.Add("");
                return res;
            }

            LetterCasePermutationHelper(S, "", 0, res);

            return res;
        }

        void LetterCasePermutationHelper(string S, string str,int start, IList<string> ls)
        {
            if(start==S.Length)
            {
                ls.Add(str);
                return;
            }
            string nextStr = str;

            if(S[start]>='A'&&S[start]<='Z')
            {
                nextStr += S[start];
                LetterCasePermutationHelper(S, nextStr, start + 1, ls);

                nextStr = str;
                nextStr += S[start].ToString().ToLower();
                LetterCasePermutationHelper(S, nextStr, start + 1, ls);
            }
            else if(S[start] >= 'a' && S[start] <= 'z')
            {
                nextStr += S[start];
                LetterCasePermutationHelper(S, nextStr, start + 1, ls);

                nextStr = str;
                nextStr += S[start].ToString().ToUpper();
                LetterCasePermutationHelper(S, nextStr, start + 1, ls);
            }
            else
            {
                nextStr += S[start];
                LetterCasePermutationHelper(S, nextStr, start + 1, ls);
            }
        }