[leetcode] Combination Sum

vector<vector<int> > findcombination(vector<int> valid, int target){
        vector<vector<int> > res;
        int len = valid.size();
        if(len == 0) return res;
        //discard all the values larger than target.
        while(valid.back() > target){
            valid.pop_back();
            if(valid.empty()) return res;

        }
        int i = valid.size() - 1;
        while( i >= 0 ){
            int head = valid[i];
            int cur = head;
            valid.pop_back();
            vector<int> headvec;
            while(cur <= target){
                headvec.push_back(head);
                if(cur == target){
                    res.push_back(headvec);
                    break;
                }
                vector<vector<int> > tails = findcombination(valid, target - cur);
                for(int j = 0; j < tails.size(); ++j){
                    for(int k = 0; k < headvec.size(); ++k){
                        tails[j].push_back(headvec[k]);
                    }
                    res.push_back(tails[j]);
                }
                cur+=head;
            }
            --i;
        }
        return res;
}

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector<vector<int> > res;
        if(candidates.empty()) return res;
        sort(candidates.begin(), candidates.end());
        res = findcombination(candidates, target);
        return res;
    }
=========================================================

    void dfs(int left, vector<int>& candidates, vector<int>& current, vector< vector<int> >& ret, int target) {
        if (!target) {ret.push_back(current); return;}
        for (int i = left; i < (int)candidates.size(); ++ i) {
            if (candidates[i] > target) break;
            current.push_back(candidates[i]);
            dfs(i, candidates, current, ret, target - candidates[i]);
            current.pop_back();
        }
    }

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector< vector<int> > ret;
        vector<int> current;
        sort(candidates.begin(), candidates.end());
        dfs(0, candidates, current, ret, target);
        return ret;
    }

[leetcode] Minimum Path Sum *

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

My Code:

 int minPathSum(vector<vector<int> > &grid) {

        if(grid.empty()) return 0;

        int width = grid[0].size();

        int height = grid.size();

        int table[height][width];

        table[0][0] = grid[0][0];

        for(int i = 0; i < height; ++i){

            for(int j = 0; j < width; ++j){

                if(i == 0 && j != 0 )

                    table[0][j] = table[0][j-1]+grid[0][j];

                else if(j == 0 && i != 0)

                    table[i][0] = table[i-1][0]+grid[i][0];

                else if(i != 0 && j != 0){

                    table[i][j] = min(table[i-1][j], table[i][j-1]) + grid[i][j];

                }

            }

        }

        return table[height-1][width-1];

    }

[leetcode] Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

My Code:

 vector<vector<int> > pathSum(TreeNode *root, int sum) {

        vector<vector<int> > res;

        vector<int> path;

        if(!root) return res;

        if(!root->left && !root->right){

            if(root->val == sum){

                path.push_back(root->val);

                res.push_back(path);

                return res;

            }else{

                return res;

            }

        }else{

            if(root->left){

                vector<vector<int> > leftres = pathSum(root->left, sum - (root->val));

                for(int i = 0; i < leftres.size(); ++i){

                leftres[i].insert(leftres[i].begin(), root->val);

                res.push_back(leftres[i]);

                }

            }

            if(root->right){

                vector<vector<int> > rightres = pathSum(root->right, sum - (root->val));

                for(int i = 0; i < rightres.size(); ++i){

                    rightres[i].insert(rightres[i].begin(), root->val);

                    res.push_back(rightres[i]);

                }

            }

            return res;

        }

    }

Discuss

[leetcode] Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

My Code:

 bool hasPathSum(TreeNode *root, int sum) {

        if(!root) return false;

        queue<TreeNode*> q;

        q.push(root);

        while(!q.empty()){

            TreeNode* cur = q.front();

            if(!cur->left && !cur->right){

                if(cur->val == sum)

                    return true;

            }

            else{

                if(cur->left){

                    cur->left->val = cur->val + cur->left->val;

                    q.push(cur->left);

                }

                if(cur->right){

                    cur->right->val = cur->val + cur->right->val;

                    q.push(cur->right);

                }

            }

            q.pop();

        }

        return false;

    }

[leetcode] Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

My Code:

 int sumNumbers(TreeNode *root) {
        if(!root) return 0;
        queue q;
        q.push(root);
        int sum = 0;
        while(!q.empty()){
            TreeNode* cur = q.front();
            if(!cur->left && !cur->right){
                sum = sum + cur->val;
            }
            else{
                if(cur->left){
                    cur->left->val = cur->val*10 + cur->left->val;
                    q.push(cur->left);
                }
                if(cur->right){
                    cur->right->val = cur->val*10 + cur->right->val;
                    q.push(cur->right);
                }
            }
            q.pop();
        }
        return sum;
    }

[leetcode] Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Basic:
Definition of Median:
The median of a finite list of numbers can be found by arranging all the observations from lowest value to highest value and picking the middle one (e.g., the median of {3, 3, 5, 9, 11} is 5). If there is an even number of observations, then there is no single middle value; the median is then usually defined to be the mean of the two middle values (the median of {3, 5, 7, 9} is (5 + 7) / 2 = 6), which corresponds to interpreting the median as the fully trimmed mid-range. 

Algorithm:
This problems seems to be easy, it can be done by O((n+m)log(m+n)) and O((m+n)). However, when it comes to O(log(m+n)), it becomes difficult. We can do this via "find kth largest in a sorted array" and do this separately on odd and even.
1. For odd, just find (m+n)/2 +1 th number. For eve, find (m+n)/2 th and find (m+n)/2+1 th and get the average of these two.
2. For findkth function, we should keep the smaller one as m always and then then it will balanced to be log(m+n).

My Code:

[leetcode] 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.

Algorithm:

The difference here is that how to handle when A[mid] == A[right]!

then we can not decide the pivot location when A[mid] == A[right]. My solution is that when this happens, just move right to left until A[mid] != A[right].

There may be better solutions, can update later.

My Code:

bool RS(int A[], int left, int right, int target){
        if(right < left) return false;
        if(left == right) {
            if(A[left] == target) return true;
            else return false;
        }
        int mid = (left+right)/2;
        if(A[mid] == target) return true;
        if(A[mid] == A[right]){
            while(A[mid] == A[right] && right >= 0){
                right--;
            }
            return RS(A, left, right, target);
        }
        else if(A[mid] < A[right]){
            // rotated pivot on the left
            if(target < A[mid]) return RS(A, left, mid-1, target);
            else{
              if(target > A[right]) return RS(A, left, mid-1, target);
              else return RS(A, mid+1, right, target);
            }
        } else {
            //rotated pivot on the right
            if(target > A[mid]) return RS(A, mid+1, right, target);
            else{
              if(target > A[right]) return RS(A, left, mid-1, target);
              else return RS(A, mid+1, right, target);
            }
        }
    }
bool search(int A[], int n, int target) {
        if(n <= 0) return false;
        return RS(A, 0, n-1, target);
}