首页 > 数码频道 > 科技 > 正文

环球热头条丨【网易实习准备】往年笔试题目练习_网易笔试题

2022-09-27 10:44:01来源：互联网

【资料图】

网易笔试题目练习

牛牛找工作（贪心）牛牛的（DFS/穷举+剪枝）DFS解法剪枝解法

牛牛找工作（贪心）

原题目以及java解法
核心思想：用哈希表和排序降低时间复杂度

技巧在于：

用哈希：使得输入某个伙伴能力值后可以立刻输出最优解用排序：实现贪心算法，避免二重循环，排序后O(n)一遍更新就可以得到所有最优解

数据结构：
D[i]数组(值 $\geq$ 0),i=0,1,…,m+n-1, 先存入工作难度再存人能力值

hs_Pay hashmap(D[i]->P[i])

对D[i]排序(sort), D[i]->P[i]的最大值就是max(P[0],P[1],…,P[i])
如此将hs_Pay更新成目标所求（maxPay）

再用hs_Pay输出每个人的最大收入的工作（maxPay）即可

示例输入：3 31 10010 10001000000000 10019 10 1000000000示例输出：10010001001

//官方题解的理解基础之上的C++版本#include<bits/stdc++.h>#include<unordered_map>using namespace std;typedef long long ll;int main(){int N, M; cin >> N >> M;vector<int>D(N + M);unordered_map<int, int>hsPay;int i;for (i = 0; i < N; i++)//输入（工作难度，收入）{cin >> D[i];cin>>hsPay[D[i]];}vector<int>Capab;//！易错点 别写成Capab(M)  否则后面别push_back，要改成直接赋值for (i = N; i < N + M; i++)//输入伙伴工作能力{cin >> D[i];Capab.push_back(D[i]);if (hsPay.find(D[i]) == hsPay.end())hsPay[D[i]] = 0;//没有记录的能力值暂定收入为0，方便后续排序(贪心)}sort(D.begin(), D.end()); //算法库中的排序//更新hsPay为最优解int max = 0;for (i = 0; i < D.size(); i++){if (max < hsPay[D[i]])max = hsPay[D[i]];hsPay[D[i]] = max;}for (i = 0; i < M; i++)cout << hsPay[Capab[i]]<<endl;}

易错点：
vector的使用（Define and Use）：

要么别开空间，直接push_back，就像python-list,要么开好空间，直接赋值，就像普通数组

1、第一种情况

//定义vector<int>List;...//使用中List.push_back(xx);

2、第二种情况

//定义vector<int>nums(n);...//使用中nums[i]=xx;

不可混淆，避免在一串0之后push_back或者指针越界报错。

牛牛的（DFS/穷举+剪枝）

题目：
http://www.k6k4.com/blog/show/aaawcsdra1528985482372
牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。

牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。

牛牛想知道在总体积不超过背包容量的情况下,他一共有多少种零食放法(总体积为0也算一种放法)。

输入描述:

输入包括两行

第一行为两个正整数n和w(1 <= n <= 30, 1 <= w <= 2 * 10^9),表示零食的数量和背包的容量。

第二行n个正整数v[i](0 <= v[i] <= 10^9),表示每袋零食的体积。

DFS解法

DFS解法的规律：
对解空间（零食列表也就是vector<int>value），带着约束条件（long sum）执行DFS，这个约束条件会出现在dfs()函数的参数中。

#include<bits/stdc++.h>using namespace std;long ans = 0;int n;long w;vector<long>value;void dfs(long sum, int loc);int main(){    cin >> n >> w;    long total = 0;    for (int i = 0; i < n; ++i) {        int b;        cin >> b;        value.push_back(b);        total += value[i];    }    if (total <= w)        ans = pow(2, n);    else {        sort(value.begin(), value.end());        dfs(0, 0);    }    cout << ans << endl;    return 0;}//带者当前已装载总体积sum进行DFS，保持sum<阈值wvoid dfs(long sum, int loc){    if (sum > w)        return;    if (sum <= w) {        ++ans;    }    for (int i = loc; i < n; ++i) {        dfs(sum + value[i], i + 1);    }}