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 <= 10002 <= arr[i] <= 109arr中的所有值 互不相同
实现代码与解析:
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. 带因子的二叉树 题目描述: 实现代码与解析: dp hash 原理思路: 823. 带因子的二叉树 题目描述: 给出一个含有不重复整数元素的数组 arr ,每个整数 arr[i] 均大于 1。 用这些整数来构建二叉树&#x…...
【教学类-35-01】学号+姓名+班级(描字帖)A4一页
背景说明: 本学期我带机动班,其中大4班去的频率比较高,与是我用大四班的名单做了一份 “描字帖”,在9月1日第一天见面时,孩子们用记号笔描字帖时,我也可以对这些孩子初步混个眼熟(聪明的&#x…...
UE5 里的一些常用的了解
# ACharacter、APawn的继承关系 ACharacter -继承自-> APawn -继承自-> AActor和 INavAgentInterface AActor -继承自-> UObject -继承自->UObjectBaseUtility -继承自-> UObjectBase(一个独立的类)INavAgentInterface是一个独立的类 #…...
【网络安全带你练爬虫-100练】第19练:使用python打开exe文件
目录 一、目标1:调用exe文件 二、目标2:调用exe打开文件 一、目标1:调用exe文件 1、subprocess 模块允许在 Python 中启动一个新的进程,并与其进行交互 2、subprocess.run() 函数来启动exe文件 3、subprocess.run(["文件路…...
【2D/3D RRT* 算法】使用快速探索随机树进行最佳路径规划(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
用反射实现自定义Java对象转化为json工具类
传入一个object类型的对象获取该对象的class类getFields方法获取该类的所有属性对属性进行遍历,并且拼接成Json格式的字符串,注意:通过属性名来推断方法名获取Method实例通过invoke方法调用 public static String objectToJsonUtil(Object o…...
rk3568 nvme硬盘分区,格式化,挂载测试
前言 环境介绍: 1.编译环境 Ubuntu 18.04.5 LTS 2.SDK rk356x_linux 3.单板 迅为itop-3568开发板 自制底板 一、查看硬盘 插上硬盘上电,进入系统后通过命令lspci查看nvme硬盘识别情况 [rootRK356X:/]# lspci -k 21:00.0 Class 0108: 1e4b:1202…...
Failed to load ApplicationContext解决办法,spring版本问题
有如下报错: "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 问题 提示为: 无法通过TLS到RDP服务器… 分析 原因是Remmina需要使用openssl通过RDP加密与Windows计算机连接,而ubuntu22.04系统中OpenSSL版本为3.0,Openssl3 将 tls<1.2 和 sha1 的默认安全级别…...
【uniapp】this有时为啥打印的是undefined?(箭头函数修改this)
😉博主:初映CY的前说(前端领域) ,📒本文核心:uniapp中this指向问题 前言:this大家知道是我们当前项目的实例,我们可以在这个this上面拿到我们原型上的全部数据。这个常用在我们在方法中调用其他方法使用。 …...
2023高教社杯数学建模思路 - 复盘:光照强度计算的优化模型
文章目录 0 赛题思路1 问题要求2 假设约定3 符号约定4 建立模型5 模型求解6 实现代码 建模资料 0 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 1 问题要求 现在已知一个教室长为15米,宽为12米&…...
河道漂浮物检测:安防监控/视频智能分析/AI算法智能分析技术如何助力河道整治工作?
随着社会的发展和人们生活水平的进步,水污染问题也越来越严重,水资源监管和治理成为城市发展的一大困扰,水面上的漂浮垃圾不仅会影响河道生态安全并阻碍船舶航行,还会影响人们的身体健康。 TSINGSEEE青犀AI智能分析平台在环保场景…...
Dubbo 应用切换 ZooKeeper 注册中心实例,流量无损迁移
首先思考一个问题:如果 Dubbo 应用使用 ZooKeeper 作为注册中心,现在需要切换到新的 ZooKeeper 实例,如何做到流量无损? 本文提供解决这个问题的一种方案。 场景 有两个基于 Dubbo 的微服务应用,一个是服务提供者&…...
ADB入门教程
安卓开发 文章目录 安卓开发前言USB 连接链接 前言 基本用法 命令语法 adb 命令的基本语法如下: adb [-d|-e|-s <serialNumber>] <command>如果只有一个设备/模拟器连接时,可以省略掉 [-d|-e|-s ] 这一部分,直接使用 adb 。 为…...
SQLPro Studio for Mac:强大的SQL开发和管理工具
SQLPro Studio for Mac是一款强大的Mac上使用的SQL开发和管理工具,它支持各种数据库,包括MySQL,PostgreSQL,SQLite等。使用 SQLPro Studio,您可以轻松地连接和管理您的数据库,执行SQL查询和脚本,…...
淘宝API技术解析,实现按图搜索淘宝商品
淘宝提供了开放平台接口(API)来实现按图搜索淘宝商品的功能。您可以通过以下步骤来实现: 1. 获取开放平台的访问权限:首先,您需要在淘宝开放平台创建一个应用,获取访问淘宝API的权限。具体的申请步骤和要求…...
错误:依赖检测失败: mysql-community-libs(x86-64) >= 5.7.9 被 (已安裝) mysql-community-li
错误: 错误原因:没有删除之前安装的依赖问题 解决办法: yum remove mysql-libs 再用下面指令检查一遍: rpm -qa | grep mysql 如果有还未清理的,用下面指令: rpm -e xxx...
使用MATLAB解算炼油厂的选址
背景 记得有一年的数据建模大赛,试题是炼油厂的选址,最后我们采用MATLAB编写(复制)蒙特卡洛算法,还到了省级一等奖,这里把仅有一些记忆和材料,放到这里来,用来纪念消失的青春。 本…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
