力扣爆刷第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天之动态规划收尾(距离编辑与回文子串) 文章目录 力扣爆刷第133天之动态规划收尾(距离编辑与回文子串)一、72. 编辑距离二、647. 回文子串三、516. 最长回文子序列 一、72. 编辑距离 题目链接:https://l…...
List集合中对asList的使用
List<String> sArrays.asList(“qwe”,”cvb”,”mnb”); List<String> s1s.subList(1,2); System.out.Pintln(“s”);//输出结果:[qwe,cvb,mnb] System.out.Pintln(“s1”);//输出结果:[cvb] s1.add(“123qwe”);//报错:java…...
软件测试所有测试方法
β测试_Beta测试 β测试,英文是Beta testing。又称Beta测试,用户验收测试(UAT)。 β测试是软件的多个用户在一个或多个用户的实际使用环境下进行的测试。开发者通常不在测试现场,Beta测试不能由程序员或测试员完成。 …...
linux 下 /usr/local的作用
在Linux系统中,/usr/local目录扮演着特定的角色,它是为用户自安装的软件提供一个标准位置。以下是/usr/local目录的主要用途和特点: 用户级程序目录:该目录用于存放用户自行编译安装的软件或者第三方应用程序,区别于操…...
【web网页制作】html+css旅游家乡河南开封主题网页制作(4页面)【附源码】
HTMLCSS家乡河南主题网页目录 🍔涉及知识🥤写在前面🍧一、网页主题🌳二、页面效果Page1 首页Page2 开封游玩Page 3 开封美食Page4 留言 🌈 三、网页架构与技术3.1 脑海构思3.2 整体布局3.3 技术说明书 🐋四…...
MySQL用命令行导出数据库
问题: 交作业的时候要求交数据文件,因为用的MySQL数据库,就在想怎么用命令行导出数据库,在csdn上找了其他文章,使用MySQL的命令行用下面语句,结果发生报错 mysqldump -u 用户名 -p 数据库名 > 输出地址…...
uniapp video 层级覆盖
层级覆盖 cover-view组件 我这里做了个判断 监听全屏时隐藏按钮 根据项目需求自行更改...
SparkSQL概述
1.1. SparkSQL介绍 SparkSQL,就是Spark生态体系中的构建在SparkCore基础之上的一个基于SQL的计算模块。SparkSQL的前身不叫SparkSQL,而是叫做Shark。最开始的时候底层代码优化、SQL的解析、执行引擎等等完全基于Hive,总是Shark的执行速度要比…...
docker 和 docker-compose
Docker是一种开源的容器化平台,它可以帮助开发人员将应用程序及其所有依赖项打包到一个独立的、可移植的容器中。这意味着您可以在任何地方运行Docker容器,而不需要担心环境差异或依赖项的问题。 Docker Compose是Docker官方提供的一个工具,…...
微信小程序支付(完整版)-ThinkPHP/Uniapp
技术说明 1.前端:uniapp、vue3 2.接口:PHP8、ThinkPHP8、MySQL8.0 3.微信支付- PHP,官方示例文档 4.示例代码的模型及业务自己进行调整,不要一味的复制粘贴!!! 流程说明 1.小程序调用接口…...
同时安装多个nodejs版本可切换使用,或者用nvm管理、切换nodejs版本(两个详细方法)
目录 一.使用nvm的方法: 1.卸载nodejs 2.前往官网下载nvm 3.安装nvm 4.查看安装是否完成 5.配置路径和淘宝镜像 6.查看和安装各个版本的nodejs 7.nvm的常用命令 二.不使用nvm,安装多个版本: 1.安装不同版本的nodejs 2.解压到你想放…...
马化腾用了一年多的时间,告诉所有人,视频号小店是新风口!
大家好,我是电商笨笨熊 当腾讯说出自己要做电商的时候,所有人都在说,根本不可能; 甚至在视频号小店正式推出之后,依旧有人说,腾讯做电商就是笑话; 一个“抄”过来的项目,毫无特色…...
代码随想录算法训练营第36期DAY19
DAY19 104二叉树的最大深度 根节点的高度就是最大深度。 非递归法: /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) …...
C#图像:1.图像区域分割与提取
(1)创建一个名为SplitImage的窗体的应用程序,将窗体改名为FormSplitImage。 (2)创建一个名为ImageProcessingLibrary的类库程序,为该工程添加名为ImageProcessing的静态类 (3)为Imag…...
炸弹使用技巧
掼蛋掼蛋,打的就是炸弹。炸弹是指掼蛋中由4-8张相同牌点的牌组成的牌型,需要注意的是:每局牌中都有两张红桃的牌型为逢人配,可以配除了大小王以外的任意牌,因此掼蛋中牌数最多的炸弹可以达到10张。 两副扑克牌中&#…...
SpringAop详解
文章目录 一、Spring自定义注解1、什么是注解👨🏫2、注解的目的或作用💞3、JDK内置注解💫 【内置元注解 一共八个固定注解】4、元注解 🎯5、自定义注解📸5、Java反射API和类加载过程51、什么是反射基本原…...
对XYctf的一些总结
对XYctf的一些总结 WEB 1.http请求头字段 此次比赛中出现的: X-Forwarded-For/Client-ip:修改来源ip via:修改代理服务器 还有一些常见的字段: GET:此方法用于请求指定的资源。GET请求应该安全且幂等,…...
Visual Studio和Visual Studio Code适用于哪些编程语言
Visual Studio和Visual Studio Code都适用于多种编程语言,它们的适用编程语言如下: Visual Studio适用于: C#Visual Basic .NETF#CJavaScriptTypeScriptPythonHTML/CSSJava(通过插件支持) Visual Studio Code适用于…...
缓存菜品操作
一:问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大。 二:实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: 每个分…...
达梦数据库常用命令整理
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$ -…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
