Leetcode1128. 等价多米诺骨牌对的数量
Every day a Leetcode
题目来源:1128. 等价多米诺骨牌对的数量
解法1:暴力
代码:
class Solution
{
public:int numEquivDominoPairs(vector<vector<int>> &dominoes){int n = dominoes.size(), count = 0;for (int i = 0; i < n - 1; i++)for (int j = i + 1; j < n; j++){if (dominoes[i] == dominoes[j] || dominoes[i] == vector<int>(dominoes[j].rbegin(), dominoes[j].rend()))count++;}return count;}
};
结果:
超时了。
复杂度分析:
时间复杂度:O(n2),其中 n 是数组 dominoes 的长度。
空间复杂度:O(1)。
解法2:哈希
遍历数组 dominoes,对每一个多米诺骨牌 domino 排序,这样就保证等价的多米诺骨牌能存储在一个哈希值里。用一个形如 unordered_map<vector<int>, int> 的哈希表,记录等价的多米诺骨牌的数量。
结果报错了:
error: call to implicitly-deleted default constructor of ‘unordered_map<vector<int>, int>‘
用 map 就行了。
具体办法:error: call to implicitly-deleted default constructor of ‘unordered_map<vector<int>, int>‘
设一种多米诺骨牌的出现次数为 n,则等价的骨牌对 (i, j) 的数量为 C(n, 2) = n * (n - 1) / 2。答案为等价的骨牌对 (i, j) 的数量的总和。
代码:
/** @lc app=leetcode.cn id=1128 lang=cpp** [1128] 等价多米诺骨牌对的数量*/// @lc code=start
// class Solution
// {
// public:
// int numEquivDominoPairs(vector<vector<int>> &dominoes)
// {
// int n = dominoes.size(), count = 0;
// for (int i = 0; i < n - 1; i++)
// for (int j = i + 1; j < n; j++)
// {
// if (dominoes[i] == dominoes[j] || dominoes[i] == vector<int>(dominoes[j].rbegin(), dominoes[j].rend()))
// count++;
// }
// return count;
// }
// };class Solution
{
public:int numEquivDominoPairs(vector<vector<int>> &dominoes){int n = dominoes.size();map<vector<int>, int> hash;for (vector<int> &domino : dominoes){sort(domino.begin(), domino.end());hash[domino]++;}int count = 0;for (auto it = hash.begin(); it != hash.end(); it++){int freq = it->second;// 组合:C(n, 2) = n * (n - 1) / 2count += freq * (freq - 1) / 2;}return count;}
};
// @lc code=end
结果:

复杂度分析:
时间复杂度:O(n),其中 n 是数组 dominoes 的长度。
空间复杂度:O(n),其中 n 是数组 dominoes 的长度。
相关文章:
Leetcode1128. 等价多米诺骨牌对的数量
Every day a Leetcode 题目来源:1128. 等价多米诺骨牌对的数量 解法1:暴力 代码: class Solution { public:int numEquivDominoPairs(vector<vector<int>> &dominoes){int n dominoes.size(), count 0;for (int i 0;…...
Dev-C调试的基本方法2-2
3.3 跳出函数 在图6所示的状态下,点击单步调试(F7)会继续调试下一行,而如果想结束在函数中的调试,则点击图4③所示的跳出函数,或CtrlF8按键跳出f()函数,程序将会停在图5所示的第11行处。 3.4 …...
企业之间的竞争,ISO三体系认证至关重要!
ISO三体系认证是指ISO 9001质量管理体系认证、ISO 14001环境管理体系认证、ISO 45001(OHSAS18001)职业健康安全管理体系认证。企业(组织)自愿申请、通过ISO三体系认证,并贯彻落实,确实能获益多多。 ISO 9001质量管理体系 我们经…...
node教程(四)Mongodb+mongoose
文章目录 一、mongodb1.简介1.1Mongodb是什么?1.2数据库是什么?1.3数据库的作用1.4数据库管理数据的特点 2.核心概念3.下载安装与启动4.命令行交互4.1数据库命令4.3文档命令 二、Mongoose1.介绍2.作用3.使用流程4.插入文档5.mongoose字段类型 一、mongod…...
作为一个初学者,该如何入门大模型?
在生成式 AI 盛行的当下,你是否被这种技术所折服,例如输入一段简简单单的文字,转眼之间,一幅精美的图片,又或者是文笔流畅的文字就展现在你的面前。 相信很多人有这种想法,认为生成式 AI 深不可测…...
编译支持GPU的opencv,并供python的import cv2调用
下载opencv和opencv_contrib,cmake过程中要下载的一些包可以手动下载配置,如果网络较好,也可以等待自动下载。主要记录的是cmake命令: cmake -D CMAKE_BUILD_TYPERELEASE \-D BUILD_opencv_python3YES \-D CMAKE_INSTALL_PREFIX/…...
Bug记录
那些年写过的很小的bug: Bug1: if args.model IRNN or irnn:# some code这实际上不会按你期望的方式工作。原因在于 ‘irnn’ 是一个非空的字符串,因此它在布尔上下文中被视为 True。所以条件总是为真,而不会考虑 args.model 的…...
web3 React dapp中编写balance组件从redux取出并展示用户资产
好啊 上文WEB3 在 React搭建的Dapp中通过redux全局获取并存储用户ETH与自定义token与交易所存储数量中 我们拿到了用户的一个本身 和 交易所token数量 并放进了redux中做了一个全局管理 然后 我们继续 先 起来ganache的一个模拟环境 ganache -d然后 我们启动自己的项目 顺手发…...
BIOS开发笔记 - DDR中的时序参数
通过前一篇文章学习,我们可以大致知道内存条(Module)的组成及SDRAM内部的结构,这一篇再介绍下SDRAM中常见的时序参数以及整个读写操作的流程。 一、外部信号 图1 DDR4的外部线路图 DDR是一种高带宽的传输接口,其外部信号较多,图1是一个DDR4的外部线路图,以下对图中跟通…...
语义分割 - 简介
语义分割是计算机视觉领域的一项重要任务,旨在将图像中的每个像素标记为对应的语义类别。与传统的图像分类任务不同,语义分割不仅要识别整个图像的类别,还需要对图像中的每个像素进行分类,从而实现对图像的像素级别理解。 语义分…...
ch0_OSI 七层网络协议介绍
目录 概述 1、三网融合的概念 三网:电信网络、有线电视网络、计算机网络 概念:把上述三种网络融合成一种网络 2、计算机网络的定义、分类 定义:计算机网络是将地理位置不同的独立计算机系统,通过传输介质链接起来,…...
超声波俱乐部分享:百度世界大会点燃AI创业者新希望
10月22日,2023年第十三期超声波俱乐部内部分享会在北京望京举行。本期的主题是:百度世界大会点燃AI创业者新希望。 到场的嘉宾有:超声波创始人杨子超,超声波联合创始人、和牛商业创始人刘思雨,中国国际经济交流中心研…...
【项目管理】项目计划中常见影响进度的风险汇总
哈喽,大家好,我是雷工。 在项目实施过程中针对项目进度的计划常常会有各种各样的的风险,相比出了问题去救火与填坑,能够提前预知风险,并提前调整计划,更能有利于项目的如期交付。 以下为项目计划中影响进度…...
Apache HttpClient库编写的Scala程序
Apache HttpClient库编写的Scala下载器程序,用于下载图片。代码如下: import org.apache.http.HttpHost import org.apache.http.client.HttpClients import org.apache.http.client.methods.HttpHead import org.apache.http.impl.client.CloseableHtt…...
Java 为什么不推荐在 while 循环中使用 sleep() 我悟了
文章目录 前言原因是否正确方案是否合理定时轮询场景事件机制等待和唤醒 个人简介 前言 最近逛 CSDN 看到一篇文章,文章大意是说为什么在循环中不推荐使用 sleep 操作,原因在于线程挂起和唤醒会有很大的性能消耗,并推荐使用 Timer 及 Schedu…...
编程新手的犯错之路
第1名:无尽的if-else陷阱 在我刚刚学习编程的时候,我对if-else语句的使用充满了好奇。我曾经写下了这样一个愚蠢的代码块,用来判断一个数字属于哪个范围: if (number > 1 && number < 10) {// 做一些事情 } else …...
高级 Python:函数
伊利亚拉扎列维奇 一、说明 读完标题后,你可能会问自己一些类似的事情,“Python 中的函数是一个高级概念?如何?所有课程都引入了功能作为语言的基本块。你既是对的,也是错的。 大多数关于 Python 的课程都将函数作为基…...
【学习笔记】[PA2019] Osady i warownie 2
这题好抽象😱 EI 说这题可以转化为对偶图,但是我完全没看懂😅 考虑维护最向右和向下的两条路径,那么不能放的位置就是两条路径的交(感性理解一下) 考虑抽象的描述这条路径, r i r_i ri表示…...
Flask——接口路由技术
接口路由技术 一、Flask 简介1、环境安装:2、一个最小的应用3、两种运行方式 二、定义路由1、普通路由2、动态路由3、限定类型4、地址尾部的“/” 三、请求与响应-请求方法四、请求与响应-处理请求数据1、request的常用属性/方法2、get 请求参数3、json 请求4、表单…...
Dubbo篇---第一篇
系列文章目录 文章目录 系列文章目录一、说说一次 Dubbo 服务请求流程?二、说说 Dubbo 工作原理三、Dubbo 支持哪些协议?一、说说一次 Dubbo 服务请求流程? 基本工作流程: 上图中角色说明: 二、说说 Dubbo 工作原理 工作原理分 10 层: 第一层:service 层,接口层,…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
