Leetcode problems http://leetcode.com/onlinejudge

Binary Tree Inorder Traversal.cc

vector<int> inorderTraversal_moris(TreeNode *root) {
    vector<int> ans;
    TreeNode* curr = root;
    while(curr) {
        if(curr->left) {
            TreeNode* p = curr->left;
            //find the right-most child, remember to check cycle
            while(p->right && p->right != curr) {
                p = p->right;
            }
            if(NULL == p->right) {//thread it to curr,next in inorder travel
                p->right = curr;
                curr = curr->left;
            }else { //unthread and visit it
                p->right = NULL;
                ans.push_back(curr->val);
                curr = curr->right;
            }
        }else {
            ans.push_back(curr->val);
            curr = curr->right;
        }
    }
    return ans;
}

Decode Ways.cc

int numDecodings(string s) {
    vector<int> m(s.length());
    int ans = 0;
    int x1 = 1; // s[0,i-2]'s num Decodings
    int x2 = 1; // s[0,i-1]'s num Decodings
    for(int i=0;i<s.length();i++) {
        ans = (s[i] == '0') ? 0 : x2; //s[i] is valid or not?
        int tmp = i>0 ? (s[i-1]-'0')*10 : 0;
        tmp += s[i]-'0';
        if(tmp >= 10 && tmp<=26) {
            ans += x1; // s[i-1]s[i] is valid
        }
        x1 = x2; 
        x2 = ans;
    }
    return ans;
}

Flatten Binary Tree to Linked List.cc

void flatten(TreeNode *root) {
    if(!root) {
        return;
    }   
    stack<TreeNode* > s;
    TreeNode* last = NULL;
    s.push(root);
    while(!s.empty()) {
        TreeNode* r = s.top();
        s.pop();
        if(last) {
            last->right = r;
        }
        last = r;
        if(r->right) {
            s.push(r->right);
        }
        if(r->left) {
            s.push(r->left);
        }
        r->left = NULL; //flatten to linked list not double linked list
    }
}

Longest Valid Parentheses.cc

int longestValidParentheses(string s) {
    return max( helper(s.begin(), s.end(),'('), 
            helper(s.rbegin(),s.rend(),')') );
}
template<class Iter> 
int helper(Iter begin, Iter end, int ch) {
    int ans = 0;
    for(int left=0,right=0; begin!=end; begin++) {
        if(*begin == ch) {
            left++;
        }else if(left > right) {
            right++;
            if(right == left) {
                ans = max(ans, left<<1);
            }
        }else {
            right = left = 0;
        }
    }
    return ans;
}

Minimum Window Substring.cc

string minWindow(string S, string T) {
    //number of char we needed, zero means just ok,minus means more than need
    vector<int> char_counts(256,0);
    int need_char_num = 0; //how many unique char in T, it's what we need
    int min_window_size = INT_MAX;
    int min_window_index = -1;
    for(int i=0;i<T.length();i++) {
        char_counts[T[i]]++;
        if(char_counts[T[i]] == 1) {
            need_char_num++;
        }
    }
    for(int begin=0,end=0; end<S.length(); end++) {
        char_counts[S[end]]--;//char not in T will be always minus
        if(char_counts[S[end]]==0) {//one char in T satisfied
            need_char_num--;
        }
        while(begin < end && char_counts[S[begin]]<0) {
            //try our best to minify the window by moving begin
            char_counts[S[begin]]++;
            begin++;
        }
        if(need_char_num == 0) {//all char in the window now
            if(end-begin+1 < min_window_size) {
                min_window_size = end-begin+1;
                min_window_index = begin;
            }
        }
    }
    return min_window_index < 0 ? "" : S.substr(min_window_index,min_window_size);
}

Partition List.cc

ListNode *partition(ListNode *head, int x) {
    ListNode *h1, *p1, *h2, *p2;
    h1 = p1 = h2 = p2 = NULL;
    while(head) {
        if(head->val < x) {
            if(p1) {
                p1 = p1->next = head;
            }else {
                h1 = p1 = head;
            }
        }else {
            if(p2) {
                p2 = p2->next = head;
            }else {
                h2 = p2 = head;
            }
        }
        head = head->next;
    }
    if(p1) {
        p1->next = h2;
    }
    if(p2) {
        p2->next = NULL;
    }
    return h1 ? h1 : h2;
}

Spiral Matrix II.cc

vector<vector<int> > generateMatrix(int n) {
    vector<vector<int> > ans(n,vector<int>(n));
    int left,right,top,bottom, x;
    left = top = 0;
    right = bottom = n-1;
    x=1;
    while(left<=right && top<=bottom) {
        for(int i=left;i<=right;i++) {
            ans[top][i] = x++;
        }
        if(++top > bottom) break;
        for(int i=top;i<=bottom;i++) {
            ans[i][right] = x++;
        }
        if(--right < left) break;
        for(int i=right;i>=left;i--) {
            ans[bottom][i] = x++;
        }
        if(--bottom < top) break;
        for(int i=bottom;i>=top;i--) {
            ans[i][left] = x++;
        }
        if(++left > right) break;
    }
    return ans;
}

Spiral Matrix.cc

vector<int> spiralOrder(vector<vector<int> > &matrix) {
    vector<int> ans;
    if(matrix.size() == 0) {
        return ans;
    }
    int left, right, top, bottom, count;
    left = top = 0;
    right = matrix[0].size() -1;
    bottom = matrix.size() -1;
    while(left<=right && top<=bottom) {
        for(int i=left;top<=bottom && i<=right;i++) {
            ans.push_back(matrix[top][i]);
        }
        if(++top > bottom) break;
        for(int i=top;left<=right && i<=bottom;i++) {
            ans.push_back(matrix[i][right]);
        }
        if(--right < left) break;
        for(int i=right;top<=bottom && i>=left;i--) {
            ans.push_back(matrix[bottom][i]);
        }
        if(--bottom < top) break;
        for(int i=bottom;left<=right && i>=top;i--) {
            ans.push_back(matrix[i][left]);
        }
        if(++left > right) break;
    }
    return ans;
}