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

LeetCode2207解题思路

题目描述

字符串中最多数目的子序列

解题思路:

题目要求我们找到在 text 中 找到最多可组成 pattern 的字符串个数,并且允许在 text 的任意位置插入 pattern 中一个字符,也就是说我们只需要考虑 text 中的 pattern 含有的字符即可。例如示例 1 中 text = "abdcdbc",pattern = "ac",如果只考虑 text 中的 ac 即可将 text 简化为 "acc",这样一来就看起来简单多了。

由上面的图可以知道,"acc" 中可组成 "ac" 的个数为 3。再考虑往 text 中添加 "a" 或 "c",为了使添加后个数最多,可以选择将 "a" 放在第一个位置上,或把 "c" 放在最后一个位置上,可以组成如下图所示的两种情况:

由上图可以看出,由于 text 中 "c" 的数目较多,所以将 "a" 添加在 text 首端,可再组成 "c" 的数目个配对

总结一个式子:result = text匹配对数 + text中数目较多 pattern 中含有的字符

text中数目较多 pattern 中含有的字符容易统计遍历一遍 text 即可。

下面来看看 text 匹配对数该如何计算:

leetcode给出的示例不足以展示所有的情况,所以看以下两个示例:

第 1 个 "c" 可匹配 "ac"个数:1。因为他的前面有 1 个 "a";

第 2 个 "c" 可匹配 "ac"个数:2。因为他的前面有 2 个 "a";

第 3 个 "c" 可匹配 "ac"个数:2。因为他的前面有 2 个 "a";

text 中共计可匹配个数为:1 + 2 + 2 = 5。

由于 text 中 "a" 的个数为 2,"c" 的个数为 3,"c" 的数目比较多,所以最终结果在加上 3,最终结果为 8。

综上可以看出来我们只需要遍历一次 text,统计出来 "a","c"个数和 "c" 前面的 "a" 个数求和即可。

再来看另一个特殊情况

示例中 pattern 的两个字符相同,在任意位置添加一个 r 计算可匹配的个数即可

如图,由第一个 "r" 匹配结果,可组成 3 对。依次类推,第二个可组成 2 对,第三个可组成 1 对。最终结果 = 3 + 2 + 1 = 6

显然这是一个等差数列求和。求和公式Sn = (首项 + 末项) * 项数 / 2。在此题中,第一项从 3 开始,即 text 中 "r" 的个数。所以我们可以直接用 text 中 "r" 的个数求和。

