jigili
BAN USEReasiet solution ever, wonder why people have written lines of code for this question:
int findMaxDiff(vector<int>& array) {
int sum=0;
for(int i=0; i<array.size(); ++i) {
sum+=array[i];
}
int sum1=0;
int max_diff=INT_MIN;
for(int i=0; i<array.size(); ++i) {
sum1+=array[i];
int diff=fabs((sum-sum1)-sum1);
if(diff>max_diff) max_diff=diff;
}
return max_diff;
}
The easiest solution posted ever, I wonder why people solve it so hard, just compute the sum of all elements, go through the array, compute the sum of first part=>second part, and compare :
int findMaxDiff(vector<int>& array) {
int sum=0;
for(int i=0; i<array.size(); ++i) {
sum+=array[i];
}
int sum1=0;
int max_diff=INT_MIN;
for(int i=0; i<array.size(); ++i) {
sum1+=array[i];
int diff=fabs((sum-sum1)-sum1);
if(diff>max_diff) max_diff=diff;
}
return max_diff;
}
cleanest solution ever:
struct cell{
int val;
int ind1;
int ind2;
cell(int val, int ind1=0, int ind2=0):val(val),ind1(ind1),ind2(ind2){}
bool operator<(const cell& before) const {
return this->val > before.val;
}
};
int getMin(vector<int>& r) {
int minV=INT_MAX;
for(int i=0; i<r.size(); ++i)
minV=min(minV, r[i]);
return minV;
}
int getMax(vector<int>& r) {
int maxV=INT_MIN;
for(int i=0; i<r.size(); ++i)
maxV=max(maxV, r[i]);
return maxV;
}
void findMinRange(vector<vector<int>>& range, vector<int>& min_range) {
priority_queue<cell> q;
for(int i=0; i<range.size(); ++i) {
q.push(cell(range[i][0], i, 0));
min_range.push_back(range[i][0]);
}
int min_diff=getMax(min_range)-getMin(min_range);
vector<int> r=min_range;
while(true) {
cell c=q.top();
q.pop();
if(range[c.ind1].size()-1 == c.ind2) break;
q.push(cell(range[c.ind1][c.ind2+1], c.ind1, c.ind2+1));
r[c.ind1]=range[c.ind1][c.ind2+1];
int diff=getMax(r)-getMin(r);
if(diff < min_diff){
min_range=r;
min_diff=diff;
}
}
}
The cleanest solution posted ever :
struct cell{
int val;
int ind1;
int ind2;
cell(int val, int ind1=0, int ind2=0):val(val),ind1(ind1),ind2(ind2){}
bool operator<(const cell& before) const {
return this->val > before.val;
}
};
int getMin(vector<int>& r) {
int minV=INT_MAX;
for(int i=0; i<r.size(); ++i) minV=min(minV, r[i]);
return minV;
}
int getMax(vector<int>& r) {
int maxV=INT_MIN;
for(int i=0; i<r.size(); ++i) maxV=max(maxV, r[i]);
return maxV;
}
void findMinRange(vector<vector<int>>& range, vector<int>& min_range) {
priority_queue<cell> q;
for(int i=0; i<range.size(); ++i) {
q.push(cell(range[i][0], i, 0));
min_range.push_back(range[i][0]);
}
int min_diff=getMax(min_range)-getMin(min_range);
vector<int> r=min_range;
while(true) {
cell c=q.top();
q.pop();
if(range[c.ind1].size()-1 == c.ind2) break;
q.push(cell(range[c.ind1][c.ind2+1], c.ind1, c.ind2+1));
r[c.ind1]=range[c.ind1][c.ind2+1];
int diff=getMax(r)-getMin(r);
if(diff < min_diff){
min_range=r;
min_diff=diff;
}
}
}
shared my super clean C++ code:
void func(vector<vector<string>>& dict, vector<string>& row,
vector<vector<string>>& matrix, string result, int ind){
if(ind == dict.size()) {
row.push_back(result);
return;
}
for(int i=0; i<dict[ind].size(); ++i) {
func(dict,row,matrix, result+dict[ind][i], ind+1);
if(ind == 0){
matrix.push_back(row);
row.clear();
result="";
}
}
}
vector<vector<string>> func(vector<vector<string>>& dic) {
vector<string> row;
vector<vector<string>> matrix;
func(dic, row, matrix, "",0);
return matrix;
}
O(n) time O(1) space, I think this question is so simple, just go forward and keep track of max seen element
int findMostRepeatedNumber(vector<int>& array) {
int max_count=1;
int max_value=array[0];
int count=1;
int pre=array[0];
for(int i=1; i<array.size(); ++i) {
if(array[i]==pre) {
count++;
}else{
count=1;
pre=array[i];
}
if(count>max_count){
max_count=count;
max_value=pre;
}
}
return max_value;
}
Imagine that your state is something like this:
state(current element of the set, set A, set B)
In each step you have 2 possible scenarios:
1) Add the value to the set A
2) Add the value to the set B
void findTwoSubset(const vector<int>&array,vector<int>&s1, vector<int>& s2,
vector<int>& solution_s1, vector<int>& solution_s2,
int start, int sum1, int sum2, int& diff) {
int N=array.size();
if(start==N) {
bool condition=false;
if(N%2==0) {
if(s1.size()==N/2 && s2.size()==s1.size())
condition=true;
}else{
if(s1.size()==N/2 && s2.size()==N/2+1)
condition=true;
}
if(condition) {
int d=fabs(sum1-sum2);
if(d<diff) {
diff=d;
solution_s1=s1;
solution_s2=s2;
}
}
}
for(int i=start; i<N; ++i) {
if(s1.size()<(N/2)) {
s1.push_back(array[i]);
findTwoSubset(array,s1, s2,solution_s1, solution_s2,i+1, sum1+array[i], sum2, diff);
s1.pop_back();
}
if((s2.size()<=N/2 && N%2==1) || (s2.size()<N/2 && N%2==0)) { //odd length array
s2.push_back(array[i]);
findTwoSubset(array,s1, s2, solution_s1, solution_s2, i+1, sum1, sum2+array[i], diff);
s2.pop_back();
}
}
}
void findTwoSubset(const vector<int>&array,vector<int>& solution_s1, vector<int>& solution_s2) {
vector<int> s1, s2;
int diff=INT_MAX;
findTwoSubset(array, s1, s2, solution_s1, solution_s2, 0, 0,0, diff);
}
int main() {
vector<int> array={1,2,3,6,7,8,9};
vector<int> s1;
vector<int> s2;
findTwoSubset(array, s1, s2);
for(int i=0; i<s1.size(); ++i)
cout<<s1[i] << " ";
cout << endl;
for(int i=0; i<s2.size(); ++i)
cout<<s2[i] << " ";
cout << endl;
return 0;
}
I updated my code with finding the second subset also:
void findTwoSubset(const vector<int>&array,vector<int>&s,
vector<int>& solution, int start, int sum,
int total, int &diff) {
if(s.size()==array.size()/2) {
int sum1=sum;
int sum2=total-sum;
int d=fabs(sum1-sum2);
if(d<diff) {
solution=s;
diff=d;
}
return;
}
for(int i=start; i<array.size(); ++i) {
s.push_back(i);
findTwoSubset(array, s, solution, i+1, sum+array[i],total,diff);
s.pop_back();
}
}
void findTwoSubset(const vector<int>& array, vector<int> &s1, vector<int>& s2) {
int total=0;
for(int i=0; i<array.size(); ++i)
total+=array[i];
vector<int> solution;
int diff=INT_MAX;
findTwoSubset(array, s1, solution, 0, 0, total, diff);
s1=solution;
// finding the second subset elements as first subset elements are sorted in indices it is easy
int i=0;
int j=0;
while(i<s1.size()) {
if(j<s1[i]) { //before this index, push it to the result
s2.push_back(j);
j++;
}else if(s1[i]==j) {
i++;
j++;
}
}
// add everything after the last element
int end=s1[s1.size()-1];
for(int i=end+1; i<array.size(); ++i) {
s2.push_back(i);
}
}
int main() {
vector<int> array={1,2,3,6,7,8,9};
vector<int> s1;
vector<int> s2;
findTwoSubset(array, s1, s2);
for(int i=0; i<s1.size(); ++i)
cout<<array[s1[i]] << " ";
cout << endl;
for(int i=0; i<s2.size(); ++i)
cout<<array[s2[i]] << " ";
cout << endl;
return 0;
}
I just go through the array and test all subsets of length n/2, which have the minimum difference, this solution gives one of the sets indices, and once having one of the sets, as I found indices in a sorted order, I can easily find the second subset indices:
void findTwoSubset(const vector<int>&array,vector<int>&s,
vector<int>& solution, int start, int sum,
int total, int &diff) {
if(s.size()==array.size()/2) {
int sum1=sum;
int sum2=total-sum;
int d=fabs(sum1-sum2);
if(d<diff) {
solution=s;
diff=d;
}
return;
}
for(int i=start; i<array.size(); ++i) {
s.push_back(i);
findTwoSubset(array, s, solution, i+1, sum+array[i],total,diff);
s.pop_back();
}
}
void findTwoSubset(const vector<int>& array, vector<int> &s1, vector<int>& s2) {
int total=0;
for(int i=0; i<array.size(); ++i)
total+=array[i];
vector<int> solution;
int diff=INT_MAX;
findTwoSubset(array, s1, solution, 0, 0, total, diff);
s1=solution;
// finding the second subset elements as first subset elements are sorted in indices it is easy
int i=0;
int j=0;
while(i<s1.size()) {
if(j<s1[i]) { //before this index, push it to the result
s2.push_back(j);
j++;
}else if(s1[i]==j) {
i++;
j++;
}
}
// add everything after the last element
int end=s1[s1.size()-1];
for(int i=end+1; i<array.size(); ++i) {
s2.push_back(i);
}
}
int main() {
vector<int> array={1,2,3,6,7,8,9};
vector<int> s1;
vector<int> s2;
findTwoSubset(array, s1, s2);
for(int i=0; i<s1.size(); ++i)
cout<<array[s1[i]] << " ";
cout << endl;
for(int i=0; i<s2.size(); ++i)
cout<<array[s2[i]] << " ";
cout << endl;
return 0;
}
bool comperator(const pair<int,int>& A, const pair<int,int>& B) {
if(A.first < B.first) return true;
if(A.first==B.first)
return A.second>B.second;
return false;
}
int findMaximumIntersection(vector<pair<int,int>>& pairs) {
sort(pairs.begin(), pairs.end(), comperator);
int max_intersection=0;
for(int i=0; i<pairs.size(); ++i) {
int lo=0, hi=pairs.size()-1;
while(lo<hi) {
int mid=lo+(hi-lo)/2;
if(pairs[i].second < pairs[mid].first){
hi=mid;
}else{
lo=mid+1;
}
}
int intersection=(lo-i);
max_intersection=max(max_intersection, intersection);
}
return max_intersection;
}
This is correct O(1) answer, flatten the tree in single linked list, then reverse back and put the left links in their place.
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode* root_c=root;
TreeNode* r_left;
while(root!=NULL){
r_left=root->left; //rightmost left
if(r_left!=NULL) {
// find the rightmost node in the left child
while(r_left->right!=NULL) r_left=r_left->right;
r_left->right=root->right;
root->right=root->left;
root->left=NULL;
}
root=root->right;
}
// now make the left links
root=root_c;
TreeNode* pre;
while(root->right != NULL) {
pre=root;
root=root->right;
root->left=pre;
}
}
};
what is question asking ?
- jigili September 18, 2015