【每日刷题】Day162

【每日刷题】Day162

🥕个人主页:开敲🍉

🔥所属专栏:每日刷题🍍

🌼文章目录🌼

1. 3302. 字典序最小的合法序列 - 力扣(LeetCode)

2. 44. 通配符匹配 - 力扣(LeetCode)

3. 10. 正则表达式匹配 - 力扣(LeetCode)

1. 3302. 字典序最小的合法序列 - 力扣(LeetCode)

//思路:前后缀和+贪心

//本题要点在于:如何贪?

//根据题目可知,我们 最多只能改变一个字符 使得 word1中的字典序最小的序列对应的字符串 与 word2 完全相等

//既然如此,我们首先肯定是优先考虑:word1 中 字典序最小的、不需要改变字符 就能和 word2 完全相同的字符串

//其次考虑:改变一个字符后,这个字符所在的序列对应的字典序是最小的 并且 对应的字符串和 word2 完全相同。想要找出这个序列,就必须借助前、后缀。

//前缀:word1的当前字符之前有多少个字符和 word2 按照顺序匹配

//后缀:word1的当前字符之后有多少个字符和 word2 按照顺序匹配

class Solution {

public:

    vector<int> validSequence(string word1, string word2)

    {

        int n = word1.size(),m = word2.size();

        vector<int> post(n+1);

        vector<int> ans(m);

        for(int i = n-1,j = m-1;i>=0;i--)//计算后缀

        {

            if(j>=0&&word1[i]==word2[j]) j--;

            post[i] = m-j-1;

        }

        int p = 0;//前缀:word1 和 word2 前面匹配的长度

        for(int i = 0,j = 0;i<n;i++)

        {

            if(j<m&&word1[i]==word2[j])//优先考虑不需要改变字符就相等的字符串

            {

                ans[p++] = i;

                if(++j==m) return ans;

                continue;

            }

            if(p+post[i+1]+1>=m)//如果遇到不相等的需要改变,判断是否应该改变当前字符来形成序列。判断条件:前、后缀和 + 1的长度 ≥ m

            {

                ans[p++] = i++;

                while(p<m&&i<n)//当改变了一个字符后,就只能继续去后面找匹配的,相同的字符,无法再进行改变操作

                {

                    if(word1[i]==word2[p]) ans[p++] = i;

                    i++;

                }

                return ans;

            }

        }

        return {};

    }

};

2. 44. 通配符匹配 - 力扣(LeetCode)

//思路:动态规划——二维dp

class Solution {

public:

    bool isMatch(string s, string p)

    {

        int n = s.size(),m = p.size();

        vector<vector<bool>> dp(n+1,vector<bool>(m+1));

        dp[0][0] = true;

        for(int j = 0;j<m;j++)//考虑 s 字符串为空的情况

        {

            if(p[j]!='*') break;

            dp[0][j+1] = true;

        }

        for(int i = 0;i<n;i++)

        {

            for(int j = 0;j<m;j++)//套用状态转移方程

            {

                if(p[j]=='*') dp[i+1][j+1] = dp[i][j+1]||dp[i+1][j];

                else if(p[j] == s[i] || p[j] == '?') dp[i+1][j+1] = dp[i][j];

            }

        }

        return dp[n][m];

    }

};

3. 10. 正则表达式匹配 - 力扣(LeetCode)

//思路:动态规划——二维dp

//大体思路与上一题类似,区别在于 '*' 的判断

class Solution {

public:

    bool isMatch(string s, string p)

    {

        int n = s.size(),m = p.size();

        vector<vector<bool>> dp(n+1,vector<bool>(m+1));

        s = ' '+s,p = ' '+p;

        dp[0][0] = true;

        for(int j = 2;j<=m;j+=2)

        {

            if(p[j]=='*') dp[0][j] = true;//处理 s 为空串的情况

            else break;

        }

        for(int i = 1;i<=n;i++)

        {

            for(int j = 1;j<=m;j++)

            {

                if(p[j]=='*')//套用状态转移方程,这里进行了合并处理

                    dp[i][j] = dp[i][j-2] ||(p[j-1]=='.'||p[j-1]==s[i])&&dp[i-1][j];

                else

                    dp[i][j] = (p[j]=='.'||p[j]==s[i])&&dp[i-1][j-1];

            }

        }

        return dp[n][m];

    }

};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/929346.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Hadoop生态圈框架部署 伪集群版(四)- Zookeeper单机部署

