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      }

Largest rectangle area in histogram -- Leetcode

Answer:

 1 public int largestRectangleArea2(int[] height) {
 2         Stack<Integer> stack = new Stack<Integer>();
 3         int i = 0;
 4         int maxArea = 0;
 5         int[] h = new int[height.length + 1];
 6         h = Arrays.copyOf(height, height.length + 1);
 7         while(i < h.length){
 8             if(stack.isEmpty() || h[stack.peek()] <= h[i]){
 9                 stack.push(i++);
10             }else {
11                 int t = stack.pop();
12                 maxArea = Math.max(maxArea, h[t] * (stack.isEmpty() ? i : i - stack.peek() - 1));
13             }
14         }
15         return maxArea;
16     }

Decode ways -- Leetcode

Question:

Answer:
DP method.
Transformation function :
Count[i] = Count[i-1],  if S[i-1] is a valid char

or           = Count[i-1]+ Count[i-2],  if S[i-1] and S[i-2] together is still a valid char.

#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<iostream>
#include<string>

using namespace std;

int check(char one){
    return (one != '0') ? 1 : 0;    
}

int check2(char one, char two){
      return (one == '1' || (one == '2' && two <= '6')) ? 1 : 0;    
}

int numDecode(string s){
int len = s.length();
if(s.empty()) return 0;
vector<int> f(len,0);
   
//Edge cases.
f[0] = check(s[0]);      
if(f[0] == 0) return 0;
if(check(s[1]) && check(s[0]) && check2(s[0],s[1])){
f[1] = 1+ f[0];
}
else if(check(s[1])){
f[1] = f[0];
}
if(len == 1) return f[0];
if(len == 2) return f[1];

int i= 2;
while(i<len){       //len >= 3.Recursion cases.
if(check(s[i]) && check(s[i-1]) && check2(s[i],s[i-1])){
f[i] = f[i-1] + f[i-2];
}
else if(check(s[i])){
f[i] = f[i-1];
}
else{           //!check(s[i])
return 0;
}
++i;
}
return f[len-1];
}

/*****Similar, but Better, O(1) space *******/
/*
int numDecode(string s){
int len = s.length();
if(s.empty()) return 0;    
if(!check(s[0])) return 0;
int fn=0, fn_1=0, fn_2=1;
   
//Edge cases.
if(check(s[1]) && check(s[0]) && check2(s[0],s[1])){
fn_1 = 1 + fn_2;
}
else if(check(s[1])){
fn_1 = fn_2;
}
if(len == 1) return fn_2;
if(len == 2) return fn_1;

int i= 2;
while(i<len){                            //len >= 3.Recursion cases.
if(check(s[i]) && check(s[i-1]) && check2(s[i],s[i-1])){
fn = fn_1 + fn_2;
}
else if(check(s[i])){
fn = fn_1;
}
else{                    //!check(s[i])
return 0;
}
fn_2 = fn_1;
fn_1 = fn;
++i;
}
return fn_1;
}
*/

int main(){
int res = numDecode("1212");
cout << res;
getchar();
return 0;
}