czhao86
BAN USER2D segment tree
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
void init(int A[][6],int B[][13],int xbegin,int xend,int ybegin,int yend,int xnode,int ynode)
{
if (xbegin>xend || ybegin>yend) return;
if (xbegin==xend && ybegin==yend) {B[xnode][ynode]=A[xbegin][ybegin];return;}
int xmid=(xbegin+xend)/2;
int ymid=(ybegin+yend)/2;
init(A,B,xbegin,xmid,ybegin,ymid,xnode*2+1,ynode*2+1);
init(A,B,xbegin,xmid,ymid+1,yend,xnode*2+1,ynode*2+2);
init(A,B,xmid+1,xend,ybegin,ymid,xnode*2+2,ynode*2+1);
init(A,B,xmid+1,xend,ymid+1,yend,xnode*2+2,ynode*2+2);
int m1=max(B[xnode*2+1][ynode*2+1],B[xnode*2+1][ynode*2+2]);
int m2=max(B[xnode*2+2][ynode*2+2],B[xnode*2+2][ynode*2+1]);
B[xnode][ynode]=max(m1,m2);
}
int query(int A[][6],int B[][13],int xbegin,int xend,int ybegin,int yend,int qxb,int qxe,int qyb,int qye,int xnode,int ynode)
{
if (qxb<=xbegin && qxe>=xend && qyb<=ybegin && qye>=yend) return B[xnode][ynode];
if (qxb>xend || qxe<xbegin || qyb>yend || qye<ybegin) return -1;
int xmid=(xbegin+xend)/2;
int ymid=(ybegin+yend)/2;
int l1=query(A,B,xbegin,xmid,ybegin,ymid,qxb,qxe,qyb,qye,xnode*2+1,ynode*2+1);
int l2=query(A,B,xbegin,xmid,ymid+1,yend,qxb,qxe,qyb,qye,xnode*2+1,ynode*2+2);
int l3=query(A,B,xmid+1,xend,ybegin,ymid,qxb,qxe,qyb,qye,xnode*2+2,ynode*2+1);
int l4=query(A,B,xmid+1,xend,ymid+1,yend,qxb,qxe,qyb,qye,xnode*2+2,ynode*2+2);
return max(max(l1,l2),max(l3,l4));
}
int main()
{
int A[6][6]={
{1,2,3,4,5,6},
{11,12,13,14,15,16},
{21,22,23,24,25,26},
{31,32,33,34,35,36},
{41,42,43,44,45,46},
{51,52,53,54,55,56}};
int l=2*pow(2,log(6)/log(2))+1;
cout<<l<<endl;
int B[13][13]={0};
init(A,B,0,5,0,5,0,0);
cout<<query(A,B,0,5,0,5,1,3,1,3,0,0)<<endl;
return 0;
}
- czhao86 November 14, 2014#include <iostream>
#include <vector>
#include <sstream>
#include <unordered_map>
#include <string>
#include <tuple>
using namespace std;
bool pointsPossible(vector<string> input)
{
vector<tuple<string,string,int,int> > allinone;
for (int i=0;i<input.size();++i)
{
istringstream ss;
ss.str(input[i]);
string p1,dir,p2;
ss>>p1>>dir>>p2;
string dirstr[8]={"S","W","N","E","SW","NW","SE","NE"};
int x[8]={0,-1,0,1,-1,-1,1,1};
int y[8]={-1,0,1,0,-1,1,-1,1};
int pos;
for (pos=0;pos<8 && dirstr[pos]!=dir;++pos) {}
auto cur=make_tuple(p1,p2,x[pos],y[pos]);
allinone.push_back(cur);
for (int i=0;i<allinone.size();++i)
{
if (get<2>(allinone[i])==get<2>(cur) && get<3>(allinone[i])==get<3>(cur))
{
if (get<1>(allinone[i])==get<0>(cur))
{allinone.push_back(make_tuple(get<0>(allinone[i]),get<1>(cur),get<2>(cur),get<3>(cur)));}
if (get<0>(allinone[i])==get<1>(cur))
{allinone.push_back(make_tuple(get<0>(cur),get<1>(allinone[i]),get<2>(cur),get<3>(cur)));}
}
}
for (int i=0;i<allinone.size();++i)
{
cout<<get<0>(allinone[i])<<" "<<get<1>(allinone[i])<<" "<<get<2>(allinone[i])<<" "<<get<3>(allinone[i])<<" "<<endl;
}
for (int i=0;i<allinone.size();++i)
{
if (get<0>(allinone[i])==get<0>(cur) && get<1>(allinone[i])==get<1>(cur) && (get<2>(allinone[i])!=get<2>(cur) || get<3>(allinone[i])!=get<3>(cur))) return false;
if (get<0>(allinone[i])==get<1>(cur) && get<1>(allinone[i])==get<0>(cur) && (get<2>(allinone[i])!=-get<2>(cur) || get<3>(allinone[i])!=-get<3>(cur))) return false;
}
cout<<endl;
}
return true;
}
int main()
{
string s1="p1 S p2";
string s2="p2 S p3";
string s5="p3 S p1";
string s3="p3 N p4";
string s4="p4 S p2";
vector<string> input;
input.push_back(s1);
input.push_back(s2);
input.push_back(s3);
input.push_back(s4);
input.push_back(s5);
cout<<pointsPossible(input)<<endl;
return 0;
}
- czhao86 November 13, 2014#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <cassert>
using namespace std;
class Solution
{
public:
unordered_map<char,vector<int> > countmap;
string st;
void makeMap(string st)
{
int l=st.length();
for (int i=0;i<l;++i)
{
countmap[st[i]].push_back(i);
}
}
bool repeatOrNot()
{
bool ans;
unordered_map<char,vector<int> >::iterator it,jt;
for (it=countmap.begin();it!=countmap.end();++it)
{
for (jt=countmap.begin();jt!=countmap.end();++jt)
{
ans=true;
cout<<jt->second.size()<<' '<<it->second.size()<<endl;
if (jt->second.size()!=it->second.size()) {ans=false;continue;}
int vil=jt->second.size();
if (vil<2) {ans=false;continue;}
for (int i=1;i<vil;++i)
{
if (((it->second)[i]-(jt->second)[i])*((it->second)[0]-(jt->second)[0])<=0) {ans=false;break;}
}
if (ans==true) return true;
}
}
return false;
}
};
int main()
{
Solution sol;
string st="aabcghxyzb";
sol.makeMap(st);
cout<<sol.repeatOrNot()<<endl;
return 0;
}
- czhao86 October 26, 2014use trie with count
#include <iostream>
#include <string>
using namespace std;
struct node
{
char key;
node *child[26];
int count=0;
};
class trie
{
public:
node *root;
trie()
{
root=new node;
}
void insert(string st)
{
node *cur=root;
for (int i=0;i<st.length();++i)
{
if (!cur->child[st[i]-'a'])
{
node *tmp=new node;
cur->child[st[i]-'a']=tmp;
}
(cur->child[st[i]-'a']->count)++;
cur=cur->child[st[i]-'a'];
}
}
bool search(string st)
{
node *cur=root;
for (int i=0;i<st.length();++i)
{
if (!cur->child[st[i]-'a']) return false;
else cur=cur->child[st[i]-'a'];
}
return true;
}
void print(string prefix, node* &root)
{
int i=0;
while (i<26)
{
if (root->child[i] && root->child[i]->count==1)
{
prefix.push_back(i+'a');
cout<<prefix<<endl;
prefix.pop_back();
}
else if (root->child[i] && root->child[i]->count!=1)
{
prefix.push_back(i+'a');
print(prefix,root->child[i]);
prefix.pop_back();
}
i++;
}
}
};
int main()
{
trie test;
test.insert("zebra");
test.insert("dog");
test.insert("duck");
test.insert("dot");
test.insert("bearc");
test.insert("bear");
test.print("",test.root);
cout<<endl;
cout<<test.root->child[3]->child[14]->child[6]->count<<endl;
return 0;
}
- czhao86 October 25, 2014class Solution
{
public:
vector<string> shortprefix(vector<string> input)
{
sort(input.begin(),input.end());
int l=input.size();
vector<string> ans(l," ");
for (int i=0;i<l;++i)
{
int left=0,right=0;
if (i>0)
{
int l1=min(input[i].length(),input[i-1].length());
while (left<l1 && input[i][left]==input[i-1][left]) left++;
}
if (i<l-1)
{
int l2=min(input[i].length(),input[i+1].length());
while (right<l2 && input[i][right]==input[i+1][right]) right++;
}
int x=max(left,right);
ans[i]=input[i].substr(0,x+1);
if (x==input[i].length()) ans[i]="";
}
return ans;
}
};
class Solution
{
public:
list<list<string> > comb(list<list<string> > &input)
{
list<list<string> > ans,abl;
if (input.empty()) return ans;
list<string> last=input.back();
input.pop_back();
abl=comb(input);
for (list<string>::iterator ls=last.begin();ls!=last.end();++ls)
{
for (list<list<string> >::iterator lls=abl.begin();lls!=abl.end();++lls)
{
list<string> tmp=*lls;
tmp.push_back(*ls);
ans.push_back(tmp);
}
if (abl.empty())
{
list<string> tmp;
tmp.push_back(*ls);
ans.push_back(tmp);
}
}
return ans;
}
};
seems like modified insertion sort.
- czhao86 November 14, 2014