网易2018校招内推笔试编程题参考代码及思路

练习链接: https://www.nowcoder.com/test/6291726/summary

等差数列

分析

对序列排序,然后比对一下是否等差即可。

参考code

#include <bits/stdc++.h>

using namespace std;

int n;
int x[55];
string solve() {
    sort(x, x + n);
    if(n <= 2) return "Possible";
    else {
        int d = x[1] - x[0];
        bool ok = 1;
        for(int i = 1; ok && i < n; i++) {
            if(d != x[i] - x[i - 1]) return "Impossible";
        }
        return "Possible";
    }
}
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> x[i];
    cout << solve() << endl;
    return 0;
}

彩色砖块

分析

题目有点唬人。。
设颜色种数为s,那么
if s > 2 ans = 0
else ans = s

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;
set<char> S;
int main() {
    cin >> s;
    for(int i = 0; i < s.size(); i++) S.insert(s[i]);
    int ans = S.size();
    if(ans > 2) ans = 0;
    cout << ans << endl;
    return 0;
}

交错01串

分析

就挨着比较,记录当前是交错01串的长度,维护最大值即可。

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;
int main() {
    cin >> s;
    int ans = 1, cnt = 1;
    for(int i = 1; i < s.size(); i++) {
        if(s[i] != s[i - 1]) {
            cnt++;
        } else {
            cnt = 1;
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}

独立的小易

分析

首先计算能保证的房屋能租多少天,如果有剩余再考虑购买水果。

参考代码

#include <bits/stdc++.h>

using namespace std;

int x, f, d, p;
int solve(int x, int f, int d, int p) {
    int tmp1 = d / x;
    if(tmp1 <= f) return tmp1;
    d -= f * x;
    return f + d / (x + p);
}
int main() {
    cin >> x >> f >> d >> p;
    cout << solve(x, f, d, p) << endl;
    return 0;
}

堆棋子

分析

对于一个k,我们找一个坐标(x, y)让k个棋子距离这个坐标的曼哈顿距离之和最小。注意到x和y其实是独立的,考虑枚举棋盘上所有可能得坐标(x[i], y[j]),计算这个坐标到所有棋子的距离分别是多少,然后维护k个棋子对于这个坐标最小曼哈顿距离和即可。

参考代码

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

int n, x[55], y[55];
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> x[i];
    for(int i = 0; i < n; i++) cin >> y[i];
    vector<int> res(n, inf);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            for(int k = 0; k < n; k++) {
                vector<int> res2(n);
                for(int l = 0; l < n; l++) {
                    res2[l] = abs(x[l] - x[j]) + abs(y[l] - y[k]);
                }
                sort(res2.begin(), res2.end());
                int res3 = 0;
                for(int l = 0; l < i + 1; l++) res3 += res2[l];
                res[i] = min(res[i], res3);
            }
        }
    }
    for(int i = 0; i < n; i++) {
        i == 0 ? cout << res[i] : cout << " " << res[i];
    }
    return 0;
}

操作序列

分析

观察每一次操作之后的序列跟之前的关系,可以根据这个直接得到最终的数列。

参考代码

#include <bits/stdc++.h>

using namespace std;


const int maxn = 2e5 + 5;

int a[maxn];
int n;
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    if(n % 2) {
        for(int i = n; i >= 1; i -= 2) printf("%d ", a[i]);
        for(int i = 2; i <= n; i += 2) i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]);
    } else {
        for(int i = n; i >= 1; i -= 2) printf("%d ", a[i]);
        for(int i = 1; i <= n; i += 2) i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

疯狂队列

分析

根据样例提示,猜想了一个结论:
我们要把这个队列安排为交错的形式(证明略)。
交错有两种形式,看第一个人是比他相邻的人高还是矮。
以矮的为例:
总共的疯狂值为(h2 - h1) + (h2 - h3) + (h4 - h3) + ... = -h1 + 2h2 - 2h3 + 2h4 - ...,

如果总共是偶数个人,疯狂值为-h1 + 2h2 - 2h3 + 2h4 - ... - 2h{n-1} + h{n},所以我们需要从最大的开始依次安排h2,...h{n-2},然后安排h{n},然后继续安排剩下的。

如果总共是奇数个人,疯狂值为-h1 + 2h2 - 2h3 + 2h4 - ... + 2h{n-1} - h{n},所以我们需要从最大的开始依次安排h2,...h{n-1},然后安排h1和h{n},然后继续安排剩下的。

然后另外一种形式类似,维护最大的疯狂值即可。

参考代码

#include <bits/stdc++.h>

using namespace std;

int h[55];
int n;
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> h[i];
    sort(h, h + n);
    int tmp, ans = 0, ans1 = 0, ans2 = 0;
    if(n % 2 == 0) {
        tmp = n / 2;
        for(int i = 0; i < tmp; i++) {
            ans += 2 * (h[tmp + i] - h[i]);
        }
        ans += h[tmp - 1] - h[tmp];
        cout << ans << endl;
        return 0;
    } else {
        tmp = n / 2;
        for(int i = 0; i < tmp; i++) {
            ans1 += 2 * (h[tmp + 1 + i] - h[i]);
            ans2 += 2 * (h[tmp + 1 + i] - h[i]);
        }
        ans1 += -h[tmp] + h[tmp - 1]; 
        ans2 += h[n] - h[n + 1];
        cout << max(ans1, ans2) << endl;
        return 0;
    }
    return 0;
}

