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

力扣爆刷第133天之动态规划收尾(距离编辑与回文子串)

力扣爆刷第133天之动态规划收尾(距离编辑与回文子串)

文章目录

      • 力扣爆刷第133天之动态规划收尾(距离编辑与回文子串)
      • 一、72. 编辑距离
      • 二、647. 回文子串
      • 三、516. 最长回文子序列

一、72. 编辑距离

题目链接:https://leetcode.cn/problems/edit-distance/description/
思路:本题也是前面重复子序列的变体,可以对字符串进行增删替换操作,其中增加和删除是一样的,而替换依赖的是前一个位置。
定义dp[i][j]表示以下标i为结尾的word1和以下标j为结尾的word2要相等所需要的操作。
如果word1[i] == word2[j],那么所需次数依赖于word1[i-1]和word2[j-1],即dp[i][j] = dp[i-1][j-1]。
如果word1[i] != word2[j],那么增删对应的都是dp[i-1][j],dp[i][j-1],替换对应的是dp[i-1][j-1],取三者最低。

class Solution {public int minDistance(String word1, String word2) {int m = word1.length(), n = word2.length();int[][] dp = new int[m+1][n+1];for(int i = 0; i <= m; i++) dp[i][0] = i;for(int i = 0; i <= n; i++) dp[0][i] = i;for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(word1.charAt(i) == word2.charAt(j)) {dp[i+1][j+1] = dp[i][j];}else{dp[i+1][j+1] = Math.min(Math.min(dp[i+1][j], dp[i][j+1]), dp[i][j]) + 1;}}}return dp[m][n];}
}

二、647. 回文子串

题目链接:https://leetcode.cn/problems/palindromic-substrings/description/
思路:
常规做法:本题求回文子串的个数,子串是要求连续的,我们可以从单点和双点,向字符串两段遍历,并且记录下子串的个数。
也可以使用动态规划,定义dp[i][j]表示,区间s[i,j]是回文子串,dp[i][j]依赖于dp[i+1][j-1],也就是当前位置的左下方。

class Solution {public int countSubstrings(String s) {int sum = 0;for(int i = 0; i < s.length(); i++) {sum += countSum(s, i, i);sum += countSum(s, i, i+1);}return sum;}int countSum(String s, int i, int j) {int count = 0;while(i >= 0 && j < s.length()) {if(s.charAt(i) == s.charAt(j)) {count++;i--;j++;}else{break;}}return count;}}

动态规划解法:

class Solution {public int countSubstrings(String s) {int len = s.length(), sum = 0;boolean[][] dp = new boolean[len][len];for(int i = len-1; i >= 0; i--) {for(int j = i; j < len; j++) {if(s.charAt(i) == s.charAt(j) && (j-i<=2 || dp[i+1][j-1])) {dp[i][j] = true;sum++;}}}return sum;}
}

三、516. 最长回文子序列

题目链接:https://leetcode.cn/problems/longest-palindromic-subsequence/
思路:上一题求的是回文子串的个数,本题求的是回文子序列的长度,一个连续一个不连续。定义dp[i][j]表示区间[i, j]中的最长回文子序列的长度是dp[i][j],例如a b b b a的长度依赖于 bbb中回文子序列的长度,所以遍历的方式是从下往下,从左往右。s[i] = s[j]时依赖于左下角的元素dp[i][j] = dp[i+1][j-1],s[i] != s[j]时,就类似于a b b b 或者 b b b a,即dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);

class Solution {public int longestPalindromeSubseq(String s) {int len = s.length();int[][] dp = new int[len][len];for(int i = 0; i < len; i++) dp[i][i] = 1;for(int i = len-1; i >= 0; i--) {for(int j = i+1; j < len; j++) {if(s.charAt(i) == s.charAt(j)) {dp[i][j] = dp[i+1][j-1] + 2;}else{dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);}}}return dp[0][len-1];}
}

相关文章:

力扣爆刷第133天之动态规划收尾(距离编辑与回文子串)

力扣爆刷第133天之动态规划收尾&#xff08;距离编辑与回文子串&#xff09; 文章目录 力扣爆刷第133天之动态规划收尾&#xff08;距离编辑与回文子串&#xff09;一、72. 编辑距离二、647. 回文子串三、516. 最长回文子序列 一、72. 编辑距离 题目链接&#xff1a;https://l…...

List集合中对asList的使用

List<String> sArrays.asList(“qwe”,”cvb”,”mnb”); List<String> s1s.subList(1,2); System.out.Pintln(“s”);//输出结果&#xff1a;[qwe,cvb,mnb] System.out.Pintln(“s1”);//输出结果&#xff1a;[cvb] s1.add(“123qwe”);//报错&#xff1a;java…...

软件测试所有测试方法

β测试_Beta测试 β测试&#xff0c;英文是Beta testing。又称Beta测试&#xff0c;用户验收测试&#xff08;UAT&#xff09;。 β测试是软件的多个用户在一个或多个用户的实际使用环境下进行的测试。开发者通常不在测试现场&#xff0c;Beta测试不能由程序员或测试员完成。 …...

linux 下 /usr/local的作用

在Linux系统中&#xff0c;/usr/local目录扮演着特定的角色&#xff0c;它是为用户自安装的软件提供一个标准位置。以下是/usr/local目录的主要用途和特点&#xff1a; 用户级程序目录&#xff1a;该目录用于存放用户自行编译安装的软件或者第三方应用程序&#xff0c;区别于操…...

【web网页制作】html+css旅游家乡河南开封主题网页制作(4页面)【附源码】

