[Leetcode] Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

Analysis:

Pretty straightforward. Push right and left tree into the stack. 

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> ret;
        if (root == NULL)
            return ret;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty())
        {
            TreeNode* curr = s.top();
            s.pop();
            ret.push_back(curr->val);
            if (curr->right != NULL)
                s.push(curr->right);
            if (curr->left != NULL)
                s.push(curr->left);               
        }
        
        return ret;
    }
};

[Leetcode] Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Analysis:

左右子树为空，或者是最后访问的子树是当前子树的左或者右子树时，当前节点就可以访问了

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> ret;
        if (root == NULL)
            return ret;
        stack<TreeNode *> s;
        s.push(root);
        TreeNode * lastVisited = NULL;
        while(!s.empty())
        {
            TreeNode* curr = s.top();
            s.pop();
            if ((curr->left == NULL && curr->right == NULL) || 
                (curr->right != NULL && curr->right== lastVisited) ||
                (curr->right == NULL && curr->left == lastVisited))
            {
                lastVisited = curr;
                ret.push_back(curr->val);
            }
            else
            {
                s.push(curr);
                if (curr->right != NULL)
                    s.push(curr->right);
                if (curr->left != NULL)
                    s.push(curr->left);
            }
        }
        
        return ret;
    }
};

[Leetcode] LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Analysis:

The goal is to have O(1) time complexity for both get and set. To get O(1), we have to use a hash table to access the the element; To get O(1) for least visited element, we use a double linked list and keep the most recent visited key at the beginning of the list and the tail of the list would be least recent used element. Note when the capacity is reached, you have to remove both the tail of the list and the element in the hash table.

class LRUCache{
    int m_size;
    int m_capacity;
    list<pair<int, int>> m_list;
    map<int, list<pair<int, int>>::iterator> m_map;
public:
    LRUCache(int capacity) {
        m_capacity = capacity;
        m_size = 0;
    }
    
    int get(int key) {
        int value = -1;
        if (m_map.find(key) != m_map.end())
        {
            //key exists in the cache, move the element to the beginning of the list
            list<pair<int, int>>::iterator itr = m_map[key];
            value = itr->second;
            m_list.erase(itr);
            m_list.push_front(make_pair(key,value));
            m_map[key] = m_list.begin();
        }
        
        return value;
    }
    
    void set(int key, int value) {
        if (m_map.find(key) != m_map.end())
        {
            //if the key is present, update and move the element to the beginning of the list
            m_list.erase(m_map[key]);
            m_list.push_front(make_pair(key, value));
            m_map[key] = m_list.begin();
        }
        else
        {
            //if reach the capacity, remove the last element and erase the element in map
            if (m_capacity <= m_size)
            {
                int tmp = m_list.back().first;
                m_map.erase(tmp);
                m_list.pop_back();
                m_size--;
            }
            //insert to the front of the list
            m_list.push_front(make_pair(key, value));
            m_map[key] = m_list.begin();
            m_size++;
            
        }
    }
};

[Leetcode] Insertion Sort List

Sort a linked list using insertion sort.
Analysis:
Using the insertion sort algorithm, for each node x, iterate from the beginning of the list and look for a node which is greater than current one. Split and insert node x before the node; since the head may be changed, use a dummy head to handle the head node changes
The idea is simple but the implementation may be a little tricky, need to be careful. 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
 ListNode *insertionSortList(ListNode *head) {
  if (head == NULL || head->next == NULL)
   return head;

  ListNode* dummyHead = new ListNode(0);
  dummyHead->next = head;
  ListNode* curr = head;
  ListNode* currPrev = dummyHead;
  while (curr != NULL)
  {
   //don't use ListNode* p as head was changed
   ListNode* p = dummyHead->next;
   ListNode* prev = dummyHead;
   while (curr != p && p->val < curr->val)
   {
    prev = p;
    p = p->next;
   }

   ListNode* next = curr->next;
   if (p != curr)
   {
    prev->next = curr;
    curr->next = p;
    //note: don't forget to set the p next
    currPrev->next = next;
   }
   else
   {
    currPrev = curr;
   }

   curr = next;
  }

  ListNode* newHead = dummyHead->next;
  delete dummyHead;

  return newHead;
 }
};

