102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

** Level order traversal is done by queue. I used two queues for saving nodes. q1->q2->q1..etc

public class Solution
{
  public IList<IList<int>> LevelOrder(TreeNode root)
  {
    IList<IList<int>> result = new List<IList<int>>();
    
    Queue<TreeNode> q1 = new Queue<TreeNode>();
    Queue<TreeNode> q2 = new Queue<TreeNode>();
    
    Queue<TreeNode> curQue = null;
    Queue<TreeNode> nextQue = null;

    q1.Enqueue(root);
    
    while (q1.Count > 0 || q2.Count > 0)
    {
      // decide queue
      if (q1.Count > 0)
      {
        curQue = q1;
        nextQue = q2;
      }
      else
      {
        curQue = q2;
        nextQue = q1;
      }
      
      List<int> founds = new List<int>();
      while (curQue.Count > 0)
      {
        TreeNode n = curQue.Dequeue();
        if (n != null)
        {
          founds.Add(n.val);
          
          if(n.left != null)
            nextQue.Enqueue(n.left);
          if(n.right != null)
            nextQue.Enqueue(n.right);
        }
      }
      if(founds.Count > 0)
        result.Add(founds);
    }
    return result;
  }
}
  
Advertisements

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

This question asks about the how to save time for repeated search. That is, the hashtable or hashset is the answer.

public class Solution
{
  public int LengthOfLongestSubstring(string s)
  {
    
    if(string.IsNullOrEmpty(s))
      return 0;
    
    char[] str = s.ToCharArray();
    int maxSubLength = 1;
    HashSet<char> set = new HashSet<char>();
    
    for (int i = 0; i < str.Length; i++)
    {
      set.Clear();
      set.Add(str[i]);
      
      for (int j = i+1; j < str.Length; j++)
      {
        char c = str[j];
        
        if (set.Contains(c))
        {
          break;
        }
        else
        {
          set.Add(c);
          if(set.Count> maxSubLength)
            maxSubLength = set.Count;
        }
      }
    }
    return maxSubLength;
  }
}
  

206. Reverse Linked List

question: simply reverse a linked list.

** simply a stack is used to reverse data. O(n) takes

public class Solution
{
  public ListNode ReverseList(ListNode head)
  {
    Stack<ListNode> stack = new Stack<ListNode>();
    
    ListNode curNode = head;

    while (curNode != null)
    {
      stack.Push(curNode);
      curNode = curNode.next;
      
    }
    
    curNode = null;
    ListNode newHead = null;
    while (stack.Count > 0)
    {
      if (curNode == null)
      {
        curNode = stack.Pop();
        newHead = curNode;
      }
      else
      {
        curNode.next = stack.Pop();
        
        if(stack.Count > 0)
          curNode = curNode.next;
        else
        {
          curNode = curNode.next;
          curNode.next = null;
        }  
      }
    }
    return newHead;
  }
}
  

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) — Push element x onto stack.
  • pop() — Removes the element on top of the stack.
  • top() — Get the top element.
  • getMin() — Retrieve the minimum element in the stack.

** important thing: remember previous using a stack!

    Example:

    MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.

    public class MinStack
    {
      int minValue = int.MaxValue;
      Stack<int> stack = null;
      
      public MinStack()
      {
        stack = new Stack<int>();
      }
    
      public void Push(int x)
      {
        // important if (x < minValue) : is not, the minValue should be updated constantly
        if (x <= minValue)
        {
          // save previous min value
          stack.Push(minValue);
          minValue = x;
        }
        
        stack.Push(x);
      }
    
      public void Pop()
      {
        if (stack.Pop() == minValue)
        {
          // update min value (previously min value)
          minValue = stack.Pop();
        }
      }
      
      public int Top()
      {
        return stack.Peek();
      }
      
      public int GetMin()
      {
        return minValue;
      }
    }
      

    141. Linked List Cycle

    Question:

    Given a linked list, determine if it has a cycle in it.

    Follow up : Can you solve it without using extra space?

    ————————————————————————–

    solution: very simple question. Everybody anyone version solution is following.

    public class Solution
    {
      public bool HasCycle(ListNode head)
      {
        
        ListNode cursor = head;
        HashSet<ListNode> checker = new HashSet<ListNode>();
    
        while (cursor != null)
        {
          if(checker.Contains(cursor))
            return true;
          
          checker.Add(cursor);
          cursor = cursor.next;
        }
        return false;
      }
    }
      

    138. Copy List with Random Pointer

    A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

    Return a deep copy of the list.

    ———————————————————–

    At first, I wanted to solve this problem in one loop. For it, the logic became messy. Simply I have changed my mind to use two loops. Now it is better and simple.

    ———————————————————–

    public class Solution
    {
      public RandomListNode CopyRandomList(RandomListNode head)
      {
    
        Dictionary<RandomListNode, RandomListNode> maps = new Dictionary<RandomListNode, RandomListNode>();
    
        RandomListNode curNode = head;
        RandomListNode newHead = null;
        RandomListNode prevNewNode = null;
    
        while (curNode != null)
        {
          RandomListNode newNode = new RandomListNode(curNode.label);
    
          // save head first
          if (newHead == null)
            newHead = newNode;
    
          maps.Add(curNode, newNode);
    
          //now Update curNode
          curNode = curNode.next;
    
          // update new node cursor
          if (prevNewNode != null)
          {
            prevNewNode.next = newNode;
            prevNewNode = newNode;
          }
          else
          {
            prevNewNode = newNode;
          }
        }
    
        // reset cursor
        curNode = head;
    
        // build random nodes for each copied nodes
        while (curNode != null)
        {
          if (curNode.random != null)
          {
            RandomListNode mappedNode = maps[curNode];
            RandomListNode mappedRandNode = maps[curNode.random];
            mappedNode.random = mappedRandNode;
    
          }
    
          // update cursor
          curNode = curNode.next;
    
        }
        return newHead;
      }
    }
      

    78. Subsets

    Given a set of distinct integers, nums, return all possible subsets.

    Note: The solution set must not contain duplicate subsets.

    For example,
    If nums = [1,2,3], a solution is:

    [
      [3],
      [1],
      [2],
      [1,2,3],
      [1,3],
      [2,3],
      [1,2],
      []
    ]
    

    comments:

    this problem is quite famouse one.

    things to consider

    • results set includes a null group – it means null input should have including null results
    • Recursion, of course, is the first thing comes in my mind. – yes it is
    • Imagine a result tree.
    • maintaining visit history as maps !!

    IMG_2798

    • List is object. And need to see the snapshot

    public class Solution
    {
      public IList<IList<int>> Subsets(int[] nums)
      {
        bool[] maps = new bool[nums.Length];
        for (int i = 0; i < maps.Length; i++)
          maps[i] = false;
        
        IList<IList<int>> results = new List<IList<int>>();
        List<int> current = new List<int>();
        int startIndex = 0;
        
        GetSubset(maps, nums, startIndex, current, results);
        
        results.Add(new List<int>());
        
        return results;
      }
      
      // maintaining startIndex: for considering direction
      // 
      public void GetSubset(bool[] maps, int[] nums, int startIndex, List<int> current, IList<IList<int>> globalList)
      {
        // main loop
        for (int i = startIndex; i < maps.Length; i++)
        {
          if (maps[i] == false)
          {
            maps[i] = true;
            current.Add(nums[i]);
            
            // add snapshop, 
            List<int> temp = new List<int>();
            temp.AddRange(current);
            globalList.Add(temp);
            
            GetSubset(maps, nums, i+1, current, globalList);
            
            maps[i] = false;
            current.Remove(nums[i]);
          }
        }
      }
      
    }