网易2018校招笔试编程题题解与思路
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;
}
查看9道真题和解析
