Leetcode每日一题:1267. 统计参与通信的服务器

这篇具有很好参考价值的文章主要介绍了Leetcode每日一题:1267. 统计参与通信的服务器。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

原题

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

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

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

示例 1:

Leetcode每日一题:1267. 统计参与通信的服务器,算法,LeetCode,C++

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

示例 2:

Leetcode每日一题:1267. 统计参与通信的服务器,算法,LeetCode,C++

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

示例 3:

Leetcode每日一题:1267. 统计参与通信的服务器,算法,LeetCode,C++

输入: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

来源:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

解题思路

我们把题目读懂之后,就会发现题目要求我们统计每行每列中1大于等于2个行列上1的个数。一个简单的解题方法就是统计每行每列中1的个数,然后遍历每个值是1的点,看看所在行列上1的个数是否大于等于2。于是我们得到官方题解的实现:

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

作者:力扣官方题解
链接:https://leetcode.cn/problems/count-servers-that-communicate/solutions/101819/tong-ji-can-yu-tong-xin-de-fu-wu-qi-by-leetcode-so/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

优化题解

官方题解需要遍历两次全部的点,有没有优化的空间呢?其实我们遍历每行的时候,如果该行1的个数大于等于2,那么全都是符合结果的点。如果刚好等于1,那么需要后续判断这一列上1的点的个数是否大于等于2。因此我们可以先收集起来,最后判断,这样我们第二轮的时间复杂度可以降低到O(n)。基于这个思路,我们的优化版本:文章来源地址https://www.toymoban.com/news/detail-686488.html

class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        unordered_map<int, int> cols;
        int ans = 0,col = 0, rows=0;
        vector<int> srows;
        for(int i = 0; i < m;i++){
            rows=0;
            for(int j =0;j< n;j++){
                if(grid[i][j] == 1){
                    ++rows;
                    ++cols[j];
                    col = j;
                }
            }
            if(rows >= 2){
                ans+=rows;
            }else if(rows == 1){
                srows.emplace_back(col);
            }
        }
        for(int &j:srows){
            if(cols[j]>=2){
                ++ans;
            }
        }
        return ans;
    }
};

到了这里,关于Leetcode每日一题:1267. 统计参与通信的服务器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

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

    力扣题目链接:https://leetcode.cn/problems/count-servers-that-communicate/ 这里有一幅服务器分布图,服务器的位置标识在  m * n  的整数矩阵网格  grid  中,1 表示单元格上有服务器,0 表示没有。 如果两台服务器位于同一行或者同一列,我们就认为它们之间可以进行通信。 请你统计并

    2024年02月11日
    浏览(34)
  • ​LeetCode解法汇总1267. 统计参与通信的服务器

    https://github.com/September26/java-algorithms 这里有一幅服务器分布图,服务器的位置标识在  m * n  的整数矩阵网格  grid  中,1 表示单元格上有服务器,0 表示没有。 如果两台服务器位于同一行或者同一列,我们就认为它们之间可以进行通信。 请你统计并返回能够与至少一台其他

    2024年02月11日
    浏览(42)
  • 【力扣每日一题】2023.8.24 统计参与通信的服务器

    目录 题目: 示例: 分析: 代码: 题目顾名思义,要我们统计参与通信的服务器,给我们一个二维矩阵,元素为1的位置则表示是一台服务器。 判断一台服务器是否参与通信的条件是同一列或是同一行中也有服务器。 那么我们只需要遍历整个矩阵,遇到服务器的时候我们进

    2024年02月11日
    浏览(33)
  • 【1267. 统计参与通信的服务器】

    来源:力扣(LeetCode) 描述: 这里有一幅服务器分布图,服务器的位置标识在 m * n 的整数矩阵网格 grid 中,1 表示单元格上有服务器,0 表示没有。 如果两台服务器位于同一行或者同一列,我们就认为它们之间可以进行通信。 请你统计并返回能够与至少一台其他服务器进行

    2024年02月11日
    浏览(38)
  • LC-1267. 统计参与通信的服务器(枚举 + 计数)

    中等 这里有一幅服务器分布图,服务器的位置标识在 m * n 的整数矩阵网格 grid 中,1 表示单元格上有服务器,0 表示没有。 如果两台服务器位于同一行或者同一列,我们就认为它们之间可以进行通信。 请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。 示

    2024年02月11日
    浏览(30)
  • 2023-08-23 LeetCode每日一题(统计点对的数目)

    点击跳转到题目位置 给你一个无向图,无向图由整数 n ,表示图中节点的数目,和 edges 组成,其中 edges[i] = [u i , v i ] 表示 u i 和 v i 之间有一条无向边。同时给你一个代表查询的整数数组 queries 。 第 j 个查询的答案是满足如下条件的点对 (a, b) 的数目: a b cnt 是与 a 或者 b

    2024年02月11日
    浏览(55)
  • 每日一题:leetcode 1448 统计二叉树中好节点的数目

    给你一棵根为  root  的二叉树,请你返回二叉树中好节点的数目。 「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。 示例 1: 示例 2: 示例 3: 提示: 二叉树中节点数目范围是  [1, 10^5]  。 每个节点权值的范围是  [-10^4, 10^4]  。 思路

    2024年02月11日
    浏览(41)
  • Leetcode每日一题:1448. 统计二叉树中好节点的数目

    给你一棵根为  root  的二叉树,请你返回二叉树中好节点的数目。 「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。 示例 1: 示例 2: 示例 3: 提示: 二叉树中节点数目范围是  [1, 10^5]  。 每个节点权值的范围是  [-10^4, 10^4]  。 显然

    2024年02月11日
    浏览(37)
  • Leetcode每日一题:1782. 统计点对的数目(2023.8.24 C++)

    目录 1782. 统计点对的数目 题目描述: 实现代码与解析: hash + 双指针 原理思路:         给你一个无向图,无向图由整数  n   ,表示图中节点的数目,和  edges  组成,其中  edges[i] = [ui, vi]  表示  ui  和  vi  之间有一条无向边。同时给你一个代表查询的整数数组 

    2024年02月10日
    浏览(44)
  • 2023-08-25 LeetCode每日一题(统计二叉树中好节点的数目)

    点击跳转到题目位置 给你一棵根为 root 的二叉树,请你返回二叉树中好节点的数目。 「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。 示例 1: 示例 2: 示例 3: 提示: 二叉树中节点数目范围是 [1, 10 5 ] 。 每个节点权值的范围是 [-10

    2024年02月11日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包