您的位置:首页 > 娱乐 > 明星 > 每日一练 | Day 2

每日一练 | Day 2

2024/12/23 16:19:08 来源:https://blog.csdn.net/weixin_59271089/article/details/140860524  浏览:    关键词:每日一练 | Day 2

LCP 40. 心算挑战

题目链接

https://leetcode.cn/problems/right-triangles/

相关算法

哈希、数组、数学

题目描述

给你一个二维 boolean 矩阵 grid
请你返回使用 grid 中的 3 个元素可以构建的 直角三角形 数目,且满足 3 个元素值 1

注意:
如果 grid 中 3 个元素满足:一个元素与另一个元素在 同一行,同时与第三个元素在 同一列 ,那么这 3 个元素称为一个 直角三角形 。这 3 个元素互相之间不需要相邻。

  • 数据范围:
    • 1 <= grid.length <= 1000
    • 1 <= grid[i].length <= 1000
    • 0 <= grid[i][j] <= 1

解题思路

本题直角三角形的表述看上去复杂,实际上很简单,即以一个元素作为三角形的角上的点,如果和这个元素的位置同行同列均有元素,就可以组成直角三角形。因此易得:位于坐标(x,y)处的元素可以构成(countX - 1)*(countY - 1)个直角三角形
countXcountY 分别指代坐标(x,y)处行和列上值为 1 的元素个数

完整代码

class Solution {public long numberOfRightTriangles(int[][] grid) {int[] countX = new int[grid[0].length];long res = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {countX[j] += grid[i][j];}}for (int i = 0; i < grid.length; i++) {int countY = 0;for (int j = 0; j < grid[0].length; j++) {countY += grid[i][j];}for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == 1) {res += (countX[j] - 1) * (countY - 1);}}}return res;}
}
  • 时间复杂度:O(mn)
  • 空间复杂度:O(n)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com