小易喜欢的数列

分析

想象一下,如果我们确定这个数列的第一个数是i,那么第二个数可以是1到k中除了是i的约数的任何数。
于是我们定义dp[j][i]表示长度为i最后一个数是j的小易喜欢的数列的数量,然后挨着转移即可。。实现请参考参考代码。

参考代码

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int dp[maxn][15];
int n, k;
int main() {
    cin >> n >> k;
    dp[1][0] = 1;
    for(int i = 1; i <= n; i++) {
        int sum = 0;
        for(int j = 1; j <= k; j++) {
            sum += dp[j][i - 1];
            sum %= mod;
        }
        for(int j = 1; j <= k; j++) {
            int sum2 = 0;
            for(int z = j + j; z <= k; z += j) {
                sum2 += dp[z][i - 1];
                sum2 %= mod;
            }
            dp[j][i] = (sum - sum2 + mod) % mod;
        }
    }
    int ans = 0;
    for(int j = 1; j <= k; j++) {
        ans += dp[j][n];
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}
#Java工程师##C++工程师##iOS工程师##安卓工程师##运维工程师##前端工程师##算法工程师#
全部评论
import java.util.*; import java.lang.*; public class Main { public static Integer[] chess_min(Integer[] X, Integer[] Y, Integer n) { Set<Integer> xAxis = new HashSet<Integer>(Arrays.asList(X)); Set<Integer> yAxis = new HashSet<Integer>(Arrays.asList(Y)); List<List<Integer>> centers = new ArrayList<List<Integer>>(); for (Integer x: xAxis) { for (Integer y: yAxis) { List<Integer> distances = new ArrayList<Integer>(); for (Integer i=0; i<n; i++) { distances.add(Math.abs(X[i]-x) + Math.abs(Y[i]-y)); } Collections.sort(distances); centers.add(distances); } } Integer[] min_step = new Integer[n]; Integer[] sum = new Integer[centers.size()]; for (Integer i=0; i<centers.size(); i++) { sum[i] = 0; } for (Integer i=0; i<n; i++) { for (Integer j=0; j<centers.size(); j++) { sum[j] += centers.get(j).get(i); } min_step[i] = Collections.min(Arrays.asList(sum)); } return min_step; } public static void main(String[] args) { Scanner in = new Scanner(System.in ); while(in.hasNext()) { Integer n = in.nextInt(); Integer[] X = new Integer[n]; Integer[] Y = new Integer[n]; for (Integer i=0; i<n; i++) { X[i] = in.nextInt(); } for (Integer i=0; i<n; i++) { Y[i] = in.nextInt(); } StringBuilder str = new StringBuilder(); for (Integer i: chess_min(X, Y, n)) { str.append(i+" "); } System.out.println(str.substring(0,str.length()-1)); } } } 棋子 java过的
点赞 回复
分享
发布于 2017-08-12 18:21
沙发没抢到
点赞 回复
分享
发布于 2017-08-12 17:32
阿里巴巴
校招火热招聘中
官网直投
JAVA  独立生活100 棋盘40 最喜欢数列0 GG
点赞 回复
分享
发布于 2017-08-12 17:37
堆棋子那个题  怎么保证 中心点就在你枚举的这些点里面呢
点赞 回复
分享
发布于 2017-08-12 18:10
堆棋子这个题目我有疑问,题目中说的棋盘的范围是21亿乘21亿, 给出的解法只考虑了n 乘以 n.
点赞 回复
分享
发布于 2017-08-12 20:06
关上前五大门
点赞 回复
分享
发布于 2017-08-12 17:34
膜拜骏博日博
点赞 回复
分享
发布于 2017-08-12 17:35
为什么你这么熟练呢
点赞 回复
分享
发布于 2017-08-12 17:37
堆棋子这题想想复杂度就不敢写
点赞 回复
分享
发布于 2017-08-12 17:58
#include<bits/stdc++.h> using namespace std; int h[55]; int n; int main(void){ cin >> n; for(int i = 0; i < n; i++) cin >> h[i]; sort(h, h + n); int tmp, ans = 0; if(n % 2 == 0) { tmp = n / 2; for(int i = 0; i < tmp; i++) { ans += 2 * (h[tmp + i] - h[i]); } ans += h[tmp - 1] - h[tmp]; cout << ans << endl; } else { tmp = n / 2; for(int i = 0; i < tmp; i++) { ans += 2 * (h[tmp + 1 + i] - h[i]); } ans += -h[tmp + 1] + h[tmp]; cout << ans << endl; } return 0; } 疯狂队列,贴子里给的答案ans2越界了,这是我修改后的答案。还是很佩服作者的思路
点赞 回复
分享
发布于 2017-08-12 21:00
//堆棋子JAVA import java.util.*; public class Main{ //public static int m = 10^9; //循环边界 public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); int[] temp1 = new int[n]; int[] temp2 = new int[n]; //取所有初始棋子的最大边界作为循环边界(这样会超内存),不理解大佬说的为何汇聚点一定在已有棋子的横纵坐标处?? //int maxX = 0; //int maxY = 0; //循环边界 for(int i=0; i<n; i++){ temp1[i] = sc.nextInt(); //循环边界 //maxX = Math.max(maxX,temp1[i]); } for(int i=0; i<n; i++){ temp2[i] = sc.nextInt(); //maxY = Math.max(maxY,temp2[i]); } Point[] point = new Point[n+1]; //棋子的初始位置 for(int i=0; i<n; i++){ point[i+1] = new Point(temp1[i],temp2[i]); } int[] shortDistance = new int[n+1]; //放置i个棋子的最少操作次数 Arrays.fill(shortDistance,Integer.MAX_VALUE); //循环边界没取10^9,只能通过30%;取初始棋子的最大边界,通过60%。取初始棋子下标,100% for(int i : temp1){ for(int j : temp2){ int[] distance = new int[n+1]; //在坐标(i,j)放置k个棋子 for(int k=1; k<=n; k++){ //求出(i,j)到每个初始点的距离,排序 distance[k] = Math.abs(i-point[k].x) + Math.abs(j-point[k].y); } Arrays.sort(distance); int temp = 0; //求若在(x,y)放置1~n个棋子的最短距离,更新结果集合(判断全局最短是否为在(i,j)处获得) for(int k=1; k<=n; k++){ temp += distance[k]; shortDistance[k] = Math.min(shortDistance[k],temp); } } } for(int i=1; i<=n-1; i++){ System.out.print(shortDistance[i] + " "); } System.out.println(shortDistance[n]); } } private static class Point{ int x; int y; Point(int x, int y){ this.x = x; this.y = y; } } }
点赞 回复
分享
发布于 2017-08-13 10:53
疯狂队列:ans2 += h[tmp] - h[tmp + 1];
点赞 回复
分享
发布于 2017-08-13 17:13
8题?
点赞 回复
分享
发布于 2017-08-12 17:29
牛人就是吊
点赞 回复
分享
发布于 2017-08-12 17:32
厉害
点赞 回复
分享
发布于 2017-08-12 17:34
学习了。。。。
点赞 回复
分享
发布于 2017-08-12 17:34
厉害
点赞 回复
分享
发布于 2017-08-12 17:34
不错。 不知道01那个还能够输入string啊。。。。。
点赞 回复
分享
发布于 2017-08-12 17:35
大佬,赞。。
点赞 回复
分享
发布于 2017-08-12 17:36
厉害,厉害
点赞 回复
分享
发布于 2017-08-12 17:37

相关推荐

点赞 217 评论
分享
牛客网
牛客企业服务