9.4网易笔试100、100、89、第四题没写完
第一题找最大同余数
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
vector<int> vec(n,0);
for(int i = 0 ; i < n ;i++){
cin>>vec[i];
}
if(k == 1){
cout<<n;
return 0;
}
unordered_map<int,int> hashtable;
int maxelement = 0;
for(int i = 0 ; i < n ;i++){
hashtable[vec[i]%k]++;
maxelement = max(maxelement,hashtable[vec[i]%k]);
}
cout<<maxelement;
return 0;
} 第二题 #include <bits/stdc++.h>
using namespace std;
int main(){
int n,k,t;
cin>>n>>k>>t;
if(t >= k || n - k < k - t - 1){
cout<<-1;
return 0;
}
if(k-1 == t){
cout<<string(k,'1')+string(n-k,'0');
return 0;
}
int gap = t;
int zero = n - k;
int dem1 = k - t - 1;
string newstring = string(gap+1,'1');
while(zero--){
newstring += '0';
if(dem1 > 0){
newstring += '1';
dem1--;
}
}
cout<<newstring;
return 0;
} 第三题 #include <bits/stdc++.h>
using namespace std;
int main(){
int n,k,x;
cin>>n>>k>>x;
vector<int> vec(n,0);
for(int i = 0 ; i < n;i++){
cin>>vec[i];
}
sort(vec.begin(),vec.end(),greater<int>());
int index = 0;
while(k > 0){
while(vec[index] - x < vec[n-1] && index < n-1){
index++;
}
if(index == n-1){
break;
}
vec[index] -= x;
k--;
}
sort(vec.begin(),vec.end());
int item = k/n;
int yu = k%n;
cout<<vec[n-1-yu] - item*x;
return 0;
} 第四题我只写了简单遍历，肯定只能过一些用例，优化应该是记忆化搜索 #include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int value;
TreeNode *left;
TreeNode *right;
TreeNode(int val):value(val),left(nullptr),right(nullptr){}
};
long long getweight(TreeNode *cur){
if(cur == nullptr){
return 0;
}
long long sum = 1;
queue<TreeNode *> que;
que.push(cur);
while(!que.empty()){
TreeNode *p = que.front();
que.pop();
sum *= p->value;
if(p->left){
que.push(p->left);
}
if(p->right){
que.push(p->right);
}
}
unordered_set<int> set1;
for(int i = 1 ; i <= sqrt(sum);i++){
if(sum%i == 0){
set1.insert(i);
set1.insert(sum/i);
}
}
cout<<set1.size();
return set1.size();
}
long long getnumber(TreeNode *cur){
if(cur == nullptr){
return 0;
}
return (getweight(cur) + getnumber(cur->left) + getnumber(cur->right))%1000000007;
}
int main(){
int n;
cin>>n;
vector<int> vec(n,0);
for(int i = 0 ; i < n ;i++){
cin>>vec[i];
}
vector<vector<int>> edge;
int temp1,temp2;
for(int i = 0 ; i < n -1;i++){
cin>>temp1>>temp2;
edge.push_back({temp1,temp2});
}
sort(edge.begin(),edge.end(),[](vector<int> &lhs,vector<int> &rhs){
if(lhs[0] == rhs[0]){
return lhs[1] < rhs[1];
}
return lhs[0] < rhs[0];
});
unordered_map<int,TreeNode*> hashtable;
TreeNode *root = new TreeNode(vec[0]);
hashtable[1] = root;
for(int i = 0 ; i < edge.size();i++){
TreeNode *cur = hashtable[edge[i][0]];
if(cur->left==nullptr){
cur->left = new TreeNode(edge[i][1]);
hashtable[edge[i][1]] = cur->left;
}else{
cur->right = new TreeNode(edge[i][1]);
hashtable[edge[i][1]] = cur->right;
}
}
cout<<getnumber(root);
return 0;
} 
美团公司福利 1403人发布