【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缓存服务器使用。它采用事件驱动、异步非阻塞的处理方式,能够处理大量并发连接和高流量负载ÿ…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
