WeeklyContest164

发表于 更新于 分类于

力扣164场周赛[链接][https://leetcode-cn.com/contest/weekly-contest-164/]

就过了一题，差点被零封，菜出奇迹。。。。自闭中。。。

第一题：切比雪夫距离

1266. 访问所有点的最小时间

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

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

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

示例 1：

img

1
2
3
4
5
6
输入：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：

1
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

算法描述

每次找两个点之间对角线走的最大距离，最后在走竖线的，总结的来看，每次加上两个坐标的横纵坐标绝对值的最大值就是答案:ans+=max(abs(x1-x2),abs(y1-y2))

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minTimeToVisitAllPoints(vector<vector<int>>& points) {
        int ans = 0;
        int x1 = points[0][0],y1 = points[0][1];
        for(int i=1;i<points.size();i++){
            int x2 = points[i][0],y2 = points[i][1];
            int t = min(abs(x1-x2),abs(y1-y2));
            ans+=t;
            if(abs(x1-x2)==t)t=abs(abs(y1-y2)-t);
            if(abs(y1-y2)==t)t=abs(abs(x1-x2)-t);
            ans+=t; 
            x1=x2,y1=y2;
        }
        return ans;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
class Solution {
    public int minTimeToVisitAllPoints(int[][] points) {
        int ans = 0;
        for(int i=1;i<points.length;i++){
            ans+=Math.max(Math.abs(points[i-1][1]-points[i][1]),Math.abs(points[i-1][0]-points[i][0]));
        }
        return ans;
    }
}

第二题：计数

1267. 统计参与通信的服务器

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

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

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

示例 1：

img

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

示例 2：

img

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

示例 3：

img

1
2
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

算法描述

  • 统计各个行列的1的个数存储在两个数组中
  • 遍历矩阵，当矩阵的值为1的时候，判断时候横行或者竖行的1的个数是否大于1
  • 大于res(结果)加一，不大于继续，直到遍历完所有数组

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<int> r(m,0),c(n,0);
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(grid[i][j]){
                    r[i]++;
                    c[j]++;
                }
        int res = 0;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(grid[i][j]&&(c[j]>1||r[i]>1))res++;
        return res;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int countServers(int[][] grid) {
        int  m = grid.length;
        int  n = grid[0].length;
        int[] r = new int[m];
        int[] c = new int[n];
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(grid[i][j]==1){
                    r[i]++;
                    c[j]++;
                }
        int res = 0;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(grid[i][j]==1&&(r[i]>1||c[j]>1))res++;
        return res;
    }
}

第三题：字典树（我用的暴力）

1268. 搜索推荐系统

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

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

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

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：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：

1
2
输入：products = ["havana"], searchWord = "havana"
输出：[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

示例 3：

1
2
输入：products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
输出：[["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

示例 4：

1
2
输入：products = ["havana"], searchWord = "tatiana"
输出：[[],[],[],[],[],[],[]]

提示：

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

算法描述

首先按字典序排序产品列表，之后读取单词依次找子串，找得到了放入结果集，如果当前结果集的长度等于3或者遍历完了产品表后退出，最后返回结果；

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        vector<vector<string>> res;
        sort(products.begin(),products.end());
        for(int i=0;i<searchWord.length();i++){
            string str = searchWord.substr(0,i+1);
            vector<string> vec ;
            for(int j=0;j<products.size();j++){
                string ss = products[j].substr(0,i+1);
                if(str==ss){
                    vec.push_back(products[j]);
                }
                if(vec.size()==3)break;
            } 
            res.push_back(vec);
        }
        return res;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> res = new ArrayList<>();
        Arrays.sort(products);
        for(int i=0;i<searchWord.length();i++){
            String str = searchWord.substring(0,i+1);
            List<String> list = new ArrayList<>();
            for(int j=0;j<products.length;j++){
                if(i+1>products[j].length())continue;
                String s = products[j].substring(0,i+1);
                if(s.equals(str)){
                    list.add(products[j]);
                }
                if(list.size()==3)break;
            }
            res.add(list);
        }
        return res;
    }
}

第四题：动态规划

1269. 停在原地的方案数

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：steps = 4, arrLen = 2
输出：8

提示：

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

算法描述

[大佬题解][https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/solution/cjian-dan-dpdai-ma-by-roeexu/]