Day 33, 49, 50,53,55, Anagrams, Pow(x, n), Maximum Subarray,Jump Game

Anagrams
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
---------------------
Solution#1, hashing

class Solution {
public:    
    vector<string> anagrams(vector<string> &strs) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        unordered_map<string,string> mapping;
        vector<string> ret;
        for (int i=0;i<strs.size();i++) {
            string str = strs[i];
            sort(str.begin(),str.end());
            if (!mapping.count(str)) {
                mapping[str] = strs[i];
            }else {
                if (find(ret.begin(),ret.end(),mapping[str]) == ret.end()) {
                    ret.push_back(mapping[str]);
                }
                ret.push_back(strs[i]);
            }
        }
        return ret;
    }
};

Solution#2, optimized running time, trader off with extra space

class Solution {
public:   
    vector<string> anagrams(vector<string> &strs) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        unordered_map<string,string> mapping;
        unordered_map<string,bool> put; // to record if string has been put in result array
        vector<string> ret;
        
        for (int i=0;i<strs.size();i++) {
            string str = strs[i];
            sort(str.begin(),str.end());
            if (mapping.find(str) == mapping.end()) {
                mapping[str] = strs[i];
                put[strs[i]] = false;
            }else {
                if (put[mapping[str]] == false) {
                    ret.push_back(mapping[str]);
                    put[mapping[str]] = true;
                }
                put[strs[i]] = true;
                ret.push_back(strs[i]);
            }
        }
        return ret;
    }
};

Pow(x, n)
Implement pow(x, n).
-------------------------------
log(n) recursive solution

class Solution {
public:
    double pow(double x, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        if (n == -1) {
            return 1/x;
        }
        double result = pow(x,n/2);
        double extra = 1;
        if (n%2 == -1) {
            extra = 1/x;
        }else if (n%2 == 1) {
            extra = x;
        }
        return result * result * extra;
    }
};

bit shift, iterative solution, watch out for casting from internet
proof:
2^4 = 4^2 = 16^1
5^6 = 25^3 = 25^2 * 25 = 625^1 * 25

class Solution {
public:
    double pow(double x, int n) {
        unsigned m = abs((double)n);
        double ret = 1;
        for ( ; m; x *= x, m >>= 1) {
            if (m & 1) {
                ret *= x;
            }
        }
        return (n < 0) ? (1.0 / ret) : (ret);
    }
};

Maximum Subarray Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

More practice:If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

----------------------------------
121 Best time to buy and sell is based on this algorithm  
how is this DP??

class Solution {
public:
    int maxSubArray(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int max=INT_MIN;
        int sum=0;
        for (int i=0;i<n;i++) {
            if (sum < 0) {
                sum = A[i];
            }else {
                sum += A[i];
            }
            if (sum > max) {
                max = sum;
            }
        }
        return max;
    } 
};

A easier to understand version Kadane's algorithm
sum是局部最优，表示当前连续子集的最后一位必定是在i
maxSum是全局最优
类似题目买卖股票3跟4

class Solution {
public:
    int maxSubArray(int A[], int n) {
        int sum = A[0];
        int maxSum = A[0];
        
        for (int i = 1; i < n; i++) {
            sum = max(A[i], sum + A[i]);
            maxSum = max(sum,maxSum);
        }
        return maxSum;
    }
};

divide and conquer, O(n * lg n)
#1: max subarray is in left part
#2: max subarray is in right part
#3: max subarray is acrossing the middle element

class Solution {
public:
    int maxSub(vector<int> &nums,int left,int right) {
        if (left == right) return nums[left];
        
        int mid = (left + right) / 2;
        int leftMax = maxSub(nums,left,mid);
        int rightMax = maxSub(nums,mid + 1, right);
        int crossMax = nums[mid] + nums[mid + 1];
        int temp = crossMax;
        for (int i = mid - 1; i >= left; i--) {
            temp += nums[i];
            crossMax = max(crossMax,temp);
        }
        
        temp = crossMax; // it's possible temp will be smaller than crossMax
        for (int i = mid + 2; i <= right; i++) {
            temp += nums[i];
            crossMax = max(crossMax,temp);
        }
        
        return max(crossMax,max(leftMax,rightMax));
    }

    int maxSubArray(vector<int>& nums) {
        return maxSub(nums,0,nums.size() - 1);
    }
};

Jump Game Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example: A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false. ------------------------------------ DP bottom up, O(n) starting at [end - 1] towards [0], find out the first elem that can jump to the end, then set it to be the new end

class Solution {
public:
    bool canJump(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int index = n-1;
        for (int i=n-2;i>=0;i--) {
            if (A[i] >= index-i) {
                index = i;
            }
        }
        return index == 0;
    }
};