Open youngyangyang04 opened 3 months ago
每日一爱carl
java的第一种方法超时呜呜呜
Go的写法超出了时间限制
java 第一种每次递归全遍历搜索直接撞官方枪口上了,第二种map简化搜索就不超时了。。
这里对目标机场的排序是如何什么操作的?
虽然不精通c++, 但是感觉这个没有排序呢,只是找出一个符合条件的。而且backtracing在testcase 80超时了
用Java的Collection的排序耗时多
class Solution
{
public:
int ticketNum = 0;
// 门票信息包括始发地,目的地,数量,且目的地要按照字母顺序,故选择map
// 始发地 目的地 机票数量
unordered_map<string, map<string, int>> targets;
vector
// 因为只要一个结果 所以返回值设置成bool即可
bool backtracking()
{
// 终止条件,result的size等于总票数+1
if (result.size() == ticketNum + 1)
{
return true;
}
// 记录当前所在地
string current = result.back();
// 因为是unorder_map 所以可以直接索引到当前所在地
for (auto it = targets[current].begin(); it != targets[current].end(); it++)
{
// 遍历到排序最靠前且有票的目的地
if (it->second != 0)
{
// 将目的地加入结果集,并且去除该机票
result.push_back(it->first);
it->second--;
// 回溯遍历该路线
if (backtracking())
{
return true;
}
// 该路线探寻失败,弹出该目的地,恢复机票数量
result.pop_back();
it->second++;
}
}
return false;
}
vector<string> findItinerary(vector<vector<string>> &tickets)
{
// 记录总票数
ticketNum = tickets.size();
// 构建unordered_map记录所有机票信息
for (int i = 0; i < tickets.size(); i++)
{
targets[tickets[i][0]][tickets[i][1]]++;
}
// 起始机场
result.push_back("JFK");
backtracking();
return result;
}
}; 斗胆贴一下自己的权当抛砖引玉
不明白,好像只看到了深度搜索,不需要回溯吗?比如一条路走不通得回头的情况似乎没有考虑进去?
不太理解为什么这样子的就是返回最小的行程组合
https://www.programmercarl.com/0332.%E9%87%8D%E6%96%B0%E5%AE%89%E6%8E%92%E8%A1%8C%E7%A8%8B.html