LeetCode Problem : Sort List

Problem

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

Code

ListNode *partition(ListNode *p,ListNode *q,ListNode *prev,
ListNode **head,ListNode **left,ListNode **right){
    ListNode *i = p,*j = p,*r = p;
    int x = i->val;
    while(j && j->next && j->next != q){
        if(j->next->val < x){
            swap(i->next->val,j->next->val);
            i = i->next;
            j = j->next;
        }
        else if(j->next->val == x){
            if(r == j){
                r = r->next;
                i = r;
                j = j->next;
            }
            else{
                ListNode *tmp = j->next;
                j->next = tmp->next;
                tmp->next = r->next;
                r->next = tmp;
                if(i == r)
                    i = r->next;
                r = r->next;
            }
        }
        else
            j = j->next;
    }
    if(r != i){
        ListNode *first = r->next;
        r->next = i->next;
        i->next = p;
        if(p == *head)
            *head = first;
        else
            prev->next = first;
        *left = first;
        *right = r;
    }
    else{
        *left = p;
        *right = r;
    }
    return i;
}
void qsList(ListNode *p,ListNode *q,ListNode *prev,ListNode **head){
    if(p == q)
        return;
    ListNode *left,*right;
    ListNode *i = partition(p,q,prev,head,&left,&right);
    qsList(left,p,prev,head);
    qsList(right->next,q,right,head);
}
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)
        return 0;
    qsList(head,0,0,&head);    
    return head;
}

LeetCode Problem : Evaluate Reverse Polish Notation

Problem

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

Code

bool isOperator(const string& str)
{
    if(str.size() > 1)
    return false;
    char ch = str[0];
    switch(ch)
    {
        case '*' :
        case '/' :
        case '+' :
        case '-' :
            return true;
        default :
            return false;
    }
}
int eval(int op1,int op2,char op){
    switch(op)
    {
        case '*' :
            return (op2 * op1);
        case '/' :
            return (op2 / op1);
        case '+' :
            return (op2 + op1);
        case '-' :
            return (op2 - op1);
    }
}
int strToInt(const string& str)
{
    return atoi(str.c_str());
}

int evalRPN(vector<string> &tokens) {
    stack<int> st;
    int n = tokens.size();
    for(int i = 0;i < n; ++i){
        if(isOperator(tokens[i])){
            int op1 = st.top();
            st.pop();
            int op2 = st.top();
            st.pop();
            st.push(eval(op1,op2,tokens[i][0]));
        }
        else{
            st.push(strToInt(tokens[i]));
        }
    }
    return st.top();
}

LeetCode Problem : Insertion Sort List

Problem

Sort a linked list using insertion sort.

Code

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)
        return 0;
    ListNode *node = head;
    while(node->next){
        if(node->next->val < head->val){
            ListNode *tmp = node->next;
            node->next = tmp->next;
            tmp->next = head;
            head = tmp;
        }
        else{
            ListNode *pos = head;
            while(pos != node && node->next->val > pos->next->val)
                pos = pos->next;
            if(pos == node)
                node = node->next;
            else{
                ListNode *tmp = pos->next;
                pos->next = node->next;
                node->next = node->next->next;
                pos->next->next = tmp;
            }
        }
    }
    return head;
}

LeetCode Problem : Sudoku Solver

Problem

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

Code

