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

​LeetCode解法汇总823. 带因子的二叉树

 目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台


描述:

给出一个含有不重复整数元素的数组 arr ,每个整数 arr[i] 均大于 1。

用这些整数来构建二叉树,每个整数可以使用任意次数。其中:每个非叶结点的值应等于它的两个子结点的值的乘积。

满足条件的二叉树一共有多少个?答案可能很大,返回 对 109 + 7 取余 的结果。

示例 1:

输入: arr = [2, 4]
输出: 3
解释: 可以得到这些二叉树: [2], [4], [4, 2, 2]

示例 2:

输入: arr = [2, 4, 5, 10]
输出: 7
解释: 可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

提示:

  • 1 <= arr.length <= 1000
  • 2 <= arr[i] <= 109
  • arr 中的所有值 互不相同

解题思路:

从小到大排列,后面的数字,一定是前面数字的乘积。所以我们先求前面的值二叉树可能数量,并且保存下来。后面的值如果存在两个数的乘积,就是前面两个数的可能数量的乘积,如果两个数不同,则还需要乘以2,因为左右位置可以调换。

代码:

class Solution823
{
public:int numFactoredBinaryTrees(vector<int> &arr){sort(arr.begin(), arr.end());map<int, long long> numMap;long long sum = 0;int index = 0;long long mod = 1e9 + 7;while (index < arr.size()){int i = 0;long long num = 1;int currentValue = arr[index];while (arr[i] <= (currentValue / arr[i])){if (currentValue % arr[i] != 0){i++;continue;}int value = currentValue / arr[i];if (numMap.find(value) == numMap.end()){i++;continue;}if (value == arr[i]){num = (num + numMap[value] * numMap[value]) % mod;}else{num = (num + (numMap[value] * numMap[arr[i]] * 2)) % mod;}i++;}sum = (sum + num) % mod;numMap[currentValue] = num;index++;}return sum;}
};

相关文章:

​LeetCode解法汇总823. 带因子的二叉树

目录链接&#xff1a; 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目&#xff1a; https://github.com/September26/java-algorithms 原题链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 描述&#xff1a; 给出一个含…...

TypeScript的变量声明的各种方式

TypeScript是一种静态类型的JavaScript超集&#xff0c;它为JavaScript代码提供了类型检查和更好的代码组织结构。在TypeScript中&#xff0c;变量声明是非常重要的&#xff0c;因为它们定义了变量的类型和范围。本文将详细介绍TypeScript的变量声明&#xff0c;并通过代码案例…...

c++ lambda

Lambda Lambda 表达式一般用于定义匿名函数&#xff0c;使得代码更加灵活简洁&#xff0c;优点&#xff1a; 声明式编程风格&#xff1a;就地匿名定义目标函数或函数对象&#xff0c;不需要额外写一个命名函数或者函数对象。以更直接的方式去写程序&#xff0c;好的可读性和可…...

泊松回归和地理加权泊松回归

01 泊松回归 泊松回归(Poisson Regression)是一种广义线性模型,用于建立离散型响应变量(计数数据)与一个或多个预测变量之间的关系。它以法国数学家西蒙丹尼泊松(Simon Denis Poisson)的名字命名,适用于计算“事件发生次数”的概率,比如交通事故发生次数、产品缺陷数…...

【数学建模竞赛】各类题型及解题方案

评价类赛题建模流程及总结 建模步骤 建立评价指标->评价体系->同向化处理&#xff08;都越多越好或越少越少&#xff09;->指标无量纲处理 ->权重-> 主客观->合成 主客观评价问题的区别 主客观概念主要是在指标定权时来划分的。主观评价与客观评价的区别…...

【12期】谈一谈redis两种持久化机制的区别?

Redis两类持续性的方法 RDB方案可以在规定时间间隔内创建数据集的时间点快照。 AOF方案记录了服务器执行的所有写操作命令&#xff0c;并在服务器启动时通过重新执行这些命令来还原数据集。AOF文件完全遵循Redis协议格式保存&#xff0c;新命令会被追加到文件末尾。此外&#…...

Lambda 编程(Kotlin)一

学习记录&#xff0c;以下为个人理解 知识点&#xff1a; Lambda的定义&#xff1a;允许你把代码块当作参数传递给函数Lambda的语法约定&#xff1a;如果lambda 表达式是函数调用的最后一个实参&#xff0c;它可以放到括号的外边当lambda表达式时函数唯一的实参时&#xff0c…...

网络字节序——TCP接口及其实现简单TCP服务器

网络字节序——TCP接口及其实现简单TCP服务器 文章目录 网络字节序——TCP接口及其实现简单TCP服务器简单TCP服务器的实现1. 单进程版&#xff1a;客户端串行版2. 多进程版&#xff1a;客户端并行版netstat查看网络信息3.多线程版&#xff1a;并行执行log.hpp 守护进程fg、bg s…...