[Leetcode] Sort List

Sort a linked list in O(n log n) time using constant space complexity.
Analysis:

Similar to Merge sort, http://en.wikipedia.org/wiki/Merge_sort

1. Find the middle of the list and divide it into two part, the second one begin from middle
2. Recursively divide the two part until NULL or only one element in the list
3. Do the merge

Special test case: 2->1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
 //merge the two lists
    ListNode* mergeList(ListNode* head1, ListNode* head2)
    {
        ListNode* dummyHead = new ListNode(0);
        ListNode* curr = dummyHead;
        while(head1!=NULL && head2!=NULL)
        {
            if (head1->val < head2->val)
            {
                curr->next = head1;
                curr = curr->next;
                head1=head1->next;
            }
            else
            {
                curr->next = head2;
                curr = curr->next;
                head2=head2->next;
            }
        }
        
        while(head1!=NULL)
        {
            curr->next = head1;
            curr = curr->next;
            head1 = head1->next;
        }
        
        while(head2!=NULL)
        {
            curr->next = head2;
            curr = curr->next;
            head2 = head2->next;
        }
        
        ListNode* newHead = dummyHead->next;
        delete dummyHead;
        return newHead;
        
    }

    ListNode *sortList(ListNode *head) {
        if (head == NULL || head->next == NULL)
            return head;
        
        //divide the list into 2 part    
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* prev = NULL;
        //note: the second part should begin from slow rather than slow->next
        while(fast != NULL && fast->next != NULL)
        {
            prev = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        
        ListNode* head2 = slow;
        prev->next = NULL;
        
        ListNode * h1 = sortList(head);
        ListNode * h2 = sortList(head2);
        
        return mergeList(h1, h2);
        
    }
};

[Leetcode] Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Analysis:

Points are on the same straight line they have the same slope. Use a hash table to accumulate all slopes for every pair of points. 

Note: special case:
1. slope could be infinite if two points have the same x value.
2. duplicate points

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        
        int maxPoints = 0;
        for(int i=0; i < points.size(); i++)
        {
            int samePoints = 0;
            int infinite = 0;
            map<double, int> m;
            for(int j=i + 1; j < points.size(); j++)
            {
                if (points[j].y == points[i].y && points[j].x == points[i].x)
                    samePoints++;
                else if (points[j].x == points[i].x)
                    infinite++;
                else
                {
                    double slope = 1.0 * (points[j].y - points[i].y) / (points[j].x - points[i].x);
                    m[slope]++;
                }
            }
            
            int points = 0;
            for(map<double, int>::iterator itr = m.begin(); itr != m.end(); itr++)
            {
                points = max(points, itr->second);
            }
            
            points = max(points, infinite);
            maxPoints = max(maxPoints, points + 1 + samePoints);
            
        }
        return maxPoints;
    }
};

[Leetcode] Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3] 

Analysis:

It is basically to find all subset and save the results when target = 0. Notice that since the number could be used unlimited time, so in the code, dfs call should be i rather than i+1. The current A[i] could be used until sum > n and till then, i = i + 1.

class Solution {
public:

void dfs(vector<vector<int> >& ret, int target, int m, vector<int>& candidates, vector<int>& nums)
{
 if (target == 0)
 {
  ret.push_back(nums);
 }
 else if (target < 0)
 {
     return;
 }
 else
 {
  for (int i = m; i < candidates.size(); i++)
  {
   nums.push_back(candidates[i]);
   dfs(ret, target -candidates[i], i, candidates, nums);
   nums.pop_back();
  }
 }
}

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int> > ret;
        vector<int> nums;
        dfs(ret, target, 0, candidates, nums);
        
        return ret;
    }
};