#include<bits/stdc++.h>
#include "iostream"
using namespace std;
class node{
public:
int data;
int l,r;
int count;
node* left,*right;
};
node* newNode(int data,int l,int r){
node* newN = new node;
newN->data = data;
newN->l = l;
newN->r = r;
newN->count = 1;
return newN;
}
int operationOnData(int data1,int data2){
return max(data1,data2);
}
node* buildTree(int arr[],int l,int r)
{
if(l>r) return NULL;
node* nd;
if(l==r)
nd = newNode(arr[l],l,r);
else{
nd = newNode(0,l,r);
int mid = (l+r)/2;
nd->left = buildTree(arr,l,mid);
nd->right = buildTree(arr,mid+1,r);
nd->data = operationOnData(nd->left->data,nd->right->data);
if(nd->left->data==nd->right->data) nd->count = nd->left->count+nd->right->count;
else{
if(nd->left->data > nd->right->data) nd->count = nd->left->count;
else nd->count = nd->right->count;
}
}
return nd;
}
pair<int,int> getMax(node* root,int l, int r){
if(root->l>=l && root->r<=r){
return {root->data,root->count};
}
else
if(root->r<l ||root->l>r)
return {INT_MIN,0} ;
else{
pair<int,int> left = getMax(root->left,l,r);
pair<int,int> right = getMax(root->right,l,r);
if(left.first==right.first){
return {left.first,left.second+right.second};
}
else if(left.first>right.first){
return {left.first,left.second};
}
else
return{right.first,right.second};
}
}
int height(node* root)
{
if(root==NULL) return 0;
int lHeight = height(root->left);
int rHeight = height(root->right);
return lHeight>rHeight?lHeight+1:rHeight+1;
}
void printLevel(node* root,int d)
{
if(root==NULL) return;
if(d==1) cout<<root->data<<" "<<root->count<<" "<<root->l<<" "<<root->r<<endl;
printLevel(root->left,d-1);
printLevel(root->right,d-1);
}
void levelorder(node* root)
{
for(int d =1; d<=height(root) ;d++)
printLevel(root,d);
}
int main()
{
int n,m;
//cin>>n>>m;
n=5;m=1;
int arr[100000] = {3,1,3,2,1};
for(int i=0;i<n;i++);
//cin>>arr[i];
node* root = buildTree(arr,0,n-1);
while(m--){
int l,r;
//cin>>l>>r;
pair<int,int> p = getMax(root,l,r);
cout<<"Max Element is "<<p.first<<" and its Count in given range is ";
cout<<p.second<<endl;
}
}
Sunday 16 August 2015
Segment Tree (Range Maximum Query Along with Count of Maximum Element)
Segment Tree Implementation in C++
1. buildTree function creates the segment tree.
2. getSum() function return the sum.
2. getSum() function return the sum.
#include<bits/stdc++.h>
#include "iostream"
using namespace std;
class node{
public:
int data;
int l,r;
node* left,*right;
};
node* newNode(int data,int l,int r){
node* newN = new node;
newN->data = data;
newN->l = l;
newN->r = r; newN->left = NULL; newN->right = NULL; return newN;
}
int operationOnData(int data1,int data2){
return data1+data2;
}
node* buildTree(int arr[],int l,int r)
{
if(l>r) return NULL;
node* nd;
if(l==r)
nd = newNode(arr[l],l,r);
else{
nd = newNode(0,l,r);
int mid = (l+r)/2;
nd->left = buildTree(arr,l,mid);
nd->right = buildTree(arr,mid+1,r);
nd->data = operationOnData(nd->left->data,nd->right->data);
}
return nd;
}
int getSum(node* root,int l, int r){
if(root->l>=l && root->r<=r){
return root->data;
}
else
if(root->r<l ||root->l>r)
return 0;
else
return getSum(root->right,l,r)+getSum(root->left,l,r);
}
void update(node* root,int arr[],int index,int newValue,int l,int r)
{
if(l>r) return;
if(!root) return;
if(l==r && l == index)
root->data = newValue;
else{
int mid = (l+r)/2;
update(root->left,arr,index,newValue, l,mid);
update(root->right,arr,index,newValue,mid+1,r);
int left =0,right=0;
if(root->left) left = root->left->data;
if(root->right) right = root->right->data;
if(left || right)
root->data = operationOnData(left,right);
}
}
int height(node* root)
{
if(root==NULL) return 0;
int lHeight = height(root->left);
int rHeight = height(root->right);
return lHeight>rHeight?lHeight+1:rHeight+1;
}
void printLevel(node* root,int d)
{
if(root==NULL) return;
if(d==1) cout<<root->data<<" "<<root->l<<" "<<root->r<<endl;
printLevel(root->left,d-1);
printLevel(root->right,d-1);
}
void levelorder(node* root)
{
for(int d =1; d<=height(root) ;d++)
printLevel(root,d);
}
int main()
{
int arr[] = {1, 3, 5, 7, 9,11};
int n=sizeof(arr)/sizeof(int);
node* root = buildTree(arr,0,n-1);
update(root,arr,0,3,0,n-1);
cout<<getSum(root,0,1);
}
Monday 10 August 2015
DP For Beginners
http://www.spoj.com/problems/COINS/
#include<bits/stdc++.h>
#include "iostream"
using namespace std;
map<long long,long long> dp;
long long coins(long long i)
{
if(i>=0 && i<12)
{
if(! dp[i])
dp[i] = i;
return dp[i];
}
else
{
if(! dp[i]){
dp[i] = coins(i/2)+coins(i/4)+coins(i/3);
}
return dp[i];
}
}
int main()
{
long long n;
while(cin>>n){
cout<<coins(n)<<endl;
}
}
Wednesday 5 August 2015
Reverse alternate levels of a perfect binary tree.
Given a Perfect Binary Tree, reverse the alternate level nodes of the binary tree.
Code:
void reverseAlternateLevelOfPrefectBTUtil(node* left,node* right,int level,int d){
if(left==NULL || right==NULL) return;
if(level%2!=0 && level==d){
int a= left->data;
int b= right->data;
swap(&a,&b);
left->data = a;
right->data = b;
}
reverseAlternateLevelOfPrefectBTUtil(left->left,right->right,level+1,d);
reverseAlternateLevelOfPrefectBTUtil(left->right,right->left,level+1,d);
}
void reverseAlternateLevelOfPrefectBT(node* root)
{
for(int i=1; i<=height(root); i+=2)
reverseAlternateLevelOfPrefectBTUtil(root->left,root->right,1,i);
cout<<"Level Order After modification\n";
levelorder(root);
}
Binary Tree Basic Functions
class node
{
public:
int data;
struct node *left,*right,*random;
bool isThreaded ;
};
node* newNode(int data)
{
node* neNode = new node;
neNode->data = data;
neNode->left = NULL;
neNode->right = NULL;
neNode->isThreaded =false;
return neNode;
}
void inorder(node* root)
{
if(!root) return;
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
int height(node* root)
{
if(root==NULL) return 0;
int lHeight = height(root->left);
int rHeight = height(root->right);
return lHeight>rHeight?lHeight+1:rHeight+1;
}
int main()
{
node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
//root->left->left = newNode(1);
//root->left->right = newNode(5);
root->right->left = newNode(4);
root->right->left->left = newNode(6);
root->right->left->left->left = newNode(8);
root->right->left->left->right = newNode(9);
root->right->right = newNode(5);
//root->right->right->left = newNode(9);
root->right->right->right = newNode(7);
root->right->right->right->left = newNode(10);
cout<<closestLeafDistance(root,5);
}
Quick Syntax Reminder Basic Data Structure C++
Maps:
maps<int,int> m;
m[key1] = value1;
m[key2] = value2;
How to iterate
for(map<int,int>::iterator it = m.begin() ; it != m.end(); it++){
cout<<"Key is "<<it->first<<" ";
cout<<"Value is "<<it->second<<endl;
}
List:
maps<int,int> m;
m[key1] = value1;
m[key2] = value2;
How to iterate
for(map<int,int>::iterator it = m.begin() ; it != m.end(); it++){
cout<<"Key is "<<it->first<<" ";
cout<<"Value is "<<it->second<<endl;
}
List:
list<int> *adj = new list<int>[size];
adj[index1].push_back(value);
for(list<int>::iterator i = g->adj[u].begin(); i!=g->adj[u].end(); ++i){
cout<<"->"<<*i;
}
Overload < operator for Sort() Function
class freq
{
public:
int data;
int count;
};
inline bool operator<(const freq& a, const freq& b)
{
return a.count <= b.count;
}
sort(arr,arr+n);
Overload < operator for Sort() Function
class freq
{
public:
int data;
int count;
};
inline bool operator<(const freq& a, const freq& b)
{
return a.count <= b.count;
}
sort(arr,arr+n);
Subscribe to:
Posts (Atom)