网易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;
}