​LeetCode解法汇总823. 带因子的二叉树

news/2024/4/21 0:02:45/

 目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台


描述:

给出一个含有不重复整数元素的数组 arr ,每个整数 arr[i] 均大于 1。

用这些整数来构建二叉树,每个整数可以使用任意次数。其中:每个非叶结点的值应等于它的两个子结点的值的乘积。

满足条件的二叉树一共有多少个?答案可能很大,返回 对 109 + 7 取余 的结果。

示例 1:

输入: arr = [2, 4]
输出: 3
解释: 可以得到这些二叉树: [2], [4], [4, 2, 2]

示例 2:

输入: arr = [2, 4, 5, 10]
输出: 7
解释: 可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

提示:

  • 1 <= arr.length <= 1000
  • 2 <= arr[i] <= 109
  • arr 中的所有值 互不相同

解题思路:

从小到大排列,后面的数字,一定是前面数字的乘积。所以我们先求前面的值二叉树可能数量,并且保存下来。后面的值如果存在两个数的乘积,就是前面两个数的可能数量的乘积,如果两个数不同,则还需要乘以2,因为左右位置可以调换。

代码:

class Solution823
{
public:int numFactoredBinaryTrees(vector<int> &arr){sort(arr.begin(), arr.end());map<int, long long> numMap;long long sum = 0;int index = 0;long long mod = 1e9 + 7;while (index < arr.size()){int i = 0;long long num = 1;int currentValue = arr[index];while (arr[i] <= (currentValue / arr[i])){if (currentValue % arr[i] != 0){i++;continue;}int value = currentValue / arr[i];if (numMap.find(value) == numMap.end()){i++;continue;}if (value == arr[i]){num = (num + numMap[value] * numMap[value]) % mod;}else{num = (num + (numMap[value] * numMap[arr[i]] * 2)) % mod;}i++;}sum = (sum + num) % mod;numMap[currentValue] = num;index++;}return sum;}
};


http://www.ppmy.cn/news/1070861.html

相关文章

AMD即将上市大量中端显卡,为新显卡支付过高价格的日子可能结束

​AMD在本周末&#xff08;8月25日&#xff09;的德国Gamescom活动中展示了两款新显卡和一些新的升级技术&#xff0c;这些新GPU的定价将与英伟达的GeForce RTX 4000卡竞争。 这是一件大事&#xff0c;因为新的Radeon RX 7700 XT和7800 XT卡占据了AMD Radeon RX 7000系列产品线…

yolov8使用C++推理的流程及注意事项

1.下载yolov8项目源码GitHub - ultralytics/ultralytics: NEW - YOLOv8 &#x1f680; in PyTorch > ONNX > OpenVINO > CoreML > TFLite 2.下载opencvReleases - OpenCV,建议版本>4.7.0,选择下载源码&#xff0c; windows版本由于使用的编译器与我们所使用的m…

今天的小结

1、冒泡排序 冒泡排序&#xff08;Bubble Sort&#xff09;是一种简单的排序算法&#xff0c;它重复地遍历待排序的元素列表&#xff0c;比较相邻的元素并交换它们的位置&#xff0c;直到整个列表排序完成。冒泡排序的基本思想是通过不断交换相邻元素&#xff0c;将最大&#…

为什么劝年轻人不要频繁跳槽?

这是一个让很多年轻人犯愁的问题&#xff0c;尤其是在现如今竞争激烈的职场环境中。许多年轻人因为各种原因选择频繁跳槽&#xff0c;但是在我看来&#xff0c;这并不是一个明智的选择。下面就让我们来看看为什么劝年轻人不要频繁跳槽。 1. 错失成长机会 每一个工作都有其独特…

博流RISC-V芯片JTAG debug配置与运行

文章目录 1、Windows下安装与配置2、Linux下安装与配置3、芯片默认 JTAG PIN 列表4、命令行运行JTAG5、Eclipse下使用JTAG 1、Windows下安装与配置 CKLink 驱动安装 Windows版驱动下载地址&#xff1a; https://occ-oss-prod.oss-cn-hangzhou.aliyuncs.com/resource//1666331…

docker 04.更加重要的命令

之前的都是基础命令&#xff0c; 前台交互进程和后台守护进程&#xff1a; 重新进入容器&#xff1a; docker中的导入导出&#xff1a; docker中的拷贝到&#xff1a;

leetcode 496. 下一个更大元素 I

2023.8.28 这题提供暴力解法和单调栈法两种方法。 暴力解&#xff1a; class Solution { public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> ans(nums1.size(),-1);for(int i0; i<nums1.size…

asp、jsp环境安装

