Divide Two Integers [Leetcode]

Divide two integers without using multiplication, division and mod operator.

Solution: bit manipulation [check here for original solution]

class Solution {
public:
    int divide(int dividend, int divisor) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(divisor==0) return 0; //error
        long long a = abs(double(dividend));
        long long b = abs(double(divisor));
        long long r = 0;
        while(a>=b){
            long long c = b;
            for(int i=0; c<=a; i++, c<<=1){
                a-=c;
                r+=(1<<i);
            }
        }
        return (dividend^divisor)>>31?-r:r;
    }
};

Deepest Left Leaf Node in a Binary Tree [GeeksforGeeks]

Given a Binary Tree, find the deepest leaf node that is left child of its parent. For example, consider the following tree. The deepest left leaf node is the node with value 9.

       1
     /   \
    2     3
  /      /  \  
 4      5    6
        \     \
         7     8
        /       \
       9         10

Check here for more detailed info.

Solution: we recursively traverse the given binary tree. During the traversal, we record the level of the current node and the maxLevel (the level of the deepest left leaf node found so far). If we are encountering a left leaf node and it's level is greater than maxLevel, we know this leaf node is the most recent deepest left leaf node. [Part of code is from GeeksforGeeks]

#include <iostream>
using namespace std;

struct Node{
    int val;
    struct Node *left, *right;
};

Node *newNode(int data){
    Node *temp = new Node;
    temp->val = data;
    temp->left = temp->right =  NULL;
    return temp;
}

void deepestLeftLeaf(Node *root, bool isLeft, int level, int& maxLevel, Node * &ret){
    // Base case
    if (root==NULL)
        return;
    //Update result if 'root' is the deepest left leaf node so far
    if(root->left==NULL && root->right==NULL){
        if(isLeft && level>maxLevel){
            maxLevel = level;
            ret = root;
        }
        return;
    }
    //Recursively find the obj. in its two substrees
    deepestLeftLeaf(root->left, true, level+1, maxLevel, ret);
    deepestLeftLeaf(root->right, false, level+1, maxLevel, ret);
}


// Driver program to test above function
int main(){
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->left = newNode(5);
    root->right->right = newNode(6);
    root->right->left->right = newNode(7);
    root->right->right->right = newNode(8);
    root->right->left->right->left = newNode(9);
    root->right->right->right->right = newNode(10);

    int maxLevel = 0;
    Node *ret = NULL;
    deepestLeftLeaf(root, false, 0, maxLevel, ret);

    if (ret)
        cout << "The deepest left child is " << ret->val << endl;
    else
        cout << "There is no left leaf in the given tree" << endl;

    return 0;
}

Evaluate Reverse Polish Notation [Leetcode]

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Solution: I implemented the algorithm provided in Reverse Polish Notation.

class Solution {
public:
    bool isOperator(string token){
        return token=="+" || token=="-" || token=="*" || token=="/";
    }
    int cal(int lOperand, int rOperand, string op){
        if(op=="+")
            return lOperand+rOperand;
        if(op=="-")
            return lOperand-rOperand;
        if(op=="*")
            return lOperand*rOperand;
        return lOperand/rOperand;
    }
    int evalRPN(vector<string> &tokens) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(tokens.empty())
            return INT_MIN;
        stack<int> s;
        for(size_t i=0; i<tokens.size(); ++i){
            if(isOperator(tokens[i])){
                if(s.size()>=2){
                    int rOperand = s.top();
                    s.pop();
                    int lOperand = s.top();
                    s.pop();
                    s.push(cal(lOperand, rOperand, tokens[i]));
                }
                else
                    return INT_MIN;
            }
            else
                s.push(stoi(tokens[i]));
        }
        if(s.size()==1)
            return s.top();
        return INT_MIN;
    }
}; 

Trie Implementation in C++ [GeeksforGeeks]

Check here for node insertion and searching, and here for node removal. In addition, I used postorder traversal to delete the entire tree.

#include <iostream>
#include <unordered_map>

using namespace std;

struct TrieNode{
    bool leaf;
    unordered_map<char, TrieNode*> children;
    TrieNode():leaf(false), children(){}
};

