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

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 个重复字符的最长子串 题目难度&#xff1a;中等 标签&#…...

java八股文面试[多线程]——Synchronized的底层实现原理

笔试&#xff1a;画出Synchronized 线程状态流转实现原理图 synchronized关键字解决的是多个线程之间访问资源的同步性&#xff0c;synchronized 翻译为中文的意思是同步&#xff0c;也称之为”同步锁“。 synchronized的作用是保证在同一时刻&#xff0c; 被修饰的代码块或方…...

C#,《小白学程序》第三课:类、类数组与排序

类class把数值与功能巧妙的进行了结合&#xff0c;是编程技术的主要进步。 下面的程序你可以确立 分数 与 姓名 之间关系&#xff0c;并排序。 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…...

百数应用中心——生产制造管理解决方案解决行业难题

传统生产制造业面临着许多挑战&#xff0c;其中一些主要问题包括效率低下、交期压力大、需求预测不准确、生产模式复杂、异常响应慢、库存高和计划脱节等。这些问题不仅影响了生产效率和质量&#xff0c;也导致了不必要的成本和客户满意度下降。 生产制造管理应用对于企业的生产…...

《存储IO路径》专题:IO虚拟化初探

大家好&#xff0c;欢迎来到今天的科技小课堂。今天我们要聊聊的是一项非常有趣且实用的技术——I/O虚拟化&#xff08;Input/Output Virtualization&#xff0c;简称IOV&#xff09;。想象一下&#xff0c;如果把物理硬件资源比作一道丰盛的大餐&#xff0c;那么IOV就是那位神…...

Springboot2.0快速入门(第一章)

目录 一&#xff0c;SpringBoot简介1.1&#xff0c;回顾什么是Spring1.2&#xff0c;Spring是如何简化Java开发的1.3&#xff0c;什么是SpringBoot 二&#xff0c;Hello&#xff0c;World2.1&#xff0c;准备工作2.2&#xff0c;创建基础项目说明2.3&#xff0c;创建第一个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是一个文本文件&#xff0c;其中包含了一系列的指令&#xff0c;用于构建Docker镜像。这些指令可以用来自动化镜像的构建过程&#xff0c;并创建自定义镜像。 以下是一些常用的Dockerfile指令及其功能&#xff1a; FROM&#xff1a;指定基础镜像。这是Dockerfile中…...

两个hdfs之间迁移传输数据

本文参考其他大数据大牛的博文做了整理和实际验证&#xff0c;主要解决hdfs跨集群复制/迁移问题。 在hdfs数据迁移时总会涉及到两个hdfs版本版本问题&#xff0c;致力解决hdfs版本相同和不同两种情况的处理方式&#xff0c;长话短说&#xff0c;进正文。 distcp: hadoop自带的…...

C++ 缺失的数字

有n个数字&#xff0c;值就是1~n&#xff0c;现发现丢失了2个数字&#xff0c;请你根据剩余的n-2个数字&#xff0c;编程计算一下&#xff0c;缺失的是哪两个数字呢&#xff1f; &#xff08;使用桶排&#xff0c;标记输入过的数字&#xff09; #include<bits/stdc.h> us…...

JVM,JRE和JDK的区别

JVM&#xff0c;JRE和JDK的区别 JVM(Java Virtual Machine&#xff0c;Java虚拟机)JREJRE目录结构 JDK JVM(Java Virtual Machine&#xff0c;Java虚拟机) Java程序的跨平台特性主要是指字节码文件可以在任何具有Java虚拟机的计算机或者电子设备上运行&#xff0c;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&#xff1a;1.3 MySQL常用命令1.4表&#xff1a;1.5SQL语句分类&#xff1a; 2.CRUD操作2.1 DQL1.基础查询基础查询&#xff08;简单查询&#xff09;条件查询&#xff1a;排序查询&#xff1a;分组查询&#xff1a;分…...

C语言每日一题 ---- 打印从1到最大的n位数(Day 1)

本专栏为c语言练习专栏&#xff0c;适合刚刚学完c语言的初学者。本专栏每天会不定时更新&#xff0c;通过每天练习&#xff0c;进一步对c语言的重难点知识进行更深入的学习。 &#x1f493;博主csdn个人主页&#xff1a;小小unicorn ⏩专栏分类&#xff1a;C语言天天练 &#x…...

2023-08-23 LeetCode每日一题(统计点对的数目)

2023-08-23每日一题 一、题目编号 1782. 统计点对的数目二、题目链接 点击跳转到题目位置 三、题目描述 给你一个无向图&#xff0c;无向图由整数 n &#xff0c;表示图中节点的数目&#xff0c;和 edges 组成&#xff0c;其中 edges[i] [ui, vi] 表示 ui 和 vi 之间有一…...

LLMs之Code:SQLCoder的简介、安装、使用方法之详细攻略

LLMs之Code&#xff1a;SQLCoder的简介、安装、使用方法之详细攻略 目录 SQLCoder的简介 1、结果 2、按问题类别的结果 SQLCoder的安装 1、硬件要求 2、下载模型权重 3、使用SQLCoder 4、Colab中运行SQLCoder 第一步&#xff0c;配置环境 第二步&#xff0c;测试 第…...

数学建模(四)整数规划—匈牙利算法

目录 一、0-1型整数规划问题 1.1 案例 1.2 指派问题的标准形式 2.2 非标准形式的指派问题 二、指派问题的匈牙利解法 2.1 匈牙利解法的一般步骤 2.2 匈牙利解法的实例 2.3 代码实现 一、0-1型整数规划问题 1.1 案例 投资问题&#xff1a; 有600万元投资5个项目&…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; 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是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...