RxJS如何根据事件创建Observable对象?

RxJS提供了一些用来创建Observable对象的函数&#xff0c;我们可以根据事件、定时器、Promise&#xff0c;AJAX等来创建Observable对象。 下面是根据事件创建Observable对象的几个例子。 this.outsideClick$ fromEvent(document, click).subscribe((event: MouseEvent) > …...

网站常见安全漏洞 | 青训营

Powered by:NEFU AB-IN 文章目录 网站常见安全漏洞 | 青训营 网站基本组成及漏洞定义服务端漏洞SQL注入命令执行越权漏洞SSRF文件上传漏洞 客户端漏洞开放重定向XSSCSRF点击劫持CORS跨域配置错误WebSocket 网站常见安全漏洞 | 青训营 网站常见安全漏洞-网站基本组成及漏洞定义…...

vue2使用 vis-network 和 vue-vis-network 插件封装一个公用的关联关系图

效果图&#xff1a; vis组件库&#xff1a;vis.js vis-network中文文档&#xff1a;vis-network 安装组件库&#xff1a; npm install vis-network vue-vis-network 或 yarn add vis-network vue-vis-network 新建RelationGraph.vue文件&#xff1a; <template><…...

给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。

LeetCode第73题矩阵置零 1.思路&#xff1a; 想到一个开辟一点空间来解决方法&#xff0c;使用哈希集。就是使用一个哈希集&#xff08;row和col&#xff09;来储存数组中的元素为0的下标。然后再遍历&#xff0c;整个二维数组&#xff0c;在哈希集中存在对应的下标&#xff0c…...

java-初识Servlet,Tomcat,JDBC

文章目录 前言一、ServletServlet 生命周期Servlet 实例Servlet 过滤器 二、TomcatJDBCJDBC连接数据库实例 总结 前言 java入门须知的重要概念/名词/技术 等 一、Servlet Servlet是Java Web开发中的一个核心组件&#xff0c;它是基于Java语言编写的服务器端程序&#xff0c;…...

SpringBoot+mybatis+pgsql多个数据源配置

一、配置文件 jdk环境&#xff1a;1.8 配置了双数据源springbootdruidpgsql&#xff0c;application.properties配置修改如下&#xff1a; #当前入库主数据库 spring.primary.datasource.typecom.alibaba.druid.pool.DruidDataSource spring.primary.datasource.driver-class…...

视频汇聚/视频监控管理平台EasyCVR接入海康SDK协议后无法播放该如何解决?

开源EasyDarwin视频监控/安防监控/视频汇聚EasyCVR能在复杂的网络环境中&#xff0c;将分散的各类视频资源进行统一汇聚、整合、集中管理&#xff0c;在视频监控播放上&#xff0c;视频安防监控汇聚平台可支持1、4、9、16个画面窗口播放&#xff0c;可同时播放多路视频流&#…...

MQ消息队列(主要介绍RabbitMQ)

消息队列概念&#xff1a;是在消息的传输过程中保存消息的容器。 作用&#xff1a;异步处理、应用解耦、流量控制..... RabbitMQ&#xff1a; SpringBoot继承RabbitMQ步骤&#xff1a; 1.加入依赖 <dependency><groupId>org.springframework.boot</groupId&g…...

2023年7月天猫糕点市场数据分析(天猫数据怎么看)

烘焙食品行业是近几年食品领域比较火热的赛道之一&#xff0c;随着居民饮食结构的变化&#xff0c;人均消费水平的上升&#xff0c;蛋糕、面包等烘焙糕点越发成为消费者饮食的重要组成部分。同时&#xff0c;在烘焙糕点市场中&#xff0c;老品牌不断推新迭变&#xff0c;新品牌…...

开源双语对话语言模型 ChatGLM-6B 本地私有化部署

本文首发于&#xff1a;https://www.licorne.ink/2023/08/llm-chatglm-6b-local-deploy/ ChatGLM-6B 是一个开源的、支持中英双语的对话语言模型&#xff0c;基于 General Language Model (GLM) 架构&#xff0c;具有 62 亿参数。结合模型量化技术&#xff0c;用户可以在消费级…...

Zabbix 5.0 媒体介质 邮箱配置例子

QQ企业邮箱 参考&#xff1a;zabbix 腾讯企业邮箱配置图_harveymomo的博客-CSDN博客...

基于Red Hat Enterprise Linux 7操作系统的PostgresSql15的备份恢复(实践笔记)

零、前言 本文是基于阿里云ECS服务器进行的实践操作&#xff0c;操作系统版本&#xff1a;Red Hat Enterprise Linux 7 PG数据库版本&#xff1a;PostgresSql 15 PG安装方式&#xff1a;yum 由于本人新接触pg数据&#xff0c;本次也是出于好奇&#xff0c;就对pg数据库的pg_du…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...