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

LeetCode每日一题:823. 带因子的二叉树(2023.8.29 C++)

目录

823. 带因子的二叉树

题目描述:

实现代码与解析:

dp + hash

原理思路:


823. 带因子的二叉树

题目描述:

        给出一个含有不重复整数元素的数组 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 中的所有值 互不相同

实现代码与解析:

dp + hash

class Solution {
public:int mod = 1e9 + 7;int numFactoredBinaryTrees(vector<int>& arr) {unordered_map<long, long> f; // 以 first 为根的种类为 secondsort(arr.begin(), arr.end());for (auto t: arr) f[t] = 1;for (int i = 0; i < arr.size(); i++){for (int j = 0; j < i; j++){long long x = arr[i], y = arr[j];if (x % y == 0 && f.count(x / y)) f[x] += f[y] * f[x / y] % mod;}}long res = 0;for (auto [a, b]: f)res = (res + b) % mod;return res;}
};

原理思路:

        dp含义:以 first 为 根 的种类为 second。

        这里为什么没用数组来存dp呢,如果我们这里用数组存,后面要判断一个数的因数是否存在arr中也要再定义一个hash,等于说这个map其两个作用,一个是dp,一个是hash。当然也可以不用hash,用双指针或者二分也可以找到。  

        遍历顺序肯定是从树底到顶,也就是从小到大,排序后开始遍历。

        若x 可整除 y 并且 两个因数y , x / y都在arr中,那么f[ i ] += f[x] += f[y] * f[x / y]; (种类是子树种类乘积)

