首页 > > 程序设计 > C/C++ >

2017年腾讯秋招软件开发笔试编程题回忆版

2018-06-17 21:55:13来源：未知阅读 ()

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

输出：

代码大致如下，正确性很难讲：

#include <iostream>

#include <vector>

#include <string>

#include <map>

#include <set>

#include <cstring>

#include <math.h>

#include <algorithm>