算法分析课程博客分享 7

发表于 | 分类于

算法分析课程博客分享 7

513. 找树左下角的值(Find Bottom Left Tree Value)

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:
输入:
    2
   / \
  1   3
输出:
1

示例 2:
输入:
        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7
输出:
7

注意: 您可以假设树（即给定的根节点）不为 NULL。

解题思路:
考虑到这周末还要考托福，手上还握着好几个 deadline，这个礼拜就做一下水题吧。尽管这是一道中等难度的题目，但很显然，我们要获得树的最后一行就需要用到层次遍历。我们使用队列即可实现树的层次遍历，而最后一行最左边的值即遍历到最后一行时，队列中的第一个值。因此，我们很轻松就可以写出以下代码： 

int findBottomLeftValue(TreeNode* root) {
    queue<TreeNode*> q{ {root} };
    int ans = 0;
    while (!q.empty()) {
        ans = q.front()->val;

        int size = q.size();
        for (int i = 0; i < size; ++i) {
            TreeNode* cur = q.front();
            q.pop();
            if (cur->left != NULL) {
                q.push(cur->left);
            }
            if (cur->right != NULL) {
                q.push(cur->right);
            }
        }
    }

    return ans;
}


787. K 站中转内最便宜的航班(Cheapest Flights Within K Stops)

有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。

示例 1:
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释:
城市航班图如下
从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。

示例 2:
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释:
城市航班图如下
从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。

提示：

  • n 范围是 [1, 100]，城市标签从 0 到 n - 1.
  • 航班数量范围是 [0, n * (n - 1) / 2].
  • 每个航班的格式 (src, dst, price).
  • 每个航班的价格范围是 [1, 10000].
  • k 范围是 [0, n - 1].
  • 航班没有重复，且不存在环路

解题思路:
这道题目虽然是求加权图的最短路径，但是题目限制了可以经过的节点的数目，因此，直接套用 Dijkstra 等算法貌似不太可行。考虑到这一点，我们可以遍历所有节点数小于等于 K 的路径，然后求出最短的加权路径。题目给出的 flights 数组是若干乱序的加权边，故应用 DFS 或 BFS 前，我们需要先做一个预处理，将 flights 数组转换为一个邻接列表。接下来，我们使用队列进行广搜，我们将节点储存为 (index, cost) 的形式，同时，我们用一个整型变量 cost 来记录最便宜的路线。我们分层来进行遍历，对于每一层的节点，我们检测与它们相连的节点，若当前节点与 dst 相连，我们将更新 cost 的值，否则，我们将总价格小于 cost 的线路放进队列中。注意，如果我们往队列中放入新节点时，不筛选掉价格大于等于 cost 的线路，我们的内存将超过限制，具体代码如下： 

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
    vector<vector<pair<int, int>>> edges(n, vector<pair<int, int>>());
    for (vector<int> e : flights) {
        edges[e[0]].push_back(make_pair(e[1], e[2]));
    }

    queue<pair<int, int>> q{ {make_pair(src, 0)} };        
    int cost = INT_MAX;
    for (int i = 0; !q.empty() && i <= K; ++i) {
        int size = q.size();
        for (int j = 0; j < size; ++j) {
            pair<int, int> u = q.front();
            q.pop();
            for (pair<int, int> e : edges[u.first]) {
                if (e.first == dst) {
                    cost = min(cost, u.second+e.second);
                } else if (cost > u.second+e.second) {
                    q.push(make_pair(e.first, u.second+e.second));
                }
            }
        }
    }

    return (cost == INT_MAX) ? -1 : cost;
}


虽然上述的算法效率已经不错，但在查阅资料后，我发现了一种更巧妙的基于 Bellman Ford 的解法。其中，我们用 1e9 来表示距离为无穷，不使用 INT_MAX 是为了防止进行加法后超出数据类型的范围。由于每次循环都要遍历所有的边，这个算法会比上述的要稍慢，具体代码如下： 

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
    vector<int> dist(n, 1e9);
    dist[src] = 0;
    for (int i = 0; i <= K; ++i) {
        vector<int> tmp = dist;
        for (vector<int> f : flights) {
            tmp[f[1]] = min(tmp[f[1]], dist[f[0]]+f[2]);
        }
        dist = tmp;
    }

    return (dist[dst] >= 1e9) ? -1 : dist[dst];
}


815. 公交路线(Bus Routes)

我们有一系列公交路线。每一条路线 routes[i] 上都有一辆公交车在上面循环行驶。例如，有一条路线 routes[0] = [1, 5, 7]，表示第一辆 (下标为0) 公交车会一直按照 1->5->7->1->5->7->1->… 的车站路线行驶。

假设我们从 S 车站开始（初始时不在公交车上），要去往 T 站。 期间仅可乘坐公交车，求出最少乘坐的公交车数量。返回 -1 表示不可能到达终点车站。
s

示例:
输入:
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
输出: 2
解释:
最优策略是先乘坐第一辆公交车到达车站 7, 然后换乘第二辆公交车到车站 6。

说明:

  • 1 <= routes.length <= 500.
  • 1 <= routes[i].length <= 500.
  • 0 <= routes[i][j] < 10 ^ 6.

解题思路:
本想着用 Dijkstra 或 Bellman Ford 算法来求解，但仔细思考过后，发现这道题的本质是一个无权图，因此仅需用广搜即可求解。题目的难点在于给出的 routes 的存储格式并不是我们所熟悉的邻接列表之类的，而是每一辆公交的线路，故我们需要先对 routes 进行预处理。最简单的思路是计算一个 src 到 dst 的邻接列表，其中，每条路径的长度皆为 1。但是，在这道题中，bus stop 的数目最多为 1e6 个，计算上述的邻接列表会导致在部分复杂的用例中超出内存限制，所以我们只能生成一个 src 与 bus 的邻接列表，代表经过某个车站的所有公交车。接下来，我们只需要简单地套用分层的广搜算法即可获得最短路径。然而，考虑到邻接列表的储存格式，我们需要在遍历 routes[bus] 才可以获得从 src 搭乘 bus 能到达的所有车站。这种操作显然会导致超时或超出内存限制，因此，我们需要记录下去过的车站与搭乘过的公交车，以确保我们不会重复访问去过的车站或搭乘过的公交车。这里，为了节省空间的使用，我使用了一个比较 tricky 的办法，当遍历完一条公交线路时，我们将把这条线路删除以避免重复访问，当遍历完一个车站时，我们将把这个车站删除以避免重复访问。当然，这个操作也可以通过一个 visited 数组来替代，只是会造成多一点的内存开销。具体代码如下： 

int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
    if (S == T)
        return 0;

    unordered_map<int, unordered_set<int>> path;
    for (int i = 0; i < routes.size(); ++i) {
        for (int src : routes[i]) {
            path[src].insert(i);
        }
    }

    queue<int> q{ {S} };
    int dist = 1;
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            int src = q.front();
            q.pop();
            for (int bus : path[src]) {
                for (int dst : routes[bus]) {
                    if (dst == T)
                        return dist;
                    q.push(dst);
                }
                routes[bus].clear();
            }
            path[src].clear();
        }
        ++dist;
    }

    return -1;
}