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

力扣刷题之3128.直角三角形

题干描述

给你一个二维 boolean 矩阵 grid 。

请你返回使用 grid 中的 3 个元素可以构建的 直角三角形 数目,且满足 3 个元素值  为 1 。

注意:

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

示例 1:

010
011
010
010
011
010

输入:grid = [[0,1,0],[0,1,1],[0,1,0]]

输出:2

解释:

有 2 个直角三角形。

示例 2:

1000
0101
1000

输入:grid = [[1,0,0,0],[0,1,0,1],[1,0,0,0]]

输出:0

解释:

没有直角三角形。

示例 3:

101
100
100
101
100
100

输入: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 个元素可以构建的 直角三角形 数目&#xff0c;且满足 3 个元素值 都 为 1 。 注意&#xff1a; 如果 grid 中 3 个元素满足&#xff1a;一个元素与另一个元素在 同一行&#xff0c;同时与第三个元素…...

OD C卷 - 机场航班调度

机场航班调度&#xff08;100&#xff09; 航班组成&#xff1a;前两个大写字母代表航空公司缩写&#xff0c;后面4个数字代表航班信息&#xff1b;对输入的航班排序 首先按照航空公司缩写升序排序&#xff1b;同一航空公司的按照航班信息升序排序&#xff1b; 输入描述&…...

uni-app中使用支付宝扫码插件并且在真机调试时使用(详细教程)

前言&#xff1a;uni-app自带的扫码api 识别不灵敏&#xff0c;每次都得扫很长时间且不断调整才能扫出来码&#xff0c;所以决定使用支付宝扫码插件&#xff0c;官方插件地址&#xff1a;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 标题&#xff1a; SV4D&#xff1a;具有多帧和多视图一致性的动态 3D 内容生成 作者&#xff1a;Yiming Xie, Chun-Han Yao, Vikram Voleti, Huaizu Jiang, Varun Jampani 文章链接&…...

1、操作系统相关概念

1、操作系统是计算机上的第一层软件&#xff0c;用于管理计算机硬件设备&#xff0c;提高他们的利用率和通吐量&#xff0c;并为用户和应用程序提供一个接口。不同操作系统目标不同&#xff0c;查询设备的操作系统&#xff0c;侧重人机交互性&#xff1b;武器控制操作系统&…...

【ModelSim】仿真问题记录

1、波形出不全&#xff1a; 1、甚至连clk波形都出不来 2、个别波形只有到仿真结束的时候才出现 解决办法&#xff1a; 1、添加波形需要是实例中的net 2、排查是否存在声明与示例的位宽不一致的信号 3、观察是否存在未初始化的变量寄存器 4、缩短整个仿真的步长 2、Instance列…...

如何提高深度学习中数据运行的稳定性

在深度学习中&#xff0c;模型的训练通常会受到随机性因素的影响&#xff0c;如参数初始化、数据加载顺序等。这会导致每次训练得到的结果有所不同。要减少这种不稳定性&#xff0c;可以采取以下措施&#xff1a; 1.固定随机种子 通过设置随机种子&#xff0c;可以使得每次训…...

【连续数组】python刷题记录

R3-前缀和专题 绝对要用字典记录 ben神&#xff0c;前缀和字典 class Solution:def findMaxLength(self, nums: List[int]) -> int:#前缀和字典,key为差值&#xff0c;value为坐标dict{0:-1}#当前1和0的差值counter0ret0for i,num in enumerate(nums):#多1&#xff0b;1if…...

JavaScript青少年简明教程:DOM和CSS简介

JavaScript青少年简明教程&#xff1a;DOM和CSS简介 DOM简介 DOM&#xff08;Document Object Model&#xff09;将文档表示为一个树形结构&#xff0c;其中每个节点都是一个对象&#xff0c;每个对象都有其自身的属性和方法。 通过对DOM的操作&#xff0c;开发者可以使用编…...

架构师知识梳理(一):计算机硬件

目录 计算机硬件组成 CPU CPU的组成 CPU的功能 校验码 奇偶校验 CRC CRC计算案例 指令 指令指行过程 指令系统 指令系统分类 指令流水线技术 流水线技术相关计算公式 存储 计算机存储系统设计 高速缓存Cache 缓存的局部性原理 地址映射 替换算法 关于命中…...

从根儿上学习spring 四 之run方法启动第一段