class Trie{
private:
    TrieNode* root;
public:
    Trie():root(new TrieNode()){}
    ~Trie(){ 
        deleteTrie(root); 
    } 
    //Insert a given word
    void addWord(string s){
        cout << "Insert: " << (s.empty()?"empty string":s) << endl;
        TrieNode* cur = root;
        for(size_t i=0; i<s.size(); ++i){
            if(cur->children.count(s[i])==0)
                cur->children[s[i]] = new TrieNode();
            cur = cur->children[s[i]];
        }
        cur->leaf= true;
    }
    //Search a given word
    bool searchWord(string s){
        cout << "Search: " << (s.empty()?"empty string":s) << endl;
        if(root==NULL)
            return false;
        TrieNode* cur = root;
        for(size_t i=0; i<s.size(); ++i){
            if(cur->children.count(s[i])==0)
                return false;
            cur = cur->children[s[i]];
        }
        return cur->leaf;
    }
    //Delete a given word
    void delWord(string s){
        cout << "Delete: " << (s.empty()?"empty string":s) << endl;
        if(root==NULL)
            return;
        if(s.empty()){
            cout << "Deleting node: empty string"<< endl;
            root->leaf=false;
        }
        delWordHelper(s, root, 0);
    }
    //delword helper
    bool delWordHelper(string s, TrieNode* r, size_t cur){
        cout << "\tGo deep: "<< s[cur] << endl;        
        if(r==NULL)
            return false;
        if(cur==s.size()){ //base case
            r->leaf = false; //unmark the leaf
            if(r->children.size()!=0) //if s is a prefix of other string
                return false;
            return true;
        }
        else{
            if(r->children.count(s[cur])==0) //if can not find s
                return false;
            if(delWordHelper(s, r->children[s[cur]], cur+1)){
                //delete eligible nodes
                cout << "\tDeleting node: "<< s[cur] << endl;
                delete r->children[s[cur]];
                r->children.erase(s[cur]);
                //recursively climb up, and delete eligible nodes
                return r->children.empty() && r->leaf==false;
            }
            return false;
        }
    }
    //Delete the trie following post-order traversal
    void deleteTrie(TrieNode* r){
        if(r==NULL)
            return;
        for(size_t i=0; i<r->children.size(); i++)
            deleteTrie(r->children[i]);
        delete r;
        r = NULL;
    }
    //To avoid shallow copy, you may need to give 
    //copy constructor and overload assignment operator
    Trie(const Trie&);
    Trie& operator=(const Trie&);
};
int main(){
    Trie t = Trie();
    t.addWord("");
    t.addWord("Hello");
    t.addWord("Balloon");

    if (t.searchWord("Hell")) 
        cout << "Found Hell" << endl;
    if (t.searchWord("Hello"))
        cout << "Found Hello" << endl;
    if (t.searchWord("Helloo"))
        cout << "Found Helloo" << endl;
    if (t.searchWord("Ball"))
        cout << "Found Ball" << endl;
    if (t.searchWord("Balloon"))
        cout << "Found Balloon" << endl;
    if (t.searchWord(""))
        cout << "Found empty string" << endl;

    t.delWord("Balloon");
    if (t.searchWord("Balloon"))
        cout << "Found Balloon" << endl;
        
    t.addWord("Balloon");
    t.addWord("Ball");

    t.delWord("Balloon");
    t.delWord("");
    if (t.searchWord(""))
        cout << "Found empty string" << endl;
    return 0;
}

Max Points on a Line [Leetcode]

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

Solution: the key point here is how to check if three points are in the same line, i.e., collinear. Give points i, j, k, we say they are in the same line iff (j.y-i.y)*(k.x-j.x)-(k.y-j.y)*(j.x-i.x)=0. The time complexity is O(n^3). [Note computing the slope of a line is not a good way]

/**
 * 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:
    //Check if three points, i, j and k, are collinear
    bool sameLine(Point i, Point j, Point k){
        return (j.y-i.y)*(k.x-j.x)-(k.y-j.y)*(j.x-i.x)==0;
    }
    //Check if all points are the same
    bool allSamePoints(vector<Point> &points){
        int i=0;
        while(i<points.size()){
            if(points[i].x!=points[0].x || points[i].y!=points[0].y)
                break;
            ++i;
        }
        return i==points.size();
    }
    int maxPoints(vector<Point> &points) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(points.size()<=1 || allSamePoints(points))
            return points.size();
        int maxPoints = 2;
        for(int i=0; i<points.size(); ++i){
            for(int j=i+1; j<points.size(); ++j){
                if(points[i].x==points[j].x && points[i].y==points[j].y)
                    continue;
                int count = 2;
                for(int k=0; k<points.size(); ++k){
                    if(k!=i && k!=j && sameLine(points[i], points[j], points[k]))
                        count++;
                }
                maxPoints = max(maxPoints, count);
            }
        }
        return maxPoints;
    }
};

17.4 [CTCI]

Write a method which finds the maximum of two integers. You should not use if-else or any other comparison operator.

Solution: Given two numbers a and b: one straightforward idea is to check the sign of a-b; if a-b>0, return a, otherwise b; but it is possible that a-b overflows if a and b have different signs. So we can not do this way. We need to consider two cases:
1. a and b have the same signs: return a if a-b>0, otherwise b;
2. a and b have different signs: return a if a>0, otherwise b;
We define k=1 iff (sign(a)=sign(b) && a-b>0)  OR (sign(a)!=sign(b)&&a>0) and p to be inverse of k, i.e., 1^k. Then, the maximum of a and b is a*k+b*p.

int sign(int a){
    return 1^(a>>31 && 1);
}
int getMax(int a, int b){
    int c = a-b;
    int sa = sign(a);
    int sb = sign(b);
    int sc = sign(c);
    
    int diff = sa ^ sb;
    int same = 1^diff;
    int k = sc*same + sa*diff;
    int p = 1^k;
    return a*k+b*p;
}

Maximum Depth of Binary Tree [Leetcode]

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Solutions: here I will give three solutions to this problem including both iteration and recursion.

• DFS (recursion) ;
• BFS (iteration);
• DFS (iteration; postorder traversal) [check here for iterative postorder traversal].

   /*******************************SOLUTION 1***********************************/

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(!root) return 0;
        return max(maxDepth(root->left), maxDepth(root->right))+1;
    }
};

   /*******************************SOLUTION 2***********************************/

