8.31.2017(Q120-Q125).md

Questions 120 ~ 125

Full score: 3 X 100 = 300

Actual score:

121, Best Time to Buy and Sell Stock

Questions: Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Idea:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        int ans = 0, m = prices[0];
        for(auto k:prices){
            m = min(m,k);
            ans = max(ans,k-m);
        }
        return ans;
    }
};

122, Best Time to Buy and Sell Stock II

Questions: Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Idea:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for(int i=0;i<(int)prices.size()-1;++i) ans += max(prices[i+1]-prices[i],0);
        return ans;
    }
};

123. Best Time to Buy and Sell Stock III

Questions: Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions.

Idea: record a prof vector denoting the maximum profit that a person can get within the first i days, with at most r transactions.

typedef vector<int> vi;
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        int n = (int)prices.size();
        vi prof(n,0);
        for(int r=0;r<2;++r){
            for(int i=1,m=prof[0]-prices[0];i<n;++i){
                m = max(m,prof[i]-prices[i]);
                prof[i] = max(prof[i-1],prices[i]+m);
            }
        }
        return prof[n-1];
    }
};

124. Binary Tree Maximum Path Sum

Questions: Given a binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Idea: Not a good solution. Need to construct a new tree. There is a memory leakage.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode *constrTree(TreeNode *root){
        if(!root) return NULL;
        TreeNode *cp = new TreeNode(0);
        cp->left = constrTree(root->left);
        cp->right = constrTree(root->right);
        cp->val = max(0, root->val + max(cp->left? cp->left->val:0, cp->right?cp->right->val:0));
        return cp;
    }
    int maxHelpSum(TreeNode *root,TreeNode *cp){
        if(!root) return 0;
        int ans = root->val + (cp->left?cp->left->val:0) + (cp->right?cp->right->val:0);
        if(root->left) ans = max(ans, maxHelpSum(root->left,cp->left));
        if(root->right) ans = max(ans,maxHelpSum(root->right,cp->right));
        return ans;
    }
public:
    int maxPathSum(TreeNode* root) {
        if(!root) return 0;
        TreeNode *cp = constrTree(root);
        return maxHelpSum(root,cp);
    }
};

125. Valid Palindrome

Questions: Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,

A man, a plan, a canal: Panama is a palindrome.

race a car is not a palindrome.

Idea: judge one by one.

class Solution {
    bool equal(char a,char b){
        if(a>='a' && a<='z') return a==b || a-'a'==b-'A';
        else if(a>='0' && a<='9') return a==b;
        return a==b|| a-'A'==b-'a';
    }
public:
    bool isPalindrome(string s) {
        int n = (int)s.size();
        int i = 0, j = n-1;
        while(i<j){
            while(i<j && !isalnum(s[i])) ++i;
            while(i<j && !isalnum(s[j])) --j;
            if(i<j && !equal(s[i++],s[j--])) return false;
        }
        return true;
    }
};