关键词：
2017年腾讯秋招软件开发笔试编程题回忆版
（所有题目大致描述如下，并非完整的题目回忆，但意思大致一样）
1、又一个魔法城市，城市里面有n个魔法城堡，序号为0，1，2。。。n-1；魔法城堡之间都有路径相连；魔法城堡两两之间的到达的距离不同，因此所需时间也可能不会相同。如魔法城堡0到魔法城堡2需要耗时4小时；现，小明想从魔法城堡0到魔法城堡1，他想知道需要花费多少时间；为了快速到达，有一魔法扫把，魔法扫把使用次数有限，使用一次，可以将某一段间的时间减半；求小明从魔法城堡0到魔法城堡1花费的最小时间，精确到一位小数。
输入：总共n+1行；
第一行，魔法城堡数n；魔法扫把能够使用的次数k；
第二行到第n行为魔法城堡之间到达需要的时间；
输出：从魔法城堡0到魔法城堡花费的最短时间：t，精确到小数点后一位。
示例：
输入：
3 2
094
904
440
（注：腾讯这里输入的094，904，440，是以字符串的形式输入的）
输出：
4.0
个人大致思路：
利用Dijkstra最短路径求法；记录到魔法城堡1的最短路径上每一个前驱节点和对应的距离；然后对每段的距离进行降序排序；之后把魔法扫把使用在所耗时最多的段中。如0到1的最短路径为0到2，消耗为4；2到1消耗为3；魔法扫把能使用1次；那么把这一次机会使用在0到2这一段路径上；那么最后最短时间即为：2+3=5.0；
代码实现为：
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cstring>
#include <math.h>
#include <algorithm>
using namespace std;
#define MIN 99999
vector<int> dijkstra_shortpath(vector<vector<int>> arcs, int ednode)
{
int size = arcs.size();
vector<int> dist(size); //保存当前最短路径
vector<int> path(size); //保存前驱节点
vector<int> S(size); //保存已经找到最短路径的节点
//初始化
for (size_t i = 0; i < size; i++)
{
dist[i] = arcs[0][i];
S[i] = 0;
path[i] = 0;
}
S[0] = 1, path[0] = -1;
//进行循环更新每次遍历每个节点的最短路径长度
for (int i = 1; i < size; i++)
{
int nmin = MIN, mi = 1;
for (int j = 1; j < size; j++)
{
if (!S[j] && dist[j] < nmin)
{
mi = j;
nmin = dist[j];
}
}
cout << "min index=" << mi << "; paht="<<nmin << endl;
S[mi] = 1;
//更新每个节点的最短路径长度
for (int j = 1; j < size; j++)
{
if (!S[j] && dist[mi] + arcs[mi][j] < dist[j])
{
dist[j] = dist[mi] + arcs[mi][j];
path[j] = mi; //保存节点j最短路径的前驱mi
}
}
}
//输出每个节点的
for (int i = 0; i < size; i++)
{
cout << "[pre=" << path[i] << ",len=" << dist[i] << "]; ";
}
cout << endl;
vector<int> res;
while (path[ednode] != -1)
{
res.push_back(arcs[path[ednode]][ednode]);
cout << "[pre=" << path[ednode] << ";len=" << arcs[path[ednode]][ednode] << "];";
ednode = path[ednode];
}
cout << endl;
return res;
}
int main(int argc,char **argv)
{
int n = 0, k = 0;
vector<int> res;
while (cin >> n>>k)
{
vector<vector<int>> nodes;
string path;
for (int i = 0; i < n; i++)
{
cin >> path;
vector<int> node(n);
for (int i = 0; i < n; i++)
node[i] = path.at(i) - ‘0‘;
nodes.push_back(node);
}
res = dijkstra_shortpath(nodes, 1);
sort(res.begin(), res.end());//默认是升序遍历
int sum = 0;
for (int i = res.size() - 1; i >= 0; i--)
{
if (k > 0)
{
sum += res[i] / 2;
k -= 1;
}
else sum += res[i];
}
cout << "min cost time=" << sum << endl;
}
return 0;
}
运行效果下图所示：
2、小明有很多枚硬币，每一枚银币的面值均为2的k次方，并且该类硬币的数量均为2枚；也即是他的硬币的序列是：1，1，2，2，4，4，8，8。。。；现在他去超市买东西，需要支付总额为n；问他有多少种支付方式，也即是有多少种硬币的组合的和为n；（腾讯给的示例，想不起来了）
个人大致思路是：利用图的深度优先遍历来做这道到，该过程得出的结果肯定有一部分结果是重复的，则需要去重；暂时未想到其他很好的办法。
代码实现如下：
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cstring>
#include <math.h>
#include <algorithm>
using namespace std;
vector<int> res;
int get_cnt(int depth, int cur_sum, int target, set<vector<int>>& sres)
{
if (cur_sum == target)
{
vector<int> tmp;
for (int i = 0; i < res.size(); i++)
{
tmp.push_back(res[i]);
cout << res[i] << ", ";
}
cout << endl;
sres.insert(tmp);
return 1;
}
if (cur_sum > target ) return 0;
for (int i = depth; i < target * 2; i++)
{
cur_sum += pow(2, (i / 2));
res.push_back(pow(2, (i / 2)));
//cout << "push tms = " << i << "; sum = " << cur_sum << endl;
get_cnt(i + 1, cur_sum, target, sres) ? 1 : 0;
res.pop_back();
cur_sum -= pow(2, (i / 2));
//cout << "popo tms = " << i << "; sum = " << cur_sum << endl;
}
return 0;
}
int main(int argc, char **argv)
{
int target = 0;
while (cin >> target)
{
set<vector<int>> sres;
get_cnt(0, 0, target, sres);
cout <<"set size = " << sres.size() << endl;
}
return 0;
}
运行效果下图所示：（注：set size，即为组合情况数）
3、这道编程大体大致是这么描述的，有一台魔法机器，机器上有两个按钮；机器的运算方式是：一次输入两个数字；两个数字根据按下不同的进行同时进行相同的操作。规则如下：红色按钮：按下则两个数，分别同时加1；蓝色按钮按下：两个数分别同时*2。现在小明想知道，他有两个数，和与之对应的目标数，分别记为a，b，A，B；经过多少次按钮操作能够把a变成A；的同时b变成B；输出按钮操作的最少次数；如果不能则输出-1。
示例输入：
100 1000 202 2002
输出：
2
代码大致如下，正确性很难讲：
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cstring>
#include <math.h>
#include <algorithm>
using namespace std;
int get_opera_cnt(int a, int A)
{
int cnt = 0;
if (A % 2 == 1) //把它变成偶数
{
A -= 1; //表示红色按钮按一次
cnt += 1;
}
if (A / 2 >= a)
{
while (A % 2 == 0 && A / 2 >= a)
{
cnt += 1;
A = A / 2; //表示蓝色按钮按一次
}
cnt += (A - a);//表示红色按钮按（A-a）次
}
else
cnt += (A - a);//表示红色按钮按（A-a）次
return cnt;
}
int main(int argc, char **argv)
{
int a, b, A, B;
while (cin >> a >> b >> A >> B)
{
int acnt = get_opera_cnt(a, A);
int bcnt = get_opera_cnt(b, B);
cout << "acnt=" << acnt << "; bcnt=" << bcnt << "; opera tms=";
if (acnt == bcnt)cout << acnt << endl;
else cout << -1 << endl;
}
return 0;
}
运行结果如下：（自己调试用的，未按标准输入输出，自行更正）
（以上仅供交流，勿喷；本人在规定时间内，未写出这几道题的答案，(┬＿┬)??）
美团点评2017秋招笔试编程题(代码片段)
C/C++代码1：#include<cstdio>#include<iostream>#include<math.h>intmain()intn;while(scanf("%d",&n)!=EOF)doubleresult=pow(2,n-1);//2的n-1次方printf("%d\n",int(result));return0;C/C++代码 查看详情
腾讯2018年9月秋招前端笔试题--编程题
varreadline=require(‘readline‘);constrl=readline.createInterface({input:process.stdin,output:process.stdout});constlines=[];rl.on(‘line‘,function(line){lines.push(line);constarr=lines.map((item)=>{ 查看详情
2017年9月秋招记录--持续更新
一、腾讯校招提前批（一面跪）二、网易内推（笔试跪）三、今日头条（免笔试，二面跪）四、蘑菇街（免笔试，一面跪）五、好未来（免笔试，一面跪）六、360（笔试跪）七、大疆（笔试跪）八、美团（笔试等通知）九、百度... 查看详情
美团点评2017秋招笔试编程题——大富翁游戏
大富翁游戏，玩家根据骰子的点数决定走的步数，即骰子点数为1时可以走一步，点数为2时可以走两步，点数为n时可以走n步。求玩家走到第n步（n<=骰子最大点数且是方法的唯一入参）时，总共有多少种投骰子的方法。 输... 查看详情
两道经典算法题-吉比特2017秋招笔试
阅读目录求素数最大差值回到顶部求素数输入M、N，1<M<N<1000000，求区间[M,N]内的所有素数的个数。素数定义：除了1以外，只能被1和自己整除的自然数称为素数输入描述:两个整数M，N输出描述:区间内素数的个数示例1输入210... 查看详情
腾讯2017暑假实习生-软件开发类笔试
和意料之中差不多，因为自己搞的PHP方向，前几个学期专业课没好好学，期末都是低分飘过...牛客刷的也不多，所以做得很一般。总结一下：1.选择题30题：数据结构5道左右，数据库3道左右，C++10道左右，操作系统5道左右，算法... 查看详情
链家秋招内推编程笔试题目
参加8.19的链家内推笔试，总体来说题目难度不大，20个选择题还有三道编程题。选择题，里面有两道关于IP地址计算的题目，有点忘了，不知道最后的计算有没有问题，所以还需要复习学习完的知识，因为不知道什么时候就会遇... 查看详情
字节秋季笔试四道编程题（2021-09-12）(代码片段)
通知：最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在【TechGuide】了，私信公众号回复【美团】或者【百度】即可获得最实时的笔试题解啦！通知：最新的秋招笔试编程题题目、思路以及参考... 查看详情
2020年腾讯/网易/字节春招秋招面试记录
2020年腾讯/网易/字节春招秋招面试记录在3月初开始忙着找实习，投了挺多公司，参加各种笔试，面试。后来实习没去，准备考研，秋招就随意投了网易和腾讯，没想到突然收到网易offer，便放弃考研，记录下半年来的面试经历。... 查看详情
网易2017秋招编程题集合-牛客网
网易2017秋招编程题集合-牛客网 链接：https://www.nowcoder.com/questionTerminal/0147cbd790724bc9ae0b779aaf7c5b50来源：牛客网如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如：{1,2,1},{15,78,78,15... 查看详情
网易秋招校招编程题(代码片段)
网易内推面试凉了，再战正式批笔试，选择和简答略难，编程题很良心，基本就是模拟、找规律，略加思考就能解出来的题目，本弱鸡只有在良心网易笔试才能AK。1、翻转翻转 这题一开始没思路，ac了后两题后再回... 查看详情
2014年腾讯实习生笔试题解析
本答案是我自己搜索资料解答出来，假设不正确敬请指出1、使用深度优先算法遍历下图。遍历的顺序为（C）AABCDEFGBABDCFEGCABDECFGDABCDFEG解析:深度优先遍历相似于树的前序遍历，其基本思想为：(1).訪问顶点v;(2).从v的未被訪问的邻... 查看详情
微软2017年预科生计划在线编程笔试第二场diligentrobots
模拟。不断分裂，然后计算时间，取个最小值。我也不知道这做法对不对的，读完题猜了一下，抱着$WA$的心态$submit$了，然后跳出一个$AC$。#include<bits/stdc++.h>usingnamespacestd;longlongn;intq;intmain(){scanf("%lld%d",&n,&q);longlongnow=1;... 查看详情
网易2017秋招编程题——回文序列解题报告
Problem:https://www.nowcoder.com/question/next?pid=2811407&qid=46573&tid=6015849如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如：{1,2,1},{15,78,78,15},{112}是回文序列,{1,2,2},{15,78,87,51},{112,2,11}不是回文序列。... 查看详情
华为2018软件岗笔试题解题思路和源代码分享
2017年9月26日，参加了华为技术有限公司的笔试，题目类型是软件题，没有选择填空问答类型，总共是3道编程题目，题目难度适中，在两个小时内完成3道题目的AC，所以分享的代码都是可运行且完全AC的! 和广大网友分享... 查看详情
腾讯测试工程师笔试体会
时间：2016年9月10日笔试题目：25道多选题（限时60分钟）+25道填空题（限时60分钟）1.多选题涉及数据结构、操作系统、计算机网络、C语言、软件工程、安卓、C++相关类型的题目2.填空题及数据结构、操作系统、计算机网络、C语... 查看详情
hihocoder1489legendaryitems（微软2017年预科生计划在线编程笔试）
http://hihocoder.com/problemset/problem/1489 笔试题第一道，虽然说第一道都很水，但是我感觉这题不算特别水把。。这道题我就卡住了我记得，tle，最后只有30分，比较惨烈。我个人感觉这道题正解比较难想把，那时候太年... 查看详情
腾讯秋招笔试真题(代码片段)
题解：从a中拿i首的个数* 从b中拿j首的个数难点：排列组合，主要用二维数组来模拟计算组合数C(n,m) #include<iostream>#include<cstdio>usingnamespacestd;/*题解：从a中拿i首的个数*从b中拿j首的个数难点：排列组合，主要用... 查看详情