class Solution {
public:
    int maxDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(!root) return 0;
        queue<TreeNode *> q;
        q.push(root);
        int curNum=1, nxtNum=0;
        int maxHeight=0;
        while(!q.empty()){
            TreeNode* cur = q.front();
            q.pop();
            curNum--;
            //Push two children
            if(cur->left!=NULL){
                q.push(cur->left);
                nxtNum++;
            }
            if(cur->right!=NULL){
                q.push(cur->right);
                nxtNum++;
            }
            if(curNum==0){
                maxHeight++;
                if(nxtNum==0)
                    break;
                swap(curNum, nxtNum);
            }
        }
        return maxHeight;
    }
};

   /*******************************SOLUTION 3***********************************/

class Solution {
public:
    int maxDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(!root) return 0;
        stack<TreeNode *> s;
        s.push(root);
        int maxHeight = 0;
        int curHeight = 0;
        TreeNode* pre=NULL;
        while(!s.empty()){
            TreeNode* cur = s.top();
            //Go down
            if(pre==NULL || pre->left==cur || pre->right==cur){
                curHeight++;
                if(cur->left!=NULL)
                    s.push(cur->left);
                else if (cur->right!=NULL)
                    s.push(cur->right);
                else {
                    s.pop();
                    maxHeight = max(maxHeight, curHeight);
                }
            }
            //Go up
            else{
                curHeight--;
                //From left child
                if(cur->left==pre){
                    if(cur->right!=NULL)
                        s.push(cur->right);
                    else
                        s.pop();
                }
                //From right child
                else
                        s.pop();
            }
            pre = cur;
        }
        return maxHeight;
    }
};

Sort List [Leetcode]

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

Solution: divide into two parts, conquer one by one, and them merge two sorted parts.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    //Merge two sorted linked list
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if(l1==NULL) return l2;
        if(l2==NULL) return l1;
        ListNode* c1 = (l1->val<=l2->val?l1:l2); //pointing to the head with the smaller val
        ListNode* c2 = (l1->val<=l2->val?l2:l1); //pointing to the head with the larger val
        while(c1->next!=NULL && c2!=NULL){
            if(c1->val<=c2->val && c2->val<=c1->next->val){
                //insert c2 behind of c1
                ListNode* tmp = c2->next;
                c2->next = c1->next;
                c1->next = c2;
                //advance both pointers
                c1 = c1->next;
                c2 = tmp;
            }
            else
                c1 = c1->next;
        }
        if(c1->next==NULL)
            c1->next = c2;
        return (l1->val<=l2->val?l1:l2);
    }
    ListNode *sortList(ListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(head==NULL || head->next==NULL)
            return head;
        //Advance slow pointer to middle node
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(fast!=NULL && fast->next!=NULL){
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode* newHead = slow->next;
        slow->next=NULL;
        //Sort two parts
        head=sortList(head);
        newHead=sortList(newHead);
        //Merge two sorted parts
        return mergeTwoLists(head, newHead);
    }
};

Line Segments Intersection [GeeksforGeeks]

Given two line segments (p1, q1) and (p2, q2), find if the given line segments intersect with each other. [Check here for problem statement and here for background information]

Two segments (p1,q1) and (p2,q2) intersect if and only if one of the following two conditions is verified: [from GeeksforGeeks]
1. General Case:
- (p1, q1, p2) and (p1, q1, q2) have different orientations AND
- (p2, q2, p1) and (p2, q2, q1) have different orientations
OR
2. Special Case
- (p1, q1, p2), (p1, q1, q2), (p2, q2, p1), and (p2, q2, q1) are all collinear and
- the x-projections of (p1, q1) and (p2, q2) intersect
- the y-projections of (p1, q1) and (p2, q2) intersect