代码实现

 class Solution {public long maximumSubsequenceCount(String text, String pattern) {// 为什么转成 char 数组, 别问, 问就是快char[] charArray = text.toCharArray();// pattern中的第一个字符char first = pattern.charAt(0);// pattern中的第二个字符char second = pattern.charAt(1);// 最终返回结果long res = 0;// 第一个字符的个数int firstCount = 0;// 第二个字符的个数int secondCount = 0;// 统计原来text中可组成pattern的个数for (char c : charArray) {if (c == first) {// 统计第一个字符的个数firstCount++;} else if (c == second) {// 统计第二个字符的个数secondCount++;// 碰到第二个字符时, 将其可匹配的个数加到结果中res += firstCount;}}/*情况1:pattern 中两个字符不同可添加一个字符将第一个字符插入到0的位置上, 可以增加 secondCount 个结果将第二个字符插入到 text 末尾, 可以增加 firstCount 个结果比较 firstCount 和 secondCount, 哪个大就用哪一个组成结果​情况1:pattern 中两个字符相同如果 pattern 两个字符相同, 直接统计该字符的个数, 等差数列求和即可*/return first == second ? ((long) firstCount + 1) * firstCount / 2 : firstCount > secondCount ? res + firstCount : res + secondCount;}}

相关文章:

LeetCode2207解题思路

题目描述 字符串中最多数目的子序列 解题思路: 题目要求我们找到在 text 中 找到最多可组成 pattern 的字符串个数,并且允许在 text 的任意位置插入 pattern 中一个字符,也就是说我们只需要考虑 text 中的 pattern 含有的字符即可。例如示例…...

opencv图像增强十四:opencv两种白平衡介绍及实现

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、白平衡介绍二、灰度世界法三、完美反射法 前言 在摄影与影像领域,白平衡是一个至关重要的概念。它直接影响着画面的色彩表现,关系到…...

Linux标准IO(四)-格式化I/O输入

C 库函数提供了 3 个格式化输入函数&#xff0c;包括&#xff1a;scanf()、fscanf()、sscanf()&#xff0c;其函数定义如下所示&#xff1a; #include <stdio.h> int scanf(const char *format, ...); int fscanf(FILE *stream, const char *format, ...); int sscanf(c…...

分布式安装LNMP

目录 搭建LNMP架构 安装mysql 1.上传mysql软件包&#xff0c;关闭防火墙和核心防护 2.安装环境依赖包&#xff0c;桌面安装可能有自带的数据库除 3.配置软件模块 4.编译及安装 5.创建mysql用户 6.修改mysql 配置文件 7.更改mysql安装目录和配置文件的属主属组 8.设置…...

TFTP协议

目录 一、TFTP协议概述 1.1 TFTP协议简介 1.2 TFTP协议特点 二、TFTP协议原理 2.1 TFTP协议工作流程 2.2 TFTP协议数据包格式 三、TFTP协议应用场景 3.1 网络设备配置文件传输 3.2 虚拟机镜像文件传输 3.3 IoT设备固件升级 四、TFTP协议优化方法 4.1 增加超时重传机…...

FPGA随记-二进制转格雷码

反射二进制码&#xff08;RBC&#xff09;&#xff0c;也称为反射二进制&#xff08;RB&#xff09;或格雷码&#xff08;Gray code&#xff09;&#xff0c;得名于Frank Gray&#xff0c;是二进制数制的一种排列方式&#xff0c;使得连续两个值之间仅有一个比特&#xff08;二…...

Android常用C++特性之std::unique_lock

声明&#xff1a;本文内容生成自ChatGPT&#xff0c;目的是为方便大家了解学习作为引用到作者的其他文章中。 std::unique_lock 是 C 标准库中的一种灵活的锁管理类&#xff0c;提供了比 std::lock_guard 更多的功能和灵活性。它可以控制对互斥锁&#xff08;std::mutex&#x…...

网络与信息安全工程师(工信部教育与考试中心)

在当今数字化时代&#xff0c;大量的敏感信息与业务流程在网络上传输和处理&#xff0c;使得网络与信息安全成为保障企业运营、政务管理以及金融交易等关键领域不可忽视的一环。 因此&#xff0c;对网络安全专家的需求日益增长。 例如&#xff0c;金融机构、大型电信运营商以…...

uni-app+vue3开发微信小程序使用本地图片渲染不出来报错[渲染层网络层错误]Failed to load local image resource

我把图片放在assets里面页面通过相对路径引入。结果一直报错。 最后我把图片放在static文件夹下面。然后修改路径指向static就可以了 或者是我们必须先import 这个图片然后在使用 import banner1 from ../../assets/images/banner/banner1.png; <image :src"banner…...

Leetcode 93-复原 IP 地址

有效 IP 地址 正好由四个整数&#xff08;每个整数位于 0 到 255 之间组成&#xff0c;且不能含有前导 0&#xff09;&#xff0c;整数之间用 ‘.’ 分隔。 例如&#xff1a;“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址&#xff0c;但是 “0.011.255.245”、“192.168.…...

unity 中向指定的动画片段添加动画事件,并播放动画,同时获取动画片段的时长。

示例一 using UnityEngine;using System;public static class AnimationUtils{/// <summary>/// 向指定的动画片段添加动画事件&#xff0c;并播放动画&#xff0c;同时获取动画片段的时长。/// </summary>/// <param name"_animator">需要添加动画…...

JavaEE:探索网络世界的魅力——玩转UDP编程

文章目录 UDPUDP的特点UDP协议端格式校验和前置知识校验和具体是如何工作的? UDP UDP的特点 UDP传输的过程类似于寄信. 无连接: 知道对端的IP和端口号就直接进行传输,不需要建立连接.不可靠: 没有确认机制,没有重传机制,如果因为网络故障导致该段无法到达对方,UDP协议也不会…...

生成式人工智能:企业数字化转型的全新引擎,深度解析The Open Group 2024生态系统架构·可持续发展年度大会

生成式人工智能&#xff1a;企业数字化转型的全新引擎&#xff0c;深度解析The Open Group 2024生态系统架构可持续发展年度大会 随着人工智能技术的飞速发展&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;正以惊人的速度渗透到各行各业&#xff0c;成为企…...

阿里云k8s如何创建可用的api token

阿里云的 Kubernetes 配置文件&#xff08;如您所提供的 YAML 格式文件&#xff09;通常不会直接包含用于连接 Kubernetes 集群的令牌。而是包含了客户端证书和私钥数据&#xff0c;这些是用于通过证书验证而不是令牌验证的方式来与 Kubernetes API 服务器进行安全交互的。 1.…...

leetcode刷题day30|贪心算法Part04重叠区间问题(452. 用最少数量的箭引爆气球、435. 无重叠区间、763.划分字母区间)

前言&#xff1a;今天的三道题目都是重叠区间的问题。 452. 用最少数量的箭引爆气球 思路&#xff1a;局部最优&#xff1a;当气球出现重叠&#xff0c;一起射&#xff0c;所用弓箭最少&#xff1b; 全局最优&#xff1a;把所有气球射爆所用弓箭最少。 按照起始位置排序&…...

MQTT客户端实战:从连接到通信。详细说明MQTT客户端和MQTT代理进行通信

EMQX安装 EMQX服务器安装 安装文档&#xff0c;见链接不另外写 https://docs.emqx.com/zh/emqx/latest/deploy/install-ubuntu.html 启动 EMQX 启动为一个 systemd 服务&#xff1a; sudo systemctl start emqx在windows安装客户端 在线 MQTT WebSocket 客户端工具&…...

【go/方法记录】cgo静态库编译以及使用dlv定位cgo崩溃问题

目录 说在前面文件树静态库编译cgo使用崩溃模拟使用dlv定位崩溃参考 说在前面 测试环境&#xff1a;WSL2go版本&#xff1a;go version go1.23.1 linux/amd64gcc版本&#xff1a;gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0cmake版本&#xff1a;3.22.1 文件树 ├── buffer …...

(笔记自用)位运算总结+LeetCode例题:颠倒二进制位+位1的个数

一.位运算总结: 在解题之前理解一下为什么需要位运算&#xff1f;它的本质是什么&#xff1f; 力扣上不少位运算相关的题&#xff0c;并且很多题也会用到位运算的技巧。这又是为什么&#xff1f; 位运算的由来 在计算机里面&#xff0c;任何数据最终都是用数字来表示的&…...

024.PL-SQL进阶—游标

课 程 推 荐我 的 个 人 主 页&#xff1a;&#x1f449;&#x1f449; 失心疯的个人主页 &#x1f448;&#x1f448;入 门 教 程 推 荐 &#xff1a;&#x1f449;&#x1f449; Python零基础入门教程合集 &#x1f448;&#x1f448;虚 拟 环 境 搭 建 &#xff1a;&#x1…...

从零开始使用树莓派debian系统使用opencv4.10.0进行人脸识别(保姆级教程)

一、总体架构 本文主要是使用树莓派自带的csi摄像头&#xff0c;搭配上opencv4.10.0进行物体的识别。本文使用的环境是python3.7.3&#xff0c;环境不一样有可能安装的opencv的过程也会很不一样&#xff0c;但是python的环境我们可以自己自行安装。 二、树莓派系统的安装 本文…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...