力扣刷题之3128.直角三角形
题干描述
给你一个二维 boolean 矩阵 grid 。
请你返回使用 grid 中的 3 个元素可以构建的 直角三角形 数目,且满足 3 个元素值 都 为 1 。
注意:
- 如果
grid中 3 个元素满足:一个元素与另一个元素在 同一行,同时与第三个元素在 同一列 ,那么这 3 个元素称为一个 直角三角形 。这 3 个元素互相之间不需要相邻。
示例 1:
| 0 | 1 | 0 |
| 0 | 1 | 1 |
| 0 | 1 | 0 |
| 0 | 1 | 0 |
| 0 | 1 | 1 |
| 0 | 1 | 0 |
输入:grid = [[0,1,0],[0,1,1],[0,1,0]]
输出:2
解释:
有 2 个直角三角形。
示例 2:
| 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 |
输入:grid = [[1,0,0,0],[0,1,0,1],[1,0,0,0]]
输出:0
解释:
没有直角三角形。
示例 3:
| 1 | 0 | 1 |
| 1 | 0 | 0 |
| 1 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 0 | 0 |
| 1 | 0 | 0 |
输入:grid = [[1,0,1],[1,0,0],[1,0,0]]
输出:2
解释:
有两个直角三角形。
题干描述
问题理解
我们需要在一个二维布尔矩阵grid中统计由1组成的直角三角形的数量。一个直角三角形由三个元素组成,要求:
- 一个元素与另一个元素在同一行。
- 这个元素还需要与第三个元素在同一列。
这些组成三角形的元素之间不需要相邻。
解题思路
为了解决这个问题,我们需要系统地检查矩阵中的每一个位置,看它是否能作为直角三角形直角顶点。具体步骤如下:
1.统计行和列中i的数量
- 对于矩阵中的内个单元格,计算它所在的行和列中1的数量。的数量。这有助于我们确定可以形成三角形的水平和垂直线。
2.计算直角三角形的数量
对于每一个位置(i,j)的1,我们计算它所在的行和列中1的数量。
如果grid[i][j]为1,则可以通过在同行中选择另一个1和在同列中选择另一个1来形成三角形。
这种情况下的三角形数量为(row_count - 1)*(col_count - 1),其中row_count是第i行中的1的数量,col_count 是第 j 列中的 1 的数量,减去当前的 1 是为了避免重复计算当前位置。
代码详解
#include <stdio.h>
#include <stdlib.h>
#include <string.h>//计算矩阵中的直角三角形数量
long long numberOfRightTriangles(int** grid, int gridSize, int* gridColSize) {int n = gridSize, m = gridColSize[0];int* col = (int*)malloc(m * sizeof(int));//动态分配内存用于计算计数数组memset(col, 0, m * sizeof(int));//将数组col中的所有数组初始化为0//计算每列中1的数量for (int i = 0; i < n; i++){for (int j = 0; j < m; j++) {col[j] += grid[i][j];}}long long res = 0;//用于存储直角三角形的数量for (int i = 0; i < n; i++){int row = 0;//计算当前行中1的数量for (int j = 0; j < m; j++){row += grid[i][j];}//对于当前行中的每个1,计算能够构成的直角三角形数量for (int j = 0; j < m; j++){if (grid[i][j] == 1) {//如果grid[i][j]为1,则可能构成三角形的个数为(row - 1) * (col[j] - 1)res += (long long)(row - 1) * (col[j] - 1);}}}free(col);//释放动态分配的内存return res;}
int main() {// 测试用例1int grid1Data[][3] = {{0, 1, 0},{0, 1, 1},{0, 1, 0}};int gridSize1 = 3;int gridColSize1 = 3;int** grid1 = (int**)malloc(gridSize1 * sizeof(int*));for (int i = 0; i < gridSize1; i++) {grid1[i] = (int*)malloc(gridColSize1 * sizeof(int));memcpy(grid1[i], grid1Data[i], gridColSize1 * sizeof(int));}int gridColSizes1[] = { gridColSize1, gridColSize1, gridColSize1 };printf("Output: %lld\n", numberOfRightTriangles(grid1, gridSize1, gridColSizes1));for (int i = 0; i < gridSize1; i++) {free(grid1[i]);}free(grid1);// 测试用例2int grid2Data[][4] = {{1, 0, 0, 0},{0, 1, 0, 1},{1, 0, 0, 0}};int gridSize2 = 3;int gridColSize2 = 4;int** grid2 = (int**)malloc(gridSize2 * sizeof(int*));for (int i = 0; i < gridSize2; i++) {grid2[i] = (int*)malloc(gridColSize2 * sizeof(int));memcpy(grid2[i], grid2Data[i], gridColSize2 * sizeof(int));}int gridColSizes2[] = { gridColSize2, gridColSize2, gridColSize2 };printf("Output: %lld\n", numberOfRightTriangles(grid2, gridSize2, gridColSizes2));for (int i = 0; i < gridSize2; i++) {free(grid2[i]);}free(grid2);// 测试用例3int grid3Data[][3] = {{1, 0, 1},{1, 0, 0},{1, 0, 0},{1, 0, 1},{1, 0, 0},{1, 0, 0}};int gridSize3 = 6;int gridColSize3 = 3;int** grid3 = (int**)malloc(gridSize3 * sizeof(int*));for (int i = 0; i < gridSize3; i++) {grid3[i] = (int*)malloc(gridColSize3 * sizeof(int));memcpy(grid3[i], grid3Data[i], gridColSize3 * sizeof(int));}int gridColSizes3[] = { gridColSize3, gridColSize3, gridColSize3, gridColSize3, gridColSize3, gridColSize3 };printf("Output: %lld\n", numberOfRightTriangles(grid3, gridSize3, gridColSizes3));for (int i = 0; i < gridSize3; i++) {free(grid3[i]);}free(grid3);return 0;
}
相关文章:
力扣刷题之3128.直角三角形
题干描述 给你一个二维 boolean 矩阵 grid 。 请你返回使用 grid 中的 3 个元素可以构建的 直角三角形 数目,且满足 3 个元素值 都 为 1 。 注意: 如果 grid 中 3 个元素满足:一个元素与另一个元素在 同一行,同时与第三个元素…...
OD C卷 - 机场航班调度
机场航班调度(100) 航班组成:前两个大写字母代表航空公司缩写,后面4个数字代表航班信息;对输入的航班排序 首先按照航空公司缩写升序排序;同一航空公司的按照航班信息升序排序; 输入描述&…...
uni-app中使用支付宝扫码插件并且在真机调试时使用(详细教程)
前言:uni-app自带的扫码api 识别不灵敏,每次都得扫很长时间且不断调整才能扫出来码,所以决定使用支付宝扫码插件,官方插件地址:https://ext.dcloud.net.cn/plugin?id2636#detail 使用步骤: 1、下载插件到项目中 2、…...
每日学术速递8.5—1
1.SV4D: Dynamic 3D Content Generation with Multi-Frame and Multi-View Consistency 标题: SV4D:具有多帧和多视图一致性的动态 3D 内容生成 作者:Yiming Xie, Chun-Han Yao, Vikram Voleti, Huaizu Jiang, Varun Jampani 文章链接&…...
1、操作系统相关概念
1、操作系统是计算机上的第一层软件,用于管理计算机硬件设备,提高他们的利用率和通吐量,并为用户和应用程序提供一个接口。不同操作系统目标不同,查询设备的操作系统,侧重人机交互性;武器控制操作系统&…...
【ModelSim】仿真问题记录
1、波形出不全: 1、甚至连clk波形都出不来 2、个别波形只有到仿真结束的时候才出现 解决办法: 1、添加波形需要是实例中的net 2、排查是否存在声明与示例的位宽不一致的信号 3、观察是否存在未初始化的变量寄存器 4、缩短整个仿真的步长 2、Instance列…...
如何提高深度学习中数据运行的稳定性
在深度学习中,模型的训练通常会受到随机性因素的影响,如参数初始化、数据加载顺序等。这会导致每次训练得到的结果有所不同。要减少这种不稳定性,可以采取以下措施: 1.固定随机种子 通过设置随机种子,可以使得每次训…...
【连续数组】python刷题记录
R3-前缀和专题 绝对要用字典记录 ben神,前缀和字典 class Solution:def findMaxLength(self, nums: List[int]) -> int:#前缀和字典,key为差值,value为坐标dict{0:-1}#当前1和0的差值counter0ret0for i,num in enumerate(nums):#多1+1if…...
JavaScript青少年简明教程:DOM和CSS简介
JavaScript青少年简明教程:DOM和CSS简介 DOM简介 DOM(Document Object Model)将文档表示为一个树形结构,其中每个节点都是一个对象,每个对象都有其自身的属性和方法。 通过对DOM的操作,开发者可以使用编…...
架构师知识梳理(一):计算机硬件
目录 计算机硬件组成 CPU CPU的组成 CPU的功能 校验码 奇偶校验 CRC CRC计算案例 指令 指令指行过程 指令系统 指令系统分类 指令流水线技术 流水线技术相关计算公式 存储 计算机存储系统设计 高速缓存Cache 缓存的局部性原理 地址映射 替换算法 关于命中…...
从根儿上学习spring 四 之run方法启动第一段
图1 由上图我们可以看到,我把run方法分成了5个小段,每小段使用红框圈了起来,这一篇我们先开始讲第一段。大家需要关注下行号,我讲的时候可能会使用行号对应具体某行代码。 图1-289-290行: 没啥好说的定义了两个变量&…...
智能闹钟如何判断用户已经醒了?
智能闹钟判断用户是否已经醒来的方式主要依赖于其内置的传感器和算法系统。以下是一些常见的判断方法: 一、传感器监测 体动传感器:智能闹钟通常配备有体动传感器,用于监测用户的身体运动。当用户从睡眠状态转变为清醒状态,并开始…...
【算法】动态规划解决背包问题
应用场景——01背包问题 有一个背包,背包的容量为 4,现有如下物品 要求 1.目标为装入背包的总价值最大,并且重量不超出 2.要求装入的物品不能重复 动态规划算法介绍 1.动态规划算法的核心是:将大问题划分为小问题进行解决&…...
day09 工作日报表
日期 30日07月2024年 任务安排 今天主要就是讲了security类工作的原理,然后就是让我们自己做项目 工作中的问题 今天做项目的时候发现有时候用postman测试返回20001,说错误见控制台,但是控制台一片祥和,于是就尝试用tr…...
C++学习之路(1)— 第一个HelloWorld程序
C学习之路(1)— 第一个HelloWorld程序 一、前言 C在C语言的基础上添加了对面向对象编程和泛型编程的支持,在 20世纪90年代便是最重要的编程语言之一,并在21世纪仍保持强劲势头。C继承了C语言高效、简洁、快速和可移植性的传统。 …...
python3 pyside6图形库学习笔记及实践(三)
目录 前言菜单栏相关控件使用QtDesigner快速构建菜单栏结构语法 上下文菜单概念为窗体添加上下文菜单为控件添加上下文菜单 折叠菜单资源的加载内置图标Rcc的使用创建资源文件加载资源文件 前言 本系列文章为b站PySide6教程以及官方文档的学习笔记 原视频传送门:【…...
03 库的操作
目录 创建查看修改删除备份和恢复查看连接情况 1. 创建 语法 CRATE DATABASE [IF NOT EXISTS] db_name [create_specification [, create_specification] …] create_specification: CHARACTER SET charset_name CPLLATE collation_name 说明: 大写的标识关键…...
嵌入式人工智能(44-基于树莓派4B的扩展板-LED按键数码管TM1638)
树莓派性能非常强悍,但是对于某些复杂的项目来说,会出现心有余而口不足的情况,为了解决这类问题,可以在树莓派上使用扩展板,我们介绍几款常见的扩展板,不仅可以扩展到树莓派,其他单片机或嵌入式…...
linux通过抓包工具tcpdump查看80端口访问量情况
方法: tcpdump -i ens32 -tn dst port 80 -c 10 | awk -F"." {print $1"."$2"."$3"."$4} | sort | uniq -c | sort -nr |head -n 10 #-i:指定端口 #-t:在输出的每一行不打印时间戳 #-nÿ…...
Mac 上安装和卸载 SDKMAN 及管理多个 JDK
前言 当电脑上有多个 JDK 环境的时候,切换管理比较麻烦,这时候可以使用 SDKMAN 来安装、管理 JDK。 一、安装 SDKMAN! 1. 安装前置条件 首先,确保已经安装了 curl 。如果没有,可以通过 Homebrew 来安装: brew inst…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...
Qt的学习(二)
1. 创建Hello Word 两种方式,实现helloworld: 1.通过图形化的方式,在界面上创建出一个控件,显示helloworld 2.通过纯代码的方式,通过编写代码,在界面上创建控件, 显示hello world; …...