#include <iostream>

using namespace std;

struct Point{
    int x, y;
    Point(int a, int b):x(a),y(b){}
};

//Given 3 colinear pointers p, q and r; Determine if r is on the segment pq
bool onSegment(Point p, Point q, Point r){
    return r.x<=max(p.x, q.x)&&r.x>=min(p.x, q.x)&&
           r.y<=max(p.y, q.y)&&r.y>=min(p.y, q.y);
} 

//Calculate the orientation of segments pq, and qr
int orientation(Point p, Point q, Point r){
    int o = (q.y-p.y)*(r.x-q.x)-
        (r.y-q.y)*(q.x-p.x);
    if (o==0)
        return 0; //colinear
    return o>0?1:-1; //clockwise and counterclockwise
}

bool doIntersect(Point p1, Point q1, Point p2, Point q2){
    int d1=orientation(p1, q1, p2);
    int d2=orientation(p1, q1, q2);
    int d3=orientation(p2, q2, p1);
    int d4=orientation(p2, q2, q1);

    // General case
    if(d1!=d2 && d3!=d4)
        return true;
    //Special case
    if(d1==0 && onSegment(p1, q1, p2))
        return true;
    if(d2==0 && onSegment(p1, q1, q2))
        return true;
    if(d3==0 && onSegment(p2, q2, p1))
        return true;
    if(d4==0 && onSegment(p2, q2, q1))
        return true;
    return false;
}

int main(){
    struct Point p1 = {1, 1}, q1 = {10, 1};
    struct Point p2 = {1, 2}, q2 = {10, 2};

    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    p1 = {10, 0}, q1 = {0, 10};
    p2 = {0, 0}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    p1 = {-5, -5}, q1 = {0, 0};
    p2 = {1, 1}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";
    return 0;
}

Insertion Sort List

Sort a linked list using insertion sort.

Solution: nothing but pointer manipulation; check here for insertion sort.

