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

【力扣每日一题】2023.8.29 带因子的二叉树

目录

题目:

示例:

分析:

代码:


题目:

示例:

分析:

题目给我们一些元素,让我们用这些元素连接形成特定的二叉树,每种元素可以使用任意次数,形成的二叉树要求每个非叶子节点的值都为左右子树节点的值的乘积。

一个数要等于两个数的乘积,那么那两个数一定会比那一个数更小,所以我们可以从较小的数入手,那么我们首先将数组从小到大进行排序,接着从左到右,从小到大去遍历。

在遍历之前我们先做个预处理,我们用一个map来存住所有元素的值,以元素为键,值全部初始化为1。map每个键值对的含义就是以键为根节点能形参的二叉树有多少个,因为每个元素都可以以自身一个节点为一棵符合标准的二叉树,所以是初始化为1。

初始化完毕就开始遍历,我们需要套两层for循环,第一层去遍历每个根节点,去更新以当前节点为根节点所能形成的二叉树的数量,更新的方法就是第二层for循环去遍历比这个节点的值更小的元素,因为要相乘等于当前元素,那么乘数肯定是比当前元素更小的。

第一层遍历我们设下标为 i ,第二层下标为 j ,我们去寻找 arr[ i ] / arr[ j ] 这个元素在不在我们的map里,如果在,那么我们就把map里键为arr[ i ] 的键值对中的值加上以那两个乘数为根节点能形成的二叉树的数量的乘积,化简一下就是 m[ arr [ i ] ] += m[ arr[ i ] / arr[ j ] ] * m[ arr[ j ] ]。

由于我们是从小到大遍历的,所以我们每次都是会更新比后面的数更小的元素,以此元素为根节点能形参的二叉树,这样就可以得到推导出以后面较大的元素为根节点能形参的二叉树的数量。所以虽然我们没有用到dp数组,但它本质上来说还是属于动态规划。

还有一点要注意的就是题目有说要对结果取余10的九次方加7,所以为了避免数值溢出,我们每次操作都要做一个取余的操作。

代码:

