一二题：Rectangle Overlap, K Closest Points, Window Sum, Longest Palindrome
Rectangle Overlap：
class Node{ double x, y; };
bool checkRecOve(Node topLeftA, Node topLeftB, Node bottomRightA, Node bottomRightB){
if( topLeftA.x <= bottomRightB.x || topLeftB.x <= bottomRightA.x) return true;
if( topLeftA.y <=bottomRightB.y || topLeftB.y <= bottomRightA.y ) return true;
return false;
}
K Closest Points:
// find the k closest points from (0,0)
struct cmp{ bool operator()(Point& x, Point& y){ return x.a*x.a+x.b*x.b<y.a*y.a+y.b*y.b; } };
vectorkcp2(std::vector& input, int k){
int size=input.size();
if(k>=size) return input;
priority_queue<Point, vector<Point>, cmp> q;
for(int i=0;i<size;i++){
q.push(input[i]);
if(q.size()>k) q.pop();
}
vector<Point> res(k,Point(0,0));
for(int i=k-1;i>=0;i--){
res[i]=q.top();
q.pop();
}
return res;
Window Sum:
vector<int> windowsum(vector<int>& input, int k){
vector<int> res; // if size<1 || size<k return res;
int size=input.size(), sum=0;
for(int i=0;i<k;i++) sum+=input[i];
res.push_back(sum);
for(int i=k;i<size;i++){
sum=sum+v[i]-v[i-k];
res.push_back(sum);
}
return res;
}
Longest Palindrome:
string LP(string& s){
int size=s.size(), nsize=2*size+3, dp[nsize], C=0, R=0; // if size<2 return s;
string test="^$";
for(int i=0;i<size;i++) test+=s[i], test+='#';
test+='$';
memset(dp, 0, nsize);
for(int i=1;i<nsize-1;i++){
if(R>i) dp[i]=min(dp[2*C-i], R-i);
while(test[i+dp[i]+1]==test[i-dp[i]-1]) dp[i]++;
if(i+dp[i]>R) R=i+dp[i], C=i;
}
for(int i=1;i<nsize-1;i++) if(R<dp[i]) R=dp[i], C=i;
return s.substr((C-1-R)/2, R);
}
第三题：Copy List with Random Pointer, Order Dependency, Minimum Spanning Tree, Five Scores, Maximum Subtree
Copy List with Random Pointer：
RandomListNode *copyRandomList(RandomListNode *head) {
RandomListNode *temp, *cur=head, *res;
while(cur){
temp=new RandomListNode(cur->label);
temp->next=cur->next;
cur->next=temp;
cur=temp->next;
}
cur=head;
while(cur){
if(cur->random) cur->next->random=cur->random->next;cur=cur->next->next;
}
cur=head;
temp=res=head?head->next:head;
while(cur){
cur->next=temp->next;
cur=cur->next;
if（cur）temp->next=cur->next;
temp=temp->next;
}
return res;
}
Order Dependency：
vector<Order> getOrder(vector<OrderDep>& input){
map<string, int> indegree;
map<string, vector<string> > leadto;
int size=input.size();
for(int i=0;i<size;i++){
leadto[input[i].pre.name].push_back(input[i].cur.name);
indegree[input[i].cur.name]++; indegree[input[i].pre.name]+=0;
}
queue<string> q;
map<string, int>::const_iterator ptr=indegree.begin();
while(ptr!=indegree.end()){
if(ptr->second==0) q.push(ptr->first);
ptr++;
}
vector<Order> res;
while(q.size()){
string temp=q.front(); q.pop();
res.push_back(Order(temp));
for(int i=0;i<leadto[temp].size();i++) if(--indegree[leadto[temp][i]==0） q.push(leadto[temp][i]);
}
if(res.size() == indegree.size()) return res;
vector<Order> emp; return emp;
Minimum Spanning Tree：
struct cmp{ bool operator()(const Conn& a, const Conn& b){ return a.cost<b.cost; } };
struct cmp2{ bool operator()(const Conn& a, const Conn& b){ if(a.node1!=b.node1) return a.node1<b.node1; return a.node2<b.node2; } };
vector<Conn> findMST(vector<Conn>& v){
vector<Conn> res; //if v empty return res;
sort(v.begin(), v.end(), cmp() ); // sort by cost;
map<string, int> group; // group nume
int size=v.size(), groupnum=0;
for(int i=0;i<size;i++){
if( !group.count(v[i].node1) && !group.count(v[i].node2 ){ group[v[i].node1]=group[v[i].node2]=++groupnum; res.push_back(v[i]); } // two new node
else if( ! && ) {group[v[i].node1] = group[v[i].node2]; res.push_back(v[i]); } // one new node
else if( && !) {group[v[i].node2] = group[v[i].node1]; res.push_back(v[i]); } // one new node
else {
int u1=group[v[i].node1], u2=group[v[i].node2];
if(u1!=u2) change all node in group u2 to u1, if u2>u1. Otherwise change u1 to u2;
}
check if there are more than one group. If so, return empty vector, otherwise return res;
}
Five Scores：
map<int, double> getHF(vector<Result>& input){
map<int, double> res;
map<int, priority_queue<int> > record;
for( int i=0;i<input.size(); i++) record[input[i].id].push(input[i].value);
map<int, priority_queue<int> >::iterator ptr=record.begin();
while(ptr!=record.end()){
double sum=0;
for(int i=0;i<5;i++) sum+=ptr->second.top(), ptr->second.pop();
res[ptr->first]=sum/5;
ptr++;
}
return res;
}
Maximum Subtree：
Node* cTree(Node* root){
if(root==NULL) return root;
Node* res=NULL; double maxv=-1;
find(root, res, maxv);
return res;
} // subsum, subcnt
pair<int,int> find(Node* root, Node* &res, double& maxv){
if(root->children.empty()) return pair<int,int>(root->val, 1);
int curSum=root->val, curCnt=1;
for(int i=0;i<root->children.size();i++){
pair<int,int> temp=find(root->children[i], res, maxv);
curSum+=temp.first; curCnt+=temp.second;
}
double curv=(double)curSum/curCnt;
if(curv>maxv) maxv=curv. res=root;
return pair<int,int>(curSum, curCnt);
}