/**
 * 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) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(head==NULL || head->next==NULL)
            return head;
        ListNode* outerPre = head;
        ListNode* outerCur = head->next;
        while(outerCur!=NULL){
            ListNode* pre = NULL;
            ListNode* cur = head;
            while(cur!=outerCur && cur->val<=outerCur->val){
                pre=cur;
                cur=cur->next;
            }
            if(cur->val>outerCur->val){
                ListNode* tmp = outerCur->next;
                outerPre->next=tmp;
                if(pre==NULL){
                    outerCur->next = head;
                    head=outerCur;
                    outerCur=tmp;
                }
                else{
                    outerCur->next = cur;
                    pre->next=outerCur;
                    outerCur=tmp;
                }
            }
            else{
                outerPre=outerCur;
                outerCur=outerCur->next;
            }
        }
        return head;
    }
};

Word Ladder II [Leetcode]

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

Solution: first do BFS to explore all possible transitions from start to end to build a DAG; and then do DFS to backtrack all possible paths from end to start according to the DAG.

class Solution {  
public:  
    //Back track all possible paths
    void buildPath(vector<vector<string>> &ret, unordered_map<string, vector<string>> &adjDAG, 
        vector<string> path, string cur, string start) {  
        if(cur==start){
            path.insert(path.begin(), cur);
            ret.push_back(path);
            return;
        }
        path.insert(path.begin(), cur);
        for(int i=0; i<adjDAG[cur].size(); ++i)
            buildPath(ret, adjDAG, path, adjDAG[cur][i], start);
    }  

    vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function 
        vector<vector<string>> ret;
        dict.insert(start);
        dict.insert(end);
        unordered_map<string, vector<string>> adjDAG; //child and parents.
        vector<unordered_set<string>> layers(2);
        int cur=0;
        int pre=1;
        layers[cur].insert(start);
        //Do BFS to build DAG
        while(!layers[cur].empty() && !layers[cur].count(end)){
            cur=!cur;
            pre=!pre;
            for(auto it=layers[pre].begin(); it!=layers[pre].end(); ++it)
                dict.erase(*it);
            layers[cur].clear();
            for(auto it=layers[pre].begin(); it!=layers[pre].end(); ++it){
                //Try all possible variants
                for(int j=0; j<(*it).size(); ++j){
                    for(char k='a'; k<='z'; ++k){
                        string tmp = (*it);
                        if(tmp[j]==k)
                            continue;
                        tmp[j]=k;
                        if(dict.find(tmp)!=dict.end()){
                            adjDAG[tmp].push_back(*it);
                            layers[cur].insert(tmp);
                        }
                    }
                }
            }
        }
        //No path found
        if(layers[cur].empty())
            return ret;
        //Some paths found
        vector<string> path;
        //Do DFS to build paths according to the DAG
        buildPath(ret, adj, path, end, start);
        return ret;
    }  
};  

Calculating the Next Power of Two

If you are on a 32-bit (2⁵) architecture, you need to repeat right_shift-or five times (It turns out that if the val is zero or any value greater than 2³¹, it will return zero). If you are on a 64-bit (2⁶) architecture, you need to repeat right_shift-or six times. [check bit twiddling hacks]
For instance: given an integer 0000 0000 1001 0110 (150) on a 32-bit (2⁵) architecture, the next power of two is  0000 0001 0000 0000 (256). We observe that each time we do right_shift-or, we are doubling the number of consecutive highest 1's:
Original number: 0000 0000 1001 0110
After the first right_shift-or:  0000 0000 1101 1111
...

#include <iostream>
using namespace std;

int next_pow_2(int val){
    --val;
    val |= (val>>1);
    val |= (val>>2);
    val |= (val>>4);
    val |= (val>>8);
    val |= (val>>16);
    ++val;
    return val;
}
int main() {
    // Start typing your code here...
    cout << "Hello world!" << endl;
    for(int i=-10; i<10; i++)
        cout <<i<<"---->"<< next_pow_2(i)<<endl;
    
    return 0;
}

LRU Cache [Leetcode]

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.

Solution: we note that each time we visit a page, this page will become the most recently visited page. We use a singly linked list to maintain the pages in the memory; the first and last pages in the list are the least and most recently visited pages respectively; A hashtable is used to record the key of each page and the address of the previous page in the list. Here I used singly linked list, I think it would be better if we use doubly linked list.

class LRUCache{
private:
    struct Cache{
        int key, val;
        Cache* next;
        Cache(int k, int v):key(k),val(v),next(NULL) {}
    };
    Cache* head;
    Cache* tail;
    unordered_map<int, Cache*> hashTable;
    int cap;
public:
    LRUCache(int capacity):head(NULL),tail(NULL),hashTable(),cap(capacity) {
    }
    
    int get(int key) {
        if(hashTable.find(key)==hashTable.end())
            return -1;
        else{
            //if there is only one page in the cache, or the visited page is the last one
            if(head==tail || hashTable[key]!=NULL && hashTable[key]->next==tail)
                return tail->val;
            Cache* tmp = NULL;
            //if the visited page is the first one
            if(hashTable[key]==NULL){
                tmp = head;
                head = head->next;
                hashTable[head->key]=NULL;
            }
            //if the visited page is in the middle of the list
            else{
                tmp = hashTable[key]->next;
                hashTable[tmp->next->key]=hashTable[key];
                hashTable[key]->next = tmp->next;
            }
            //move the visited page to the end of the list
            tail->next=tmp;
            tmp->next=NULL;
            hashTable[key]=tail;
            tail=tail->next;
            return tail->val;
        }
    }
    
    void set(int key, int value) {
        if(get(key)!=-1)
            tail->val=value;
        else{
            Cache* newNode = new Cache(key, value);
            if(head==NULL){
                head=newNode;
                tail=newNode;
                hashTable[key]=NULL;
            }
            else{
                hashTable[key]=tail;
                tail->next=newNode;
                tail=tail->next;
            }
            //overflow; need to remove the least recently visited page
            if(hashTable.size()>cap){
                Cache* tmp = head;
                hashTable.erase(head->key);
                head = head->next;
                hashTable[head->key]=NULL;
                delete tmp;
                tmp=NULL;
            }
        }
    }
};

Here we use doubly linked list.

class LRUCache{
private:
    struct CacheNode{
        int key, val;
        CacheNode(int k, int v):key(k),val(v) {}
    };
    list<CacheNode> cache;
    unordered_map<int, list<CacheNode>::iterator> hashTable;
    int cap;
public:
    LRUCache(int capacity):cache(),hashTable(),cap(capacity) {
    }
    
    int get(int key) {
        if(hashTable.find(key)==hashTable.end())
            return -1;
        else{
            cache.splice(cache.end(), cache, hashTable[key]);
            hashTable[key]=(--cache.end());
            return hashTable[key]->val;
        }
    }
    
    void set(int key, int value) {
        if(get(key)!=-1)
            hashTable[key]->val=value;
        else{
            cache.push_back(CacheNode(key, value));
            hashTable[key]=(--cache.end());
            if(cache.size()>cap){
                hashTable.erase(cache.front().key);
                cache.pop_front();
            }
        }
    }
}; 

Here we use doubly linked list. The idea is similar to the above; the difference is that the first and last pages in the list are the most and least recently visited pages respectively;

class LRUCache{
private:
    struct CacheNode{
        int key, val;
        CacheNode(int k, int v):key(k),val(v) {}
    };
    list<CacheNode> cache;
    unordered_map<int, list<CacheNode>::iterator> hashTable;
    int cap;
public:
    LRUCache(int capacity):cache(),hashTable(),cap(capacity) {
    }
    
    int get(int key) {
        if(hashTable.find(key)==hashTable.end())
            return -1;
        else{
            cache.splice(cache.begin(), cache, hashTable[key]);
            hashTable[key]=cache.begin();
            return hashTable[key]->val;
        }
    }
    
    void set(int key, int value) {
        if(get(key)!=-1)
            hashTable[key]->val=value;
        else{
            cache.push_front(CacheNode(key, value));
            hashTable[key]=cache.begin();
            if(cache.size()>cap){
                hashTable.erase(cache.back().key);
                cache.pop_back();
            }
        }
    }
}; 

Binary Tree Inorder Traversal [Leetcode]

In the previous post, we talked about the binary tree postorder traversal. Here the solution to the inorder traversal is similar to the second solution of the postorder traversal. The basic idea is to traverse the tree in the depth first fashion; print the node if (1) its left children has been traversed or (2) it has no children. To indicate the direction of traversing (down or up), we use a pointer pre to denote the previously-traversed node, and a pointer cur to denote the node we are traversing right now. [see 1 and 2 for other good solutions]

/**
 * 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> inorderTraversal(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> ret;
        if(root==NULL)
            return ret;
        stack<TreeNode*> st;
        TreeNode* pre = NULL;
        TreeNode* cur = NULL;
        st.push(root);
        while(!st.empty()){
            //Traversing down the tree
            cur = st.top();
            if(pre==NULL || cur==pre->left || cur==pre->right){
                if(cur->left!=NULL)
                    st.push(cur->left);
                else
                {
                    ret.push_back(cur->val);
                    if(cur->right!=NULL)
                        st.push(cur->right);
                    else
                        st.pop();
                }
            }
            //Traversing up the tree from left
            else if(cur->left==pre){
                ret.push_back(cur->val);
                if(cur->right!=NULL)
                    st.push(cur->right);
                else
                    st.pop();
            }                
            //Traversing up the tree from right
            else if(cur->right==pre)
                st.pop();
            //Keep track of the previously traversed node
            pre = cur;
        }
        return ret;
    }
}; 

Binary Tree Postorder Traversal [Leetcode]

In the previous post, we did the binary tree preorder traversal without using recursion. I find its solution can be modified a little bit to achieve postorder traversal. The idea is the similar, the only difference is that we push the left child first instead of pushing right child first.

1. Push the root into stack;
2. Do the follwoing steps until the stack is empty:
• Pop out the top-most node in the stack as the current node; and add it in the front of the resulting vector (or push it into another stack and then pop it out before all nodes are pushed in the the stack);
• Push its left child and then right child into stack if they exist.

/**
 * 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.
        vector<int> ret;
        if(root==NULL)
            return ret;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()){
            TreeNode* cur = st.top();
            st.pop();
            ret.insert(ret.begin(), cur->val);
            if(cur->left!=NULL)
                st.push(cur->left);
            if(cur->right!=NULL)
                st.push(cur->right);
        }
        return ret;
    }
};

The solution above actually needs two stacks if we want to print on the fly. The following is the solution using only one stack. The basic idea is to traverse the tree in the depth first fashion; print the node if (1) all its children have been traversed or (2) it has no children. To indicate the direction of traversing (down or up), we use a pointer pre to denote the previously-traversed node, and a pointer cur to denote the node we are traversing right now. [click here for more details; see here for another good solution]

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.
        vector<int> ret;
        if(root==NULL)
            return ret;
        stack<TreeNode*> st;
        TreeNode* pre = NULL;
        TreeNode* cur = NULL;
        st.push(root);
        while(!st.empty()){
            //Traversing down the tree
            cur = st.top();
            if(pre==NULL || cur==pre->left || cur==pre->right){
                if(cur->left!=NULL)
                    st.push(cur->left);
                else if(cur->right!=NULL)
                    st.push(cur->right);
                else
                {
                    ret.push_back(cur->val);
                    st.pop();
                }
            }
            //Traversing up the tree from left
            else if(cur->left==pre){
                if(cur->right!=NULL)
                    st.push(cur->right);
                else{
                    ret.push_back(cur->val);
                    st.pop();
                }
            }                
            //Traversing up the tree from right
            else if(cur->right==pre){
                    ret.push_back(cur->val);
                    st.pop();
            }
            //Keep track of the previously traversed node
            pre = cur;
        }
        return ret;
    }
};

Binary Tree Preorder Traversal [Leetcode]

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?

Solution: when it comes to the binary tree traversal, we need a stack if the node in the tree has no parent pointer. The idea of the solution 1 is quite simple and I found it online:

1. Push the root into stack;
2. Do the follwoing steps until the stack is empty:
• Pop out the top-most node in the stack as the current node; and print it;
• Push its right child and then left child into stack if they exist.

Solution 2 is from me. Since it is quite complicated compared with Solution 1, I do not discuss it.

   /*******************************SOLUTION 1***********************************/

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

   /*******************************SOLUTION 2***********************************/

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

