网易笔试十个编程题解题报告[0806]
题目练习地址 http://www.nowcoder.com/test/2252291/summary
感谢某牛客会员大神提供的解题报告
注意事项
- 题解覆盖所有岗位的编程题目,请对号入座
- 如果发现标程有严重BUG的,欢迎指出交流
- 标程都采用C++/C书写,使用java或者其他语言的同学可以对应思路和代码自己书写一遍
- 题解书写的顺序总体是根据难度递增的
解救小易
分析：
题目本质就是求一个距离(1,1)最小的一个曼哈顿距离,枚举一遍维护最小值即可
参考代码：
#include <bits/stdc++.h>
using namespace std;
int x[1005],y[1005];
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++) scanf("%d",&x[i]);
for(int i = 0; i < n; i++) scanf("%d",&y[i]);
int ans = 100000;
for(int i = 0; i < n; i++) {
ans = min(ans,x[i]+y[i]-2);
}
cout << ans << endl;
}
统计回文
分析：
枚举每个插入位置,把B插入A,然后check一下是否是回文,记录答案个数即可。
参考代码：
#include <bits/stdc++.h>
using namespace std;
bool check(string s){
int len = s.size();
for(int i = 0; i < len / 2; i++){
if(s[i] != s[len - i - 1]) return false;
}
return true;
}
int main(){
string a,b;
cin >> a >> b;
int ans = 0;
for(int i = 0; i <= a.size(); i++){
string tmp = a;
tmp.insert(i,b);
if(check(tmp)) ans++;
}
cout << ans << endl;
}
两种排序方法
分析：
分别对整个字符串数组分别进行check是否是根据两种排序排列,根据size和字典序的比较即可。
参考code:
#include <bits/stdc++.h>
using namespace std;
string s[1005];
int n;
bool check1(){
for(int i = 1; i < n; i++){
if(s[i].size() < s[i-1].size()) return false;
}
return true;
}
bool check2(){
for(int i = 1; i < n; i++){
if(s[i] < s[i-1]) return false;
}
return true;
}
int main(){
cin >> n;
for(int i = 0; i < n; i++) cin >> s[i];
if(check1() && check2()) printf("both\n");
else if(check1() && !check2()) printf("lengths\n");
else if(!check1() && check2()) printf("lexicographically\n");
else printf("none\n");
}
Fibonacci数列
分析：
参考Fibonacci数列的定义预处理出数列,然后枚举n所处的位置计算答案即可。
参考code:
#include <bits/stdc++.h>
using namespace std;
int dp[10005];
void init(){
dp[1] = 1;
for(int i = 2; i <= 10000; i++) dp[i] = dp[i-1] + dp[i-2];
}
int main(){
int n;
cin >> n;
init();
for(int i = 1; i <= 10000; i++){
if(dp[i] <= n && dp[i + 1] >= n){
printf("%d\n",min(n - dp[i],dp[i+1] - n));
break;
}
}
return 0;
}
小易喜欢的单词
分析：
因为字符串长度很小。对于题设不满足的情况直接暴力check一下即可。
参考code：
#include <bits/stdc++.h>
using namespace std;
string judge(string word){
string res[2] = { "Dislikes", "Likes" };
int n = (int)word.size();
for (int i = 1; i < n; i++){
if(word[i] == word[i - 1])return res[0];
}
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
for (int k = j + 1; k < n; k++){
for (int w = k + 1; w < n; w++){
if (word[i] == word[k] && word[j] == word[w]) return res[0];
}
}
}
}
return res[1];
}
int main(){
string s;
cin >> s;
cout << judge(s) << endl;
}
饥饿的小易
分析：
题目给了4 * x + 3 和 8 x + 7的转移状态,所求的又是"最小步数"含义的答案。很显然是一个BFS的模型,搜索的时候标记下状态和记录下步数,并且边搜边取mod防止溢出。
参考code:
#include <bits/stdc++.h>
using namespace std;
typedef long long llint;
const llint MOD = 1000000007LL;
queue<llint> q;
map<llint, int> vis;
int solve(int x0){
vis.clear();
vis[x0] = 1;
q.push(x0);
while(!q.empty()){
llint c = q.front(); q.pop();
if(c == 0) return vis[c]-1;
if(vis[c] >= 100001) continue;
if(!vis[(4LL * c + 3) % MOD]) {
vis[(4LL * c + 3) % MOD] = vis[c] + 1;
q.push((4LL * c + 3 ) % MOD);
}
if(!vis[(8LL * c + 7) % MOD]) {
vis[(8LL * c + 7) % MOD] = vis[c] + 1;
q.push(( 8LL * c + 7 ) % MOD);
}
}
return -1;
}
int main(){
int x0;
cin >> x0;
cout << solve(x0) << endl;
}
数字游戏
分析:
考虑这道题n的范围只有20,我们就枚举数字集合的所有子集复杂度是2^(20),然后类似背包的思路把每个数字当做一个物品,去枚举出所有可能的数字,我这里为了方便是直接丢进set,然后去查找最小没有在set里面的数。 PS: 1、据说有人暴力乱搞拿了60分 2、有人排序之后边枚举可能的值边维护是否是最小的写法,这种写法可能得到答案速度会很快。
参考code:
#include <bits/stdc++.h>
using namespace std;
int n;
int a[25];
int solve(){
int sum;
set<int> S;
for(int i = 1; i < (1<<n); i++){
sum = 0;
for(int j = 0; j < n; j++){
if(i & (1<<j)){
sum += a[j];
}
}
S.insert(sum);
}
int i = 1;
while(true){
if(S.find(i) == S.end())return i;
i++;
}
}
int main(){
cin >> n;
for(int i = 0; i < n; i++) scanf("%d",&a[i]);
cout << solve() << endl;
return 0;
}
不要二
分析：
参考code:
C++
#include <bits/stdc++.h>
using namespace std;
int ms1(int w, int h) {
return (w * h + 1) / 2;
}
int main(){
int w,h;
cin >> w >> h;
cout << ms1(w/2, h/2) +
ms1((w+1)/2, (h)/2) +
ms1((w+1)/2, (h+1)/2) +
ms1((w+0)/2, (h+1)/2) << endl;
}
C++
#include <bits/stdc++.h>
using namespace std;
int main(){
int w, h, ans = 0;
cin >> w >> h;
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
if( (i / 2 + j / 2) % 2 == 0)
ans++;
}
}
cout << ans << endl;
}
幸运的袋子
分析：
这个题目主要需要想到满足幸运的袋子其实不是很多的。 我们考虑这个袋子里面已经有一些元素了,我们增加一个元素'1'不会影响乘积,但是和值增加了。但是一旦我们尝试加入大于'1'的值进去,能满足的可能就越来越小了。
下面粗略证明下： 加入"1"肯定对于答案贡献是好的。我们先考虑在1000个里面放入"1"和最小不是"1"的数2,分别设个数为x,y;于是就有以下一些关系： x + y = 1000 x + 2 y > 2 ^ y => (1000 - y) + 2 y > 2 ^ y 1000 + y > 2 ^ y => 最大满足的y就是9.含义就是最多可以有9个大于"1"的数在袋子里 类似的我们考虑'3'。解 1000 + y > 3 ^ y 得 y最大为6.含义就是最多可以有6个大于"2"的数在袋子里 ......... 最终我们推到 最多只有一个大于"31"的数在袋子里。。。
我们只有幸运袋子的个数不多只能说明解空间很小,但是搜索空间依然很大,我们需要进行合理的剪枝。 首先对所有球进行一个排序,考虑一个当前球x[i]是否放入,如果当前的和为s,当前的积为p。 考虑当’p * x[i] > s + x[i]‘,剩下的球都是大于x[i]的时候,这就是一个停止回溯的好地方,我们先预处理保持这些位置,然后搜索的时候进行剪纸处理。细节参考代码
PS:纯暴力搜也是可以20分左右的
参考代码:
C++
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
std::vector<int> num;
std::vector<int> val;
int n;
int nxt[1005];
int dfs(int i, int s, int p){
if(i >= n) return s > p;
if(val[i] > 1 && s < p) return 0;
return dfs(i + 1, s + val[i], p * val[i]) + dfs(nxt[i], s, p);
}
int solve(){
val = num;
int p = n;
for(int i = n - 1; i >= 0; i--){
if(i < n - 1 && val[i + 1] > val[i]) p = i + 1;
nxt[i] = p;
}
return dfs(0, 0, 1);
}
int main(){
scanf("%d",&n);
for(int i = 0; i < n; i++){
int x; scanf("%d",&x);
num.push_back(x);
}
sort(num.begin(),num.end());
cout << solve() << endl;
}
混合颜色
分析：
然后来解释一下样例： 你可以购买1，2，4这三种颜料，1已经有了，3可以通过由 1 XOR 2 = 3得到，7可以通过1 XOR 4 = 5，5 XOR 2 = 7 得到，所以最少为3种
想象一下对于两个给定的数(向量),他们可以生成的新的数,本质就是两个向量的所有线性表示。因为此处实际是在做一个mod 2的操作,那么线性表示的系数就是0或1。 于是原问题就抽象为,给定一些向量(数)组成的向量空间,增加一个最小的向量集合,使向量的线性组合都可以生成向量空间中的所有向量。这个叫做向量空间的基。
怎么算出这个基呢？线性代数里面我们都学过：可以对原来所有向量组成的矩阵用高斯消元法直到让剩余的向量都是线性无关的,非0向量的个数就是答案。
参考code:
#include <bits/stdc++.h>
using namespace std;
int n;
int colors[55];
int a[105][70];
int equ,var = 31;
void ini() { memset (a, 0, sizeof(a)); }
int Gauss(){
int i, j, k;
int col = 0;
for (k = 0; k < equ && col <= var; k++, col++){
for (i = k; i < equ && !a[i][col]; i++);
if (i == equ){
k--;
continue;
}
for (j = 0; j <= var; j++) swap (a[i][j], a[k][j]);
for (i = 0; i < equ; i++){
if (i == k || !a[i][col]) continue;
for (j = col; j <= var; j++) a[i][j] ^= a[k][j];
}
}
return k;
}
int minColors(){
ini();
int x,i;
equ = n;
for (i = 0; i < equ; i++){
x = colors[i];
int k = 31;
while(x){
a[i][k--] = (x&1);
x >>= 1;
}
}
return Gauss ();
}
int main(){
cin >> n;
for(int i = 0; i < n; i++) scanf("%d",&colors[i]);
cout << minColors() << endl;
}