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