The Knight’s Tour Problem [GeeksforGeeks]

Here is the detailed description of Knight's Tour problem. I use backtraking to solve this problem.

#include <iostream>
#include <iomanip>

const int W=8, H=8;

//Print solution
void printSol(int board[W][H]){
    for(int i=0; i<W; i++){
        for(int j=0; j<H; j++){
            std::cout<<std::setw(3)<<board[i][j]<< "  ";
        }
        std::cout<<std::endl;
    }
}

//Check validitiy of the current cell
bool isValid(int x, int y, int board[W][H]){
    return (0<=x && x<W && 0<=y && y<H && board[x][y]==-1);
}

//Do backtracking
bool KnightTour(int x, int y, int board[W][H], int cur){
    if(cur==W*H-1){
        board[x][y]=cur;
        return true;    
    }
    int moveX[8]={2, 1, -1, -2, -2, -1, 1, 2};
    int moveY[8]={1, 2, 2, 1, -1, -2, -2, -1};
    board[x][y]=cur;
    for(int i=0; i<8; i++){
        int a=x+moveX[i], b=y+moveY[i];
        if(isValid(a, b, board)&&KnightTour(a, b, board, cur+1))
            return true;
    }
    board[x][y]=-1;
    return false;
}

//Find Knight's Tour
int main ()
{
    int board[W][H];
    for(int i=0; i<W; i++)
        for(int j=0; j<H; j++)
            board[i][j]=-1;
    if(KnightTour(0, 0, board, 0)){
        std::cout << "The solution is:" << std::endl;
        printSol(board);
    }
    else
        std::cout << "No solution exists" << std::endl;    
    return 0;
}