图1 由上图我们可以看到&#xff0c;我把run方法分成了5个小段&#xff0c;每小段使用红框圈了起来&#xff0c;这一篇我们先开始讲第一段。大家需要关注下行号&#xff0c;我讲的时候可能会使用行号对应具体某行代码。 图1-289-290行&#xff1a; 没啥好说的定义了两个变量&…...

智能闹钟如何判断用户已经醒了?

智能闹钟判断用户是否已经醒来的方式主要依赖于其内置的传感器和算法系统。以下是一些常见的判断方法&#xff1a; 一、传感器监测 体动传感器&#xff1a;智能闹钟通常配备有体动传感器&#xff0c;用于监测用户的身体运动。当用户从睡眠状态转变为清醒状态&#xff0c;并开始…...

【算法】动态规划解决背包问题

应用场景——01背包问题 有一个背包&#xff0c;背包的容量为 4&#xff0c;现有如下物品 要求 1.目标为装入背包的总价值最大&#xff0c;并且重量不超出 2.要求装入的物品不能重复 动态规划算法介绍 1.动态规划算法的核心是&#xff1a;将大问题划分为小问题进行解决&…...

day09 工作日报表

日期 30日07月2024年 任务安排 今天主要就是讲了security类工作的原理&#xff0c;然后就是让我们自己做项目 工作中的问题 今天做项目的时候发现有时候用postman测试返回20001&#xff0c;说错误见控制台&#xff0c;但是控制台一片祥和&#xff0c;于是就尝试用tr…...

C++学习之路(1)— 第一个HelloWorld程序

C学习之路&#xff08;1&#xff09;— 第一个HelloWorld程序 一、前言 C在C语言的基础上添加了对面向对象编程和泛型编程的支持&#xff0c;在 20世纪90年代便是最重要的编程语言之一&#xff0c;并在21世纪仍保持强劲势头。C继承了C语言高效、简洁、快速和可移植性的传统。 …...

python3 pyside6图形库学习笔记及实践(三)

目录 前言菜单栏相关控件使用QtDesigner快速构建菜单栏结构语法 上下文菜单概念为窗体添加上下文菜单为控件添加上下文菜单 折叠菜单资源的加载内置图标Rcc的使用创建资源文件加载资源文件 前言 本系列文章为b站PySide6教程以及官方文档的学习笔记 原视频传送门&#xff1a;【…...

03 库的操作

目录 创建查看修改删除备份和恢复查看连接情况 1. 创建 语法 CRATE DATABASE [IF NOT EXISTS] db_name [create_specification [, create_specification] …] create_specification:  CHARACTER SET charset_name  CPLLATE collation_name 说明&#xff1a; 大写的标识关键…...

嵌入式人工智能(44-基于树莓派4B的扩展板-LED按键数码管TM1638)

树莓派性能非常强悍&#xff0c;但是对于某些复杂的项目来说&#xff0c;会出现心有余而口不足的情况&#xff0c;为了解决这类问题&#xff0c;可以在树莓派上使用扩展板&#xff0c;我们介绍几款常见的扩展板&#xff0c;不仅可以扩展到树莓派&#xff0c;其他单片机或嵌入式…...

linux通过抓包工具tcpdump查看80端口访问量情况

方法&#xff1a; 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&#xff1a;指定端口 #-t&#xff1a;在输出的每一行不打印时间戳 #-n&#xff…...

Mac 上安装和卸载 SDKMAN 及管理多个 JDK

前言 当电脑上有多个 JDK 环境的时候&#xff0c;切换管理比较麻烦&#xff0c;这时候可以使用 SDKMAN 来安装、管理 JDK。 一、安装 SDKMAN! 1. 安装前置条件 首先&#xff0c;确保已经安装了 curl 。如果没有&#xff0c;可以通过 Homebrew 来安装&#xff1a; brew inst…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !

我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...

基于江科大stm32屏幕驱动,实现OLED多级菜单(动画效果),结构体链表实现(独创源码)

引言 在嵌入式系统中&#xff0c;用户界面的设计往往直接影响到用户体验。本文将以STM32微控制器和OLED显示屏为例&#xff0c;介绍如何实现一个多级菜单系统。该系统支持用户通过按键导航菜单&#xff0c;执行相应操作&#xff0c;并提供平滑的滚动动画效果。 本文设计了一个…...