代码随想录算法训练营第四十九天| 647. 回文子串、 516.最长回文子序列

647. 回文子串

在这里插入图片描述

题目链接:647. 回文子串
文档讲解:代码随想录
状态:不会

思路:
dp[i][j] 表示字符串 s 从索引 i 到索引 j 这一段子串是否为回文子串。
当s[i]与s[j]不相等,那没啥好说的了,dp[i][j]一定是false。

当s[i]与s[j]相等时,这就复杂一些了,有如下三种情况:
情况一:下标i 与 j相同,同一个字符例如a,当然是回文子串
情况二:下标i 与 j相差为1,例如aa,也是回文子串
情况三:下标:i 与 j相差大于1的时候,例如cabac,此时s[i]与s[j]已经相同了,我们看i到j区间是不是回文子串就看aba是不是回文就可以了,那么aba的区间就是 i+1 与 j-1区间,这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

dp[i + 1][j - 1]和dp[i][j]关系:
字符串中s[i,j]就是在s[i-1][j+1]的基础上两端分别加上了一个字符,
因为chars[i] == chars[j],所以只要dp[i + 1][j - 1]为true,dp[i][j]必定为true

遍历顺序:
可以发现dp[i][j]是从左下方往右上方推导过来的,所以i往上,j往右

题解:

    public int countSubstrings(String s) {
        // 将字符串转换为字符数组
        char[] chars = s.toCharArray();
        // 获取字符串的长度
        int n = s.length();
        // 创建一个二维数组 dp,用于存储子串是否为回文
        // dp[i][j] 表示字符串 s 从索引 i 到索引 j 这一段子串是否为回文子串
        boolean[][] dp = new boolean[n][n];
        // 计数器,用于统计回文子串的数量
        int count = 0;
        //根据状态转移方程可以发现dp[i][j]是从左下方往右上方推导过来的,所以i往上,j往右
        // 从后向前遍历字符串的字符
        for (int i = n - 1; i >= 0; i--) {
            // 从当前字符向后遍历剩余字符
            for (int j = i; j < n; j++) {
                // 如果字符 i 和字符 j 相等
                if (chars[i] == chars[j]) {
                    // 如果 i 和 j 之间的距离小于等于1(即相邻或同一字符),或者子串 i+1 到 j-1 也是回文
                    // dp[i + 1][j - 1]和dp[i][j]关系:
                    // 字符串中s[i,j]就是在s[i-1],j+1]的基础上两端分别加上了一个字符,
                    // 因为chars[i] == chars[j],所以只要dp[i + 1][j - 1]为true,dp[i][j]必定为true
                    if (j - i <= 1||dp[i + 1][j - 1]) {
                        // 标记 dp[i][j] 为 true,表示该子串是回文
                        dp[i][j] = true;
                        // 回文子串计数器加1
                        count++;
                    }
                }
            }
        }
        // 返回回文子串的总数
        return count;
    }
}

516.最长回文子序列

题目链接:516.最长回文子序列
文档讲解:代码随想录
状态:不会

思路:
dp[i][j]:字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]

因为遍历的时候i是从下往上,j是从左往右,所以字符串中s[i,j]就是在s[i-1,j+1]的基础上两端分别加上了一个字符。

如果s[i]与s[j]相同,那么显然dp[i][j] = dp[i + 1][j - 1] + 2;
如果s[i]与s[j]不相同,说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度,那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
加入s[j]的回文子序列长度为dp[i + 1][j]。
加入s[i]的回文子序列长度为dp[i][j - 1]。
那么dp[i][j]一定是取最大的,即:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

题解:

public int longestPalindromeSubseq(String s) {
    int len = s.length();
    char[] chars = s.toCharArray();
    int[][] dp = new int[len][len]; // 初始化 dp 数组,dp[i][j] 表示 s[i...j] 的最长回文子序列长度
    
    // 从后往前遍历 i,以保证所有可能的子问题都被考虑到
    for (int i = len - 1; i >= 0; i--) {
        dp[i][i] = 1; // 单个字符的最长回文子序列长度为 1
        
        // 从 i+1 开始遍历 j,确保 j > i
        for (int j = i + 1; j < len; j++) {
            if (chars[i] == chars[j]) {
                // 当 chars[i] 和 chars[j] 相同时,dp[i][j] 可以从 dp[i+1][j-1] 推导过来,再加上 i 和 j 这两个字符
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                // 当 chars[i] 和 chars[j] 不相同时,dp[i][j] 取决于 dp[i+1][j] 和 dp[i][j-1] 中的较大值
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // dp[0][len-1] 表示整个字符串 s 的最长回文子序列长度
    return dp[0][len - 1];
}

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

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

相关文章

柔性测斜仪:监测钻孔位移的核心利器

柔性测斜仪&#xff0c;作为一款创新的测量工具&#xff0c;凭借其卓越的设计与性能&#xff0c;在地下建筑、桥梁、隧道及水利水电工程等领域展现出非凡的应用价值。其安装便捷、操作简便、高精度及长寿命等特性&#xff0c;使之成为监测钻孔垂直与水平位移的理想选择。以下是…

打卡第8天-----字符串

进入字符串章节了,我真的特别希望把leetcode上的题快点全部都给刷完,我是社招准备跳槽才选择这个训练营的,面试总是挂算法题和编程题,希望通过这个训练营我的算法和编程的水平能有所提升,抓住机会,成功上岸。我现在的这份工作,真的是一天都不想干了,但是下家工作单位还…

VS Code 扩展如何发布到私有Nexus的正确姿势

VS Code扩展的发布 VS Code 扩展的发布需要使用到vsce&#xff0c;vsce是一个用于打包、发布和管理 VS Code 扩展的命令行工具。可以通过 npm 来全局安装它&#xff1a; npm install -g vsce发布扩展到微软的应用市场 VS Code 的应用市场基于微软自己的 Azure DevOps。要发布…

计算机网络--tcpdump和iptable设置、内核参数优化策略

tcpdump工具 tcpdump命令&#xff1a; 选项字段&#xff1a; 过滤表达式&#xff1a; 实用命令&#xff1a; TCP三次握手抓包命令&#xff1a; #客户端执行tcpdump 抓取数据包 tcpdump -i etho tcp and host 192.168.12.36 and port 80 -W timeout.pcapnetstat命令 netst…

element el-table实现表格动态增加/删除/编辑表格行,带校验规则

本篇文章记录el-table增加一行可编辑的数据列&#xff0c;进行增删改。 1.增加空白行 直接在页面mounted时对form里面的table列表增加一行数据&#xff0c;直接使用push() 方法增加一列数据这个时候也可以设置一些默认值。比如案例里面的 产品件数 。 mounted() {this.$nextTi…

[嵌入式 C 语言] 按位与、或、取反、异或

若协议中如下图所示&#xff1a; 注意&#xff1a; 长度为1&#xff0c;表示1个字节&#xff0c;也就是0xFF&#xff0c;也就是 1111 1111 &#xff08;这里0xFF只是单纯表示一个数&#xff0c;也可以是其他数&#xff0c;这里需要注意的是1个字节的意思&#xff09; 一、按位…

URI:URL、URN

名称解释&#xff1a; URI:统一资源标识符&#xff1b; URL:统一资源定位符; URN:统一资源命名符&#xff1b; URI、URL、URN关系 URI是URL和URN的超集,也就是说URI有两种方式&#xff0c;一种是URL一种是URN,不过URL的方式用的比较多。 看了一个视频&#xff0c;博主解释非…

xcode配置swift使用自定义主题颜色或者使用RGB或者HEX颜色

要想在xcode中使用自定义颜色或者配置主题色&#xff0c;需要在Assets中配置&#xff0c;打开Assets文件&#xff0c;然后点击添加Color Set&#xff1a; 输入颜色的名称&#xff0c;然后选中这个颜色&#xff0c;会出现两个颜色&#xff1a; Any Appearance表示亮色模式下使用…

基于uni-app与图鸟UI的知识付费小程序模板

一、项目概述 在知识经济蓬勃发展的背景下&#xff0c;移动互联网成为知识传播与消费的重要渠道。本项目旨在利用前沿的前端技术栈——uni-app及高效UI框架图鸟UI&#xff0c;打造一款集多功能于一体的、面向广大求知者的知识付费平台移动端模板。该模板旨在简化开发流程&…

【最强八股文 -- 计算机网络】【快速版】TCP 与 UDP 头部格式

目标端口和源端口: 应该把报文发给哪个进程包长度: UDP 首部的长度跟数据的长度之和校验和: 为了提供可靠的 UDP 首部和数据而设计&#xff0c;接收方使用检验和来检查该报文段中是否出现差错 源端口号和目的端口号: 用于多路复用/分解来自或送到上层应用的数据。告诉主机报文段…

轻松理解c++17的string_view

文章目录 轻松理解c17的string_view设计初衷常见用法构造 std::string_view常用操作作为函数参数 注意事项总结 轻松理解c17的string_view std::string_view 是 C17 引入的一个轻量级、不拥有&#xff08;non-owning&#xff09;的字符串视图类。它的设计初衷是提供一种高效、…

Web学习day03

maven&Mybatis 目录 maven&Mybatis 文章目录 一、maven 1.1作用 1.2仓库 1.3命令 1.4依赖范围 1.5生命周期 二、MyBatis 2.1简介 2.2API 2.3增删改的实现&案例 总结 一、maven 1.1作用 统一项目结构&#xff1b;项目构建&#xff1a;通过简单命令&a…

高阶面试-dubbo的学习

SPI机制 SPI&#xff0c;service provider interface&#xff0c;服务发现机制&#xff0c;其实就是把接口实现类的全限定名配置在文件里面&#xff0c;然后通过加载器ServiceLoader去读取配置加载实现类&#xff0c;比如说数据库驱动&#xff0c;我们把mysql的jar包放到项目的…

16. Revit API: Family、FamilySymbol、FamilyInstance

前言 前面写着一直絮絮叨叨&#xff0c;感觉不好。想找些表情包来&#xff0c;写得好玩点&#xff0c;但找不到合适的&#xff0c;或者说耗时费力又不满意&#xff0c;而自个儿又做不来表情包&#xff0c;就算了。 其次呢&#xff0c;之前会把部分类成员给抄表列出来&#xf…

昇思25天学习打卡营第15天|基于 MindSpore 实现 BERT 对话情绪识别

文章目录 昇思MindSpore应用实践1、基于 MindSpore 实现 BERT 对话情绪识别BERT 模型简介数据集数据加载和数据预处理 2、模型训练模型验证 3、模型推理 Reference 昇思MindSpore应用实践 本系列文章主要用于记录昇思25天学习打卡营的学习心得。 1、基于 MindSpore 实现 BERT…

FOLANNIC FD31 UPS工作原理介绍

1&#xff0e;1简介 FOLANNIC FD31系列UPS系工业级电厂型不间断电源&#xff0c;是为重要负载提供不受电网干扰、稳压、稳频的电力供应的电源设备&#xff0c;在市电掉电后&#xff0c;UPS可给负载继续提供一段时间供电&#xff0c;此系列UPS采用带输出隔离变压器的高频双变换结…

回收站删除了是不是彻底删除了 回收站删除了怎么找回 回收站删除了还能找回来吗

电脑删除的数据文件一般不会直接被彻底删除掉&#xff0c;而是会暂存在回收站中&#xff0c;这样设计主要是为了防止误删除等操作&#xff0c;如果不小心删除了很重要的文件&#xff0c;只需要在回收站对文件进行还原即可。为了让大家更了解回收站&#xff0c;下面给大家详细讲…

JavaWeb-js(4)

js事件 在前端页面中&#xff0c;js程序大多数是由事件来驱动的&#xff0c;当触发某些事件的时候&#xff0c;可以使用js负责响应。 js事件由三部分组成: 事件源——》指的是被触发的对象; 事件类型——》如何触发的事件&#xff0c;如:鼠标单击、双击、键盘操作等;…

【题目/算法训练】:单调队列单调栈

&#x1f680; 前言&#xff1a; 【算法】单调队列&&单调栈 可以在看完这篇文章后&#xff0c;再来写下面的题目 一、绝对差不超过限制的最长连续子数组 思路&#xff1a; 1&#xff09; 就相当于滑动窗口&#xff0c;维护滑动窗口内的两个值&#xff0c;一个是最大值…

CV05_深度学习模块之间的缝合教学(1)

1.1 在哪里缝 测试文件&#xff1f;&#xff08;&#xff09; 训练文件&#xff1f;&#xff08;&#xff09; 模型文件&#xff1f;&#xff08;√&#xff09; 1.2 骨干网络与模块缝合 以Vision Transformer为例&#xff0c;模型文件里有很多类&#xff0c;我们只在最后…