当前位置: 首页 > 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…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

[拓扑优化] 1.概述

常见的拓扑优化方法有&#xff1a;均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有&#xff1a;有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...

OpenGL-什么是软OpenGL/软渲染/软光栅?

‌软OpenGL&#xff08;Software OpenGL&#xff09;‌或者软渲染指完全通过CPU模拟实现的OpenGL渲染方式&#xff08;包括几何处理、光栅化、着色等&#xff09;&#xff0c;不依赖GPU硬件加速。这种模式通常性能较低&#xff0c;但兼容性极强&#xff0c;常用于不支持硬件加速…...