HTMLCSS家乡河南主题网页目录 &#x1f354;涉及知识&#x1f964;写在前面&#x1f367;一、网页主题&#x1f333;二、页面效果Page1 首页Page2 开封游玩Page 3 开封美食Page4 留言 &#x1f308; 三、网页架构与技术3.1 脑海构思3.2 整体布局3.3 技术说明书 &#x1f40b;四…...

MySQL用命令行导出数据库

问题&#xff1a; 交作业的时候要求交数据文件&#xff0c;因为用的MySQL数据库&#xff0c;就在想怎么用命令行导出数据库&#xff0c;在csdn上找了其他文章&#xff0c;使用MySQL的命令行用下面语句&#xff0c;结果发生报错 mysqldump -u 用户名 -p 数据库名 > 输出地址…...

uniapp video 层级覆盖

层级覆盖 cover-view组件 我这里做了个判断 监听全屏时隐藏按钮 根据项目需求自行更改...

SparkSQL概述

1.1. SparkSQL介绍 SparkSQL&#xff0c;就是Spark生态体系中的构建在SparkCore基础之上的一个基于SQL的计算模块。SparkSQL的前身不叫SparkSQL&#xff0c;而是叫做Shark。最开始的时候底层代码优化、SQL的解析、执行引擎等等完全基于Hive&#xff0c;总是Shark的执行速度要比…...

docker 和 docker-compose

Docker是一种开源的容器化平台&#xff0c;它可以帮助开发人员将应用程序及其所有依赖项打包到一个独立的、可移植的容器中。这意味着您可以在任何地方运行Docker容器&#xff0c;而不需要担心环境差异或依赖项的问题。 Docker Compose是Docker官方提供的一个工具&#xff0c;…...

微信小程序支付(完整版)-ThinkPHP/Uniapp

技术说明 1.前端&#xff1a;uniapp、vue3 2.接口&#xff1a;PHP8、ThinkPHP8、MySQL8.0 3.微信支付- PHP&#xff0c;官方示例文档 4.示例代码的模型及业务自己进行调整&#xff0c;不要一味的复制粘贴&#xff01;&#xff01;&#xff01; 流程说明 1.小程序调用接口…...

同时安装多个nodejs版本可切换使用,或者用nvm管理、切换nodejs版本(两个详细方法)

目录 一.使用nvm的方法&#xff1a; 1.卸载nodejs 2.前往官网下载nvm 3.安装nvm 4.查看安装是否完成 5.配置路径和淘宝镜像 6.查看和安装各个版本的nodejs 7.nvm的常用命令 二.不使用nvm&#xff0c;安装多个版本&#xff1a; 1.安装不同版本的nodejs 2.解压到你想放…...

马化腾用了一年多的时间,告诉所有人,视频号小店是新风口!

大家好&#xff0c;我是电商笨笨熊 当腾讯说出自己要做电商的时候&#xff0c;所有人都在说&#xff0c;根本不可能&#xff1b; 甚至在视频号小店正式推出之后&#xff0c;依旧有人说&#xff0c;腾讯做电商就是笑话&#xff1b; 一个“抄”过来的项目&#xff0c;毫无特色…...

代码随想录算法训练营第36期DAY19

DAY19 104二叉树的最大深度 根节点的高度就是最大深度。 非递归法&#xff1a; /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) …...

C#图像:1.图像区域分割与提取

&#xff08;1&#xff09;创建一个名为SplitImage的窗体的应用程序&#xff0c;将窗体改名为FormSplitImage。 &#xff08;2&#xff09;创建一个名为ImageProcessingLibrary的类库程序&#xff0c;为该工程添加名为ImageProcessing的静态类 &#xff08;3&#xff09;为Imag…...

炸弹使用技巧

掼蛋掼蛋&#xff0c;打的就是炸弹。炸弹是指掼蛋中由4-8张相同牌点的牌组成的牌型&#xff0c;需要注意的是&#xff1a;每局牌中都有两张红桃的牌型为逢人配&#xff0c;可以配除了大小王以外的任意牌&#xff0c;因此掼蛋中牌数最多的炸弹可以达到10张。 两副扑克牌中&#…...

SpringAop详解

文章目录 一、Spring自定义注解1、什么是注解&#x1f468;‍&#x1f3eb;2、注解的目的或作用&#x1f49e;3、JDK内置注解&#x1f4ab; 【内置元注解 一共八个固定注解】4、元注解 &#x1f3af;5、自定义注解&#x1f4f8;5、Java反射API和类加载过程51、什么是反射基本原…...

对XYctf的一些总结

对XYctf的一些总结 WEB 1.http请求头字段 此次比赛中出现的&#xff1a; X-Forwarded-For/Client-ip&#xff1a;修改来源ip via&#xff1a;修改代理服务器 还有一些常见的字段&#xff1a; GET&#xff1a;此方法用于请求指定的资源。GET请求应该安全且幂等&#xff0c…...

Visual Studio和Visual Studio Code适用于哪些编程语言

Visual Studio和Visual Studio Code都适用于多种编程语言&#xff0c;它们的适用编程语言如下&#xff1a; Visual Studio适用于&#xff1a; C#Visual Basic .NETF#CJavaScriptTypeScriptPythonHTML/CSSJava&#xff08;通过插件支持&#xff09; Visual Studio Code适用于…...

缓存菜品操作

一&#xff1a;问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大。 二&#xff1a;实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; 每个分…...

达梦数据库常用命令整理

1.数据库自身信息 1.1 查询实例信息 SQL> select name inst_name from v$instance;行号 INST_NAME ---------- --------- 1 DMSERVER已用时间: 11.211(毫秒). 执行号:15.1.2 查询数据库当前状态 SQL> select status$ from v$instance;行号 STATUS$ -…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...