sourcecode

Monday, January 21, 2013

Roman to Integer


Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
class Solution {
    int romanToDigit(char c){
        int r = 0;
        switch(c){
            case 'I': r = 1; break;
            case 'V': r = 5; break;
            case 'X': r = 10; break;
            case 'L': r = 50; break;
            case 'C': r = 100; break;
            case 'D': r = 500; break;
            case 'M': r = 1000; break;                
        }
        return r;
    }
public:
    int romanToInt(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.empty()) return 0;
        int num = romanToDigit(s[s.length()-1]);
        int prev = num;
        for(int ii = s.length() - 2; ii >= 0; --ii){
            int const digitNum = romanToDigit(s[ii]);
            if (digitNum < prev) num -= digitNum;
            else num += digitNum;
            prev = digitNum;
        }
        return num;
    }
};

Rotate Image


You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?
class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (matrix.empty() || matrix[0].empty() ) return;
        int const max = matrix.size() - 1;
        int const quarter_col_size = matrix.size() / 2 + (matrix.size()%2);
        int const quarter_row_size = matrix.size() / 2;
        for(int row = 0; row < quarter_row_size; ++row){
            for(int col = 0; col < quarter_col_size; ++col){
                int const temp = matrix[row][col];
                matrix[row][col] = matrix[max-col][row];
                matrix[max-col][row] = matrix[max-row][max-col];
                matrix[max-row][max-col] = matrix[col][max-row];
                matrix[col][max-row] = temp;
            }
        }
    }
};

Friday, January 11, 2013

Rotate List


Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!head || !head->next || !k) return head;
        ListNode* front = head;
        for(int ii = 0; ii < k; ++ii){
            front = front->next;
            if (!front) front = head;
        }
        ListNode* it = head;
        while(front->next){
            front = front->next;
            it = it->next;
            if (!it) it = head;
        }
        front->next = head;
        head = it->next;
        it->next = NULL;
        return head;
    }
};

Same Tree


Same Tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!p || !q) return !p && !q;
        return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        
    }
};

Scramble String


Scramble String
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
class Solution {//passed small only
public:
    bool isScramble(string s1, string s2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s1.size() == 1) return s1[0] == s2[0];
        if (s1.empty() || s1.compare(s2) == 0) return true;
        int const max_index = s1.length()-1;
        for(int ii = 1; ii <= max_index; ++ii){
            string const s1_left = s1.substr(0, ii);
            string const s1_right = s1.substr(ii, s1.length()-ii);
            string const s2_left1 = s2.substr(0,ii);
            string const s2_right1 = s2.substr(ii, s2.length()-ii);
            string const s2_left2 = s2.substr(s2.length()-ii, ii);
            string const s2_right2 = s2.substr(0, s2.length()-ii);
            if (isScramble(s1_left, s2_left1) && isScramble(s1_right, s2_right1) 
              || isScramble(s1_left, s2_left2) && isScramble(s1_right, s2_right2))
              return true;
        }
        return false;
    }
};
 class Solution {//passed large
    vector<vector<vector<int> > > record;
    string sa,sb;
public:
    bool process(int pos1, int pos2, int length){
        if (length == 1) return sa[pos1] == sb[pos2];
        if (length == 0) return true;
        if (record[pos1][pos2][length] == 1) return true;
        if (record[pos1][pos2][length] == -1) return false;
        for(int ii = 1; ii < length; ++ii){//ii is size_left
            int const size_right = length - ii;
            if (process(pos1, pos2, ii) && process(pos1+ii, pos2+ii, size_right) 
              || process(pos1, pos2+length-ii,ii) && process(pos1+ii, pos2, size_right)){
                record[pos1][pos2][length] = 1;              
                return true;
              }
        }
        record[pos1][pos2][length] = -1;
        return false;
    }

    bool isScramble(string s1, string s2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        sa = s1;
        sb = s2;
        record.clear();
        record.assign(s1.length()+1,vector<vector<int> >(s1.length()+1, vector<int>(s1.length()+1, 0)));

        return process(0,0,s1.length());
  }
};

Saturday, January 5, 2013

Search a 2D Matrix


Search a 2D Matrix
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
Given target = 3, return true
class Solution {
    pair<bool, int> process(vector<vector<int> >& matrix, int const start,
      int const end, int const target, bool rowSearch = false, int row = 0){
        int const halfIndex = start + (end-start+1)/2;
        int first_val, last_val, mid_val;
        if(rowSearch){
            first_val = matrix[row][start];
            last_val = matrix[row][end];
            mid_val = matrix[row][halfIndex];
        }else{        
            first_val = matrix[start][0];
            last_val = matrix[end][0];
            mid_val = matrix[halfIndex][0];
        }
        if (start == end){
            if (target != mid_val) return pair<bool, int>(false, start);
            else return pair<bool,int>(true, start);
        }
        return ( target < mid_val? 
            process(matrix, start, halfIndex-1, target, rowSearch, row):
            process(matrix, halfIndex, end, target, rowSearch, row)  );
            
        
    }
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(matrix.empty() || matrix[0].empty() || target < matrix[0][0] || target > matrix.back().back()) return false;
        pair<bool, int> colResult = process(matrix, 0, matrix.size()-1, target);
        if (colResult.first) return true;
        return process(matrix, 0, matrix[0].size()-1, target, true, colResult.second).first;
    }
};

Search for a Range


Search for a Range
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
Using the method developed in Search Insert Position
class Solution {
    pair<bool, int> process(int A[], int start, int end, int target){
        if (start == end){
            if (target > A[start]) return pair<bool, int>(false, start+1);
            else if (target < A[start]) return pair<bool, int>(false, start);
            else return pair<bool, int>(true, start);
        }
        int half = start + (end-start)/2;
        if (target <= A[half]) return process(A, start, half, target);
        else return process(A, half+1, end, target);
    }
public:
    vector<int> searchRange(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> r(2,-1);
        pair<bool, int> found = process(A, 0, n-1, target);
        if (!found.first) return r;
        r[0] = found.second;
        found = process(A,0,n-1,target+1);
        r[1] = found.second - 1;
        return r;
        
    }
};

Search in Rotated Sorted Array (I and II)


Search in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
class Solution {
    int process(int A[], int const start, int const end, int const target){
        if (start == end){
            if (target == A[start]) return start;
            else return -1;
        }
        int const half = start + (end-start)/2;
        if ( A[start] <= A[half] && (target <= A[half] && target >= A[start])
          || A[start] > A[half] && (target <= A[half] || target >= A[start])) return process(A, start, half, target);
        else return process(A, half+1, end, target);
    }
public:
    int search(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return process(A, 0, n-1, target);
    }
};
II

Search in Rotated Sorted Array II
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.

class Solution {//with dups, one may not be able to determine to process whether the first half
//or the second half of the array, by just looking at three positions: start, half and end
//e.g. 11111111131
//in this case, both parts must be considered, which rise the worst case to O(n)

bool process(int A[], int const start, int const end, int const target){
        if (start == end){
            if (target == A[start]) return true;
            else return false;
        }
        int const half = start + (end-start)/2;
        if (A[start] == A[half] && A[half] == A[end]) return (process(A, start, half, target) || process(A, half+1, end, target));
        if ( A[start] <= A[half] && (target <= A[half] && target >= A[start])
          || A[start] > A[half] && (target <= A[half] || target >= A[start])) return process(A, start, half, target);
        else return process(A, half+1, end, target);
    }
public:
    bool search(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return process(A,0,n-1, target);
    }
};