当前位置: 首页 > news >正文

【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&#xff0c;元素不重复。计数满足要求的二叉树&#xff08;每个非叶结点的值应等于它的两个子结点的值的乘积&#xff09;的数量。元素可以重复使用。 代码 自上而下动态规划。 所有元素大于1&#xff0c;所以不会有 自己自己自己 的…...

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 伪集群

哈喽大家好&#xff0c;我是咸鱼 今天这篇文章介绍如何在一台服务器&#xff08;以 CentOS 7.9 为例&#xff09;上通过 redis-trib.rb 工具搭建 Redis cluster &#xff08;三主三从&#xff09; redis-trib.rb 是一个基于 Ruby 编写的脚本&#xff0c;其功能涵盖了创建、管…...

ealtek高清晰音频管理器(realtek高清晰音频管理器怎么设置win10)

本文为大家介绍realtek高清晰音频管理器(realtek高清晰音频管理器怎么设置win10)&#xff0c;下面和小编一起看看详细内容吧。 我们都使用电脑来听音乐、看电影或者进行其他操作&#xff0c;但是如果我们觉得电脑产生的音效不够立体&#xff0c;我们就会想要去Realtek来设置音…...

微信小程序 scroll-view 组件的 bindscroll 不触发不生效

使用微信小程序基础组件中的scroll-view&#xff0c;但是滑动的时候 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导出路径不允许存在空文件&#xff0c…...

hyperf 十四 国际化

一 安装 composer require hyperf/translation:v2.2.33 二 配置 1、设置语言文件 文件结构&#xff1a; /storage/languages/en/messages.php /storage/languages/zh_CH/messages.php // storage/languages/en/messages.php return [welcome > Welcome to our applicat…...

C语言_初识C语言指针

文章目录 前言一、指针 ... 一个内存单元多大比较合适&#xff1f;二、地址或者编号如何产生&#xff1f;三、指针变量的大小 前言 内存是电脑上特别重要的存储器&#xff0c;计算机中程序的运行都是在内存中进行的。 所以为了有效的使用内存&#xff0c;就把内存划分成一个个…...

EMQX启用双向SSL/TLS安全连接以及java连接

作为基于现代密码学公钥算法的安全协议&#xff0c;TLS/SSL 能在计算机通讯网络上保证传输安全&#xff0c;EMQX 内置对 TLS/SSL 的支持&#xff0c;包括支持单/双向认证、X.509 证书、负载均衡 SSL 等多种安全认证。你可以为 EMQX 支持的所有协议启用 SSL/TLS&#xff0c;也可…...

4399面试总结C/C++游戏开发

主要流程 首先询问了C/C知识点 然后询问操作系统&#xff0c;计算机组成&#xff0c;数据结构&#xff0c;计算机网络哪两门熟悉 涉及的相关问题 多态的概念 tcp,udp&#xff1f; tcp,udp区别 tcp可靠&#xff0c;udp不可靠 tcp这个链接的过程? 一个TCP连接必须要经过三次“…...

hashlib 模块学习

hashlib 是 Python 标准库中用于散列和摘要算法的模块。散列算法将输入数据转换为固定长度的散列值&#xff08;也称为摘要&#xff09;&#xff0c;并且对于相同的输入始终生成相同的散列值。这对于存储密码、数字签名、数据完整性验证等领域非常有用。以下是对 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&#xff0c;返回 num1 和 num2 的乘积&#xff0c;它们的乘积也表示为字符串形式。 注意&#xff1a;不能使用任何内置的 BigInteger 库或直接将输入转换为整数。 示例 1: 输入: num1 "2", num2 "3&…...

基于java Swing 和 mysql实现的飞机订票系统(源码+数据库+ppt+ER图+流程图+架构说明+论文+运行视频指导)

一、项目简介 本项目是一套基于java Swing 和 mysql实现的飞机订票系统&#xff0c;主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的Java学习者。 包含&#xff1a;项目源码、项目文档、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过…...

Jmeter性能综合实战 —— 签到及批量签到

提取性能测试的三个方面&#xff1a;核心、高频、基础功能 签 到 请 求 步 骤 1、准备工作&#xff1a; 签到线程组n HTTP请求默认值n HTTP cookie 管理器n 首页访问请求n 登录请求n 查看结果树n 调试取样器l HTTP代理服务器 &#xff08;1&#xff09;创建线程组 &#xf…...

燃气管网监测系统,提升城市燃气安全防控能力

燃气是我们日常生活中不可或缺的能源&#xff0c;但其具有易燃易爆特性&#xff0c;燃气安全使用、泄漏监测尤为重要。当前全国燃气安全事故仍呈现多发频发态势&#xff0c;从公共安全的视角来看&#xff0c;燃气已成为城市安全的重大隐忧&#xff01;因此&#xff0c;建立一个…...

【SQL】1731. 每位经理的下属员工数量 ( 新思想:确定左表,依次添加后续字段)

leetcode题目链接 注意点 确定左表&#xff08;即&#xff0c;确定result表中的主键)&#xff0c;依次添加后续字段。注意&#xff1a;主键可能是一个字段&#xff0c;也可能是多个字段COUNT(DISTINCT())&#xff0c;一般为了防止重复&#xff0c;使用COUNT计数时&#xff0c…...

AMD Radeon RX 7000/6000系列显卡安装ROCm 调用CUDA

A卡用户画图炼丹、跑大模型甚至是跑机器学习、深度学习的有福了~ 注意&#xff1a;ROCm目前仅限在Linux系统下可用&#xff0c;Windows暂不支持 1. 安装ROCm RX6000系列及以下显卡使用ROCm 5.4.2稳定版本命令 【支持包括桌面级AMD Radeon RX6950XT、RX6900XT、RX6800XT、RX6…...

钉钉小程序引用阿里巴巴图标

2.打开的界面如图&#xff0c;先建一个iconfont.acss文件&#xff0c;全选浏览器打开的样式代码&#xff0c;复制粘贴进新建的iconfont.acss文件中 3.使用...

深入了解Nginx:高性能的开源Web服务器与反向代理

一、Nginx是什么 Nginx是一款轻量级的Web 服务器/反向代理服务器及电子邮件&#xff08;IMAP/POP3&#xff09;代理服务器&#xff0c;也可以作为负载均衡器和HTTP缓存服务器使用。它采用事件驱动、异步非阻塞的处理方式&#xff0c;能够处理大量并发连接和高流量负载&#xff…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...