访问所有点的最短耗时

在二维平面上给定一系列点，需要按顺序访问每个点。每一步允许向上下左右或对角线方向移动一格。目标是计算从第一个点开始，依次到达其余各点所需的最少步数。

关键观察在于：两点之间的最小移动次数等于它们横纵坐标差值的最大值，即切比雪夫距离。这是因为对角线移动可以同时改变两个坐标，因此总步数由较长的那个轴向距离决定。

class Solution {
public:
    int minTimeToVisitAllPoints(vector<vector<int>>& path) {
        int totalSteps = 0;
        for (int i = 1; i < path.size(); ++i) {
            int deltaX = abs(path[i][0] - path[i-1][0]);
            int deltaY = abs(path[i][1] - path[i-1][1]);
            totalSteps += max(deltaX, deltaY);
        }
        return totalSteps;
    }
};

可通信服务器数量统计

给定一个二维网格表示服务器分布（1 表示有服务器，0 表示空位），若某台服务器所在的行或列中存在其他至少一台服务器，则该服务器能够参与通信。任务是统计所有能通信的服务器总数。

解决方案分为两步：首先遍历整个网格，记录每一行和每一列的服务器数量；然后再次遍历，检查每台服务器是否满足其所在行或列的计数大于1。

class Solution {
public:
    int countServers(vector<vector<int>>& network) {
        int rows = network.size(), cols = network[0].size();
        vector<int> rowCount(rows, 0), colCount(cols, 0);

        // 统计每行每列的服务器数量
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (network[i][j]) {
                    rowCount[i]++;
                    colCount[j]++;
                }
            }
        }

        int connected = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (network[i][j] && (rowCount[i] > 1 || colCount[j] > 1)) {
                    connected++;
                }
            }
        }
        return connected;
    }
};

商品搜索建议系统

实现一个推荐系统，用户输入字符过程中，每次输入后返回字典序前三个以当前输入为前缀的商品名称。

先将商品列表排序，利用双指针维护当前匹配的字符串区间。随着输入字符逐步增加，不断缩小这个区间，并提取最多前三项作为结果。

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& items, string query) {
        sort(items.begin(), items.end());
        int left = 0, right = items.size() - 1;
        vector<vector<string>> result;

        for (int i = 0; i < query.length(); ++i) {
            char c = query[i];
            // 移除不匹配的左边界
            while (left <= right && (items[left].length() <= i || items[left][i] != c))
                left++;
            // 移除不匹配的右边界
            while (left <= right && (items[right].length() <= i || items[right][i] != c))
                right--;

            result.push_back({});
            // 添加至多三个建议
            for (int j = left; j <= right && j < left + 3; ++j) {
                result.back().push_back(items[j]);
            }
        }
        return result;
    }
};

限定步数下返回原点的方法数

有一个长度为 arrLen 的数组，起始位置在索引 0。每步可以选择向左、向右或不动。求在恰好执行 steps 步之后回到位置 0 的不同路径数目，结果对 \(10^9+7\) 取模。

使用动态规划，设 dp[i][j] 表示第 i 步后位于位置 j 的方案数。由于状态只依赖前一层，可用滚动数组优化空间。注意实际可达的最大位置不会超过 min(steps, arrLen)，以此剪枝提升效率。

class Solution {
public:
    int numWays(int steps, int arrLen) {
        const int MOD = 1e9 + 7;
        arrLen = min(arrLen, steps);
        vector<int> prev(arrLen, 0), curr(arrLen, 0);
        prev[0] = 1;

        for (int step = 1; step <= steps; ++step) {
            for (int pos = 0; pos < arrLen; ++pos) {
                curr[pos] = prev[pos];  // 原地不动
                if (pos > 0)
                    curr[pos] = (curr[pos] + prev[pos - 1]) % MOD;
                if (pos + 1 < arrLen)
                    curr[pos] = (curr[pos] + prev[pos + 1]) % MOD;
            }
            swap(prev, curr);
        }
        return prev[0];
    }
};