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

【LeetCode】982. 按位与为零的三元组

982. 按位与为零的三元组

题目描述

给你一个整数数组 nums ,返回其中 按位与三元组 的数目。

按位与三元组 是由下标 (i, j, k) 组成的三元组,并满足下述全部条件:

  • 0 <= i < nums.length
  • 0 <= j < nums.length
  • 0 <= k < nums.length
  • nums[i] & nums[j] & nums[k] == 0 ,其中 & 表示按位与运算符。

示例 1

输入:nums = [2,1,3]
输出:12
解释:可以选出如下 i, j, k 三元组:
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2


示例 2

输入:nums = [0,0,0]
输出:27


提示

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] < 216

算法一:哈希表 + 枚举

思路

  • 首先遍历 nums 的前两个值,因为题目中提到 0 <= nums[i] < 216 ,所以我们可以把这两个值按位与的结果存放到哈希表的索引哈希表的值为按位与结果的出现次数,这样的时间复杂度为 O(n2 + 216 * n) 。

收获

  • 我一开始的想法是:先计算前两个的值,存入数组中,然后再遍历数组的值与第三个 num ,但其实这样也是 三重循环,复杂度也是 O(n3) ,显然超时了;因此看了题解,复杂度可以降到 O(n2 + 216 * n)。

算法情况

  • 时间复杂度: O(n2 + 216 * n),其中 n 为 nums.size();

  • 空间复杂度:O(2 16);

    在这里插入图片描述

代码

class Solution {
public:int countTriplets(vector<int>& nums) {int ans = 0;vector<int> cnt(1<<16);for(int x : nums){for(int y : nums){cnt[x & y] ++;}}for(int n : nums){for(int i=0; i<(1<<16); ++i){if((i & n) == 0) ans += cnt[i];}}return ans;}
};

算法二:哈希表 + 枚举优化

思路

在这里插入图片描述在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

算法情况

  • 时间复杂度: O(n(n+U)),其中 n 为 nums 的长度,U=max⁡(nums);

  • 空间复杂度:O(U) 。

    在这里插入图片描述

代码

class Solution {
public:int countTriplets(vector<int>& nums) {int ans = 0;int u=1;// 预先计算数组 cnt 的实际大小for(int n : nums){while(u <= n){u <<= 1;}} vector<int> cnt(u);cnt[0] = nums.size();for(int n : nums){int m = (u-1) ^ n;for(int s=m; s; s=(s-1)&m){cnt[s]++;}}for(int x : nums){for(int y : nums){ans += cnt[x & y];}}return ans;}
};

参考资料

