一二題：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);
}
