Best time to buy and sell stock -- Leetcode

Question:

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 (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Answer:
Follow-up: to print out the start and end day time.

int maxProfit(vector<int> &prices,int &start, int &end) {
        int minv = INT_MAX, maxv = 0, dif = 0, int k;
        for(int i=0;i<prices.size();++i){
            if(prices[i]<minv){
                minv = prices[i];
                k = i;                     //Just to keep previous latest minv index, when maxv updated!      
            }
            dif = prices[i] - minv;
            if(dif> maxv){
                maxv = dif;
                start = k;
                end = i;
            }
        }
        return maxv;
    }

Judge whether a undirected graph is a Tree

Question:
To judge whether a undirected graph is a Tree (don't have specify the d-ary value of tree...)
(== judge whether a undirected graph is acyclic) For a undirected graph, acyclic graph is just a tree.

Answer:
Key point:
1. Exclude the "root" node, every node can only has '1' parent;
2. Every node can have many children nodes.
3. Should notice about how many connectd components there are. (including isolated node)

#include <stdio.h>
#include <unordered_set>
#include <vector>
#include <iostream>

using namespace std;

struct GNode{
int val;
vector<GNode*> connection;
};

bool JudgeGTHelp(GNode *cur,GNode *par, unordered_set<GNode*> &sset){
if(!cur) return false;
    if(cur->connection.size()==1 && cur->connection[0] == par) return true;     //leaf node, only has '1' parent, base case.

for(int i=0; i<cur->connection.size();++i){
GNode *p = cur->connection[i];
if(p == par) continue;

if(sset.find(p)!= sset.end()) return false;    //To ensure the child node only has '1' parent,i.e.==cur, not traversed by other pars!!!
   sset.insert(p);
if(!JudgeGTHelp(p,cur,sset)) return false;     //Recursion case.
}
return true;
}

bool JudgeGT(GNode *p,unordered_set<GNode*> &sset){
return JudgeGTHelp(p, 0,sset);
}

int main(){
vector<GNode*> vertices;         //include all GNodes in a graph.
unordered_set<GNode*> sset;
GNode * q = vertices[0];
bool res = JudgeGT(q,sset);
if(res==false) cout<<"False"<<endl;
for(int i=0;i<vertices.size();++i){
if(sset.find(vertices[i]) == sset.end()){        //To check for if there exist any other unconnected component!!!
break;
cout<<"False"<<endl;
}
}
cout<<"True, the graph is a tree."<<endl;
getchar();
return 0;
}

Sort the array by frequency

Question:

Sort the array by frequency:

Input: [0, 1, 1, 2,2,2, 3, 4, 5,5,5,5,6,6,6,6,6,7,8,8,9,9,9]

Output:[0,3,4,7,1,1,2,2,2,8,8,2,2,2,9,9,9,5,5,5,5,6,6,6,6,6].

Answer:

#include<iostream>

#include<unordered_map>

#include<vector>

#include<utility>

#include<algorithm>

using namespace std;

struct wrapper{

        int value;

int freq;

wrapper():value(0),freq(0){};

};

bool cmp(wrapper &lhs, wrapper &rhs){

if(lhs.freq < rhs.freq) return true;

                else if(lhs.freq > rhs.freq) return false;

else return (lhs.value < rhs.value);

}

void sortbyfreq(int a[],int len){

wrapper *w = new wrapper[len];               //Important!

/* Method 1. No hashmap for count freq. 

sort(a,a+len);

int count = 0, k= 0;

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

if(i<len && i-1>=0 && a[i]==a[i-1] || i==0){

count++;

}

else{      //also include i=len,last initialize execute!!!

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

                 w[k].value= a[i-1];

w[k].freq = count;      //Important!

k++;

}

count = 1;

}

}

*/

       //Method 2, use hashmap for count freq!

unordered_map<int,int> mmap;

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

   if(mmap.find(a[i])==mmap.end()){

   mmap[a[i]]=1;

}

else{

mmap[a[i]]++;

}

}

int k=0;

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

w[k].value= a[i];

   w[k].freq = mmap[a[i]];     

   k++;

}

sort(w,w+len,cmp);

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

a[i] = w[i].value;

}

}

