网易0912笔试编程题参考解题报告
参考code都使用C/C++书写，思路都是一样的。 如果发现题解有问题，欢迎指出以便及时更改。
数字翻转
分析：
实现一个rev()操作，然后输出所求即可 时间复杂度：O(length(n)) = O(logn)
参考代码:
#include <iostream>
#include <cstdio>
using namespace std;
int rev(int source) {
int result = 0;
while (source != 0) {
int tail = source % 10;
result = result * 10 + tail;
source /= 10;
}
return result;
}
int main(){
int x,y;
cin >> x >> y;
cout << rev(rev(x) + rev(y)) << endl;
}
计算糖果
分析:
根据三个式子就能求出A,B,C了，然后验证一下等式即可。 时间复杂度:O(1)
参考代码:
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
int AminusB, BminusC, AplusB, BplusC;
cin >> AminusB >> BminusC >> AplusB >> BplusC;
int A = (AplusB + AminusB) / 2;
int B = (AplusB - AminusB) / 2;
int C = (BplusC - B);
if(AminusB == A - B && AplusB == A + B && BminusC == B - C && BplusC == B + C)
cout << A << " " << B << " " << C << endl;
else
cout << "No" << endl;
return 0;
}
买苹果
分析:
这题可以考虑使用背包模型去做。但是范围比较小就直接枚举6个和8个的袋数维护最小值就好了 时间复杂度:O(n^2/48)
参考code:
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
int n, ans = 1000;
cin >> n;
for(int i = 0; i <= 20; i++){
for(int j = 0; j <= 20; j++){
if(i * 6 + j * 8 == n){
ans = min(ans,(i + j));
}
}
}
if(ans == 1000) ans = -1;
cout << ans << endl;
}
圆上的整点
分析:
我们可以观察得到可能是优雅的点有两类： 第一种是构成斜边为半径的直角三角形的点,另外一个是当半径是整数的坐标轴上的4个点，于是第一类我们可以枚举一条直角边去判断得到 第二种直接判半径平方是否是平方数即可。 时间复杂度：O(sqrt(n))
参考代码:
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main(){
int r, ans = 0;
cin >> r;
for(int x = 1; x * x < r; x++){
int y = (int)sqrt(double(r - x * x));
if(x * x + y * y == r) ans++;
}
ans *= 4;
int x = (int)sqrt(double(r));
if(x * x == r) ans += 4;
cout << ans << endl;
}
暗黑的字符串
分析：
定义dp1[i]为结尾两个字符相同长度为i的暗黑字符串个数 定义dp2[i]为结尾两个字符不同长度为i的暗黑字符串个数 答案所求就是dp1[n] + dp2[n] 分别考虑当前这个字符的安放方法，可以得到以下的状态转移方程: dp1[i + 1] = dp1[i] + dp2[i] dp2[i + 1] = 2 * dp1[i] + dp2[i] 时间复杂度：O(n)
参考代码:
#include <iostream>
#include <cstdio>
using namespace std;
long long dp1[35];
long long dp2[35];
int main(){
int n;
cin >> n;
dp1[1] = 0, dp1[2] = 3;
dp2[0] = 1, dp2[1] = 3, dp2[2] = 6;
for(int i = 3; i <= n; i++){
dp1[i] = dp1[i - 1] + dp2[i - 1];
dp2[i] = dp1[i - 1] * 2 + dp2[i - 1];
}
cout << dp1[n] + dp2[n] << endl;
}
回文序列
分析:
第一眼以为是个dp。然后想了想，要变成回文那么两端的值一定要相等，如果已经相等了，把它们移除了继续在剩余的序列上操作；如果不等，我们只能把较小那端(因为没法把较大的值变小)的那个值加到相邻一个位置(等同于题设给的操作)，因此我们一直这样做下去就可以边记录操作次数即可。 时间复杂度: O(n)
参考代码:
#include <iostream>
#include <cstdio>
using namespace std;
int n;
int a[55];
int main(){
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
int l = 0, r = n - 1;
int res = 0;
while(l < r){
if (a[l] < a[r]){
a[l+1] += a[l];
++l; ++res;
} else if(a[l] > a[r]){
a[r-1] += a[r];
--r; ++res;
}else{
++l, --r;
}
}
cout << res << endl;
}
跳石板
分析
题目就是要找个最短路径的长度，这里是个比较显然的bfs题。考虑每一步状态拓展，即找某个数的所有约数，这个问题可以在O(sqrt(num))复杂度完成。所以直接搜出答案即可。 时间复杂度：讲道理，这个时间复杂度真的不太会分析。不过感性的感觉这个可以跑得非常快。 实测了下10w范围内最大的转移步数是33，于是这个几乎就是一个log级的复杂度了。如果有巨巨能量化分析，请教教我。。
参考代码
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 130000;
int dst[maxn + 5], Q[maxn + 5], l, r;
int main(){
int m,n;
cin >> n >> m;
for(int i = 0; i < maxn; i++) dst[i] = -1;
l = r = 0;
Q[r++] = n; dst[n] = 0;
for(; l < r; l++){
int x = Q[l];
for(int i = 2; i * i <= x; i++){
if (x % i == 0){
if (x + i <= m && dst[x + i] == -1)
dst[x + i] = dst[x] + 1, Q[r++] = x + i;
if (x + x/i <= m && dst[x + x/i] == -1)
dst[x + x/i] = dst[x] + 1, Q[r++] = x + x/i;
}
}
}
cout << dst[m] << endl;
}
最大的奇约数
分析:
容易观察到：对于某个N，如果N为偶数那么最大奇数因子就变为f(N/2),如果N为奇数那么就是它本身。 对于1~N的： 如果N为奇数，我们可以得到： Sum = 1 + 3 + 5 + ....N + f(2) + f(4)+...+f(N-1). 其中最大的偶数项为f((N-1)/2). f(2) + f(4)+..f(N-1) = f(1) + f(2) + f(3) + f((N-1)/2)。这样我们原始问题的N就化为求解(N-1)/2的子问题. 如果N为偶数，我们可以得到: Sum = 1 + 3 + 5 + ....(N-1) + f(2)+ f(4) + ......+ f(N). 使用上面相同的方法，我们就把原始问题的N化为求解N/2. 其中 1 + 3 + 5 +.... +N = (N + 1) * (N + 1) / 2。 我们利用int类型的除法性质把奇偶统一可以写出比较简洁的代码 每次计算问题规模减半 时间复杂度：O(log(n))
参考代码:
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
long long n;
long long solve(long long n){
if(n == 0) return 0;
return (long long)( (n + 1) / 2) * ( (n + 1) / 2) + solve(n / 2);
}
int main(){
cin >> n;
cout << solve(n) << endl;
}#网易##Java工程师##C++工程师##iOS工程师#
查看5道真题和解析