void sudokuTable(vector<vector<char> > &board,vector<vector<bool> > &p)
{
    for(int i =0;i < 9; ++i){
        for(int j =0;j < 9; ++j){
            if(board[i][j] != '.')
            p[i][j] = true;
        }
    }
}
bool getNextCell(vector<vector<char> > &board,vector<vector<bool> > &p,
     int i,int j,int &a,int &b,bool &completed){
    for(int k = j;k < 9; ++k){
        if(!p[i][k]){
            a = i;
            b = k;
            return true;
        }
    }
    for(int l = i + 1;l < 9; ++l){
        for(int k = 0;k < 9; ++k){
            if(!p[l][k]){
                a = l;
                b = k;
                return true;
            }
        }
    }
    completed = true;
    return false;
}
vector<char> getNumbers(vector<vector<char> > &board,vector<vector<bool> > &p,int i,int j){
    vector<char> result;
    for(int num = 0;num < 9;++num){
    char ch = '1' + num;
    bool found = false;
    //check row
    for(int k = 0;k < j; ++k){
        if(board[i][k] == ch){
            found = true;
            break;
        }
    }
    if(found)
        continue;
    //check row
    for(int k = j + 1;k < 9; ++k){
        if(p[i][k] && board[i][k] == ch){
            found = true;
            break;
        }
    }
    if(found)
        continue;
    //check col
    for(int k = 0;k < i; ++k){
        if(board[k][j] == ch){
            found = true;
            break;
        }
    }
    if(found)
        continue;
    //check col
    for(int k = i + 1;k < 9; ++k){
        if(p[k][j] && board[k][j] == ch){
            found = true;
            break;
        }
    }
    if(found)
        continue;
    //check block
    int blockrow = i - (i % 3);
    int blockcol = j - (j % 3);
    for(int k = blockrow;k < i; ++k){
        for(int l = blockcol;l < j; ++l){
            if(board[k][l] == ch){
                found = true;
                break;
            }
    }
    if(found)
        break;
    }
    if(found)
        continue;
    for(int k = i + 1;k < (blockrow + 3); ++k){
        for(int l = blockcol;l < (blockcol + 3); ++l){
            if(p[k][l] && board[k][l] == ch){
                found = true;
                break;
            }
        }
        if(found)
            break;
    }
    if(found)
        continue;
    for(int k = j + 1;k < (blockcol + 3); ++k){
        for(int l = blockrow;l < (blockrow + 3); ++l){
            if( l < i ){
                if(board[l][k] == ch){
                    found = true;
                    break;
                }
            }
            else{
                if(p[l][k] && board[l][k] == ch){
                found = true;
                break;
                }
            }
        }
        if(found)
        break;
    }
    if(found)
    continue;
        result.push_back(ch);
    }
    return result;
}

void solveSudoku_r(vector<vector<char> > &board,vector<vector<bool> > &p,
     int i,int j,bool &completed){
    vector<char> numbers = getNumbers(board,p,i,j);
    int sz = numbers.size();
    for(int k = 0;k < sz; ++k){
        board[i][j] = numbers[k]; 
        int a,b;
        if(!getNextCell(board,p,i,j + 1,a,b,completed))
            return;
        solveSudoku_r(board,p,a,b,completed);
        if(completed)
            break;
    }
}
void solveSudoku(vector<vector<char> > &board) {
    vector<vector<bool> > p(9,vector<bool>(9,false));
    sudokuTable(board,p);
    int a,b;
    bool completed = false;
    getNextCell(board,p,0,0,a,b,completed);
    solveSudoku_r(board,p,a,b,completed);
}

LeetCode Problem : Divide Two Integers

Problem

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

Code

int absval(int num,int bits)
{
    int mask = num>>bits;
    return ((num + mask)^mask);
}
bool isDivNegative(int n1,int n2,int bits)
{
    int mask = 1 << bits;
    return ((n1 & mask) ^ (n2 & mask));
}
int division(unsigned int n1,unsigned int n2,int bits) {
    unsigned int q = 0;
    unsigned int r = 0;
    for(int i = bits;i >= 0; --i){
        r = r << 1;
        if(n1 & (1 << i))
            r |= 1;
        else
            r &= ~1;
        if(r >= n2){
            r -= n2;
            q |= (1 << i);
        }
    }
    return q;
}
int divide(int dividend, int divisor) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    int bits = numeric_limits<int>::digits;
    unsigned int n1 = absval(dividend,bits);
    unsigned int n2 = absval(divisor,bits);
    int ret = division(n1,n2,bits);
    return ((isDivNegative(dividend,divisor,bits)) ? -ret : ret);
}

LeetCode Problem : Binary Tree Postorder Traversal

Problem 

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?

Code

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> result;
    if(!root)
        return result; 
    stack<TreeNode *> st;
    do{
        while(root){
            if(root->right)
                st.push(root->right);
            st.push(root);
            root = root->left;
        }
        TreeNode *node = st.top();
        st.pop();
        if(node->right && !st.empty() && node->right == st.top()){
            root = st.top();
            st.pop();
            st.push(node);
        }
        else{
            result.push_back(node->val);
            root = 0;
        }
    }while(!st.empty());
    return result;
}

LeetCode Problem : Binary Tree Preorder Traversal

Problem

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?

Code

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> result;
    stack<TreeNode *> st;
    if(root)
        st.push(root);
    while(!st.empty()){
        TreeNode *node = st.top();
        st.pop();
        result.push_back(node->val);
        if(node->right)
            st.push(node->right);
        if(node->left)
            st.push(node->left);
    }
    return result;
}