class Solution {
public:int numFactoredBinaryTrees(vector<int>& arr) {int res=arr.size(); //单个节点可以单独为一棵树,初始化为数组长度sort(arr.begin(),arr.end());unordered_map<int,long>m;   //用来记录以每个数为根节点的二叉树数目for(int i:arr){m[i]=1;}for(int i=0;i<arr.size();i++){for(int j=0;j<i;j++){//如果发现arr[i]整除arr[j]的数也在数组里,那么可以多组成的二叉树数目等于以arr[j]为根节点的二叉树数目乘上以另一个除数为根节点的二叉树数目.if(arr[i]%arr[j]==0&&m.find(arr[i]/arr[j])!=m.end()){int t=m[arr[i]/arr[j]]*m[arr[j]]%1000000007;m[arr[i]]+=t;   //更新以arr[i]为根节点的二叉树数目.res+=t;res%=1000000007;}}}return res;}
};

相关文章:

【力扣每日一题】2023.8.29 带因子的二叉树

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 题目给我们一些元素&#xff0c;让我们用这些元素连接形成特定的二叉树&#xff0c;每种元素可以使用任意次数&#xff0c;形成的二叉树要…...

origin导出pdf曲线超出边框

软件版本 软件版本Word2021Origin2021Adobe Acrobat Pro2023 问题描述 Origin导出的emf格式矢量图片&#xff0c;插入到Word中&#xff0c;显示正常&#xff0c;但是在使用Word导出→创建Adobe PDF→创建Adobe PDF导出PDF文件后&#xff0c;图片曲线就会超出边框&#xff0c…...

由Android10适配到Android12时遇到相关编译失败问题

最近Android系统各大应用商店联合发出公告&#xff0c;处于个人隐私安全考虑&#xff0c;强制APP适配到Android 11及以上版本。下面是其中应用市场的公告&#xff08;顺带提醒没适配的同学&#xff09;&#xff1a; 适配前的开发环境 名称版本Android studioGiraffe | 2022.3…...

高职教育应对ChatGPT应用的策略

一、完善顶层设计&#xff0c;提升技术水平 在推广ChatGPT平台的过程中&#xff0c;高职院校需要关注技术本身的问题。这就需要在国家和地方政府的引导下&#xff0c;引入更完善的技术顶层设计&#xff0c;提高人工智能在高职教育中的运用水平。具体来说&#xff0c;一方面需要…...

Linux 内核编译参数

文章目录 前言1 -Wall2 -Wundef3 -Wstrict-prototypes4 -Wno-trigraphs5 -fno-strict-aliasing6 -fno-common7 -Werror-implicit-function-declaration8 -Wno-format-security9 -fno-delete-null-pointer-checks10 -stdgnu89 前言 # cat /etc/os-release NAME"CentOS Lin…...

vscode使用anaconda自带的python环境在终端运行时报错

目录 具体报错内容官方翻译报错讲人话解决方法 具体报错内容 CommandNotFoundError: Your shell has not been properly configured to use conda activate. If your shell is Bash or a Bourne variant, enable conda for the current user with$ echo ". E:\Anaconda/e…...

葡萄叶病害识别(图像连续识别和视频识别,Python代码,pyTorch框架)

葡萄叶病害识别&#xff08;图像连续识别和视频识别&#xff0c;Python代码&#xff0c;pyTorch框架&#xff09;_哔哩哔哩_bilibili 葡萄数据集 第一个文件夹为 Grape Black Measles&#xff08;葡萄黑麻疹&#xff09;病害&#xff08;3783张&#xff09; Grape Black rot葡…...

Oracle drop删除表如何恢复

摘要&#xff1a; 在 Oracle 数据库管理中&#xff0c;DROP 命令的误操作可能导致数据不可挽回的丢失。然而&#xff0c;Oracle 提供了回收站&#xff08;recycle bin&#xff09;功能&#xff0c;允许用户在删除对象后的一段时间内恢复它们。本文将介绍如何查询、启用和管理回…...

5、监测数据采集物联网应用开发步骤(5.1)

监测数据采集物联网应用开发步骤(4) Sqlite3数据库读写操作开发、异常信息统一处理类开发 本章节需要调用sqlite3及mysql-connector 安装sqlite3 Pip3 install sqlite3 安装mysql-connector pip3 install mysql-connector 验证是否安装成功&#xff0c;python中运行下列…...

ZZULIOJ 1148: 组合三位数之一,Java

ZZULIOJ 1148: 组合三位数之一&#xff0c;Java 题目描述 把1、2、3、4、5、6、7、8、9组合成3个3位数&#xff0c;要求每个数字仅使用一次&#xff0c;使每个3位数均为完全平方数。按从小到大的顺序输出这三个三位数。 输入 无 输出 按从小到大的顺序输出这三个三位数&a…...

ROS功能包目录下CMakeLists.txt

1. add_execuble CMake基础教程&#xff08;24&#xff09;add_executable生成目标可执行文件 CMake中add_executable的使用 CMake中的add_executable命令用于使用指定的源文件向项目(project)添加可执行文件&#xff0c;其格式如下&#xff1a; add_executable(<name>…...

Python爬虫追踪新闻事件发展进程及舆论反映

目录 实现方案 1. 确定目标新闻源&#xff1a; 2. 确定关键词&#xff1a; 3. 使用网络爬虫获取新闻内容&#xff1a; 4. 提取和分析新闻文章&#xff1a; 5. 追踪新闻事件的发展进程&#xff1a; 6. 监测舆论反映&#xff1a; 7. 数据可视化&#xff1a; 完整代码示例…...

block层:7. 请求下发

blk_dispatch 源码基于5.10 1. blk_mq_sched_dispatch_requests void blk_mq_sched_dispatch_requests(struct blk_mq_hw_ctx *hctx) {// 队列struct request_queue *q hctx->queue;// 队列已停止或者被暂停if (unlikely(blk_mq_hctx_stopped(hctx) || blk_queue_quiesc…...

Matlab图像处理-平移运算

几何运算 几何运算又称为几何变换&#xff0c;是将一幅图像中的坐标映射到另外一幅图像中的新坐标位置&#xff0c;它不改变图像的像素值&#xff0c;只是改变像素所在的几何位置&#xff0c;使原始图像按照需要产生位置、形状和大小的变化。 图像几何运算的一般定义为&#…...

美创科技一体化智能化公共数据平台数据安全建设实践

公共数据是当今政府数字化转型的关键要素和未来价值释放的核心锚点&#xff0c;也是“网络强国”、“数字中国”的战略性资源。 作为数字化改革先行省份&#xff0c;近年来&#xff0c;浙江省以一体化智能化公共数据平台作为数字化改革的支撑总平台&#xff0c;实现了全省公共数…...

关于单例模式

单例模式的目的&#xff1a; 单例模式的目的和其他的设计模式的目的都是一样的&#xff0c;都是为了降低对象之间的耦合性&#xff0c;增加代码的可复用性&#xff0c;可维护性和可扩展性。 单例模式&#xff1a; 单例模式是一种常用的设计模式&#xff0c;用简单的言语说&am…...

pytest笔记: pytest单元测试框架

第一步&#xff1a;安装 和查看版本 pycharm settings 查看 第二步&#xff1a; 编写test_example.py def inc(x):return x1 def test_answer():assert inc(4) 5 第三步&#xff1a;在当前路径下执行pytest 命令 PS E:\data\web测试\Selenium3自动化测试实战——基于Pyth…...

vulnhub Seattle-0.0.3

环境&#xff1a;vuluhub Seattle-0.0.3 1.catelogue处任意文件下载(目录穿越) http://192.168.85.139/download.php?item../../../../../../etc/passwd 有个admin目录&#xff0c;可以下载里面的文件进行读取 2.cltohes详情页面处(参数prod)存在sql报错注入 http://192.16…...

MYSQL 添加行号将行号写入到主键的列

MYSQL 添加行号 SELECT rownum: rownum 1 AS rownum, a.* FROM(SELECT rownum : 0) t,is_afxt.hk_vehicle a--或者(假设CREATED_TIME日期列数据不重复) select (select count(1)1 from is_afxt.hk_vehicle b where b.CREATED_TIME < a.CREATED_TIME) rownum ,a.* from i…...

前端命令npm 、 cnpm、 pnpm、yarn 、 npx、nvm的区别

大名鼎鼎的npm(Node Package Manager)是随同NodeJS一起安装的包管理工具&#xff0c;NPM本身也是Node.js的一个模块。 npm的含义有两层: npm服务器&#xff0c;npm服务器网址为https://www.npmjs.org&#xff0c;npm是 Node 包的标准发布平台&#xff0c;用于 Node 包的发布、…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

前端中slice和splic的区别

1. slice slice 用于从数组中提取一部分元素&#xff0c;返回一个新的数组。 特点&#xff1a; 不修改原数组&#xff1a;slice 不会改变原数组&#xff0c;而是返回一个新的数组。提取数组的部分&#xff1a;slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...