On the shoulders of giants.

weekly-contest-164

访问所有点的最小时间

平面上有 n 个点,点的位置用整数坐标表示 points[i] = [xi, yi]。请你计算访问所有这些点需要的最小时间(以秒为单位)。

你可以按照下面的规则在平面上移动:

  • 每一秒沿水平或者竖直方向移动一个单位长度,或者跨过对角线(可以看作在一秒内向水平和竖直方向各移动一个单位长度)。
  • 必须按照数组中出现的顺序来访问这些点。

示例 1:

输入:points = [[1,1],[3,4],[-1,0]]
输出:7
解释:一条最佳的访问路径是: [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   
从 [1,1] 到 [3,4] 需要 3 秒 
从 [3,4] 到 [-1,0] 需要 4 秒
一共需要 7 秒

示例 2:

输入:points = [[3,2],[-2,2]]
输出:5

提示:

  • points.length == n
  • 1 <= n <= 100
  • points[i].length == 2
  • -1000 <= points[i][0], points[i][1] <= 1000
题解

两点之间最优的步数为:\( \max (dx, dy) – \min (dx, dy) + \min (dx, dy) = \max (dx, dy) \)

时间复杂度:\(O(n)\)

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

统计参与通信的服务器

这里有一幅服务器分布图,服务器的位置标识在 m * n 的整数矩阵网格 grid 中,1 表示单元格上有服务器,0 表示没有。

如果两台服务器位于同一行或者同一列,我们就认为它们之间可以进行通信。

请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。

示例 1:

输入:grid = [[1,0],[0,1]]
输出:0
解释:没有一台服务器能与其他服务器进行通信。

示例 2:

输入:grid = [[1,0],[1,1]]
输出:3
解释:所有这些服务器都至少可以与一台别的服务器进行通信。

示例 3:

输入:grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
输出:4
解释:第一行的两台服务器互相通信,第三列的两台服务器互相通信,但右下角的服务器无法与其他服务器通信。

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m <= 250
  • 1 <= n <= 250
  • grid[i][j] == 0 or 1
题解

模拟即可。

时间复杂度:\(O(nm(n+m))\)

class Solution {
private:
    const int dt[2][4] = {{0, 1, 0, -1}, {1, 0, -1, 0}};
public:
    int countServers(vector<vector<int>>& grid) {
        int count = 0, n = grid.size(), m = grid[0].size();
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == 0) continue;
                bool flag = false;
                for(int x = 0; x < n; x++) {
                    if(x == i) continue;
                    if(grid[x][j] == 1) flag = true;
                }
                for(int y = 0; y < m; y++) {
                    if(y == j) continue;
                    if(grid[i][y] == 1) flag = true;
                }
                if(flag == true) count++;
            }
        }
        
        
        return count;
    }
};

搜索推荐系统

给你一个产品数组 products 和一个字符串 searchWord ,products  数组中每个产品都是一个字符串。

请你设计一个推荐系统,在依次输入单词 searchWord 的每一个字母后,推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个,请按字典序返回最小的三个。

请你以二维列表的形式,返回在输入 searchWord 每个字母后相应的推荐产品的列表。

示例 1:

输入:products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
输出:[
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
解释:按字典序排序后的产品列表是 ["mobile","moneypot","monitor","mouse","mousepad"]
输入 m 和 mo,由于所有产品的前缀都相同,所以系统返回字典序最小的三个产品 ["mobile","moneypot","monitor"]
输入 mou, mous 和 mouse 后系统都返回 ["mouse","mousepad"]

示例 2:

输入:products = ["havana"], searchWord = "havana"
输出:[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

示例 3:

输入:products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
输出:[["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

示例 4:

输入:products = ["havana"], searchWord = "tatiana"
输出:[[],[],[],[],[],[],[]]

提示:

  • 1 <= products.length <= 1000
  • 1 <= Σ products[i].length <= 2 * 10^4
  • products[i] 中所有的字符都是小写英文字母。
  • 1 <= searchWord.length <= 1000
  • searchWord 中所有字符都是小写英文字母。
题解

在对 products 字典序排序后,可以发现合法区间是逐渐递减的。

所以,我们就可以模拟这个过程。

时间复杂度:\(O(\log n + n)\)

class Solution {
public:
    
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        int n = searchWord.length();
        vector<vector<string>> result;
        
        int lef = 0, rig = products.size() - 1;
        
        sort(products.begin(), products.end());
        for(int i = 0; i < n; i++) {
            while(lef <= rig && products[lef][i] != searchWord[i]) lef++;
            while(lef <= rig && products[rig][i] != searchWord[i]) rig--;
            if(lef <= rig) {
                result.push_back(vector<string> (products.begin() + lef, products.begin() + min(lef + 2, rig) + 1));
            } else result.push_back({});
        }
        
        return result;
    }
};

停在原地的方案数

有一个长度为 arrLen 的数组,开始有一个指针在索引 0 处。

每一步操作中,你可以将指针向左或向右移动 1 步,或者停在原地(指针不能被移动到数组范围外)。

给你两个整数 steps 和 arrLen ,请你计算并返回:在恰好执行 steps 次操作以后,指针仍然指向索引 0 处的方案数。

由于答案可能会很大,请返回方案数  10^9 + 7 后的结果。

示例 1:

输入:steps = 3, arrLen = 2
输出:4
解释:3 步后,总共有 4 种不同的方法可以停在索引 0 处。
向右,向左,不动
不动,向右,向左
向右,不动,向左
不动,不动,不动

示例  2:

输入:steps = 2, arrLen = 4
输出:2
解释:2 步后,总共有 2 种不同的方法可以停在索引 0 处。
向右,向左
不动,不动

示例 3:

输入:steps = 4, arrLen = 2
输出:8

提示:

  • 1 <= steps <= 500
  • 1 <= arrLen <= 10^6
题解

动态规划:设 dp[i][j] 为第 i 次操作后,下标在 j 位置的方案数。

有 \(dp_{i,j}=dp_{i-1,j-1}+dp_{i-1,i}+dp_{i-1,j-1}\) ,可以滚动数组优化。

时间复杂度:\(O(nm)\)

class Solution {
public:
    int numWays(int steps, int arrLen) {
        int dp[2][arrLen], o = 1, p = 1E9 + 7;
        
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for(int i = 1; i <= steps; i++) {
            for(int j = 0; j < min(i + 1, arrLen); j++) {
                dp[o][j] = 0;
                if(0 <= j - 1) dp[o][j] = (1ll * dp[o][j] + dp[o ^ 1][j - 1]) % p;
                if(j + 1 < arrLen) dp[o][j] = (1ll * dp[o][j] + dp[o ^ 1][j + 1]) % p;
                dp[o][j] = (1ll * dp[o][j] + dp[o ^ 1][j]) % p;
            }
            o ^= 1;
        }
        
        return dp[o ^ 1][0];
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注