目录

• 访问所有点的最小时间
  • 思路
  • 代码
• 统计参与通信的服务器
  • 思路
  • 代码
• 搜索推荐系统
  • 思路
  • 代码
• 停在原地的方案数
  • 思路
  • 代码

访问所有点的最小时间

由于每次移动有水平方向移动一格、竖直方向移动一格和对角方向一格，而水平方向一格\(+\)竖直方向一格\(=\)对角线方向一格，因此最后答案为相邻两点的切比雪夫距离之和。

class Solution {
public:
    int minTimeToVisitAllPoints(vector<vector<int>>& points) {
        int n = points.size(), ans = 0;
        for(int i = 1; i < n; ++i) {
            int disx = abs(points[i][0]-points[i-1][0]), disy = abs(points[i][1]-points[i-1][1]);
            ans += max(disx, disy);
        }
        return ans;
    }
};

统计参与通信的服务器

统计每一行每一列有几个服务器，然后对于每一个服务器看他同行或同列的服务器数量大于\(1\)。

class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int row[255], col[255];
        for(int i = 0; i < n; ++i) row[i] = 0;
        for(int i = 0; i < m; ++i) col[i] = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(grid[i][j]) ++row[i], ++col[j];
            }
        }
        int ans = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if((row[i] > 1 || col[j] > 1) && grid[i][j]) ++ans;
            }
        }
        return ans;
    }
};

搜索推荐系统

我们先将字符串按照字典序进行排序，然后用两个双指针进行移动，当某一个端点的字符串长度已经小于当前遍历的长度或者该位置上的字符与\(searchWord\)在这个位置上的字符不同时移动指针。

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        int n = products.size(), l = 0, r = n - 1;
        sort(products.begin(), products.end());
        int len = searchWord.length();
        vector<vector<string>> ans(len);
        for(int i = 0; i < len; ++i) {
            while(l <= r && (products[l].length() <= i || products[l][i] != searchWord[i])) ++l;
            while(r >= l && (products[r].length() <= i || products[r][i] != searchWord[i])) --r;
            if(l > r) continue;
            for(int j = l; j <= min(l + 2, r); ++j) {
                ans[i].push_back(products[j]);
            }
        }
        return ans;
    }
};

停在原地的方案数

我们定义\(dp[i][j]\)表示在第\(i\)步处于\(j\)这个位置时的方案数，那么很容易发现转移方程为\(dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1]\)，注意我们每次的状态只和上一个状态有关，因此可以用滚动数组进行优化空间。

但是这个的复杂度是\(O(steps*arrLen)\)，我们可以发现当我们最多可以移动到\(min(arrLen,steps)\)这个位置，因此大于这个值的地方就不用考虑，因此复杂度就变成了\(O(steps*min(steps,arrLen))\)。

class Solution {
public:
    const int mod = 1e9 + 7;
    int dp[2][1000005];

    int add(int x, int y) {
        x += y;
        if(x >= mod) x -= mod;
        return x;
    }

    int numWays(int steps, int arrLen) {
        arrLen = min(arrLen, steps);
        for(int i = 0; i < arrLen; ++i) dp[0][i] = dp[1][i] = 0;
        dp[0][0] = 1;
        for(int i = 1; i <= steps; ++i) {
            int nw = i % 2, pre = (i - 1) % 2;
            for(int j = 0; j < arrLen; ++j) {
                dp[nw][j] = dp[pre][j];
                if(j > 0) dp[nw][j] = add(dp[nw][j], dp[pre][j-1]);
                if(j + 1 < arrLen) dp[nw][j] = add(dp[nw][j], dp[pre][j+1]);
            }
        }
        return dp[steps%2][0];
    }
};