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个项目&…...

UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...

在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...

R 语言科研绘图第 55 期 --- 网络图-聚类
在发表科研论文的过程中,科研绘图是必不可少的,一张好看的图形会是文章很大的加分项。 为了便于使用,本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中,获取方式: R 语言科研绘图模板 --- sciRplothttps://mp.…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...