在做 [leetcode:332.重新安排行程] 这道题时，遇到了一个问题，找到原因之后发现是个之前在《C++ Primer》上看过但没在实践中遇到过，所以没放心上的问题，记一下。
我的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
vector<string> result;
int ticketsNum;
// unordered_map<出发机场, map<到达机场, 航班次数>>
unordered_map<string, map<string, int>> targets;
bool backtracking(string start){
if(result.size() == ticketsNum + 1){
return true;
}
for(auto target : targets[start]){
if(target.second > 0){
result.push_back(target.first);
target.second--;
if(backtracking(target.first))return true;
result.pop_back();
target.second++;
}
}
return false;
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
ticketsNum = tickets.size();
for (auto& ticket : tickets) {
targets[ticket[0]][ticket[1]]++;
}
result.push_back("JFK");
backtracking("JFK");
return result;
}
};
- 输入：[[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]]
- 输出：[“JFK”,”ATL”,”JFK”,”ATL”,”JFK”,”ATL”]
- 正确答案：[“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]
原因是L12处应为：for(auto& target:targets[start])，少了一个引号。
- 使用for(auto target : container)进行遍历时，会拷贝容器中的元素，修改target不会影响到原始容器中的元素。
- 使用for(auto& target : container)进行遍历时，使用引用直接访问容器中的元素，修改target会直接影响到原始容器中的元素。
原先没有使用引用，所以target.second--时并没有修改到targets中相应的内容。