int main() {

    int arr [] = {0,1,2,3,2,1,1,1};

    int len = sizeof(arr)/sizeof(int);

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

cout << arr[i] << ' ';

    }

    cout << endl;

    sortbyfreq(arr, len);

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

cout << arr[i] << ' ';

    }

    cout << endl;

getchar();

    return 0;

}

Generate Parentheses -- Leetcode

Question:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

Answer:
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        if(n==0) return res;
       
        string s;
        getParenthesis(n, n, s, res);
        return res;
    }
    void getParenthesis(int rr, int lr, string s, vector<string> &res)
    {
        if(rr==0 && lr==0){
            res.push_back(s);
            return;
        }
       
        if(lr>0){
            getParenthesis(rr, lr-1, s+'(', res);
        }
       
        if(rr>lr){
            getParenthesis(rr-1, lr, s+')', res);
        }
    }
};

Subsets II -- Leetcode

From online blog:

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

[解题思路]
跟Subset I思路一样，http://fisherlei.blogspot.com/2013/01/leetcode-subsets.html。 区别只在于去重。
代码的区别只有Line 24， 25。对于当前字符，如果下一个字符与之相等，则过滤掉。

[Code]

1:    vector<vector<int> > subsetsWithDup(vector<int> &S) {  
2:      // Start typing your C/C++ solution below    
3:      // DO NOT write int main() function  
4:      vector<vector<int> > result;  
5:      vector<int> output;   
6:      if(S.size() ==0) return result;  
7:      result.push_back(output);  
8:      sort(S.begin(), S.end());  
9:      generateSub(S, 0, result, output);  
10:    }  
11:    void generateSub(  
12:      vector<int> &s,   
13:      int step,   
14:      vector<vector<int> > &result,  
15:      vector<int>& output)  
16:    {         
17:      for(int i = step;i<s.size(); i++ )  
18:      {  
19:        output.push_back(s[i]);  
20:        result.push_back(output);  
21:        if(i< s.size()-1)  
22:          generateSub(s, i+1, result, output);  
23:        output.pop_back();  
24:        while(i<s.size()-1 && s[i] == s[i+1])  
25:          i++;  
26:      }      
27:    }  

Search in rotated sorted array -- Leetcode

From online blog:

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.

[解题思想]
同样是二分，难度主要在于左右边界的确定。需要结合两个不等式：
1. A[m] ? A[left]
2. A[m] ? target
具体逻辑看code。

[Code]

1:       int search(int A[], int n, int target) {   
2:            // Start typing your C/C++ solution below   
3:            // DO NOT write int main() function   
4:            int l = 0, r = n-1;   
5:            while(l<=r)   
6:            {   
7:                 int m = (l+r)/2;   
8:                 if(A[m] == target) return m;   
9:                 if(A[m]>= A[l])   
10:                 {   
11:                      if(A[l]<=target && target<= A[m])   
12:                      r=m-1;   
13:                      else   
14:                      l = m+1;       
15:                 }   
16:                 else   
17:                 {   
18:                      if(A[m] >= target || target>= A[l])   
19:                      r = m-1;    
20:                      else   
21:                      l = m+1;   
22:                 }   
23:            }   
24:            return -1;   
25:       }   

Maximal rectangle -- Leetcode

Answer:

int maximalRectangle2(char[][] matrix) {
 2         int m = matrix.length;
 3         int n = m == 0 ? 0 : matrix[0].length;
 4         int height[][] = new int[m][n + 1];
 5         
 9         int maxArea = 0;
10         for(int i = 0; i < m; i++){
11             for(int j = 0; j < n; j++) {
12                 if(matrix[i][j] == '0'){
13                     height[i][j] = 0;
14                 }

                   else {
15                     height[i][j] = i == 0 ? 1 : height[i - 1][j] + 1;
16                 }
17             }

               int area = maxAreaInHist(height[i]);
21             if(area > maxArea){
22                 maxArea = area;
23             }
           }
25         return maxArea;
26      }