Leetcode刷题:395. 至少有 K 个重复字符的最长子串、823. 带因子的二叉树
Leetcode刷题:395. 至少有 K 个重复字符的最长子串、823. 带因子的二叉树
- 1. 395. 至少有 K 个重复字符的最长子串
- 算法思路
- 参考代码和运行结果
- 2. 823. 带因子的二叉树
- 算法思路
- 参考代码和运行结果
1. 395. 至少有 K 个重复字符的最长子串
题目难度:中等
标签:分治、哈希表
题目如下:
给你一个字符串 s 和一个整数 k ,请你找出 s 中的最长子串, 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
如果不存在这样的子字符串,则返回 0。
题目链接为:395. 至少有 K 个重复字符的最长子串
题目示例如下:
1.
输入:s = “aaabb”, k = 3
输出:3
解释:最长子串为 “aaa” ,其中 ‘a’ 重复了 3 次。
输入:s = “ababbc”, k = 2
输出:5
解释:最长子串为 “ababb” ,其中 ‘a’ 重复了 2 次, ‘b’ 重复了 3 次。
提示
- 1 <= s.length <= 104
- s 仅由小写英文字母组成
- 1 <= k <= 10^5
算法思路
我的算法思路如下:
题目要求找到s中最长子串(子串:即原字符串中一段连续的字符序列),且该子串中每一个字符出现的次数都应该大于或等于k。既然如此,那么我们可以考虑原字符串s中那些字符出现次数少于k的字符,然后以这些字符作为分隔,分隔之后,可能有多个字符串,然后对这些字符串继续上述操作。直到某个字符串中的每一个字符出现次数均大于或等于k,然后该字符串计算长度并比较大小即可。
画出示意图如下:
原字符串s:“ababbc”,k:2
原字符串中字符次数少于k的有字符 “c”
以字符“c”对原字符串s进行分隔操作,得到"ababb"
对于“ababb”中每一个字符出现次数均大于或等于k,于是结果ans = max(len(“ababb”),ans)=5(ans初始值为0)
原字符串s:“bbaaacbd”,k : 3
原字符串中字符少于k的字符有 “c”、“d”
利用上述字符对原字符串s进行分隔操作,得“bbaaa”,“b”
对于“bbaaa”,其中字符出现次数少于k的有 “b”
对“bbaaa”进行分隔操作,得“aaa”
”aaa“中字符出现次数均大于或等于k,ans = max(ans,len(“aaa”))=3
参考代码和运行结果
class Solution(object):def longestSubstring(self, s, k):""":type s: str:type k: int:rtype: int"""map = {}for c in s:map[c] = map.get(c,0) + 1arr = []for key in map:if map[key] < k:arr.append(key)if len(arr) == 0:return len(s)else:start = 0ans = 0n = len(s)for i in range(n):c = s[i]if c in arr:ans = max(self.longestSubstring(s[start:i],k),ans)start = i + 1if start < n:ans = max(self.longestSubstring(s[start:],k),ans)return ans
运行结果:
2. 823. 带因子的二叉树
题目难度:中等
题目标签:动态规划、哈希表
题目如下:
给出一个含有不重复整数元素的数组 arr ,每个整数 arr[i] 均大于 1。
用这些整数来构建二叉树,每个整数可以使用任意次数。其中:每个非叶结点的值应等于它的两个子结点的值的乘积。
满足条件的二叉树一共有多少个?答案可能很大,返回 对 109 + 7 取余 的结果。
示例如下:
1.
输入: arr = [2, 4]
输出: 3
解释: 可以得到这些二叉树: [2], [4], [4, 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 中的所有值 互不相同
算法思路
首先arr中每个元素单独组成二叉树是满足题目要求,现在考虑多个元素组合情况,根节点和其左右节点值满足条件:root.val = root.left.val*root.right.val,其左、右节点如果还有子节点,那么也应该满足上述等式,为此,需要对原arr进行升序排序,然后依次遍历arr中每个元素,用map来记录arr中每一个元素满足上述等式次数。
示意图如下:
参考代码和运行结果
参考代码如下:
class Solution(object):def numFactoredBinaryTrees(self, arr):""":type arr: List[int]:rtype: int"""map = {}arr.sort()for e in arr:map[e] = map.get(e, 0) + 1for k in map:if e % k == 0 and map.get(e//k,None):v1 = map[k]v2 = map[e//k]map[e] += v1 * v2return sum(map.values()) % (10**9+7)
运行结果:
相关文章:
Leetcode刷题:395. 至少有 K 个重复字符的最长子串、823. 带因子的二叉树
Leetcode刷题:395. 至少有 K 个重复字符的最长子串、823. 带因子的二叉树 1. 395. 至少有 K 个重复字符的最长子串算法思路参考代码和运行结果 2. 823. 带因子的二叉树算法思路参考代码和运行结果 1. 395. 至少有 K 个重复字符的最长子串 题目难度:中等 标签&#…...
java八股文面试[多线程]——Synchronized的底层实现原理
笔试:画出Synchronized 线程状态流转实现原理图 synchronized关键字解决的是多个线程之间访问资源的同步性,synchronized 翻译为中文的意思是同步,也称之为”同步锁“。 synchronized的作用是保证在同一时刻, 被修饰的代码块或方…...
C#,《小白学程序》第三课:类、类数组与排序
类class把数值与功能巧妙的进行了结合,是编程技术的主要进步。 下面的程序你可以确立 分数 与 姓名 之间关系,并排序。 1 文本格式 /// <summary> /// 同学信息类 /// </summary> public class Classmate { /// <summary> /…...
史上最全AP、mAP详解与代码实现
文章目录 前言一、mAP原理1、mAP概念2、准确率3、精确率4、召回率5、AP: Average Precision 二、mAP0.5与mAP0.5:0.951、mAP0.52、mAP0.5:0.95 三、mAP代码实现1、真实标签json文件格式2、模型预测标签json文件格式3、mAP代码实现4、mAP结果显示 四、模型集成mAP代码1、模型mai…...
百数应用中心——生产制造管理解决方案解决行业难题
传统生产制造业面临着许多挑战,其中一些主要问题包括效率低下、交期压力大、需求预测不准确、生产模式复杂、异常响应慢、库存高和计划脱节等。这些问题不仅影响了生产效率和质量,也导致了不必要的成本和客户满意度下降。 生产制造管理应用对于企业的生产…...
《存储IO路径》专题:IO虚拟化初探
大家好,欢迎来到今天的科技小课堂。今天我们要聊聊的是一项非常有趣且实用的技术——I/O虚拟化(Input/Output Virtualization,简称IOV)。想象一下,如果把物理硬件资源比作一道丰盛的大餐,那么IOV就是那位神…...
Springboot2.0快速入门(第一章)
目录 一,SpringBoot简介1.1,回顾什么是Spring1.2,Spring是如何简化Java开发的1.3,什么是SpringBoot 二,Hello,World2.1,准备工作2.2,创建基础项目说明2.3,创建第一个Hell…...
Flink流批一体计算(17):PyFlink DataStream API之StreamExecutionEnvironment
目录 StreamExecutionEnvironment Watermark watermark策略简介 使用 Watermark 策略 内置水印生成器 处理空闲数据源 算子处理 Watermark 的方式 创建DataStream的方式 通过list对象创建 使用DataStream connectors创建 使用Table & SQL connectors…...
javeee spring cglib动态代理
cglib动态代理 依赖 <dependency><groupId>cglib</groupId><artifactId>cglib-nodep</artifactId><version>3.2.4</version></dependency>代理类 package com.test.cglibProxy;import net.sf.cglib.proxy.Enhancer; import …...
【Docker】Dockerfile介绍
Dockerfile是一个文本文件,其中包含了一系列的指令,用于构建Docker镜像。这些指令可以用来自动化镜像的构建过程,并创建自定义镜像。 以下是一些常用的Dockerfile指令及其功能: FROM:指定基础镜像。这是Dockerfile中…...
两个hdfs之间迁移传输数据
本文参考其他大数据大牛的博文做了整理和实际验证,主要解决hdfs跨集群复制/迁移问题。 在hdfs数据迁移时总会涉及到两个hdfs版本版本问题,致力解决hdfs版本相同和不同两种情况的处理方式,长话短说,进正文。 distcp: hadoop自带的…...
C++ 缺失的数字
有n个数字,值就是1~n,现发现丢失了2个数字,请你根据剩余的n-2个数字,编程计算一下,缺失的是哪两个数字呢? (使用桶排,标记输入过的数字) #include<bits/stdc.h> us…...
JVM,JRE和JDK的区别
JVM,JRE和JDK的区别 JVM(Java Virtual Machine,Java虚拟机)JREJRE目录结构 JDK JVM(Java Virtual Machine,Java虚拟机) Java程序的跨平台特性主要是指字节码文件可以在任何具有Java虚拟机的计算机或者电子设备上运行,Java虚拟机中…...
合宙Air724UG LuatOS-Air LVGL API控件--日历 (Calendar)
日历 (Calendar) LVGL 提供了一个用来选择和显示当前日期的日历控件。 示例代码 – 高亮显示的日期 highlightDate lvgl.calendar_date_t() – 日历点击的回调函数 – 将点击日期设置高亮 function event_handler(obj, event) if event lvgl.EVENT_VALUE_CHANGED then da…...
[python]问题:pandas处理excel里的多个sheet
Pandas 可以很容易地处理 Excel 文件中的多个工作表。首先,你需要安装 pandas 和 openpyxl(用于读取 .xlsx 文件)库。你可以使用以下命令安装这两个库: pip install pandas openpyxl接下来,你可以使用以下代码来处理 Excel 文件中的多个工作表: import pandas as pd# 读…...
[MySQL] MySQL基础操作汇总
文章目录 前言1.数据库概述1.1 数据库相关概念1.2登录MySQL:1.3 MySQL常用命令1.4表:1.5SQL语句分类: 2.CRUD操作2.1 DQL1.基础查询基础查询(简单查询)条件查询:排序查询:分组查询:分…...
C语言每日一题 ---- 打印从1到最大的n位数(Day 1)
本专栏为c语言练习专栏,适合刚刚学完c语言的初学者。本专栏每天会不定时更新,通过每天练习,进一步对c语言的重难点知识进行更深入的学习。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:C语言天天练 &#x…...
2023-08-23 LeetCode每日一题(统计点对的数目)
2023-08-23每日一题 一、题目编号 1782. 统计点对的数目二、题目链接 点击跳转到题目位置 三、题目描述 给你一个无向图,无向图由整数 n ,表示图中节点的数目,和 edges 组成,其中 edges[i] [ui, vi] 表示 ui 和 vi 之间有一…...
LLMs之Code:SQLCoder的简介、安装、使用方法之详细攻略
LLMs之Code:SQLCoder的简介、安装、使用方法之详细攻略 目录 SQLCoder的简介 1、结果 2、按问题类别的结果 SQLCoder的安装 1、硬件要求 2、下载模型权重 3、使用SQLCoder 4、Colab中运行SQLCoder 第一步,配置环境 第二步,测试 第…...
数学建模(四)整数规划—匈牙利算法
目录 一、0-1型整数规划问题 1.1 案例 1.2 指派问题的标准形式 2.2 非标准形式的指派问题 二、指派问题的匈牙利解法 2.1 匈牙利解法的一般步骤 2.2 匈牙利解法的实例 2.3 代码实现 一、0-1型整数规划问题 1.1 案例 投资问题: 有600万元投资5个项目&…...
openGauss学习笔记-47 openGauss 高级数据管理-权限
文章目录 openGauss学习笔记-47 openGauss 高级数据管理-权限47.1 语法格式47.2 参数说明47.3 示例 openGauss学习笔记-47 openGauss 高级数据管理-权限 数据库对象创建后,进行对象创建的用户就是该对象的所有者。数据库安装后的默认情况下,未开启三权分…...
开始MySQL之路——MySQL 事务(详解分析)
MySQL 事务概述 MySQL 事务主要用于处理操作量大,复杂度高的数据。比如说,在人员管理系统中,你删除一个人员,你即需要删除人员的基本资料,也要删除和该人员相关的信息,如信箱,文章等等…...
注解和class对象和mysql
注解 override 通常是用在方法上的注解表示该方法是有重写的 interface 表示一个注解类 比如 public interface override{} 这就表示是override是一个注解类 target 修饰注解的注解表示元注解 deprecated 修饰某个元素表示该元素已经过时了 1.不代表该元素不能用了&…...
【桌面小屏幕项目】ESP32开发环境搭建
视频教程链接: 【【有手就行系列】嵌入式单片机教程-桌面小屏幕实战教学 从设计、硬件、焊接到代码编写、调试 ESP32 持续更新2022】 https://www.bilibili.com/video/BV1wV4y1G7Vk/?share_sourcecopy_web&vd_source4fa5fad39452b08a8f4aa46532e890a7 一、esp…...
CSS 滚动容器与固定 Tabbar 自适应的几种方式
问题 容器高度使用 px 定高时,随着页面高度发生变化,组件展示的数量不能最大化的铺满,导致出现底部留白。容器高度使用 vw 定高时,随着页面宽度发生变化,组件展示的数量不能最大化的铺满,导致出现底部留白…...
IP 地址追踪工具
IP 地址跟踪工具是一种网络实用程序,允许您扫描、跟踪和获取详细信息,例如 IP 地址的 MAC 和接口 ID。IP 跟踪解决方案通过使用不同的网络扫描协议来检查网络地址空间来收集这些详细信息。一些高级 IP 地址跟踪器软件(如 OpUtils)…...
最新企业网盘产品推荐榜发布
随着数字化发展,传统的文化存储方式已无法跟上企业发展的步伐。云存储的出现为企业提供了新的文件管理存储模式。企业网盘作为云存储的代表性工具,被越来越多的企业所青睐。那么在众多企业网盘产品中,企业该如何找到合适的企业网盘呢…...
实用的面试经验分享:程序员们谈论他们的面试历程
🌷🍁 博主猫头虎 带您 Go to New World.✨🍁 🦄 博客首页——猫头虎的博客🎐 🐳《面试题大全专栏》 文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~🌺 &a…...
6.oracle中listagg函数使用
1. 作用 可以实现行转列,将多列数据聚合为一列,实现数据的压缩 2. 语法 listagg(measure_expr,delimiter) within group ( order by order_by_clause); 解释: measure_expr可以是基于任何列的表达式 delimiter分隔符,…...
习题练习 C语言(暑期)
编程能力小提升! 前言一、转义字符二、重命名与宏定义三、三目运算符四、计算日期到天数转换五、计算字符串长度六、宏定义应用七、const常量八、C语言基础九、const常量(二)十、符号运算十一、记负均正十二、SWITCH,CASE十三、错…...
C++中虚函数表的概念
当一个类对象指针调用虚函数时,这就涉及到 运行时多态 的概念。这意味着实际调用的函数取决于对象的实际类型,而不仅仅是指针的静态类型。 假设我们有以下的类层次结构: class Base { public:virtual void print() {std::cout << &qu…...
代码随想录算法训练营第四十八天 | 198.打家劫舍,213.打家劫舍II,337.打家劫舍III
代码随想录算法训练营第四十八天 | 198.打家劫舍,213.打家劫舍II,337.打家劫舍III 198.打家劫舍213.打家劫舍II337.打家劫舍III 198.打家劫舍 题目链接 视频讲解 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金ÿ…...
uniapp项目实战系列(1):导入数据库,启动后端服务,开启代码托管
目录 前言前期准备1.数据库的导入2.运行后端服务2.1数据库的后端配置2.2后端服务下载依赖,第三方库2.3启动后端服务 3.开启gitcode代码托管 ✨ 原创不易,还希望各位大佬支持一下! 👍 点赞,你的认可是我创作的动力&…...
在互联网+的背景下,企业如何创新客户服务?
随着互联网的发展,开始数字化转型的潮流,移动互联网平台为各个行业带来了发展的新方向。企业有了移动互联网的加持,为客户提供了更好的服务。当移动互联网平台能够为客户提供更好的用户体验时,相应地,客户也给企业带来…...
国内的化妆品核辐射检测
化妆品核辐射物质检测是指检测化妆品中的放射性物质,包括放射性核素和放射性同位素。这些放射性物质主要来源于环境中的放射性污染,如空气、水和土壤中的放射性物质,以及化妆品生产过程中的放射性污染,如原料、设备、工艺等。化妆…...
春秋云镜:CVE-2019-9042(Sitemagic CMS v4.4 任意文件上传漏洞)
一、题目 靶标介绍: Sitemagic CMS v4.4 index.php?SMExtSMFiles 存在任意文件上传漏洞,攻击者可上传恶意代码执行系统命令。 进入题目: admin/admin /index.php?SMExtSMFiles&SMTemplateTypeBasic&SMExecModeDedicated&SMFil…...
20230828工作日志:
今天遇到了很多问题,下次可以做得更好更快的几个地方: 1 sql语句的检查 肯定要先在navicate 里执行看,是否有语法错误。即使没有,也还是要注意一些问题:IDEA里换行的时候,“后面要空一格,如果连…...
flink on yarn 部署
需要jars -rwxr-xrwx 3 root supergroup 58284 2022-11-30 03:44 /lib/flink/commons-cli-1.5.0.jar -rw-r--r-- 3 root supergroup 48497 2022-12-10 03:04 /lib/flink/flink-cep-scala_2.12-1.14.3.jar -rw-r--r-- 3 root supergroup 189468 2022-12-10…...
postgresql基于postgis常用空间函数
1、ST_AsGeoJSON 图元转geojson格式 select ST_AsGeoJSON(l.geom) from g_zd l limit 10 2、 ST_Transform 坐标转换 select st_transform(l.shape, 3857) from sde_wf_cyyq l limit 10select st_astext(st_transform(l.shape, 3857)) from sde_wf_cyyq l limit 103、st_aste…...
详细讲解移植u-boot.2022.10版本移植到开发板基本方法
大家好,我是ST。 今天给大家讲一讲如何将u-boot.2022.10版本移植到imx6ull开发板上。 环境 选项内容编译主机UbuntuLTS 18.04目标板ATK I.MX6ULL(512MB DDR3 8GB EMMC)u-boot版本2022.10交叉编译工具链gcc-linaro-7.5.0-2019.12-i686…...
Vue.js2+Cesium1.103.0 十一、Three.js 炸裂效果
Vue.js2Cesium1.103.0 十一、Three.js 炸裂效果 Demo ThreeModelBoom.vue <template><div:id"id"class"three_container"/> </template><script> /* eslint-disable eqeqeq */ /* eslint-disable no-unused-vars */ /* eslint-d…...
Nodejs快速搭建简单的HTTP服务器,并发布公网远程访问
前言 Node.js 是能够在服务器端运行 JavaScript 的开放源代码、跨平台运行环境。Node.js 由 OpenJS Foundation(原为 Node.js Foundation,已与 JS Foundation 合并)持有和维护,亦为 Linux 基金会的项目。Node.js 采用 Google 开发…...
爬虫入门01
1. 请求头中最常见的一些重要内容 User-Agent : 请求载体的身份标识(⽤啥发送的请求)Referer: 防盗链(这次请求是从哪个⻚⾯来的? 反爬会⽤到)cookie: 本地字符串数据信息(⽤户登录信息, 反爬的token) 2. 响应头中一些重要内容 cookie: 本地字符串数据信息(⽤户登录信息, 反…...
解读GIS软件:从ArcGIS到山海鲸可视化的全方位介绍
在现代社会,地理信息系统(GIS)的应用已经渗透到了各个领域,为我们提供了丰富的地理数据分析和可视化工具。下面介绍几款常见的GIS工具软件,一起来了解它们的特点和优势。 1. ArcGIS: ArcGIS由Esri公司开发,…...
嵌入式通用硬件模块设计——串口音频播放模块
模块功能展示: 串口音频控制模块 一、简介 方案为串口音频播放芯片功放芯片,口音频播放芯片IC为my1690-16s,功放为PAM8406。 1、my1690-16s 迈优科技的一款由串口控制的插卡MP3播放控制芯片,支持串口控制播放指定音频、音量调节…...
【PLSQL】PLSQL基础
文章目录 一:记录类型1.语法2.代码实例 二:字符转换三:%TYPE和%ROWTYPE1.%TYPE2.%ROWTYPE 四:循环1.LOOP2.WHILE(推荐)3.数字式循环 五:游标1.游标定义及读取2.游标属性3.NO_DATA_FOUND和%NOTFO…...
【C++笔记】C++内存管理
【C笔记】C内存管理 一、C中动态内存申请的方式二、new和delete的实现原理2.1、operator new和operator delete函数 一、C中动态内存申请的方式 在C语言中我们需要动态申请空间的时候我们通常都是用malloc函数,但是malloc函数对自定义类型是没什么问题的࿰…...
十四五双碳双控时代下的“低碳认证”
目录 前言 十四五双碳双控时代下的“低碳认证” 一、关于“低碳认证” 二、低碳认证优势 三、环境产品认证EPD 四、EPD相关运营机构 五、碳中和相关机构 六、EPD的认证流程 七、低碳产品认证认证流程和要求 八、相关机构认证证书样例 九、证书附件表 前言 通过本篇文…...
Android——基本控件(下)(十九)
1. 菜单:Menu 1.1 知识点 (1)掌握Android中菜单的使用; (2)掌握选项菜单(OptionsMenu)的使用; (3)掌握上下文菜单(ContextMenu&am…...
聚类分析 | MATLAB实现基于DBSCAD密度聚类算法可视化
聚类分析 | MATLAB实现基于LP拉普拉斯映射的聚类可视化 目录 聚类分析 | MATLAB实现基于LP拉普拉斯映射的聚类可视化效果一览基本介绍程序设计参考资料 效果一览 基本介绍 基于DBSCAD密度聚类算法可视化,MATLAB程序。 使用带有KD树加速的dbscan_with_kdtree函数进行…...