网易2017实习生招聘笔试题编程题参考思路和代码
原题地址：https://www.nowcoder.com/test/4575457/summary
奇怪的表达式求值
分析
直接模拟过去就完了。
参考code
#include <bits/stdc++.h>
using namespace std;
string s;
int main(){
cin >> s;
int ans = s[0] - '0';
for(int i = 1; i < (int)(s.size() - 1); i+=2){
if(s[i] == '*')
ans = ans * (s[i + 1] - '0');
else if(s[i] == '+')
ans = ans + (s[i + 1] - '0');
else {
ans = ans - (s[i + 1] - '0');
}
}
cout << ans << endl;
}
分饼干
分析
枚举每个位置的数字,然后记录满足要求的答案数就可。
参考code
#include <bits/stdc++.h>
using namespace std;
long long n1[10001], n2[10001];
int main(){
string s;
int n;
cin >> s >> n;
long long ret = 0;
n1[0] = 1;
for(int i = 0; i < s.size(); i++){
memset(n2, 0, sizeof(n2));
for(int j = 0; j < n; j++){
for(int k = 0; k < 10; k++){
if(isdigit(s[i]) && s[i] - '0' != k) continue;
n2[ ( ( j * 10) + k ) % n] += n1[j];
}
}
memcpy(n1,n2,sizeof(n1));
}
cout << n1[0] << endl;
}
消除重复元素
分析
根据题意模拟一下就行
参考code
#include <bits/stdc++.h>
using namespace std;
int n;
int a[105];
map<int,int> m;
vector<int> ret;
int main(){
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < n; i++) m[a[i]]++;
for(int i = 0; i < n; i++){
m[a[i]]--;
if(!m[a[i]])
ret.push_back(a[i]);
}
int len = ret.size();
for(int i = 0; i < len; i++){
if(i == len - 1) printf("%d\n",ret[i]);
else printf("%d ",ret[i]);
}
return 0;
}
赶去公司
分析
枚举去每个出租车点打车需要的总时间,最后和完全步行总时间取个最小值即可。
参考code
#include <bits/stdc++.h>
using namespace std;
int n,tx[55],ty[55],gx,gy,walkTime,taxiTime;
int main(){
cin >> n;
for(int i = 0; i < n; i++) cin >> tx[i];
for(int i = 0; i < n; i++) cin >> ty[i];
cin >> gx >> gy;
cin >> walkTime >> taxiTime;
int ans = (abs(gx - 0) + abs(gy - 0)) * walkTime;
for(int i = 0; i < n; i++){
int res = (abs(tx[i] - 0) + abs(ty[i] - 0)) * walkTime;
res += (abs(tx[i] - gx) + abs(ty[i] - gy)) * taxiTime;
ans = min(ans, res);
}
cout << ans << endl;
return 0;
}
小易记单词
分析
用set模拟一下即可
参考code
#include <bits/stdc++.h>
using namespace std;
int m, n;
set<string> S1;
set<string> S2;
int main() {
cin >> n >> m;
for(int i = 0; i < n; i++) {
string x;
cin >> x;
S1.insert(x);
}
for(int i = 0; i < n; i++) {
string x;
cin >> x;
S2.insert(x);
}
int ans = 0;
for(auto &x : S1) {
if(S2.find(x) != S2.end()) ans += x.size() * x.size();
}
cout << ans << endl;
return 0;
}
涂棋盘
分析
暴力枚举维护答案即可。
参考code
#include <bits/stdc++.h>
using namespace std;
vector <string> mp;
int n;
int solve(vector <string> grid) {
int w = 0, b = 0, W = 0, B = 0, MAX = 0;
for(int i = 0; i < n; i++) {
w = 0; b = 0; W = 0; B = 0;
for(int j = 0; j < n; j++) {
if(grid[j][i]=='B') {
b++; w = 0;
if(b > B) B = b;
}
if(grid[j][i]=='W') {
w++; b = 0;
if(w > W) W = w;
}
}
if(B > MAX) MAX = B;
if(W > MAX) MAX = W;
}
return MAX;
}
int main() {
cin >> n;
for(int i = 0; i < n; i++) {
string s;
cin >> s;
mp.push_back(s);
}
cout << solve(mp) << endl;
return 0;
}
集合
分析
枚举所有值组成的pair,约分之后丢进set去重即可。
参考code
#include <bits/stdc++.h>
using namespace std;
int w, x, y, z;
set<pair<int, int> > S;
int main(){
cin >> w >> x >> y >> z;
for(int i = w; i <= x; i++) {
for(int j = y; j <= z; j++) {
int ii = i, jj = j;
int di = __gcd(i, j);
ii /= di; jj /= di;
S.insert(make_pair(ii, jj));
}
}
cout << S.size() << endl;
return 0;
}
工作安排
分析
暴力枚举每个位置工作的安排情况记录答案即可。
参考code
#include <bits/stdc++.h>
using namespace std;
vector<string> a;
int n;
int b[10];
int ret;
void dfs(int i) {
if(i == a.size()) {
ret++;
} else {
for(int j = 0; j < a[i].size(); j++) {
if(b[a[i][j] - '0']) {
b[a[i][j] - '0'] = 0;
dfs(i + 1);
b[a[i][j] - '0'] = 1;
}
}
}
}
int main() {
cin >> n;
for(int i = 0; i < n; i++) {
string x; cin >> x;
a.push_back(x);
}
for(int i = 0; i < 10; i++) b[i] = 1;
ret = 0;
dfs(0);
cout << ret << endl;
return 0;
}
调整队形
分析
由于我们只有目标状态只可能是两种,形如: BBBBBGGGGG GGGGGBBBBB 于是我们对于串中第一个'B'然后计算把它swap到第一个位置需要多少次,第二个'B'swap到第二个位置需要多少次...依次类推.. 然后对于'G'同理,最后取个较小值即为答案。
参考code
#include <bits/stdc++.h>
using namespace std;
string s;
int main(){
cin >> s;
int rb = 0, rg = 0;
int b = 0, g = 0;
for(int i = 0; i < s.size(); i++) {
if(s[i] == 'B') {
rb += i - b; ++b;
} else {
rg += i - g; ++g;
}
}
cout << min(rb, rg) << endl;
return 0;
}
双核处理
分析
首先我们观察到数据量都是1024的倍数,所以我们可以对于所有都除以一个1024,然后最后再算回来。 这显然是一个经典的动态规划的问题,直接搞就好了。 过不了的大概因为是用的贪心做法,可以尝试自己构造一波反例。。
参考code
#include <bits/stdc++.h>
using namespace std;
int vis[204800];
vector<int> a;
int n;
int solve(vector<int> vec) {
int i, j, len = 0;
for(int i = 0; i < vec.size(); ++i) len += (vec[i] /= 1024);
memset(vis, 0, sizeof(vis[0]) * (len / 2 + 1));
vis[0] = 1;
for(i = 0; i < vec.size(); ++i) {
for(j = len / 2 - vec[i]; j >= 0; --j) {
if(vis[j] && !vis[j + vec[i]]) {
vis[j + vec[i]] = 1;
}
}
}
i = len / 2;
while(i >= 0 && !vis[i])
--i;
return (len - i) * 1024;
}
int main(){
cin >> n;
for(int i = 0; i < n; i++) {
int x; cin >> x;
a.push_back(x);
}
cout << solve(a) << endl;
return 0;
}
魔力手环
分析
把手环数字转为一个向量,然后乘
[1 1 0 0 0]
[0 1 1 0 0]
[0 0 1 1 0]
[0 0 0 1 1]
[1 0 0 0 1]
这个矩阵N次即可。。用个矩阵快速幂,边算边求模。
参考code
#include <bits/stdc++.h>
using namespace std;
void mult(int A[50][50], int B[50][50], int C[50][50], int n) {
int T[50][50];
memset(T, 0, sizeof(T));
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
for(int k = 0; k < n; k++) {
T[i][j] = (T[i][j] + A[i][k] * B[k][j]) % 100;
}
}
}
memcpy(C, T, sizeof(T));
}
void mypower(int A[50][50], int R[50][50], int n, int m) {
if(n == 0) {
memset(R, 0, sizeof(int) * 2500);
for(int i = 0; i < m; i++) R[i][i] = 1;
} else if(n % 2 == 0) {
mypower(A, R, n/2, m);
mult(R, R, R, m);
} else {
mypower(A, R, n - 1, m);
mult(A, R, R, m);
}
}
vector<int> solve(vector<int> seq, int m) {
int A[50][50], R[50][50], n = (int)seq.size();
memset(A, 0, sizeof(A));
for(int i = 0; i < n; i++) A[i][i] = A[i][(i + 1) % n] = 1;
mypower(A, R, m, n);
vector<int> res;
for(int i = 0; i < n; i++) {
int sum = 0;
for(int j = 0; j < n; j++) sum = (sum + R[i][j] * seq[j]) % 100;
res.push_back(sum);
}
return res;
}
int main () {
int n, k;
vector<int> x;
cin >> n >> k;
for(int i = 0; i < n; i++) {
int tmp; cin >> tmp;
x.push_back(tmp);
}
vector<int> ans = solve(x, k);
for(int i = 0; i < ans.size(); i++) i == 0 ? cout << ans[i] : cout << " " << ans[i];
return 0;
}
堆砖块
分析
从没有砖块开始分析。考虑每块砖块放入的决策,放入左边,放入右边和不使用这块砖块三种情况。 然后做个dp,这里用滚动数组优化了下空间。
参考code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500010;
int n;
vector<int> a;
int dp[2][maxn];
int solve(vector<int> v) {
int res = 0;
memset(dp, 0, sizeof(dp));
int p = 0;
for(int i = 0; i < v.size(); i++) {
dp[p][v[i]] = max(dp[1-p][v[i]] , v[i]);
for(int ix = 0; ix < maxn; ix++) {
if(dp[1 - p][ix]) {
if(dp[p][ix] < dp[1 - p][ix]) dp[p][ix] = dp[1-p][ix];
dp[p][ix + v[i]] = max(dp[p][ix + v[i]], max(dp[1 - p][ix + v[i]], dp[1 - p][ix] + v[i]));
dp[p][abs(ix - v[i])] = max(dp[p][abs(ix - v[i])], max(dp[1 - p][abs(ix - v[i])], max(dp[1-p][ix] - ix + v[i], dp[1 - p][ix])));
}
}
p = 1 - p;
}
if(dp[1 - p][0]) res = dp[1 - p][0];
else res = -1;
return res;
}
int main() {
cin >> n;
for(int i = 0; i < n; i++) {
int x; cin >> x;
a.push_back(x);
}
cout << solve(a) << endl;
return 0;
}#C++工程师##iOS工程师#
投递金山WPS等公司10个岗位 >