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编写(复制)蒙特卡洛算法,还到了省级一等奖,这里把仅有一些记忆和材料,放到这里来,用来纪念消失的青春。 本…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
