Leetcode周赛第164场题解

掉分场掉分场，题目过慢了就被甩到后面去了，竞争激烈啊

周赛传送门

https://leetcode-cn.com/contest/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

题解

直观的思路就是先尽可能地斜着走，然后最后走横线或者是竖线

再思考一下其实就是横坐标与纵坐标的差的最大值

因为斜线可以投影到横纵坐标上

我下面的代码是直观的那种，比赛嘛，直接想到什么写什么了

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

统计参与通信的服务器

题目

这里有一幅服务器分布图，服务器的位置标识在 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(n^2)构造哈希表，再O(n^2)查找主机，判断主机所在的行和列的哈希表是不是有大于2

class Solution {
public:
    int countServers(vector<vector<int>>& g) {
        int n=g.size(),m=g[0].size();
        int sn[300],sm[300];
        memset(sn,0,sizeof sn);
        memset(sm,0,sizeof sm);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(g[i][j]==1)
                    sn[i]++,sm[j]++;
        int ans=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(g[i][j]==1&&(sn[i]>1||sm[j]>1))
                    ans++;
        return ans;
    }
};

搜索推荐系统

题目

给你一个产品数组 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 中所有字符都是小写英文字母。

题解

写了个Trie树但是人家排序就过了。。。

不说了，构建Trie树，然后DFS即可，都是泪啊

class Solution {
public:
    int son[20010][26],cnt[20010],idx=0,d=0;
    void insert(string& s){
        int p=0;
        for(auto x:s){
            int u=x-'a';
            if(!son[p][u]) son[p][u]=++idx;
            p=son[p][u];
        }
        cnt[p]++;
    }
    void cal(vector<string>& v,string &s){
        if(d==0) return;
        int p=0;
        for(auto x:s){
            int u=x-'a';
            if(!son[p][u]) return;
            p=son[p][u];
        }
        dfs(v,s,p);
    }
    void dfs(vector<string>& v,string& t,int p){
        if(d==0) return;
        for(int i=0;i<cnt[p]&&d;i++){
            v.push_back(t);
            d--;
        }
        if(d==0) return;
        for(int i=0;i<26;i++){
            t+=(char)('a'+i);
            if(son[p][i]) dfs(v,t,son[p][i]);
            t.pop_back();
        }
    }
    vector<vector<string>> suggestedProducts(vector<string>& products, string word) {
        for(auto s:products) insert(s);
        vector<vector<string>> ans;
        string t;
        for(auto c:word){
            t+=c;
            vector<string> v;
            d=3;
            cal(v,t);
            ans.push_back(v);
        }
        return ans;
    }
};

停在原地的方案数

题目

有一个长度为 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

题解

这题yy了好多莫名其妙的定理然后最后是动态规划

首先确定表示状态的二位数组dp[i][j]，i代表走了几步，j代表现在的位置

那么dp[i][j]就可以从dp[i-1][j]（原地不动）和dp[i-1][j-1]（从右边走过来）以及dp[i-1][j+1]（从左边走过来）共同转移得到

初始化的时候dp[0][0]=1，最后输出的是dp[steps][0]，也就是经过所有步数回到0点

有个小坑，dp的边界是min(steps,len-1)，为什么要len-1因为题目中说了len是长度，且从0开始，所以需要减1

class Solution {
public:
    int dp[600][600];
    const int mod=1e9+7;
    int numWays(int steps, int len) {
        memset(dp,0,sizeof dp);
        int n=min(steps,len-1);
        dp[0][0]=1;
        for(int i=1;i<=steps;i++)
            for(int j=0;j<=n;j++){
                dp[i][j]=dp[i-1][j];
                if (j>0)  (dp[i][j]+=dp[i-1][j-1])%=mod;
                if (j<=n-1) (dp[i][j]+=dp[i-1][j+1])%=mod;
            }
        return dp[steps][0];
    }
};