阿里外包背调的时候offer黄了。|差值|最大值|算法|绝对值|起始点|队列|阿里巴巴集团

最近一网友发文称自己收到阿里外包的offer，因为自己有三份工作经历，简历上合并成两份了，结果背调的时候导致offer黄了。现在外包要求都这么高了吗，我印象中外包是只查学历的，现在还要查个税记录。

有时候跳槽也不一定是自己的原因，现在公司裁员倒闭都很正常，如果由于裁员导致有多份工作经历，简历不合并的话，HR可能会认为跳槽太频繁，不稳定，简历筛选的时候直接给pass，连面试的机会都没有，但如果合并，即便面试过了，背调也可能被卡，确实很难。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第1631题：最小体力消耗路径，难度是中等。

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往上，下，左，右四个方向之一移动，你想要找到耗费体力最小的一条路径。

一条路径耗费的体力值是路径上相邻格子之间高度差绝对值的最大值决定的。请你返回从左上角走到右下角的最小体力消耗值。

示例1：

输入：heights = [[1,2,2],[3,8,2],[5,3,5]] 输出：2 解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。

示例2：

输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]] 输出：0 解释：上图所示路径不需要消耗任何体力。

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10^6

问题分析

这题说的是从左上角到右下角找到一条路径，使得路径上相邻两个位置的最大绝对值最小，描述可能有点绕，换句话说就是从左上角到右下角，会有很多路径，每条路径中都会有一个最大的高度差，返回所有路径中这个高度差最小的值即可。

我们需要使用一个优先队列，记录每个点的坐标和到上一个位置差的绝对值，优先队列中的元素按照绝对值大小排序。然后从起始点开始，沿着每个点的上下左右四个方向搜索，把搜索的点添加到优先队列中，顺便记录一下最大差值，这个最大差值就是我们要求的值。因为优先队列中每次取出的都是差值最小的，当搜索到终点的时候，这个差值也就是整个路径中最小值。

JAVA：

public int minimumEffortPath(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    boolean[][] vis = newboolean[m][n];// 记录当前位置是否被访问过
    // 优先队列，存放的事三元组(x,y,z)，前两个是坐标，z是和上一个位置高度差的绝对值，按照第3个元素从小到大排序
    PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
    pq.offer(newint[]{0, 0, 0});// 起始点添加到优先队列中
    int ans = 0;
    int[][] dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};// 方向数组，上下左右四个方向
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();// 出队一个元素
        int curX = cur[0], curY = cur[1];// 出队元素的坐标
        ans = Math.max(ans, cur[2]);// 记录最大差值
        if (curX == m - 1 && curY == n - 1)// 到达终点
            return ans;
        vis[curX][curY] = true;// 标记为已访问过
        for (int i = 0; i < 4; i++) {// 沿着当前点的上下左右四个方向遍历。
            int x = curX + dirs[i][0];
            int y = curY + dirs[i][1];
            // 不能越界，并跳过访问过的点
            if (x < 0 || x >= m || y < 0 || y >= n || vis[x][y])
                continue;
            // 三元组(x,y,z)添加到优先队列中，x，y是添加的坐标，z是上一个位置到该坐标位置的最大差值。
            pq.offer(newint[]{x, y, Math.abs(heights[x][y] - heights[curX][curY])});
        }
    }
    return -1;
}

C++：

public:
    int minimumEffortPath(vector> &heights) {
        int m = heights.size(), n = heights[0].size();
        // 记录当前位置是否被访问过
        vector> vis(m, vector(n, false));
        // 自定义比较器：按照第三个元素（高度差）从小到大排序
        auto cmp = [](constvector &a, constvector &b) {
            return a[2] > b[2];
        };
        // 优先队列，存放的事三元组(x,y,z)，前两个是坐标，z是和上一个位置高度差的绝对值，按照第3个元素从小到大排序
        priority_queue, vector>, decltype(cmp)> pq(cmp);
        pq.push({0, 0, 0});// 起始点添加到优先队列中
        int ans = 0;
        // 方向数组，上下左右四个方向
        int dirs[4][2] = {{0,  -1},
                          {0,  1},
                          {-1, 0},
                          {1,  0}};
        while (!pq.empty()) {
            auto cur = pq.top();
            pq.pop();// 出队一个元素
            int curX = cur[0], curY = cur[1];// 出队元素的坐标
            ans = max(ans, cur[2]);// 记录最大差值
            if (curX == m - 1 && curY == n - 1)// 到达终点
                return ans;
            vis[curX][curY] = true;// 标记为已访问过
            for (auto &dir: dirs) {// 沿着当前点的上下左右四个方向遍历。
                int x = curX + dir[0];
                int y = curY + dir[1];
                // 不能越界，并跳过访问过的点
                if (x < 0 || x >= m || y < 0 || y >= n || vis[x][y])
                    continue;
                // 三元组(x,y,z)添加到优先队列中，x，y是添加的坐标，z是上一个位置到该坐标位置的最大差值。
                pq.push({x, y, abs(heights[x][y] - heights[curX][curY])});
            }
        }
        return-1;
    }