文章目录 前言一、Zookeeper单机部署&#xff08;手动部署&#xff09;1. 下载Zookeeper安装包到Linux2. 解压zookeeper安装包3. 配置zookeeper配置文件4. 配置Zookeeper系统环境变量5. 启动Zookeeper6. 停止Zookeeper在这里插入图片描述 注意 前言 本文将详细介绍Zookeeper的…

捷联惯导原理和算法预备知识

原理和算法预备知识 牛顿第一运动定律-惯性定律&#xff1a;如一物体不受外力作用&#xff0c;它将保持静止状态或匀速直线运动状态不变。 牛顿第二运动定律&#xff1a;表达式为Fma,。其中F为物体所受的合力&#xff0c;m为物体的质量&#xff0c;a为物体的加速度。这个公式…

工业—使用Flink处理Kafka中的数据_ChangeRecord1

使用 Flink 消费 Kafka 中 ChangeRecord 主题的数据,当某设备 30 秒状态连续为 “ 预警 ” ,输出预警 信息。当前预警信息输出后,最近30

简单注册器

简单注册器 还是想查壳 发现这是apx文件 放入JEB里进行反编译 在JEB里使用快捷键Tab 可以反编译 转化成java语言 我们在搜索一下字符串flag 得到了下面这一串字符串 这里他对这串字符串进行了一系列的加密算法 img src"C:\Users\22069\Pictures\Screenshots\屏幕截图 20…

MySQL两阶段提交目的

阶段提交的过程 事务执行阶段&#xff1a;事务开始执行&#xff0c;InnoDB执行SQL语句的具体操作&#xff0c;如数据修改、删除等&#xff0c;并将这些操作记录在内存中。写入Redo Log&#xff08;准备阶段&#xff09;&#xff1a;事务即将提交时&#xff0c;首先将事务相关的…

33 基于单片机的智能窗帘控制系统

目录 一、主要功能 二、硬件资源 三、程序编程 四、实现现象 一、主要功能 基于51单片机&#xff0c;采用DHT11温湿度传感器检测温湿度&#xff0c;滑动变阻器连接ADC0832数模转换器转换模拟,光敏传感器&#xff0c;采用GP2D12红外传感器&#xff0c;通过LCD1602显示屏显示…

Qt关于padding设置不起作用的的解决办法

观察以下的代码&#xff1a; MyWidget::MyWidget(QWidget *parent): QWidget{parent},m_btn(new QToolButton(this)) {this->setFixedSize(500,500);m_btn->setToolButtonStyle(Qt::ToolButtonTextBesideIcon);m_btn->setIcon(QIcon("F:tabIcon/person-white.s…

zookeeper在确认config无误后仍处于standalone模式的解决方法

jps查看是否有QuorumPeerMain进程 停止服务后该进程仍然存在&#xff0c;输入&#xff1a; ps -ef | grep QuorumPeerMain | grep -v grep | awk {print $2} | xargs kill 之后再启动一次进程 bin/zkServer.sh start 查看状态 bin/zkServer.sh status 发现报错解决&#…

Electron-vue 框架升级 Babel7 并支持electron-preload webapck 4 打包过程记录

前言 我这边一直用的electron-vue框架是基于electron 21版本的&#xff0c;electron 29版本追加了很多新功能&#xff0c;但是这些新功能对开发者不友好&#xff0c;对electron构建出来的软件&#xff0c;使用者更安全&#xff0c;所以&#xff0c;我暂时不想研究electron 29版…

Gartner报告解读(四)| 如何运用上升期的基础设施自动化(IA)为企业数字化转型赋能?

