Link: Login - professional IT written examination interview preparation platform_ Niuke network
Source: niuke.com
 

Middle order sequence

Given the preorder traversal and postorder traversal sequences of a binary tree with n nodes, find the middle order traversal sequence.
If a node has only one child node, it will be regarded as the left child node here

The left son node can be used as the dividing point between the left subtree and the right subtree in the post order traversal sequence, and the rest can be traversed normally.

class Solution {
public:
    vector<int> v;
    void deal(int pl,int pr,int sl,int sr, vector<int>& pre, vector<int>& suf) {
        if(pl==pr) {v.push_back(pre[pl]); return ;}
        int pos=-1;
        int x=pre[pl+1];
        for(int i=sl;i<=sr;++i)
        {
            if(suf[i]==x) pos=i;
        }
        deal(pl+1,pl+1+pos-sl,sl,pos,pre,suf);
        v.push_back(pre[pl]);
        if(pos+1<=sr-1) deal(pl+1+pos-sl+1,pr,pos+1,sr-1,pre,suf);
    }
    vector<int> solve(int n, vector<int>& pre, vector<int>& suf) {
        // write code here
        deal(0,n-1,0,n-1,pre,suf);
        return v;
    }
};

Link: Login - professional IT written test, interview preparation platform_ Niuke network
Source: niuke.com
 

Raid

The system is charged by N nuclear power stations, and any failure will make the system invalid. The general soon began to raid the station by N agents who parachuted to the stronghold. Unfortunately, due to the attack of the imperial air force, they failed to land in the expected position. As an experienced general, the first thing Arthur wants to know is which agent is closest to any power station. Can you help the general calculate the shortest distance between the agent and the station?

The bool type is used to distinguish the information of an agent from that of a nuclear power plant. First, all points are sorted according to the x coordinate, and then the x coordinate of the middle point of the point is used as the dividing line. Taking this as the benchmark, find the minimum value of the dividing point in the two intervals, that is, the interval boundary.

If a point falls within this interval in the current search interval, record the sequence number of this point into the array, sort the sequence number in the array from small to large according to the y coordinate of the point, and judge whether it is within the long range of the interval by calculating the difference between the y coordinates of two points, that is, it can be used as the standard of whether it is a point in the interval, And if there are no duplicate points, there are at most 8 points including yourself(

1        2/3       8  

4 ， 5 / 6 ， 7 if there are other points, it will contradict the minimum distance obtained before).

Among them, the most time-consuming is the sorting operation, which sorts O(nlogn) once, and the half division makes the sorting times logn, so the total time complexity is O(nlogn). Then, find the minimum value in the middle interval.

As for the critical case, it is divided into two points and three points. Because there can't be only one point.

#include<bits/stdc++.h>
using namespace std;
int t,n;
const int maxn=200100;
const long long INF=1e10;
int help[maxn];
struct point{
    int x,y;
    bool type;
}p[maxn];
bool cmpx(point a,point b){
    return a.x<b.x;
}
bool cmpy(int a,int b){
    return p[a].y<p[b].y;
}
double dist(int l,int r){
    if(p[l].type==p[r].type) return INF;
    double dx=p[l].x-p[r].x,dy=p[l].y-p[r].y;
    return sqrt(dx*dx+dy*dy);
}
double near_dist(int l,int r){
    if(l>=r) return INF;
    if(r==l+1) return dist(l,r); 
    if(r==l+2) return min(dist(l,r),min(dist(l,l+1),dist(l+1,r)));
    int mid=(l+r)>>1;
    double ans=min(near_dist(l,mid),near_dist(mid+1,r));
    int cnt=0;
    for(int i=l;i<=r;i++){
        if(p[mid].x-ans<=p[i].x&&p[i].x<=p[mid].x+ans) help[cnt++]=i; 
    }
    sort(help,help+cnt,cmpy);
    for(int i=0;i<cnt;i++){
        for(int j=i+1;j<cnt;j++){
            if(p[help[j]].y-p[help[i]].y>=ans) break;
            ans=min(ans,dist(help[i],help[j]));
        }
    }
    return ans;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){            
            scanf("%d%d",&p[i].x,&p[i].y);
            p[i].type=true;
        }
        for(int i=n;i<2*n;i++){
            scanf("%d%d",&p[i].x,&p[i].y);
            p[i].type=false;
        }
        sort(p,p+2*n,cmpx);
        printf("%.3f\n",near_dist(0,2*n-1));
    }
    return 0;
}

Find the value of the b-th power module p of a

Idea: multiply available.

as, you can find a^0 first, multiply two a^0 to get a^1, multiply two a^1 to get a^2... And so on. Finally, through multiplication, we first calculate various power values in the sense of module p, and then divide them into multipliers according to the binary of b. Ordinary fast power thought, no code.