luckycat
BAN USERdo not need count array.
int digit(int num, int bit) //bit numbered from 0
{
return num/(pow(10.0,bit))-(int)(num/(pow(10.0,(bit+1))))*10;
}
int biggestnum(int num)
{
int result=digit(num,0);
int countend=num;
int i=0;
while((int)(countend/10)!=0)
{
i++;
int j=0;
int d=digit(num,i);
while(j<i&&d>digit(result,j))
{
j++;
}
result=result%(int)(pow(10.0,j))+(int)(result/(int)pow(10.0,j))*pow(10.0,j+1)+d*(int)pow(10.0,j);
countend/=10;
}
return result;
}
my suggestion is to use dp, and we can do this in O(n*k) time, where k is the target sum numer.
The basic idea is to fill a Boolean dptable of size n*(k+1), and dptable[i][j] means the first i numbers form the set have a subset that sum to j, and the recursive relation is dptable[i][j]=(dptable[i-1][j])|(dptable[i-1][j-data[i]]).
Here is the code, and the output is a little ugly, is there any suggestion to improve the output based on the boolean table?
#include<iostream>
using namespace std;
bool ** dptable;
//n is the size of data, m is the largest number in the set
void find(int * data,int n, int target)
{
if(n<1||target<0)
return;
//initialize
dptable= new bool *[n];
for(int i=0;i<n;i++)
{
dptable[i]=new bool[target +1];
dptable[i][0]=true;
}
for(int i=1;i<target+1;i++)
{
if(data[0]==i)
{
dptable[0][i]=true;
}
else
dptable[0][i]=false;
}
//fill the table row by row
for(int i=1;i<n;i++)
{
for(int j=0;j<target+1;j++)
{
dptable[i][j]=(dptable[i-1][j])|(dptable[i-1][j-data[i]]);
}
}
}
void output(int *data, int m, int target) //m is row num, fisrt call should be n-1
{
if (!dptable[m][target])
{
cout<<"cannot find such a subset"<<endl;
return;
}
if(m==0&&target!=0&&dptable[0][target])
{
cout<< "{"<<target<<"}";
return;
}
if(m==0&&target==0)
{
return;
}
int i=m;
int j=target;
if (dptable[m-1][target]) //supose 0 is not in the set(otherwise, just add it to any satisfied subset)
{
output(data, i-1,j);
}
if(target>=data[i]&&dptable[m-1][target-data[i]])
{
cout<<"{"<<data[i];
output(data, i-1,target-data[i]);
cout<<"}";
}
}
void main()
{
int data[]={1,2,3,4,5,6};
int n=6;
find(data,n, 10);
output(data, n-1,10);
}
what i think is 1)computer all points' distance to the given point, and put them in an array
2) find the kth element in the array in O(n) time on average, by choosing a pivot from the array and then put all smaller elements in front of the pivot and all larger ones after it, just as quicksort. if # of smaller/equal elements <k, we find the element with rank=( k - # of smaller /equal elements) in the array after the pivot, and discard the other half. Do this recursively.
#include<iostream>
#include<math.h>
using namespace std;
struct point{
int x;
int y;
};
int * computedistance(point * set, int n)
{
int *a =new int[n];
for(int i=0;i<n;i++)
{
a[i]=(int)pow((double)set[i].x,2)+(int)pow((double)set[i].y,2);
}
return a;
}
void swap(int *a, int i, int j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
int findkth(int * a, int size, int k)
{
if(size==1)
{
return a[0];
}
int pivot=a[size/2];
swap(a,0,size/2);
int left=1;
int right=size-1;
while(left<right)
{
while(a[left]<=pivot&&left<right)
left++;
while(a[right]>=pivot&&left<right)
right--;
swap(a,left,right);
}
int bound;
if(a[left]<=pivot)
{
bound=left;
}
else
{
bound=left-1;
}
swap(a,0,bound);
if(bound==k)
return a[bound];
else if(bound>k)
findkth(a,bound,k);
else
findkth(a+bound+1,size-bound-1,k-(bound+1));
}
void main()
{
point p;
p.x=1;
p.y=2;
int x[]={7,2,4,5,6,4,7};
int y[]={2,3,4,5,6,7,9};
int n=sizeof(x)/sizeof(int);
point * set=new point[n];
for(int i=0;i<n;i++)
{
set[i].x=x[i]-p.x;
set[i].y=y[i]-p.y;
}
int k=1;
int *a=computedistance(set, n);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
int r=findkth(a, n, k-1);
double result=sqrt((double) r);
cout<<result<<endl;
}
#include<iostream>
#include<string>
void reverse(char *a, int i, int j)
{
if(i>j)
{
int temp=i;
i=j;
j=temp;
}
char temp;
while(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
i++;
j--;
}
}
void reversesentence(char * a, int length) //assumption
{
int i=0;
int j=0;
while(j<length-1)
{
while(a[j]==' '&&j<length-1)
{
j++;
i=j;
}
while(a[j]!=' '&&j<length-1)
{
j++;
}
if(a[j]==' ')
{
j--;
}
reverse(a,i,j);//first blank
j++;
i=j;
}
reverse(a,0,length-1);
}
void main()
{
char a[]=" i am lucky ";
reversesentence(a,strlen(a));
puts(a);
}
bfs
- luckycat March 05, 2012struct tnode{
char value;
int flag; //0 means untouched; 1 means in queue; 2 means processed
tnode ** childrenarray;
int degree;
tnode * brother; //the special pointer
int level;
};
void bfs(tnode * r) // assume all 0 nodes
{
queue<tnode *> q;
r->flag=-1;
q.push(r);
tnode * curr;
while(!q.empty())
{
curr=q.front();
q.pop();
tnode * child;
for(int i=0;i<curr->degree;i++)
{
child=curr->childrenarray[i];
if(child!=NULL&&child->flag==0)
{
child->flag=1;
child->level=curr->level+1;
q.push(child);
}
}
if(!q.empty()&&curr->level==q.front()->level)
curr->brother=q.front();
curr->flag=2;
}
}