近期&#xff0c;Gartner发布的《2024年中国基础设施战略技术成熟度曲线》显示&#xff0c;未来5-10年&#xff0c;大量具有颠覆性或较高影响力的创新技术可能会实现主流采用&#xff0c;其中就包括基础设施自动化&#xff08;IA&#xff09;。 基础设施自动化Gartner评估情况 …

博泽Brose EDI项目案例

Brose 是一家德国的全球性汽车零部件供应商&#xff0c;主要为全球汽车制造商提供机电一体化系统和组件&#xff0c;涵盖车门、座椅调节系统、空调系统以及电动驱动装置等。Brose 以其高质量的创新产品闻名&#xff0c;在全球拥有多个研发和生产基地&#xff0c;是全球第五大家…

springboot读取tif图片转为png在前端预览

springboot读取tif图片转为png在前端预览 我这里是读取tif后转为png,再转为base64直接传给前端。 在线预览base64的地址&#xff1a;http://www.ecomcn.com/tool/Base64/ 文件目录结构&#xff1a; 代码&#xff1a; Overridepublic List<YbglSetYbSPlitListVo> ybgl…

学习日志020---qt信号与槽

作业 import sysfrom PySide6.QtWidgets import QApplication, QWidget,QPushButton,QLineEditfrom Form import Ui_Form from second import Ui_second from PySide6.QtCore import Qtclass MyWidget(QWidget,Ui_Form):def __init__(self):super().__init__()self.setupUi(se…

Lua元表和元方法的使用

元表是一个普通的 Lua 表&#xff0c;包含一组元方法&#xff0c;这些元方法与 Lua 中的事件相关联。事件发生在 Lua 执行某些操作时&#xff0c;例如加法、字符串连接、比较等。元方法是普通的 Lua 函数&#xff0c;在特定事件发生时被调用。 元表包含了以下元方法&#xff1…

【HarmonyOS】鸿蒙应用使用lottie动画

【HarmonyOS】鸿蒙应用使用lottie动画 一、lottie动画是什么&#xff1f; https://airbnb.design/lottie Lottie是由Airbnb团队开发的一个适用于iOS、Android、React Native、Web和Windows的开源动画库&#xff0c;用于解析使用Bodymovin导出为JSON的Adobe After Effects动…

前缀和(四)除自身以外数组的乘积

238. 除自身以外数组的乘积 给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&…

在数据库设计中同步冗余字段的思考与实践

目录 前言1. 冗余字段设计的背景与场景1.1 场景描述1.2 冗余字段的必要性 2. 冗余字段设计的优点2.1 提高查询效率2.2 简化应用逻辑 3. 冗余字段设计的缺点与挑战3.1 数据不一致问题3.2 更新开销增加3.3 数据冗余占用存储空间 4. 如何同步更新冗余字段4.1 手动更新方式4.2 使用…

Qt开发技巧(二十四)滚动部件的滑动问题,Qt设置时区问题,自定义窗体样式不生效问题,编码格式问题,给按钮左边加个图,最小化后的卡死假象

继续记录一些Qt开发中的技巧操作&#xff1a; 1.滚动部件的滑动问题 再Linux嵌入式设备上&#xff0c;有时候一个页面的子部件太多&#xff0c;一屏放不下是需要做页面滑动&#xff0c;可以使用“QScrollArea”控件&#xff0c;拖来一个“QScrollArea”控件&#xff0c;将子部件…

【5G】5G技术组件 5G Technology Components

5G的目标设置非常高&#xff0c;不仅在数据速率上要求达到20Gbps&#xff0c;在容量提升上要达到1000倍&#xff0c;还要为诸如大规模物联网&#xff08;IoT&#xff0c; Internet of Things&#xff09;和关键通信等新服务提供灵活的平台。这些高目标要求5G网络采用多种新技术…

后端返回前端的数据量过大解决方案

后端返回前端的数据量过大解决方案 性能面板(Performance) chrome调试指南 原因 遇到一个页面有好几个表格&#xff0c;部分表格采用虚拟滚动条 数据量有点大 接近快60s了&#xff0c;看一下是哪里导致的慢 后台请求方法执行并不慢 2024-12-04 15:21:52.889 INFO 69948 …