【LeetCode - 每日一题】823. 带因子的二叉树 (2023.08.29)
823. 带因子的二叉树
题意
- 元素都大于1,元素不重复。
- 计数满足要求的二叉树(每个非叶结点的值应等于它的两个子结点的值的乘积)的数量。
- 元素可以重复使用。
代码
自上而下动态规划。
- 所有元素大于1,所以不会有 自己×自己=自己 的情况;
- 元素本身就是一棵二叉树,所以将
dp初始化为全 1; - 将数组
arr排序后,遍历数组arr,当arr[i]为根节点时,其子结点必然在arr[0]~arr[i-1]之间;- 在
arr[0]~arr[i-1]之间寻找(long long)arr[left] * arr[right] == arr[i]。当left == right时,dp[i] += dp[left] * dp[right];当left != right时,dp[i] += 2 * dp[left] * dp[right];
- 在
class Solution {
public:int MAXN = 1e9 + 7;int numFactoredBinaryTrees(vector<int>& arr) {sort(arr.begin(), arr.end());int n = arr.size();vector<long long> dp(n+1, 1); // 单个根节点的符合要求的二叉树数量就可能溢出,用 longlong// dp[0] = 1; // 最小的数,只有一棵符合要求的二叉树for(int i = 1; i < n; i++){// 子结点只能在 0 ~ i-1 之间(因为元素都大于1)int left = 0, right = i-1;while(left <= right) // 元素可被多次使用,所以要 <={if((long long)arr[left] * arr[right] == arr[i]) // 可能溢出,用 longlong{// if(arr[left] != arr[right]) 元素不会重复,可以直接比较下标if(left != right){dp[i] += 2 * dp[left] * dp[right];}else{dp[i] += dp[left] * dp[right];}left++;}else if((long long)arr[left] * arr[right] <= arr[i]) // 可能溢出,用 longlong{left++;}else{right--;}}}long long ans = 0;for(int i = 0; i < n; i++){ans += dp[i];ans = ans % MAXN;}return ans;}
};
复杂度
时间复杂度:O(N2),对每个元素遍历一次其之前的元素。
空间复杂度:O(N),存储 dp 数组。
相关文章:
【LeetCode - 每日一题】823. 带因子的二叉树 (2023.08.29)
823. 带因子的二叉树 题意 元素都大于1,元素不重复。计数满足要求的二叉树(每个非叶结点的值应等于它的两个子结点的值的乘积)的数量。元素可以重复使用。 代码 自上而下动态规划。 所有元素大于1,所以不会有 自己自己自己 的…...
flutter 上传图片并裁剪
1.首先在pubspec.yaml文件中新增依赖pub.dev image_picker: ^0.8.75 image_cropper: ^4.0.1 2.在Android的AndroidManifest.xml文件里面添加权限 <activityandroid:name"com.yalantis.ucrop.UCropActivity"android:screenOrientation"portrait"andro…...
一台服务器上部署 Redis 伪集群
哈喽大家好,我是咸鱼 今天这篇文章介绍如何在一台服务器(以 CentOS 7.9 为例)上通过 redis-trib.rb 工具搭建 Redis cluster (三主三从) redis-trib.rb 是一个基于 Ruby 编写的脚本,其功能涵盖了创建、管…...
ealtek高清晰音频管理器(realtek高清晰音频管理器怎么设置win10)
本文为大家介绍realtek高清晰音频管理器(realtek高清晰音频管理器怎么设置win10),下面和小编一起看看详细内容吧。 我们都使用电脑来听音乐、看电影或者进行其他操作,但是如果我们觉得电脑产生的音效不够立体,我们就会想要去Realtek来设置音…...
微信小程序 scroll-view 组件的 bindscroll 不触发不生效
使用微信小程序基础组件中的scroll-view,但是滑动的时候 bindscroll 一直不生效。 <view class"container log-list"><scroll-view scroll-y style"height:100%;white-space:nowrap;" scroll-into-view"{{toView}}" enable…...
datax 删除分区数据,再写入MySQL脚本
#! /bin/bashDATAX_HOME/opt/module/datax#1、判断参数是否传入 if [ $# -lt 1 ] thenecho "必须传入all/表名..."exit fi #2、判断日期是否传入 [ "$2" ] && datestr$2 || datestr$(date -d -1 day %F)#DataX导出路径不允许存在空文件,…...
hyperf 十四 国际化
一 安装 composer require hyperf/translation:v2.2.33 二 配置 1、设置语言文件 文件结构: /storage/languages/en/messages.php /storage/languages/zh_CH/messages.php // storage/languages/en/messages.php return [welcome > Welcome to our applicat…...
C语言_初识C语言指针
文章目录 前言一、指针 ... 一个内存单元多大比较合适?二、地址或者编号如何产生?三、指针变量的大小 前言 内存是电脑上特别重要的存储器,计算机中程序的运行都是在内存中进行的。 所以为了有效的使用内存,就把内存划分成一个个…...
EMQX启用双向SSL/TLS安全连接以及java连接
作为基于现代密码学公钥算法的安全协议,TLS/SSL 能在计算机通讯网络上保证传输安全,EMQX 内置对 TLS/SSL 的支持,包括支持单/双向认证、X.509 证书、负载均衡 SSL 等多种安全认证。你可以为 EMQX 支持的所有协议启用 SSL/TLS,也可…...
4399面试总结C/C++游戏开发
主要流程 首先询问了C/C知识点 然后询问操作系统,计算机组成,数据结构,计算机网络哪两门熟悉 涉及的相关问题 多态的概念 tcp,udp? tcp,udp区别 tcp可靠,udp不可靠 tcp这个链接的过程? 一个TCP连接必须要经过三次“…...
hashlib 模块学习
hashlib 是 Python 标准库中用于散列和摘要算法的模块。散列算法将输入数据转换为固定长度的散列值(也称为摘要),并且对于相同的输入始终生成相同的散列值。这对于存储密码、数字签名、数据完整性验证等领域非常有用。以下是对 hashlib 模块的…...
大模型开发05:PDF 翻译工具开发实战
大模型开发实战05:PDF 翻译工具开发实战 PDF-Translator 机器翻译是最广泛和基础的 NLP 任务 PDF-Translator PDF 翻译器是一个使用 AI 大模型技术将英文 PDF 书籍翻译成中文的工具。这个工具使用了大型语言模型 (LLMs),如 ChatGLM 和 OpenAI 的 GPT-3 以及 GPT-3.5 Turbo 来…...
LeetCode 43题:字符串相乘
题目 给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。 注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。 示例 1: 输入: num1 "2", num2 "3&…...
基于java Swing 和 mysql实现的飞机订票系统(源码+数据库+ppt+ER图+流程图+架构说明+论文+运行视频指导)
一、项目简介 本项目是一套基于java Swing 和 mysql实现的飞机订票系统,主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的Java学习者。 包含:项目源码、项目文档、数据库脚本等,该项目附带全部源码可作为毕设使用。 项目都经过…...
Jmeter性能综合实战 —— 签到及批量签到
提取性能测试的三个方面:核心、高频、基础功能 签 到 请 求 步 骤 1、准备工作: 签到线程组n HTTP请求默认值n HTTP cookie 管理器n 首页访问请求n 登录请求n 查看结果树n 调试取样器l HTTP代理服务器 (1)创建线程组 …...
燃气管网监测系统,提升城市燃气安全防控能力
燃气是我们日常生活中不可或缺的能源,但其具有易燃易爆特性,燃气安全使用、泄漏监测尤为重要。当前全国燃气安全事故仍呈现多发频发态势,从公共安全的视角来看,燃气已成为城市安全的重大隐忧!因此,建立一个…...
【SQL】1731. 每位经理的下属员工数量 ( 新思想:确定左表,依次添加后续字段)
leetcode题目链接 注意点 确定左表(即,确定result表中的主键),依次添加后续字段。注意:主键可能是一个字段,也可能是多个字段COUNT(DISTINCT()),一般为了防止重复,使用COUNT计数时,…...
AMD Radeon RX 7000/6000系列显卡安装ROCm 调用CUDA
A卡用户画图炼丹、跑大模型甚至是跑机器学习、深度学习的有福了~ 注意:ROCm目前仅限在Linux系统下可用,Windows暂不支持 1. 安装ROCm RX6000系列及以下显卡使用ROCm 5.4.2稳定版本命令 【支持包括桌面级AMD Radeon RX6950XT、RX6900XT、RX6800XT、RX6…...
钉钉小程序引用阿里巴巴图标
2.打开的界面如图,先建一个iconfont.acss文件,全选浏览器打开的样式代码,复制粘贴进新建的iconfont.acss文件中 3.使用...
深入了解Nginx:高性能的开源Web服务器与反向代理
一、Nginx是什么 Nginx是一款轻量级的Web 服务器/反向代理服务器及电子邮件(IMAP/POP3)代理服务器,也可以作为负载均衡器和HTTP缓存服务器使用。它采用事件驱动、异步非阻塞的处理方式,能够处理大量并发连接和高流量负载ÿ…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
