当前位置: 首页 > 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;用来纪念消失的青春。 本…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...