文章目录 phpasp安装环境打开asp大马 aspx修改配置打开aspx大马 jsp安装环境打开jsp大马 jspx php 在github下载138shell文件夹&#xff0c;解压后放入win10虚拟机&#xff0c;然后安装phpstudy&#xff08;在这里不再演示&#xff09;&#xff0c;并将php大马文件放在C:\phpS…

数据结构:八种数据结构大全

数据结构 1.1 数据结构概述 数据结构是计算机存储、组织数据的方式&#xff1b;通常情况下&#xff0c;精心选择的数据结构可以带来更高的运行或者存储效率。数据结构的优良将直接影响着我们程序的性能&#xff1b;常用的数据结构有&#xff1a;数组&#xff08;Array&#xff…

[python]问题:pandas处理excel,选中特定的sheet

要使用pandas处理Excel文件并选中特定的sheet,首先需要安装pandas和openpyxl库。可以使用以下命令进行安装: pip install pandas openpyxl然后,可以使用以下代码读取Excel文件中的特定sheet: import pandas as pd# 读取Excel文件 file_path = your_excel_file.xlsx sheet…

JavaIO流

JavaIO流 一、概念二、File类三、File类的使用1、File文件/文件夹类的创建2、File类的获取操作3、File类判断操作 - boolean4、File类对文件/文件夹的增删改5、File类的获取子文件夹以及子文件的方法 四、Java中IO流多种维度的维度1、按照流向 - Java程序2、按照流的大小分类3、…

JavaScript—BOM

BOM是什么&#xff1f; Browser Object Model是浏览器对象模型 官方&#xff1a;浏览器对象模型提供了独立于内容的、可以与浏览器窗口进行互动的对象结构&#xff0c;BOM由多个对象构成&#xff0c;其中代表浏览器窗口的window对象是BOM的顶层对象&#xff0c;其他对象都是该…

【少年的救赎——放牛班的春天】

风中飞舞的风筝&#xff0c;请你别停下 池塘之底 这是马修在池塘之底写下的日记 他所有的故事&#xff0c;还有“我们”的 1949年一月十五日&#xff0c;在经历了所有领域的挫折后&#xff0c;马修来到了人生低谷期&#xff0c;“池塘之底”像专为他挑选的一般。那是在一个…

网络中的问题2

距离-向量算法的具体实现 每个routerY的路由表表项 involve<目的网络N&#xff0c;距离d&#xff0c;下一跳X> 对邻居X发来的报文,先把下一跳改为X,再把距离1,if original route table doesn’t involve N,add this item&#xff1b; else if original table’s relate…

Windows安装6s模型

官网给出了详细的安装步骤 第一步&#xff1a;安装编译器 安装GnuWin32&#xff0c;按照提示安装&#xff0c;安装到你想安装的地方&#xff0c;记住目录。 安装G77&#xff0c;下载链接里面的Fort99.zip&#xff0c;将G77文件夹提取到C盘根目录。 将这两个目录的bin目录添加…

Windows Qt 5.12.10下载与安装

Qt 入门实战教程&#xff08;目录&#xff09; C自学精简实践教程 目录(必读) 1 Qt5.12.10下载 qt-opensource-windows-x86-5.12.10.exe 官方离线安装包 Download Source Package Offline Installers | Qt 下载巨慢&#xff08;也可能很快&#xff09; 只能下载到最新的&…

HTTP/1.1协议中的八种请求

2023年8月29日&#xff0c;周二晚上 目录 概述八种请求GET请求POST请求PUT请求PATCH请求DELETE请求HEAD请求OPTIONS请求TRACE请求 概述八种请求 HTTP/1.1协议中定义了8种常用的请求方法,分别是:1. GET 用途:请求指定的页面信息,并返回实体主体。例子:获取一个网页、图片等静态…

手搓文本向量数据库(自然语言搜索生成模型)

import paddle import jieba import pandas as pd import numpy as np import os from glob import glob from multiprocessing import Process, Manager, freeze_supportfrom tqdm import tqdm# 首先 确定的是输出的时候一定要使用pd.to_pickle() pd.read_pickle() # 计算的时…

stm32----SPI协议

一、概述 SPI&#xff08;Serial Peripheral Interface&#xff0c;串行外围设备接口&#xff09;&#xff0c;是Motorola公司提出的一种同步串行接口技术&#xff0c;是一种高速、全双工、同步通信总线&#xff0c;在芯片中只占用四根管脚用来控制及数据传输&#xff0c;节约…

Java Web 程序部署方式发展史

一、物理机时代 &#x1f4d2; 在虚拟机出现于业务环境中以前&#xff0c;应用往往部署在物理机器上&#xff0c;但无论是哪种服务器都缺乏相应技术手段保证一台服务器上可以稳定且安全的同时运行多个应用&#xff0c;因此&#xff0c;这样部署方式存在弊端是&#xff1a;空闲资…