面试刷题：查找阈值距离内邻居最少的城市 Q1334
Leetcode解题或者面试刷题有时会需要储备一些已有的算法思想，而不全是凭借临场发挥。因为有些问题如果不是记住了对应解决思路，在短时间内是很难或者说基本不太可能凭经验试探出来的。比如最短路径的问题，学习过《数据结构与算法》的朋友可能会记得dijkstra算法和floyd算法。而这两种算法是目前解决这类问题时最高效的，也是事实上公认的标准算法。这里就借助 Leetcode Q1334问题简要谈一谈。
1. 题目 Q1334 查找阈值距离内邻居最少的城市
有$n$个城市，编号从$0$到$n-1$。给定数组边，其中 edge[i] = [$from_i$，$to_i$，$weight_i$] 代表城市 $from_i$ 和 $to_i$ 之间的双向和加权边，并给出整数 distanceThreshold。返回通过某些路径可到达且距离最大为distanceThreshold的城市数量最少的城市，如果有多个这样的城市，则返回编号最大的城市。
请注意，连接城市i和j的路径的距离等于沿该路径的边权重之和。
约束条件：
- (a) 2 <= n <= 100
- (b) 1 <= edges.length <= n * (n - 1) / 2
- (c) edges[i].length == 3
- (d) 0 <= $from_i$ < $to_i$ < n
- (e) 1 <= $weight_i$, distanceThreshold <= $10^4$
- (f) 所有点对 (fromi, toi) 是不重复的.
示例1
Input: n = 4,
edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]],
distanceThreshold = 4
Output: 3
解释： 上方图片描述了一个Graph。对任何一个城市满足distanceThreshold = 4要求的城市如下：
City 0 -> [City 1, City 2]
City 1 -> [City 0, City 2, City 3]
City 2 -> [City 0, City 1, City 3]
City 3 -> [City 1, City 2]
城市0和城市3都有两个邻居满足要求，但是我们必须返回城市3，因为它在符合基本要求的情况下，编号最大。
示例2
Input: n = 5,
edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]],
distanceThreshold = 2
Output: 0
解释： 上图描述了输入的Graph。对任何一个城市满足distanceThreshold = 2要求的城市如下：
City 0 -> [City 1]
City 1 -> [City 0, City 4]
City 2 -> [City 3, City 4]
City 3 -> [City 2, City 4]
City 4 -> [City 1, City 2, City 3]
城市0 有一个邻居，并满足基本要求。
2. 解题思路
乍一看这题目还挺吓人，描述长、要求多，还涉及到Graph。但真正的要求其实就只有两个：
(1) 找到要求距离内的邻居；
(2) 返回邻居最少的城市编号。
事实上，难点就在第一个要求，即指定距离内的邻居。这个要求的表述与“最短路径”存在一些差异，导致很多朋友难以联想到使用“最短路径”算法来解决。如果将这个要求翻译成以下表述就清晰多了：
找到与邻居最短距离在要求数值之内的城市
对于那些求解指定起点到指定重点之间距离的问题，可以使用dijkstra算法；但对于这种求解一个点集的任意两点之间的最短距离，应当使用floyd算法。
3. Floyd算法基本流程
使用伪代码表述的Floyd算法如下：
Input: edges, n x 3, [start, end, distance]
Initialize: dist, n x n, MAX_NUM
------------------------------
Step1: dist = fill_edges(edges)
Step2: for i in range(0, n):
for j in range(0, n):
for k in range(0, n):
if j == k :
continue
d = dist[j][i] + dist[i][k];
if dist[j][k] > d:
dist[j][k] = d;
-----------------------------
Output: dist
最终得到dist数组中的第i行第j列就存储着城市i到城市j的最短距离。如果还想得到最短距离的具体路径，那么在以上算法流程的基础上，还需要记录更多的信息，比如，生成当前最短距离的父节点。在解决当前这个问题时倒是不需要那么复杂。从算法描述来看，Floyd算法的时间复杂度是$O(n^3)$。虽然比我们日常处理其他问题的复杂度高，但这已经是目前最快的算法了。
4. C++解决方案
以下给出具体的C++解决方案。
class Solution {
private:
const static int _max_node = 100;
const static int _max_num = 100000000;
int _dist[_max_node][_max_node];
void _init_dist(vector<vector<int>> & edges) {
// fill with the biggest number
for (int i=0; i<_max_node; ++i) {
for (int j=0; j<_max_node; ++j) {
_dist[i][j] = _max_num;
}
}
// fill i->j and j->i
for (auto & vec : edges) {
_dist[vec[0]][vec[1]] = vec[2];
_dist[vec[1]][vec[0]] = vec[2];
}
}
void _floyd(const int & n) {
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
for (int k=0; k<n; ++k) {
if (j == k) {
continue;
}
int d = _dist[j][i] + _dist[i][k];
if (_dist[j][k] > d) {
_dist[j][k] = d;
}
} // end of for k
} // end of for j
} // end of for i
}
public:
// Runtime: 32 ms, faster than 98.37%
// Memory Usage: 11.4 MB, less than 100.00%
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
_init_dist(edges);
_floyd(n);
int min_cnt = _max_num, tmp_cnt = 0;
int min_id = 0;
for (int i=0; i<n; ++i) {
tmp_cnt = 0;
for (int j=0; j<n; ++j) {
if (_dist[i][j] <= distanceThreshold) {
++tmp_cnt;
}
}
if (min_cnt >= tmp_cnt) {
min_cnt = tmp_cnt;
min_id = i;
}
}
return min_id;
}
};
从Leetcode上的评测来看，当前解决方案已经超过了98%的提交，应该来说算是一个不错的解决方案。试想，如果我们没有记住Floyd算法，那么在临场发挥的时候能够想的出来这其中复杂的逻辑吗？当然不排除有个别的天才，但是对于面试而言，还是谨慎稳重一点比较靠谱。那么积累一些业内公认的标准算法还是很必要的。
COMMENT
博客评论区功能由Github Issue提供，提交Issue时请以本文标题为话题。
"BG82-面试刷题：查找阈值距离内邻居最少的城市 Q1334"