LeetCode: Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

C++ Solution:

class Solution {
public:
    int maxProduct(int A[], int n) {
        int res = A[0];
        int pos = max(0, A[0]);
        int neg = min(0, A[0]);
        for (int i = 1; i < n; ++i) {
            if (A[i] == 0) {
                pos = 0;
                neg = 0;
            } else if (A[i] > 0) {
                pos = max(1, pos)*A[i];
                neg = neg*A[i];
            } else {
                int pos_old = pos;
                pos = neg*A[i];
                neg = min(A[i], A[i]*pos_old);
            }
            res = max(res, pos);
        }
        return res;
    }
};

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?

/**
 * 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) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        stack<TreeNode *> buffer;
        vector<int> output;
        if (root == NULL) return output;
        buffer.push(root);
        while (!buffer.empty()) {
            TreeNode *temp = buffer.top();
            if (temp->right == NULL && temp->left == NULL) {
                output.push_back(temp->val);
                buffer.pop();
                while (!buffer.empty() && 
                    (buffer.top()->left == temp || buffer.top()->right == temp)  ) {
                    temp = buffer.top();
                    output.push_back(temp->val);
                    buffer.pop();
                }
            } else {
                if (temp->right != NULL) 
                    buffer.push(temp->right);
                if (temp->left != NULL) 
                    buffer.push(temp->left);
            }
        }
        return output;
    }
};

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.

class LRUCache {
    class ListNode {
    public:
        ListNode(int v, int k) : val(v), key(k) {
            prev = NULL;
            next = NULL;
        }
        int val;
        int key;
        ListNode *next;
        ListNode *prev;
    };
public:    
    int c;
    ListNode *head;
    ListNode *tail;
    map<int, ListNode *> key_node_map;
    
    LRUCache(int capacity) : c(capacity) {
        head = NULL;
        tail = NULL;
    }
    
    int get(int key) {
        if (key_node_map.find(key) == key_node_map.end())
            return -1;
        else {
            int temp = key_node_map[key]->val;
            set(key, temp);
            return temp;
        }
    }
    void set(int key, int value) {
        if (key_node_map.find(key) == key_node_map.end()) {
           ListNode *n = new ListNode(value, key);
           key_node_map[key] = n;
           n->next = head;
           n->prev = NULL;
           if (head!=NULL) head->prev = n;
           if (!tail) tail = n;
           head = n;
           if (key_node_map.size() > c) {
               key_node_map.erase(tail->key);
               ListNode *temp = tail->prev;
               delete tail;
               if (temp) {
                   temp->next = NULL;
                   tail = temp;
               } else {
                   tail = NULL;
               }
           }
        } else {
            ListNode *n = key_node_map[key];
            n->val = value;
            if (n->prev != NULL)
                n->prev->next = n->next;
            if (n->next != NULL) 
                n->next->prev = n->prev ? n->prev : n;
            if (n->next == NULL)
                tail = n->prev ? n->prev : n;
            if (n->prev != NULL) {
                n->next = head;
                head->prev = n;
                n->prev = NULL;
                head = n;
            }
        }
    }
};

LeetCode: Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        // Get the List len.
        if (head == NULL) {
            return;
        }
        ListNode *tmp = head;
        int len = 0;
        while (tmp != NULL) {
            tmp = tmp->next;
            ++len;
        }
        int num_insertion = (len-1)/2;
        // Find the start of second half.
        tmp = head;
        int count = 0;
        while (count < len-1-num_insertion) {
            tmp = tmp->next;
            ++count;
        }
        ListNode *second_half = tmp->next;
        tmp->next= NULL;
        // Reverse the second half of the List.
        if (second_half != NULL && second_half->next != NULL) {
            ListNode * temp1 = second_half->next;
            second_half->next = NULL;
            while (temp1 != NULL) {
                ListNode *temp2 = temp1->next;
                temp1->next = second_half;
                second_half = temp1;
                temp1 = temp2;
            }
        }
        // Insert second half to first half.
        ListNode *first_half = head;
        while (second_half != NULL) {
            ListNode *temp1 = second_half->next;
            second_half->next = first_half->next;
            first_half->next = second_half;
            second_half = temp1;
            first_half = first_half->next->next;
        }
    }
    
};

LeetCode: Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region .

For example,
X X X X
X O O X
X X O X
X O X X




After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X

DFS

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (board.size() < 3 || board[0].size() < 3) 
            return;
        int m = board.size(), n = board[0].size();
        unordered_set<int> visited;
        stack<int> to_visit;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if ( board[i][j] == 'O' && (i == 0 || i == m-1 || j == 0 || j == n-1)) {
                    to_visit.push(i * n + j);
                }
            }
        }
        while (!to_visit.empty()) {
            int temp = to_visit.top();
            to_visit.pop();
            int x = temp/n, y = temp%n;
            for (int i = -1; i < 2; ++i) {
                for (int j = -1; j < 2; ++j) {
                    if (i * j == 0 && i+j != 0 &&
                        x+i > 0 && x+i < m-1 && y+j > 0 && y+j < n-1 &&
                        board[x+i][y+j] == 'O' &&
                        visited.find((x+i) * n +y+j) == visited.end()) {
                        to_visit.push((x+i) * n +y+j);
                        visited.insert((x+i) * n +y+j);
                    }
                }
            }
        }
        
        for (int i = 1; i < m-1; ++i) {
            for (int j = 1; j < n-1; ++j) {
                if ( board[i][j] == 'O' && visited.find(i * n + j) == visited.end()) {
                  board[i][j] = 'X';
                }
            }
        }
    }
};

LeetCode: Linked List Cycle

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

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

Two solutions:

1.  o(n) solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        unordered_set<ListNode *> visited;
        while (head != NULL) {
            if(visited.find(head) != visited.end()) {
                return true;
            } else {
                visited.insert(head);
            }
            head = head->next;
        }
        return false;
    }
};

2. o(1) Solution: Use two pointers, one steps forward one node at a time, the other steps forward two nodes at a time. If a cycle exists, these two eventually will meet. 

class Solution {

public:
    bool hasCycle(ListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        ListNode *single_forward = head, *double_forward = head;
        
        while (double_forward != NULL) {
            single_forward = single_forward->next;
            double_forward = double_forward->next == NULL ? 
                double_forward->next : double_forward->next->next; 
            if (double_forward != NULL && single_forward == double_forward) {
                return true;
            }
        }
        return false;
    }
};

LeetCode: Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

 /* Definition for undirected graph.

 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (node == NULL) {
            return NULL;
        }
        unordered_map<int, UndirectedGraphNode *> visited;
        unordered_set<int> completed;
        queue<UndirectedGraphNode *> uncompleted;
        uncompleted.push(node);
        int start_node_label = node->label;
        
        while (!uncompleted.empty()) {
            UndirectedGraphNode *curr = uncompleted.front();
            uncompleted.pop();
            if(completed.find(curr->label) == completed.end()) {
                UndirectedGraphNode *copy;
                if (visited.find(curr->label) == visited.end()) {
                    copy = new UndirectedGraphNode(curr->label);
                    visited.insert(make_pair(copy->label, copy));
                } else {
                    copy = visited[curr->label];
                }
                for (UndirectedGraphNode *temp : curr->neighbors) {
                    if (visited.find(temp->label) != visited.end()) {
                        copy->neighbors.push_back(visited[temp->label]);
                    } else {
                        UndirectedGraphNode *neighbor = new UndirectedGraphNode(temp->label);
                        copy->neighbors.push_back(neighbor);
                        visited.insert(make_pair(neighbor->label, neighbor));
                    }
                }
                completed.insert(copy->label);
                for (UndirectedGraphNode *temp : curr->neighbors) {
                    if (completed.find(temp->label) == completed.end()) {
                    uncompleted.push(temp);
                    }
                }
            }
        }
        return visited[start_node_label];   
    }
};

LeetCode: Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Use iteration to find the prev node in the path of final solution, and use backtracking to recover the solution. We can also use iteration to directly compute the solution, but would cost much more space as a lot of redundant strings on the path.

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<vector<int>> prevs(s.length()+1);
        vector<bool> checked(s.length()+1, false);
        checked[0] = true;
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (checked[j] && dict.find(s.substr(j,i-j)) != dict.end()) {
                    if (!checked[i]) {
                        checked[i] = true;
                    }
                    prevs[i].push_back(j);
                }
            }
        }
        vector<string> res;
        backtracking(s, prevs, res, s.length());
        return res;
    }
    void backtracking(const string &s, const vector<vector<int>> &prevs, vector<string> &res, int index) {
        for (int i = 0; i < prevs[index].size(); ++i) {
            if (prevs[index][i] == 0) {
                res.push_back(s.substr(0, index));
            } else {
                backtracking(s, prevs, res, prevs[index][i]);
                for (int j = 0; j < res.size(); ++j) {
                    string temp = res[j];
                    temp.erase(remove( temp.begin(), temp.end(), ' '), temp.end());
                    if(temp.length() == prevs[index][i]){
                        res[j] += " " + s.substr(prevs[index][i], index-prevs[index][i]);
                    }
                }   
            }
        }
    }
};