当前位置: 首页 > 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…...

字节测开一面面经

1 . 自我介绍 2 . 讲一下常见的数据结构 : 讲了数组,set,list,map,树&#xff0c;图&#xff0c;队列 &#xff0c; 栈等 ; 3 . 讲一下java反射场景和作用 ; 4 . 讲一下你了解的机器学习算法 ; 5 . 我讲完ML之后 &#xff0c; 问了knn和贝叶斯的使用的场景区别(没答上来) ; 6 .…...

HTML 段落

HTML 段落 概述 HTML&#xff08;超文本标记语言&#xff09;是构建网页的标准语言&#xff0c;而段落是构成网页内容的基本单元。在HTML中&#xff0c;段落是通过<p>标签来定义的。本文将详细介绍HTML段落的相关知识&#xff0c;包括段落的基本结构、样式设置、以及在…...

【Mind+】掌控板入门教程04 迷你动画片

还记得小时候每天放学必看的动画片吗&#xff1f;还记得那些年陪伴我一起长大的卡通人物吗&#xff1f;勇救爷爷的葫芦娃&#xff0c;我们的朋友小哪吒&#xff0c;相信这些经典的动画形象已经成为了一代人童年的美好回忆。今天就让我们用掌控板来制作一部迷你动画片吧。 项目示…...

文件上传漏洞-HackBar使用

介绍 HackBar 是一个用于浏览器的扩展插件&#xff0c;主要用于进行网络渗透测试和安全评估。它提供了一系列方便的工具和功能&#xff0c;可以帮助用户执行各种网络攻击和测试&#xff0c;包括 XSS、SQL 注入、CSRF、路径穿越等 下载地址 可以到github上面去下载&#xff0…...

鸿蒙媒体开发【相机数据采集保存】音频和视频

相机数据采集保存 介绍 本示例主要展示了相机的相关功能&#xff0c;使用libohcamera.so 接口实现相机的预览、拍照、录像、前后置摄像头切换进行拍照、录像&#xff0c;以及对焦、曝光等控制类功能。 效果预览 使用说明 弹出是否允许“CameraSample”使用相机&#xff1f;…...

【java基础】徒手写Hello, World!程序

文章目录 前提&#xff1a;java环境变量配置使用vscode编写helloworld解析 前提&#xff1a;java环境变量配置 https://blog.csdn.net/xzzteach/article/details/140869188 使用vscode编写helloworld code .为什么用code看下图 报错了&#xff01;&#xff01;&#xff01;&…...

对 vllm 与 ollama 的一些研究

今天咱们来聊聊 vllm 和 ollama 这两个听起来就挺酷的玩意儿。这俩都是现在 AI 圈子里的大明星&#xff0c;专门用来让那些超大型的 AI 模型跑得更顺溜。 先说说 vllm 吧&#xff0c;这家伙的绝活儿是剪枝。啥叫剪枝呢&#xff1f;想象一下&#xff0c;你有个花园&#xff0c;…...

浅谈基础的图算法——强联通分量算法(c++)

文章目录 强联通分量SCC概念例子有向图的DFS树代码例题讲解[POI2008] BLO-Blockade题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 思路AC代码 【模板】割点&#xff08;割顶&#xff09;题目背景题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示…...

C#:通用方法总结—第13集

大家好&#xff0c;今天继续讲解我们的通用方法系列。 下面是今天要介绍的通用方法&#xff1a; &#xff08;1&#xff09;这个通用方法为ug获取选择圆边的圆心 /// <summary> /// ug获取选择圆边的圆心 /// </summary> /// <param name"a">&l…...

AI答题应用平台相关面试题

目录 1、请介绍整个系统后端的架构设计&#xff0c;有哪些模块以及各模块之间的关系&#xff1f; 2、你在项目中是如何设计库表的&#xff1f;可以从字段、索引、关联等方面回答。 3、为什么使用策略模式来封装不同的应用评分算法&#xff1f;它有哪些好处&#xff1f;具体如…...