首页 > 技术交流 > 网易2018校招笔试编程题题解与思路

网易2018校招笔试编程题题解与思路

头像
雨baby
编辑于 2017-09-10 16:27:00 APP内打开
赞 82 | 收藏 254 | 回复62 | 浏览34143
https://www.nowcoder.com/test/6910869/summary

相反数

分析

根据题意处理即可。

参考代码

#include <bits/stdc++.h>

using namespace std;

int n;
int main() {
    cin >> n;
    int cn = 0;
    int x = n;
    while(x) {
        cn = cn * 10 + x % 10;
        x /= 10;
    }
    cout << n + cn << endl;
    return 0;
}

字符串碎片

分析

计算有多少个片段,用总长度除以它即可。

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;

int main() {
    cin >> s;
    char c = s[0];
    double n = 1, d;
    for(int i = 1; i < s.size(); i++) {
        if(c != s[i]) {
            c = s[i];
            n++;
        }
    }
    d = (double)s.size() / n;
    printf("%.2lf\n", d);
    return 0;
}

魔法币

分析

注意到答案肯定是确定的,对于每一步的奇偶进行判断,用栈保存输出即可。

参考代码

#include <bits/stdc++.h>

using namespace std;

int n;
stack<char> s;
int main() {
    cin >> n;
    while(n) {
        if(n % 2 == 0) {
            n = (n - 2) / 2;
            s.push('2');
        } else {
            n = (n - 1) / 2;
            s.push('1');
        }
    }
    while(!s.empty()) {
        printf("%c", s.top());
        s.pop();
    }
    printf("\n");
    return 0;
}

重排数列

分析

记录能被4整除的个数,能被2整除的个数以及奇数的个数,然后分情况讨论一下。

参考代码

#include <bits/stdc++.h>

using namespace std;

int n;
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        int cnt4 = 0;
        int cnt2 = 0;
        int cnt1 = 0;
        for(int i = 0; i < n; i++) {
            int x;
            scanf("%d", &x);
            if(x % 4 == 0) cnt4++;
            else if(x % 2 == 0) cnt2++;
            else cnt1++;
        }
        if(cnt2 == 0) {
            if(cnt4 >= cnt1 - 1)
                printf("Yes\n");
            else
                printf("No\n");
        } else {
            if(cnt4 >= cnt1)
                printf("Yes\n");
            else
                printf("No\n");
        }
    }
    return 0;
}

游历魔法王国

分析

贪心。找出最长的那条树链长度,然后就可以判断出L是否足够走完最长的树链,贪心讨论下就好。

参考代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 50 + 5;
int n, L;
int parent[maxn];
int dp[200];
int main() {
    scanf("%d%d", &n, &L);
    for(int i = 0; i < n - 1; i++) scanf("%d", &parent[i]);
    int mx = 0;
    for(int i = 0; i < n - 1; i++) {
        dp[i + 1] = dp[parent[i]] + 1;
        mx = max(mx, dp[i + 1]);
    }
    int d = min(L, mx);
    cout << min((n), 1 + d + (L - d) / 2) << endl;
    return 0;
}

最长公共子括号序列

分析

因为长度相同,并且也是合法的括号序列,所以正反括号数跟原来一样。
我们考虑在原序列上枚举一个字符,把这个插入到序列的某个位置去,其他序列相对顺序不变,,这样就可以让LCS最大,然后我们判断一下是否合法,丢进set去重就好了。

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;
int main() {
    cin >> s;
    set<string> S;
    int len = s.size();
    for(int i = 0; i < len; i++) {
        string w = s.substr(0, i) + s.substr(i + 1);
        for(int j = 0; j < len - 1; j++) {
            string u = w.substr(0, j) + s[i] + w.substr(j);
            int tmp = 0;
            for(int k = 0; k < len; k++) {
                tmp += (u[k] == '(' ? 1 : -1);
                if(tmp < 0) {
                    break;
                }
            }
            if(tmp >= 0) {
                S.insert(u);
            }
        }
    }
    cout << (int)S.size() - 1 << endl;
    return 0;
}

合唱

分析

动态规划。
dp[i][j]表示小Q上一个演唱的音符是v[i],牛博士上一个演唱的音符是v[j]的最小难度和。
记忆化搜索一下就好了。

参考代码

java版本

import static java.lang.StrictMath.abs;

import java.util.Scanner;

public class Main {

    static int maxn = 2000 + 5;
    static int[] v = new int[maxn];
    static int[][] dp = new int[maxn][maxn];
    static int n;