  1. 有技巧的枚举 + 常数优化(Python/Java/C++/Go)

相关文章:

【LeetCode】982. 按位与为零的三元组

982. 按位与为零的三元组 题目描述 给你一个整数数组 nums &#xff0c;返回其中 按位与三元组 的数目。 按位与三元组 是由下标 (i, j, k) 组成的三元组&#xff0c;并满足下述全部条件&#xff1a; 0 < i < nums.length0 < j < nums.length0 < k < num…...

Linux内核源码进程原理分析

Linux内核源码进程原理分析一、Linux 内核架构图二、进程基础知识三、Linux 进程四要素四、task_struct 数据结构主要成员五、创建新进程分析六、剖析进程状态迁移七、写时复制技术一、Linux 内核架构图 二、进程基础知识 Linux 内核把进程称为任务(task)&#xff0c;进程的虚…...

电子技术——CMOS反相器

电子技术——CMOS反相器 在本节&#xff0c;我们深入学习CMOS反相器。 电路原理 下图是我们要研究的CMOS反相器的原理图&#xff1a; 下图展示了当输入 vIVDDv_I V_{DD}vI​VDD​ 时的 iD−vDSi_D-v_{DS}iD​−vDS​ 曲线&#xff1a; 我们把 QNQ_NQN​ 当做是驱动源&#x…...

gazebo仿真轨迹规划+跟踪(不在move_base框架下)

以Tianbot为例子&#xff0c;开源代码如下&#xff1a; https://github.com/tianbot/tianbot_mini GitHub - tianbot/abc_swarm: Ant Bee Cooperative Swarm, indicating air-ground cooperation. This repository is for Tianbot Mini and RoboMaster TT swarm kit. 1.在…...

C. Good Subarrays(前缀和)

C. Good Subarrays一、问题二、分析三、代码一、问题 二、分析 这道题目的意思就是给我们一个数组&#xff0c;然后我们从数组中选取一个连续的区间&#xff0c;这个区间满足条件&#xff1a;区间内的元素和等于区间的长度。 对于区间和问题我们先想到的是前缀和的算法。 那…...

关于Facebook Messenger CRM,这里有你想要知道的一切

关于Facebook Messenger CRM&#xff0c;这里有你想要知道的一切&#xff01;想把Facebook Messenger与你的CRM整合起来吗&#xff1f;这篇博文是为你准备的! 我们将介绍有关获得Facebook Messenger CRM整合的一切信息。然后&#xff0c;我们将解释为什么你需要像SaleSmartly&a…...

ChIP-seq 分析:数据与Peak 基因注释(10)

动动发财的小手&#xff0c;点个赞吧&#xff01; 1. 数据 今天&#xff0c;我们将继续回顾我们在上一次中研究的 Myc ChIPseq。这包括用于 MEL 和 Ch12 细胞系的 Myc ChIPseq。 可在此处[1]找到 MEL 细胞系中 Myc ChIPseq 的信息和文件可在此处[2]找到 Ch12 细胞系中 Myc ChIP…...

《C++ Primer Plus》第18章:探讨 C++ 新标准(8)

使用大括号括起的初始化列表语法重写下述代码。重写后的代码不应使用数组 ar&#xff1a; class Z200 { private:int j;char ch;double z; public:Z200(int jv, char chv, zv) : j(jv), ch(chv), z(zv) {} ... };double x 8.8; std::string s "What a bracing effect!&q…...

YOLO-V5 系列算法和代码解析(八)—— 模型移植

文章目录工程目标芯片参数查阅官方文档基本流程Python 版工具链安装RKNPU2的编译以及使用方法移植自己训练的模型工程目标 将自己训练的目标检测模型【YOLO-V5s】移植到瑞芯微【3566】芯片平台&#xff0c;使用NPU推理&#xff0c;最终得到正确的结果。整个过程涉及模型量化、…...

js实现复制拷贝的兼容方法

1. 定义复制拷贝的方法 在某个工具类方法中定义该方法&#xff0c;兼容不同浏览器处理 /*** description 拷贝的类方法*/ class CopyClass {// constructor() {}setRange(input) {return new Promise((resolve, reject) > {try {// 创建range对象const range document.c…...

学习 Python 之 Pygame 开发魂斗罗(八)

学习 Python 之 Pygame 开发魂斗罗&#xff08;八&#xff09;继续编写魂斗罗1. 创建敌人类2. 增加敌人移动和显示函数3. 敌人开火4. 修改主函数5. 产生敌人6. 使敌人移动继续编写魂斗罗 在上次的博客学习 Python 之 Pygame 开发魂斗罗&#xff08;七&#xff09;中&#xff0…...

Lesson11---分类问题

11.1 逻辑回归 11.1.1 广义线性回归 课程回顾 线性回归&#xff1a;将自变量和因变量之间的关系&#xff0c;用线性模型来表示&#xff1b;根据已知的样本数据&#xff0c;对未来的、或者未知的数据进行估计 11.1.2 逻辑回归 11.1.2.1 分类问题 分类问题&#xff1a;垃圾…...

Python基础学习12——异常

在Python中&#xff0c;会使用“异常”这个十分特殊的对象来管理程序执行期间发生的错误&#xff0c;即报错。本文将介绍一下python基础的处理异常的方法以及一些基本的异常类型。 异常处理方法 try-except代码块 当我们编写程序时&#xff0c;我们可以编写一个try-except代…...

[日常练习]练习17:链表头插法、尾插法练习

[日常练习]练习17&#xff1a;链表头插法、尾插法练习练习17描述输入输出输入示例1输出示例1输入示例2输出示例2代码演示&#xff1a;总结练习17 【日常练习】 链表头插法、尾插法练习 描述 输入3 4 5 6 7 9999一串整数&#xff0c;9999代表结束&#xff0c;通过头插法新建链…...

第十四届蓝桥杯模拟赛(第三期)试题与题解 C++

目录 一、填空题 &#xff08;一&#xff09;最小的十六进制(答案&#xff1a;2730) &#xff08;二&#xff09;Excel的列(答案&#xff1a;BYT) &#xff08;三&#xff09;相等日期(答案&#xff1a;70910) &#xff08;四&#xff09;多少种取法(答案&#xff1a;189)…...

关于 “宏“

起源 宏 Macro"这个词源于希腊语 “makros”&#xff0c;意为“大的&#xff0c;长的” 延伸使用 随后用于计算机领域是&#xff0c;在汇编语言时用于描述一大堆的汇编指令。 只要用宏指令&#xff0c;就是直接用的一大堆的汇编指令&#xff08;有点函数的味道&#xf…...

1.2 CSS标签选择器,类选择器

CSS选择器&#xff1a; 根据不同的需求选出不同的标签&#xff0c;进行美化装饰 1. 标签选择器 标签选择器(元素选择器)&#xff1a;用 HTML标签名作为选择器&#xff0c;按标签名称进行分类&#xff0c;为页面某一类标签指定统一的CSS样式 作用: 可以把某一类标签全部选中&…...

【Linux】进程等待 | 详解 wait/waitpid 的 status 参数

&#x1f923; 爆笑教程 &#x1f449; 《看表情包学Linux》&#x1f448; 猛戳订阅 &#x1f525; &#x1f4ad; 写在前面&#xff1a;在上一章中我们讲解了进程创建与进程终止&#xff0c;本章我们开始讲解进程等待。进程等待这部分知识相较于前面还是较为复杂的&#xff0…...

OpenAI眼中的无线调优策略

问&#xff1a;无线调优策略该怎么优化无线调优是指对无线网络的各种参数进行优化&#xff0c;以提高网络性能和用户体验。以下是几个无线调优策略&#xff1a;频谱分配&#xff1a;通过优化频谱的分配&#xff0c;可以提高网络的容量和覆盖范围。在频谱分配时&#xff0c;需要…...

DataX入门

目录 1. DataX介绍 2. DataX支持的常用数据源类型 3. 设计理念 4. DataX框架设计 4.1. Reader 4.2. Writer 4.3. Framework 5. DataX的运行流程 6. DataX与Sqoop对比 7. 部署 8. 配置详解 9. 案例 同步MySql到HDFS 9.1. 整体结构 9.2. mySqlReader 9.2.1. …...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...