leetcode每日一题day14(24.9.24)——字符串最多的子序列

ops/2024/10/19 4:10:31/


思路:对于应该首要和贡献联系起来,对于什么是贡献呢,即在某种情况下,会贡献出多少种,符合要求的结果,此题属于较为基础的,对于text中的一个字符如果是非pattern中的元素,则对结果无任何影响,如果出现pattern[0]则需考虑后方有多少个pattern[1],如果出现pattern[1]时则忽略,因为其在patern[0]中考虑过了,不能起点到终点算一次 ,终点到起点又算一次,对于最后的添加一个,也是差不多的既然可以随便放,当然选择放最边上,至于放哪边,则看pattern([0]/[1])谁多。

此时便容易联想到

        方案一从后方开始,遍历如果出现pattern[1]则计数一次,当某时刻遍历到pattern[0]时则在结果累加计数器的值,含义为对结果贡献了计数器组子序列,同时pattern[0]也需计数,用以最后的操作。

        对于方案一寻找漏洞:各有的的操作表面风平浪静,仔细一想,出现pattern[0]如果也同时出现了pattern[1],即pattern两字符相等,此时先后顺序应该怎么处理呢,仔细一想应该是先累加计数器的值,再对pattern进行计数的,思考过程忽略。

代码

long long maximumSubsequenceCount(string text, string pattern) {int len = text.length(), cut_0 = 0, cut_1 = 0;long int ret = 0;for (int i = 0; i < len; i++) {//先更新贡献,再继续计数,主要是为了应对pattern相同,不相同则无所谓先后,不存在同时满足情况。if (text[i] == pattern[1]) { // 如果是结尾元素,则计算贡献ret += cut_0;cut_1++;}if (text[i] == pattern[0]) { // 如果是起点元素,则进行计数cut_0++;}}return ret + max(cut_0, cut_1);}

结语:详细提到了心路历程,任然是大胆猜想,小心求证,在确定看下情况下尽可能考虑到更多的特殊情况。


http://www.ppmy.cn/ops/118116.html

相关文章

计算机科学(学习笔记四)

早期的编程方式 纸片打孔等方法 汇编语言 编程语言发展史 汇编语言也叫机器语言&#xff0c;是计算机的母语。但01不便于人们操作&#xff0c;人们为了方便操作&#xff0c;会输入文字指令&#xff0c;通过汇编器自动转成二进制指令。 但汇编码和底层硬件仍息息相关&#xff…

Android 开发每日定时任务

1、先注册一个广播 setDailyAlarm();IntentFilter filter3 new IntentFilter("UPDATERULE");registerReceiver(updateRuleReceive, filter3); private BroadcastReceiver updateRuleReceive new BroadcastReceiver() {Overridepublic void onReceive(Context con…

封装聊天组件(fang微信聊天)

用法 图 文 视频还没写好&#xff0c;后期补上&#xff0c;因为基于微博本身的ui框架&#xff0c;所以有的样式会有一些问题&#xff0c;可能跟普通写法有一点不同&#xff0c;但是修改一点就可以 //自己做的假数据 <template><wbx-view style"" click"…

学习和备课数据结构要求----重点*******

目录 要求3&#xff1a;如何学习殷人昆大师的书&#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f; 要求1&#xff1a; 要求2&#xff1a; 要求3&#xff1a; 要求1&#xff1a; 1&#xff09;李冬梅&#xff0c;刘畅 2&#xff09;王红梅教师用书先看老版&a…

uniapp url取消#

hbuilder uniapp取消hash(#)模式 manifest.json "h5": { "template": "static/index.html", "devServer": { "port": 9290, "https": false }, "…

【系统规划与管理师】【案例分析】【考点】【答案篇】第10章 团队建设与管理

【问题篇】☞【系统规划与管理师】【案例分析】【考点】【问题篇】第10章 团队建设与管理 【移动端浏览】☞【系统规划与管理师】【案例分析】【模拟考题】章节考题汇总&#xff08;第10章&#xff09;&#xff08;答案篇&#xff09;&#xff08;共15个知识点&#xff09; 第1…

基于JavaWeb开发的Java+SpringMvc+vue+element实现驾校管理系统详细设计

基于JavaWeb开发的JavaSpringMvcvueelement实现驾校管理系统详细设计 &#x1f345; 作者主页 网顺技术团队 &#x1f345; 欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; &#x1f345; 文末获取源码联系方式 &#x1f4dd; &#x1f345; 查看下方微信号获取联系方式 承…

SpringBoot3+Swagger3(最新版springdoc-openapi教程)

第一步&#xff1a;引入springdoc-openapi依赖 <dependency><groupId>org.springdoc</groupId><artifactId>springdoc-openapi-starter-webmvc-ui</artifactId><version>2.6.0</version></dependency> 第二步&#xff1a; 配置…