【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缓存服务器使用。它采用事件驱动、异步非阻塞的处理方式,能够处理大量并发连接和高流量负载ÿ…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...
协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...