        最后sum一下即可。

相关文章:

LeetCode每日一题:823. 带因子的二叉树(2023.8.29 C++)

目录 823. 带因子的二叉树 题目描述&#xff1a; 实现代码与解析&#xff1a; dp hash 原理思路&#xff1a; 823. 带因子的二叉树 题目描述&#xff1a; 给出一个含有不重复整数元素的数组 arr &#xff0c;每个整数 arr[i] 均大于 1。 用这些整数来构建二叉树&#x…...

【教学类-35-01】学号+姓名+班级(描字帖)A4一页

背景说明&#xff1a; 本学期我带机动班&#xff0c;其中大4班去的频率比较高&#xff0c;与是我用大四班的名单做了一份 “描字帖”&#xff0c;在9月1日第一天见面时&#xff0c;孩子们用记号笔描字帖时&#xff0c;我也可以对这些孩子初步混个眼熟&#xff08;聪明的&#x…...

UE5 里的一些常用的了解

# ACharacter、APawn的继承关系 ACharacter -继承自-> APawn -继承自-> AActor和 INavAgentInterface AActor -继承自-> UObject -继承自->UObjectBaseUtility -继承自-> UObjectBase&#xff08;一个独立的类&#xff09;INavAgentInterface是一个独立的类 #…...

【网络安全带你练爬虫-100练】第19练:使用python打开exe文件

目录 一、目标1&#xff1a;调用exe文件 二、目标2&#xff1a;调用exe打开文件 一、目标1&#xff1a;调用exe文件 1、subprocess 模块允许在 Python 中启动一个新的进程&#xff0c;并与其进行交互 2、subprocess.run() 函数来启动exe文件 3、subprocess.run(["文件路…...

【2D/3D RRT* 算法】使用快速探索随机树进行最佳路径规划(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

用反射实现自定义Java对象转化为json工具类

传入一个object类型的对象获取该对象的class类getFields方法获取该类的所有属性对属性进行遍历&#xff0c;并且拼接成Json格式的字符串&#xff0c;注意&#xff1a;通过属性名来推断方法名获取Method实例通过invoke方法调用 public static String objectToJsonUtil(Object o…...

rk3568 nvme硬盘分区,格式化,挂载测试

前言 环境介绍&#xff1a; 1.编译环境 Ubuntu 18.04.5 LTS 2.SDK rk356x_linux 3.单板 迅为itop-3568开发板 自制底板 一、查看硬盘 插上硬盘上电&#xff0c;进入系统后通过命令lspci查看nvme硬盘识别情况 [rootRK356X:/]# lspci -k 21:00.0 Class 0108: 1e4b:1202…...

Failed to load ApplicationContext解决办法,spring版本问题

有如下报错&#xff1a; "D:\Program Files\Java\jdk-13.0.1\bin\java.exe" -agentlib:jdwptransportdt_socket,address127.0.0.1:7325,suspendy,servern -ea -Didea.test.cyclic.buffer.size1048576 -Dfile.encodingUTF-8 -classpath "D:\Program Files\JetBr…...

Is f(z)=1/z truly an analytic function

https://math.stackexchange.com/questions/755566/is-fz-1-z-truly-an-analytic-function...

代理模式 静态代理和动态代理(jdk、cglib)——Java入职第十一天

一、代理模式 一个类代表另一个类去完成扩展功能,在主体类的基础上,新增一个代理类,扩展主体类功能,不影响主体,完成额外功能。比如买车票,可以去代理点买,不用去火车站,主要包括静态代理和动态代理两种模式。 代理类中包含了主体类 二、静态代理 无法根据业务扩展,…...

Remmina在ubuntu22.04中无法连接Windows

Remmina在ubuntu22.04中无法连接Windows 问题 提示为&#xff1a; 无法通过TLS到RDP服务器… 分析 原因是Remmina需要使用openssl通过RDP加密与Windows计算机连接&#xff0c;而ubuntu22.04系统中OpenSSL版本为3.0&#xff0c;Openssl3 将 tls<1.2 和 sha1 的默认安全级别…...

【uniapp】this有时为啥打印的是undefined?(箭头函数修改this)

&#x1f609;博主&#xff1a;初映CY的前说(前端领域) ,&#x1f4d2;本文核心&#xff1a;uniapp中this指向问题 前言&#xff1a;this大家知道是我们当前项目的实例&#xff0c;我们可以在这个this上面拿到我们原型上的全部数据。这个常用在我们在方法中调用其他方法使用。 …...

2023高教社杯数学建模思路 - 复盘:光照强度计算的优化模型

文章目录 0 赛题思路1 问题要求2 假设约定3 符号约定4 建立模型5 模型求解6 实现代码 建模资料 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 1 问题要求 现在已知一个教室长为15米&#xff0c;宽为12米&…...

河道漂浮物检测:安防监控/视频智能分析/AI算法智能分析技术如何助力河道整治工作?

随着社会的发展和人们生活水平的进步&#xff0c;水污染问题也越来越严重&#xff0c;水资源监管和治理成为城市发展的一大困扰&#xff0c;水面上的漂浮垃圾不仅会影响河道生态安全并阻碍船舶航行&#xff0c;还会影响人们的身体健康。 TSINGSEEE青犀AI智能分析平台在环保场景…...

Dubbo 应用切换 ZooKeeper 注册中心实例,流量无损迁移

首先思考一个问题&#xff1a;如果 Dubbo 应用使用 ZooKeeper 作为注册中心&#xff0c;现在需要切换到新的 ZooKeeper 实例&#xff0c;如何做到流量无损&#xff1f; 本文提供解决这个问题的一种方案。 场景 有两个基于 Dubbo 的微服务应用&#xff0c;一个是服务提供者&…...

ADB入门教程

安卓开发 文章目录 安卓开发前言USB 连接链接 前言 基本用法 命令语法 adb 命令的基本语法如下&#xff1a; adb [-d|-e|-s <serialNumber>] <command>如果只有一个设备/模拟器连接时&#xff0c;可以省略掉 [-d|-e|-s ] 这一部分&#xff0c;直接使用 adb 。 为…...

SQLPro Studio for Mac:强大的SQL开发和管理工具

SQLPro Studio for Mac是一款强大的Mac上使用的SQL开发和管理工具&#xff0c;它支持各种数据库&#xff0c;包括MySQL&#xff0c;PostgreSQL&#xff0c;SQLite等。使用 SQLPro Studio&#xff0c;您可以轻松地连接和管理您的数据库&#xff0c;执行SQL查询和脚本&#xff0c…...

淘宝API技术解析,实现按图搜索淘宝商品

淘宝提供了开放平台接口&#xff08;API&#xff09;来实现按图搜索淘宝商品的功能。您可以通过以下步骤来实现&#xff1a; 1. 获取开放平台的访问权限&#xff1a;首先&#xff0c;您需要在淘宝开放平台创建一个应用&#xff0c;获取访问淘宝API的权限。具体的申请步骤和要求…...

错误:依赖检测失败: mysql-community-libs(x86-64) >= 5.7.9 被 (已安裝) mysql-community-li

错误&#xff1a; 错误原因&#xff1a;没有删除之前安装的依赖问题 解决办法&#xff1a; yum remove mysql-libs 再用下面指令检查一遍&#xff1a; rpm -qa | grep mysql 如果有还未清理的&#xff0c;用下面指令&#xff1a; rpm -e xxx...

使用MATLAB解算炼油厂的选址

背景 记得有一年的数据建模大赛&#xff0c;试题是炼油厂的选址&#xff0c;最后我们采用MATLAB编写&#xff08;复制&#xff09;蒙特卡洛算法&#xff0c;还到了省级一等奖&#xff0c;这里把仅有一些记忆和材料&#xff0c;放到这里来&#xff0c;用来纪念消失的青春。 本…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

pam_env.so模块配置解析

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

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...