Reorder List [Leetcode]

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-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}.

Solution: nothing but pointer manipulation.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverse(ListNode* head){
        ListNode* prev = NULL;
        ListNode* cur=head;
        while(cur!=NULL){
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    void reorderList(ListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(head==NULL || head->next==NULL || head->next->next==NULL)
            return;
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* tail = NULL;
        //Find the (nNode/2)-th node, the new tail
        while(fast!=NULL && fast->next!=NULL){
            tail = slow;
            slow=slow->next;
            fast=fast->next->next;
        }
        if(fast!=NULL)
            tail = tail->next;
        //Reverse the second part
        ListNode *sHead = reverse(tail->next);
        tail->next = NULL;
        //Combination
        ListNode* sCur = sHead;
        ListNode* cur = head;
        while(sCur!=NULL){
            ListNode* nxt = cur->next;
            ListNode* sNxt = sCur->next;
            cur->next = sCur;
            sCur->next = nxt;
            cur=nxt;
            sCur=sNxt;
        }
    }
};

Wildcard Matching [Leetcode]

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

Solution: the first method is recursion, but I got TLE. Then I tried DP; got MLE; then I reduced the space requirement to O(n), where n is the length of string S. I found the solution 3 online; check here.

   /*******************************SOLUTION 1***********************************/

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        //cout << s << "  "<< p << endl;      
        if(s==NULL || p==NULL)
            return false;
        if(*p=='\0')
            return *s=='\0';
        if(*p!='*'){
            if(*p==*s || *p== '?'){
                if(*s=='\0')
                    return false;
                return isMatch(s+1, p+1);
            }
            else
                return false;
        }
        while(*p == '*')
            ++p;
        if(*p=='\0')
            return true;
        while(*s!='\0'){
            if(isMatch(s, p))
                return true;
            s++;
        }
        while(*p)
            if(*p++ != '*')
                return false;
        return true;
    }
};

   /*******************************SOLUTION 2***********************************/

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(s==NULL || p==NULL)
            return false;
        if(*p=='\0')
            return *s=='\0';
        int m=strlen(s), n=strlen(p);
        int nStar=0;
        for(int i=0; i<n; i++)
            if(p[i]=='*')
                nStar++;
        if(m<n-nStar)
            return false;
        
        vector<bool> helper(n+1, false);
        vector<vector<bool>> dp(2, vector<bool>(n+1, false));
        dp[0][0] = true;
        helper[0] = true;
        for(int i=1; i<=n && p[i-1]=='*'; i++){
            dp[0][i]=true;
            helper[i]=true;
        }

        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                dp[i%2][0] = false;  
                if(s[i-1]==p[j-1] || p[j-1]=='?')
                    dp[i%2][j]=dp[(i-1)%2][j-1];
                else if(p[j-1]=='*')
                    dp[i%2][j]=helper[j-1];
                else
                    dp[i%2][j]=false;
                if(dp[i%2][j])
                    helper[j]=true;
            }
        }

        return dp[m%2][n];
    }
};

   /*******************************SOLUTION 3***********************************/

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(s==NULL || p==NULL)
            return false;
        if(*p=='\0')
            return *s=='\0';
        const char *pres=NULL, *prep=NULL;
        while(*s){
            if(*p==*s || *p=='?'){
                ++p;
                ++s;
                continue;
            }
            if(*p=='*'){
                while(*p == '*')
                    ++p;
                if(*p=='\0')
                    return true;
                pres = s;
                prep = p;
                continue;
            }
            if(prep!=NULL){
                p = prep;
                ++pres;
                s = pres;
                continue;
            }
            return false;
        }
        while(*p)
            if(*p++ != '*')
                return false;

        return true;
    }
};

