ChenH1989
BAN USERHere is an other solution with LINK LIST
we maintain a list indicates the vacant space stack, whose top node is "cur"
For
(1) Push, we simply add node(cur) to the stack respectively,and pop node(cur) from the vacant stack.
(2) Pop, we add node( Stack_now.top ) to the top of the vacant space stack.
#include <iostream>
#include <cmath>
#include <cstdio>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <cstring>
#include <sstream>
using namespace std;
#define mp make_pair
#define pb push_back
typedef double db;
typedef long long LL ;
const int MAXN = 5;
int cur;
int arr[ MAXN ];
int pre[ MAXN ];
struct Stack{
int top ;
bool push( int x) {
if(cur == - 1) return false ; //overflows
int p=pre[cur];
pre[ cur ] = top ;
arr[ cur ] = x;
top = cur;cur=p;
return true;
}
void init(){
top = - 1;
}
bool pop(){
if(top == -1) return false;
int p=pre[top];
pre[top]=cur;
cur=top;top=p;
return true ;
}
}S[3];
int main(){
for(int i = 1; i < MAXN; ++ i) pre[i]=i-1; pre[0]=-1;
cur = MAXN - 1;
for(int i = 0; i < 3; ++ i) S[i].init();
S[0].push( 5 );
S[0].push( 4 );
S[1].push( 3 );
S[2].push( 2 );
S[0].push( 1 ); // {5, 4, 3, 2, 1}
cout << S[0].push( 7 ) << endl; // FULL
S[2].pop(); // {5, 4, 3, x, 1}
cout << S[0].push( 7 ) << endl; //{5,4,3,7,1}
for(int i=0;i<MAXN;++i) cout << arr[i] <<' '; cout << endl;
S[1].pop();//{5,4,x,7,1}
cout << S[2].push(6) << endl;//{5,4,6,7,1}
for(int i=0;i<MAXN;++i) cout << arr[i] <<' '; cout << endl;
cin >> cur ;
return 0;
}
I think we can maintain a DOUBLE LINKED LIST
I use nxt[x] to indicates the next node of node x ( if next node is empty, then nxt[x] = -1)
I use pre[x] to indicates the previous node in the Stacks.
In the following code, "cur" is the HeadPoint of the vacant list, and "las" is the last node of the vacant list.
For
(1) push, we simply check whether cur is valid.
(2) pop, we may add one node to the vacant list, we have to note that in this time, the list may be empty.
#include <iostream>
#include <cmath>
#include <cstdio>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <cstring>
#include <sstream>
using namespace std;
#define mp make_pair
#define pb push_back
typedef double db;
typedef long long LL ;
const int MAXN = 5;
int cur, las;
int arr[ MAXN ];
int pre[ MAXN ];
int nxt[ MAXN ];
struct Stack{
int top ;
bool push( int x) {
if(cur == - 1) return false ; //overflows
arr[ cur ] = x;
pre[ cur ] = top ;
top = cur; cur = nxt[ cur ];
return true;
}
void init(){
top = - 1;
}
bool pop(){
if(top == -1) return false;
if(cur == -1) cur = las = top; //the vacant list is empty
else nxt[ las ] = top,las = top;// otherwise
nxt[top]=-1;
top = pre[ top ];
return true ;
}
}S[3];
int main(){
for(int i=0;i<MAXN-1;++i) nxt[i]=i+1; nxt[MAXN-1]=-1;
cur = 0; las = MAXN - 1;
for(int i = 0; i < 3; ++ i) S[i].init();
S[0].push( 5 );
S[0].push( 4 );
S[1].push( 3 );
S[2].push( 2 );
S[0].push( 1 ); // {5, 4, 3, 2, 1}
cout << S[0].push( 7 ) << endl; // FULL
S[2].pop(); // {5, 4, 3, x, 1}
cout << S[0].push( 7 ) << endl; //{5,4,3,7,1}
for(int i=0;i<MAXN;++i) cout << arr[i] <<' '; cout << endl;
S[1].pop();//{5,4,x,7,1}
cout << S[2].push(6) << endl;//{5,4,6,7,1}
for(int i=0;i<MAXN;++i) cout << arr[i] <<' '; cout << endl;
cin >> cur ;
return 0;
}
However, here is one other non-recursion algorithm.
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<set>
using namespace std ;
const int MAXN = 1111 ;
char s[ MAXN ];
int n ;
bool next_permutation( char s[], int l, int r ) {
for(int i = r-1; i >= l+1; -- i) {
if(s[i] > s[i-1]) {
for(int j = r-1; j >=i; -- j) if( s[j] > s[i-1] ) {
swap( s[i-1], s[j]);
break;
}
reverse(s+i,s+r); //O(n)
return true ;
}
}
return false;
}
int main(){
while( cin >> s){
n=strlen(s);
sort(s,s+n);
do{
puts(s);
}while(next_permutation(s,0,n));
}
return 0;
}
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<set>
using namespace std ;
const int MAXN = 1111 ;
map< char ,int > m;
int n ;
char s[ MAXN ],t[ MAXN ];
vector< pair<char, int > > v ;
void pe(int dep) {
if(dep != n){
for(int p=0; p != v.size(); ++ p) if( v[p].second> 0){
-- v[p].second;
t[ dep ] = v[p].first ;
pe(dep + 1);
++ v[p].second;
}
}else{
cout << t << endl ;
}
}
int main(){
while( cin >> s){
m.clear(); v.clear();
n=strlen(s); t[n]=0;
for(int i = 0; s[i]; ++ i) m[ s[i] ] ++ ;
for( map< char, int >::iterator p = m.begin(); p != m.end(); ++ p)
v.push_back( make_pair(p->first, p->second));
sort(v.begin(), v.end());
pe(0);
}
return 0;
}
In my stament, A[], B[] is the given two sorted arrays, and |A|=n,|B|=m
1) two pointers Algorithm must works (such as one sub-program in MERGE_SORT)
however, you may have to scan all the element in worst case (k=n+m). And the time complexity is O(n+m)
2) we could find that the result element will either in A[] or in B[] (or both cause the duplicates)
Now suppose the result element is in A[], we can binary search it.
for one element you are searching now (suppose it's X), we can calculate how many element in total is less or equal to X. (do another binary search in B[])
Then we can get the result if it's indeed in the A[].
For the result in B[], we could process in the same way.
so the Time Complexity is O( log(n)*log(m) )
Easy to find one Omega(nlogn) solution. n = |s|
(1) s = s + s, for example, s="abc", then s = "abc"+"abc"="abcabc"
(2) for any integer i, t[i]=s[i,i+1...i+n-1]
(3) we want to find such i that t[i] is lexicographic mininum.
now we can not store all t[i] (the space may be O(n^2))
so we want to write one function cmp(i,j)
to compare t[i] and t[j], but how?
First of all, we calculate the Hash array. O(2n)=O(n)
Hash[i]=s[0]*p^(i)+s[1]*p^(i-1)+...+s[i-1]*p^1+s[i]
If we want to get the Hash value of the substring s[x..y], we can simply have:
Hash(x..y) = Hash[y]-Hash[x-1]*pow(p,y-x+1) O(1) // we can calculate pow(p,*) at first in O(2n)=O(n) time
Then for 2 given integer i and j, we wanna compare t[i] and t[j]
(1) we find LCP(t[i],t[j]). Binary search with Hash O(logn)
(2) compare the (LCP(t[i],t[j])+1) -th value;
for example:
t[i]="abcd"
t[j]="abef"
LCP(t[i],t[j])=2
so we compare t[i][3] = 'c' and t[j][3] = 'e'
then we get the result.
Now we can compare t[i], t[j] in O(logn) time
Then we use one random algorithm to find the k-th "i". O(n * logn) (The algorithm is something like the quick-sort)
// implement 1
unsigned Add(unsigned a, unsigned b) {
if(!a)return b;
if(!b)return a;
return Add(a^b,(a&b)<<1);
}
//implement 2
unsigned Add(unsigned a, unsigned b, unsigned carry) {
if(!(a|b))return carry; //both a and b is zero.
if(!((a|b)&1)) return Add(a>>1,b>>1,0)<<1|carry; // the lowest bit of a and b is 0
if(!(a&b&1)) return Add(a>>1,b>>1,carry)<<1|(!carry); //the lowest bit of a and b must be 1 one and 1 zero
return Add(a>>1,b>>1,1)<<1|carry;// both 1
}
consider the column and row separately.(say,one n by m matrix, all index starts from 0. )
Any element with row # i , will be placed in the i-th column in the result matrix.
Any element with column #i, will be placed in the i-th row
So the problem is solved:
new_i, new_j = j,i
tips: the result matrix is m by n
Good problem.
we consider the bit separately
v0 is the set whose occurrence time mod 3 = 0
v1 is the set whose occurrence time mod 3 = 1
v2 is the set whose occurrence time mod 3 = 2
we know that each bit must exactly in one state {mod3 = 0, or mod 3 = 1. or mod 3 = 2)
so for a new number, the only thing may happen is that some bit is in vi goto v( (i+1)%3) if both vi and x contains that bit.
- ChenH1989 January 01, 2013