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

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...