Text Justification [Leetcode]

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.
Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

click to show corner cases.

Corner Cases:

• A line other than the last line might contain only one word. What should you do in this case?
  In this case, that line should be left-justified.

Solution: nothing special; check the code for the details.

class Solution {
public:
    string generateOneLince(vector<string> &words, int start, int end, int L){
        string s;
        //the line has exactly one word
        if(start==end){
            s+=words[start];
            s.append(L-words[start].size(), ' ');
            return s;
        }
        //the last line
        if(end==words.size()-1){
            for(int i=start; i<=end; i++){
                s+=words[i];
                if(i!=end)
                    s.append(1, ' ');
            }
            s.append(L-s.size(), ' ');
            return s;
        }
        //ordinary line
        int wordsL = 0;
        for(int i=start; i<=end; i++)
            wordsL+=words[i].size();
        int aveSpace = (L-wordsL)/(end-start);
        int addSpace = (L-wordsL)%(end-start);
        for(int i=start; i<end; i++){
            s+=words[i];
            if(i-start<addSpace)
                s.append(aveSpace+1, ' ');
            else
                s.append(aveSpace, ' ');
        }
        s+=words[end];
        return s;
    }
    vector<string> fullJustify(vector<string> &words, int L) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<string> ret;
        if(words.empty() || words[0].empty() || L<=0){
            string r(L, ' ');
            ret.push_back(r);
            return ret;
        }
        int start = 0;
        int count = 0;
        for(int i=0; i<words.size(); i++){
            if(count+words[i].size()==L){
                ret.push_back(generateOneLince(words, start, i, L));
                start=i+1;
                count=0;
            }
            else if(count+words[i].size()>L){
                ret.push_back(generateOneLince(words, start, i-1, L));
                start=i;
                count=words[i].size()+1;
            }
            else
                count+=(words[i].size()+1);
        }
        if(count!=0)
            ret.push_back(generateOneLince(words, start, words.size()-1, L));
        return ret;
    }
};

String to Integer (atoi) [Leetcode]

Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

spoilers alert... click to show requirements for atoi.

Requirements for atoi: The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Solution: see the following code for details.

class Solution {
public:
    string clearTwoEnds(const char *s){
        //remove leading spaces and trailing non-digits
        string ret;
        int start=0;
        while(start<strlen(s) && isspace(s[start]))
            start++;
        if(start==strlen(s))
            return ret;
        if(s[start]=='+' || s[start]=='-'){
            ret+=s[start];
            start++;
        }
        for(int i=start; i<=strlen(s); ++i){
            if(isdigit(s[i]))
                ret+=s[i];
            else
                break;
        }
        return ret;
    }
    int atoi(const char *str) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(str==NULL || *str=='\0')
            return 0;
        string r = clearTwoEnds(str);
        if(r.empty())
            return 0;
        //if out of range: INT_MAX (2147483647) or INT_MIN (-2147483648) is returned
        bool negative = (r[0]=='-'?true:false);
        int i= (!isdigit(r[0])?1:0);
        long long ret = 0;
        while(i<r.size()){
            if(negative){
                if(ret*10-(r[i]-'0')<INT_MIN)
                    return INT_MIN;
                else
                    ret = ret*10-(r[i]-'0');
            }
            else{
                if(ret*10+(r[i]-'0')>INT_MAX)
                    return INT_MAX;
                else
                    ret = ret*10+(r[i]-'0');
            }
            ++i;
        }
        return ret;
    }
};