不愧是鹅厂，连面试算法题都是这样恐怖至极，已顺利 OC，附赠课程 + 题库

* };

*/

/**

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

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

* };

*/

class Solution {

public``:

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* 你需要返回m个指针，第i个指针指向一条链，表示第i个问题的答案

* @param root TreeNode类 指向链表树的根

* @param b int整型vector 表示每个问题是什么

* <a href="/profile/547241" data-card-uid="547241" class="" target="_blank" from-niu="default" data-card-index="3">@return ListNode类vector

*/

int fa[1005];

void dfs(TreeNode* root,``int f){

if``(!root) return ;

fa[root->val]=f;

dfs(root->left,root->val);

dfs(root->right,root->val);

}

vector<ListNode*> solve(TreeNode* root, vector<``int``>& b) {

vector<ListNode*> ans;

dfs(root,root->val);

for``(auto &X:b){

vector<``int``> now;

int x=X;

while``(fa[x]!=x){

now.push_back(x);

x=fa[x];

}

now.push_back(x);

reverse(now.begin(),now.end());

ListNode* head=``new ListNode(now[0]);

ListNode* H=head;

for``(``int i=1;i<now.size();i++){

H->next=``new ListNode(now[i]);

H=H->next;

}

ans.push_back(head);

}

return ans;

}

};

</a>

第二题

===

/*

一个数字n，三种操作，n=n-1，偶数可以n=n/2，三的倍数可以n=n/3

问变成1最小操作次数

1<=n<=1e9

* @Author: 7QQQQQQQ

* @IDE: vscode

* @Date: 2021-03-21 20:00:29

*/

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const

《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》
浏览器打开：qq.cn.hn/FTe 免费领取

int N=1e6+50;

int main(){

int T;cin>>T;

while``(T--){

map<``int``,``int``> vis;

int n;cin>>n;

queue<``int``> que;

que.push(n);

vis[n]=1;

while``(!que.empty()){

int x=que.front();

que.pop();

if``(x==1) ``break``;

if``(!vis[x-1]){

vis[x-1]=vis[x]+1;

que.push(x-1);

}

if``(x%2==0 && !vis[x/2]){

vis[x/2]=vis[x]+1;

que.push(x/2);

}

if``(x%3==0 && !vis[x/3]){

vis[x/3]=vis[x]+1;

que.push(x/3);

}

}

cout<<vis[1]<<endl;

}

return 0;

}

第三题

===

/*

给了n个数字，然后q次查询，每次查询给了若干个数组，求这些数组合并后的第k小

范围都是1e5

* @Author: 7QQQQQQQ

* @IDE: vscode

* @Date: 2021-03-21 20:14:53

*/

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e6+50;

vector<``int``> e[N];

int cnt[N];

int main(){

int n;cin>>n;

for``(``int i=1;i<=n;i++){

cin>>cnt[i];

for``(``int j=1;j<=cnt[i];j++){

int x;cin>>x;

e[i].push_back(x);

}

sort(e[i].begin(),e[i].end());

}

int Q;cin>>Q;

while``(Q--){

int num;cin>>num;

vector<``int``> query;

for``(``int i=0;i<num;i++){

int x;cin>>x;

query.push_back(x);

}

int K;cin>>K;

int L=0,R=1e9;

while``(L+1<R){

int mid=L+R>>1;

int sum=0;

for``(``int i=0;i<num;i++){

int j=query[i];

sum+=lower_bound(e[j].begin(),e[j].end(),mid)-e[j].begin();

}

if``(sum<K) L=mid;

else R=mid;

}

cout<<L<<endl;

}

return 0;

}

第四题

===

update：这题数据水了，当时过了，就没管那么多。

对于 x[i]<=mid && y[i]>=mid 的，如果 cnt*2>=n，那么取 x[i],否则取 mid，对于其他的取 x[i]即可，对于

x[i]>mid 的，因为他会增加 cnt 的个数，所以?应该先按照左端点从大到小排序，这样优先选择了更多>=mid 的数字，可以减少在中间部分，选择更多的 x[i]，而不是 mid，使得总和 S 尽可能小。

代码已更新

/*

n个人，总共有w元，每个人要得到的钱数量在x和y之间，求让分配后，中位数最大值是多少

n<=1e5

w<=1e14

∑x[i]<=w<=∑y[i]

* @Author: 7QQQQQQQ

* @IDE: vscode

* @Date: 2021-03-21 20:23:00

*/

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;