网易互娱4.15 笔试

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode():val(0),left(nullptr),right(nullptr){}
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
    TreeNode(int x,TreeNode* left,TreeNode* right):val(x),left(left),right(right){}
};

TreeNode* help(vector<int>& inorder,vector<int>& postorder,int left,int right,int begin,unordered_map<int,int>& map){
    if(left>right)return nullptr;
    int midVal=postorder[right];
    int mid=map[midVal];
    TreeNode* root=new TreeNode(midVal);
    root->left=help(inorder,postorder,left,left+mid-begin-1,begin,map);
    root->right=help(inorder,postorder,left+mid-begin,right-1,mid+1,map);
    return root;
}

TreeNode* buildTree(vector<int>& inorder,vector<int>& postorder){
    unordered_map<int,int> map;
    for(int i=0;i<inorder.size();++i)map[inorder[i]]=i;
    return help(inorder,postorder,0,postorder.size()-1,0,map);
}

int dfs(TreeNode* root,int& res){
    if(root==nullptr)return 0;
    auto left=dfs(root->left,res);
    auto right=dfs(root->right,res);
    res=max(1+left+right,res);
    return 1+max(left,right);
}
int main(){

    int n;
    cin>>n;
    vector<int> inorder(n);
    vector<int> postorder(n);
    for(int i=0;i<n;++i)cin>>inorder[i];
    for(int i=0;i<n;++i)cin>>postorder[i];
    auto root=buildTree(inorder,postorder);
    int res=0;
    dfs(root,res);
    cout<<res-1<<endl;
}

class Solution {
public:
    
    int stat_hit_count(vector<int>& R, int N) {
        capacity=N;
        for(auto& r:R)insert(r);
        return res;
        
    }
private:
    list<int> lru;
    unordered_map<int,list<int>::iterator> map;
    int capacity;
    int res=0;
    void insert(int key){
        if(map.find(key)!=map.end()){
            res++;
            lru.splice(lru.begin(), lru,map[key]);
            return;
        }
        if(map.size()>=capacity){
            int key=lru.back();
            map.erase(key);
            lru.pop_back();
        }
        lru.push_front(key);
        map[key]=lru.begin();
    }
};

int bfs(vector<int>& jump){
    int n=jump.size();
    if(n==1)return 1;
    queue<int> que;
    unordered_set<int> visited;
    que.push(0);
    visited.insert(0);
    
    int res=0;
    while(!que.empty()){
        int size=que.size();
        for(int i=0;i<size;++i){
            auto cur=que.front();
            que.pop();
            if(cur>=n)return res;
            
            int right=cur+jump[cur];
            if(!visited.count(right)){
                que.push(right);
                visited.insert(right);
            }
            
            for(int j=cur-1;j>0;--j){
                if(!visited.count(j)){
                    que.push(j);
                    visited.insert(j);
                }
            }

        }
        res++;
    }
    return res;
}

int main(){
    int n;
    cin>>n;
    vector<int> jump(n);
    for(int i=0;i<n;++i)cin>>jump[i];
    cout<<bfs(jump);
    return 0;
}