当前位置: 首页 > news >正文

网站什么时候做SEO优化最合适短视频seo搜索优化

网站什么时候做SEO优化最合适,短视频seo搜索优化,ui做的好的网站有哪些,wordpress免费企业模板下载2316. 统计无向图中无法互相到达点对数 难度: 中等 来源: 每日一题 2023.10.21 给你一个整数 n ,表示一张 无向图 中有 n 个节点,编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ,其中 edges[i] [ai, bi] 表示节点 ai 和 bi 之间…


2316. 统计无向图中无法互相到达点对数
难度: 中等
来源: 每日一题 2023.10.21

给你一个整数 n ,表示一张 无向图 中有 n 个节点,编号为 0n - 1 。同时给你一个二维整数数组 edges ,其中 edges[i] = [ai, bi] 表示节点 aibi 之间有一条 无向 边。

请你返回 无法互相到达 的不同 点对数目

示例 1:

输入:n = 3, edges = [[0,1],[0,2],[1,2]]
输出:0
解释:所有点都能互相到达,意味着没有点对无法互相到达,所以我们返回 0 。

示例 2:

输入:n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
输出:14
解释:总共有 14 个点对互相无法到达:
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]
所以我们返回 14 。

提示:

  • 1 <= n <= 10^5
  • 0 <= edges.length <= 2 * 10^5
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • 不会有重复边。
class StockSpanner {public long countPairs(int n, int[][] edges) {}
}

分析与题解

  • 邻接表 + 深度优先遍历

    这个题目其实就是对无向图的邻接表的理解, 那么求两个点没有任何关联, 我们只要如果只要求出一条完整的边, 那么剩下所有的节点一定与这条完整的边不连接, 不连接的含义就是这条边上的节点与剩下的所有节点都是两两无法相互到达.

    那么基于这样的理论, 我们假设这条边上的节点个数是 m 个, 那么对于这条边上的所有节点与剩下的节点两两无法相互到达的组合个数为 m * (n - m) .

    另外, 假设 节点1节点2 无法相互到达, 那么深度优先遍历 节点1 时,会计算一遍 节点1节点2; 深度优先遍历 节点1 时, 同样会计算一遍 节点1节点2. 所以最终结果我们需要除以2.

    接下来, 我们看一下具体的解题过程.

    首先, 我们先创建无向图的邻接表, 这里我使用的是HashMap来作为邻接表的存储空间.

    // 创建邻接表
    HashMap<Integer, ArrayList<Integer>> cache = new HashMap<>();
    for(int i = 0; i < n; i++) {cache.put(i, new ArrayList<>());
    }
    for(int[] item: edges) {Integer first = item[0];Integer second = item[1];cache.get(first).add(second);cache.get(second).add(first);
    }
    

    然后通过深度优先遍历查找每一条边符合题目的个数.

    // 深度优先遍历
    // 当我们找到一个完整链路节点, 那么这些节点就不可能和剩下的节点有链接了
    // 假设找到某条无线边的所有节点为m个, 总结点数为n个. 那么相互不能到达的两两节点数为 m * (n - m)
    boolean[] visited = new boolean[n];
    long result  = 0;
    for(Integer key : cache.keySet()) {if(!visited[key]) {long count = dfs(key, cache, visited);result += (n - count) * count;}
    }
    

    对于深度优先遍历, 我们就没有啥好说的, 我们只需要按照常规方式进行递归即可.

    public int dfs(Integer key,  HashMap<Integer, ArrayList<Integer>> cache, boolean[] visited) {if(visited[key]) {return 0;}visited[key] = true;int count = 1;ArrayList<Integer> group = cache.get(key);for(Integer item : group) {if(visited[item] == false) {count += dfs(item, cache, visited);}}return count;
    }
    

    然后最后的计算结果因为所有的个数都计算了两遍, 我们需要除以2来求出最终的结果.

    return result/2;
    

    最后, 我们一起看一下整体的代码逻辑.

    class Solution {public long countPairs(int n, int[][] edges) {// 创建邻接表HashMap<Integer, ArrayList<Integer>> cache = new HashMap<>();for(int i = 0; i < n; i++) {cache.put(i, new ArrayList<>());}for(int[] item: edges) {Integer first = item[0];Integer second = item[1];cache.get(first).add(second);cache.get(second).add(first);}// 深度优先遍历// 当我们找到一个完整链路节点, 那么这些节点就不可能和剩下的节点有链接了// 假设找到某条无线边的所有节点为m个, 总结点数为n个. 那么相互不能到达的两两节点数为 m * (n - m)boolean[] visited = new boolean[n];long result  = 0;for(Integer key : cache.keySet()) {if(!visited[key]) {long count = dfs(key, cache, visited);result += (n - count) * count;}}return result/2;}public int dfs(Integer key,  HashMap<Integer, ArrayList<Integer>> cache, boolean[] visited) {if(visited[key]) {return 0;}visited[key] = true;int count = 1;ArrayList<Integer> group = cache.get(key);for(Integer item : group) {if(visited[item] == false) {count += dfs(item, cache, visited);}}return count;}
    }
    

    复杂度分析:

    • 时间复杂度: O(m + n), n 是总结点的个数, m是边数
    • 空间复杂度: O(m + n)

    结果如下所示.

http://www.15wanjia.com/news/18597.html

相关文章:

  • 做威士忌的网站经典广告语
  • 国内知名公关公司网络推广优化seo
  • 武汉商业网站网络营销活动策划方案
  • 营销网络世界地图优化大师官方免费
  • wordpress前端发表文章长沙seo推广外包
  • 宣传型网站功能定位怎么开发自己的小程序
  • 哈尔滨正规制作网站公司百度搜索量最大的关键词
  • 一个网站不兼容ie怎么做黄页网站推广公司
  • 做网站最好的公司东莞网站建设平台
  • 石家庄做网站设计网络营销推广方法有哪些
  • 海南网站建设推荐今日国内新闻大事
  • 网站前端设计要做什么的推广资源网
  • 自己做网站步骤 域名班级优化大师怎么加入班级
  • 知乎 网站开发工具seo的方式包括
  • 网站排版设计欣赏四年级下册数学优化设计答案
  • 英国T4学生签证 可以做网站吗百度指数的使用
  • 郑州公司做网站汉狮品牌营销推广方案
  • python 做网站开发吗武汉网站推广公司
  • 织梦网站新闻列表调用如何注册一个域名
  • 昆明云南微网站制作seo是啥
  • wordpress是建站工具 还是语言app拉新推广平台渠道
  • wordpress文章付费阅读设置怎么样关键词优化
  • 公司网站建设的签订合同seo搜索优化招聘
  • 建网络商城网站吗北京建站优化
  • 国外网站众筹怎做重大军事新闻
  • 聊城网站建设哪个好些西安关键词优化排名
  • 静态网站制作流程百度怎么做网站
  • 做网站在哪里租服务器石家庄最新疫情
  • 导游网站如何建设的个人网页设计
  • 房地产企业网站建设百度搜索服务