    public static int max(int a, int b) {
        return (a > b) ? a : b;
    }

    public static int min(int a, int b) {
        return (a < b) ? a : b;
    }



    public static int solve(int la,int lb){

        int now = max(la, lb) + 1;
        if(now == n + 1) return 0;
        if(dp[la][lb] != -1) return dp[la][lb];
        return dp[la][lb] = min(solve(now, lb) + (la>0 ? abs(v[now] - v[la]) : 0), solve(la, now) + (lb>0 ? abs(v[now] - v[lb]) : 0));
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);


        n = cin.nextInt();
        v[0] = -1;
        for(int i = 1; i <= n; i++) v[i] = cin.nextInt();


        for (int i = 0; i < maxn; i ++)
            for (int j = 0; j < maxn; j ++)
                dp[i][j] = -1;

        System.out.println(solve(0,0));
    }
}

C++版本

#include <bits/stdc++.h>

using namespace std;


const int maxn = 2000 + 5;
int v[maxn];
int n;
int dp[maxn][maxn];
int solve(int la, int lb) {
    int now = max(la, lb) + 1;
    if(now == n + 1) return 0;
    if(dp[la][lb] != -1) return dp[la][lb];
    return dp[la][lb] = min(solve(now, lb) + (la ? abs(v[now] - v[la]) : 0), solve(la, now) + (lb ? abs(v[now] - v[lb]) : 0));
}
int main() {
    scanf("%d", &n);
    v[0] = -1;
    for(int i = 1; i <= n; i++) scanf("%d", &v[i]);
    memset(dp, -1, sizeof(dp));
    printf("%d\n", solve(0, 0));
    return 0;
}

射击游戏

分析

注意到允许的移动和旋转都是对于怪物整体而言的,那么其实等价于整个坐标轴做移动或者旋转。
然后我们现在要移动或者旋转之后在坐标轴上的点最多,坐标轴肯定是由给定点集来组成的,接下来的问题就是枚举坐标轴统计就好了,中间会涉及到直线的垂直和平行的判断。

参考代码

java版本

import java.util.Scanner;

public class Main {

    public static int max(int a, int b) {
        return (a > b) ? a : b;
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);

        int[] x = new int[100];
        int[] y = new int[100];
        int n;
        n = cin.nextInt();
        for (int i = 0; i < n; i++) {
            x[i] = cin.nextInt();
        }
        for (int i = 0; i < n; i++) {
            y[i] = cin.nextInt();
        }

        if (n <= 2) {
            System.out.println(n);
            return;
        }
        int res = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    int dx1 = x[j] - x[i];
                    int dy1 = y[j] - y[i];
                    for (int k = 0; k < n; k++) {
                        int cnt = 0;
                        if (i != k && j != k) {
                            for (int r = 0; r < n; r++) {
                                int dx2 = x[r] - x[i];
                                int dy2 = y[r] - y[i];
                                if (dy1 * dx2 == dy2 * dx1) {
                                    cnt++;
                                } else {
                                    dx2 = x[r] - x[k];
                                    dy2 = y[r] - y[k];
                                    if (dy1 * dy2 == -dx2 * dx1) {
                                        cnt++;
                                    }
                                }
                            }
                        }
                        res = max(res, cnt);
                    }
                }
            }
        }
        System.out.println(res);


    }
}

C++版本

#include <bits/stdc++.h>

using namespace std;

const int maxn = 50 + 5;

int x[maxn], y[maxn];
int n;
int solve() {
    if(n <= 2) return n;
    int res = 1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i != j) {
                int dx1 = x[j] - x[i];
                int dy1 = y[j] - y[i];
                for(int k = 0; k < n; k++) {
                    int cnt = 0;
                    if(i != k && j != k) {
                        for(int r = 0; r < n; r++) {
                            int dx2 = x[r] - x[i];
                            int dy2 = y[r] - y[i];
                            if(dy1 * dx2 == dy2 * dx1) {
                                cnt++;
                            } else {
                                dx2 = x[r] - x[k];
                                dy2 = y[r] - y[k];
                                if(dy1 * dy2 == -dx2 * dx1) {
                                    cnt++;
                                }
                            }
                        }
                    }
                    res = max(res, cnt);
                }
            }
        }
    }
    return res;
}
int main() {
    cin >> n; 
    for(int i = 0; i < n; i++) cin >> x[i];
    for(int i = 0; i < n; i++) cin >> y[i];
    cout << solve() << endl;
}

关注相关话题,参与更多讨论

62条回帖

回帖
加载中...
回帖

技术交流近期热帖

近期精华帖

热门推荐