算法学习——LeetCode力扣动态规划篇10

算法学习——LeetCode力扣动态规划篇10

在这里插入图片描述

583. 两个字符串的删除操作

583. 两个字符串的删除操作 - 力扣（LeetCode）

描述

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

示例

示例 1：

输入: word1 = “sea”, word2 = “eat”
输出: 2
解释: 第一步将 “sea” 变为 “ea” ，第二步将 "eat "变为 “ea”

示例 2:

输入：word1 = “leetcode”, word2 = “etco”
输出：4

提示

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母

代码解析

动态规划

和1143相同，只要求出两个字符串的最长公共子序列长度即可，那么除了最长公共子序列之外的字符都是必须删除的，最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。

class Solution {
public:
    
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1 , vector<int>(word2.size()+1 ,0));

        for(int i=0 ;i<word1.size() ;i++)
        {
            for(int j=0 ;j<word2.size() ;j++)
            {
                if(word1[i] == word2[j]) dp[i+1][j+1] = dp[i][j] + 1;
                else dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
            }
        }
        return word1.size() + word2.size() - 2*dp[word1.size()][word2.size()];
    }
};

72. 编辑距离

72. 编辑距离 - 力扣（LeetCode）

描述

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例

示例 1：

输入：word1 = “horse”, word2 = “ros”
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)

示例 2：

输入：word1 = “intention”, word2 = “execution”
输出：5
解释：
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)

提示

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

代码解析

动态规划
  • 确定dp数组以及下标的含义
    dp[i][j] 表示前 i 个字符的word1，和前 j 个字符的word2，最近编辑距离。
  • 递推公式
    • if (word1[ i ] == word2[ j ]) 那么说明不用任何编辑，
      即dp[i+1][j+1] = dp[i ][j ];
    • if (word1[ i ] ！= word2[ j ]) 有三种情况
      • 删除world1
        word1第 i 个字符删除一个元素，就是world1第 i -1 与world2第 j 再加上一个操作。
        即 dp[i+1][j+1] = dp[ i ][ j+1] + 1;
      • 删除world2（相当于添加world1）
        word2第 j 个字符删除一个元素，就是world1第 i 与world2第 j -1 再加上一个操作。
        即 dp[i+1][j+1] = dp[ i +1][ j] + 1;
      • 替换元素
        word1第 i 个字符和word1第 i -1个字符替换，world2同样，就是world1第 i -1 与world2第 j -1 再加上一个操作。
        即 dp[i+1][j+1] = dp[ i ][ j] + 1;
      • 最终三种情况取最小
        dp[i+1][j+1] = min( dp[i][j] , min(dp[i][j+1],dp[i+1][j])) + 1;
  • dp数组初始化

    • dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。
      那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i;

    • 同理dp[0][j] = j;
      在这里插入图片描述
      在这里插入图片描述

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1 , vector<int>(word2.size()+1));

        for(int i=0 ; i<word1.size();i++)
            dp[i+1][0] = i+1;
        for(int j=0 ; j<word2.size();j++)
            dp[0][j+1] = j+1;
        
        for(int i=0;i<word1.size();i++)
        {
            for(int j=0; j<word2.size();j++)
            {
                if(word1[i] == word2[j]) dp[i+1][j+1] = dp[i][j];
                else dp[i+1][j+1] = min( dp[i][j] , min(dp[i][j+1],dp[i+1][j])) + 1;
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

647. 回文子串

647. 回文子串 - 力扣（LeetCode）

描述

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例

示例 1：

输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”

示例 2：

输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示

1 <= s.length <= 1000
s 由小写英文字母组成

代码解析

暴力法
class Solution {
public:
    bool cheak(const string s , int left,int right)
    {
        for(int i=left ,j=right; i<=(right-left)/2 +left; i++,j--)
        {
            if(s[i]!=s[j]) return false;
        }
        return true;
    }
    int countSubstrings(string s) {
        if(s.size()<=1) return 1;
        int num=0;
        int left=0,right=1;
        for(int left=0 ; left<s.size() ;left++)
        {
            for(right=left ; right<s.size();right++)
            {
                if(cheak(s,left,right)==1)
                {
                    num++;
                    // cout<<left<<' '<<right<<endl;
                }
            }
        }
        return num;
    }
};
动态规划

  • 确定dp数组（dp table）以及下标的含义
    布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

  • 确定递推公式
    在确定递推公式时，就要分析如下几种情况。

    • 当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数组如何初始化
    dp[i][j]可以初始化为true么？ 当然不行，怎能刚开始就全都匹配上了。
    所以dp[i][j]初始化为false。

  • 确定遍历顺序
    遍历顺序可有有点讲究了。
    首先从递推公式中可以看出，情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。
    dp[i + 1][j - 1] 在 dp[i][j]的左下角，
    一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。
    因为dp[i][j]的定义，所以j一定是大于等于i的，那么在填充dp[i][j]的时候一定是只填充右上半部分。
    在这里插入图片描述

class Solution {
public:
    int countSubstrings(string s) {
        if(s.size()<=1) return 1;
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size() , false));
        int num = 0;
        for(int i=s.size()-1 ; i>=0;i--)
            for(int j=i ;j<s.size();j++)
            	//s[i]==s[j]为首尾相同
            	//并且j-i <= 1为"a"或者"aa"的情况,为回文串
            	//如果j-i不是<=1,但是dp[i+1][j-1]==true，也是回文串，因为首位相同中间是回文串
            	//如dabcd，首位d相同，中间dp[i+1][j-1]为abc也是回文串，即dabcd为回文串
                if(  s[i]==s[j] &&
                    (j-i <= 1||dp[i+1][j-1]==true)  )  
                {
                    num++;
                    dp[i][j] = true;
                }
        return num;
    }
};

516. 最长回文子序列

516. 最长回文子序列 - 力扣（LeetCode）

描述

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例

示例 1：

输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。

示例 2：

输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。

提示

1 <= s.length <= 1000
s 仅由小写英文字母组成

代码解析

动态规划

  • 确定dp数组（dp table）以及下标的含义
    dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

  • 确定递推公式
    在判断回文子串的题目中，关键逻辑就是看s[i]与s[j]是否相同。

    • 如果s[i]与s[j]相同，
      • j - i ==0 , dp[i][j] = 1;
      • j - i == 1, dp[i][j] = 2;
      • j - i > 2, dp[i][j] = dp[i + 1][j - 1] + 2;
        在这里插入图片描述
    • 如果s[i]与s[j]不同
      dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

在这里插入图片描述

  • 确定遍历顺序
    从递推公式dp[i][j] = dp[i + 1][j - 1] + 2 和 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 可以看出，dp[i][j]是依赖于dp[i + 1][j - 1] 和 dp[i + 1][j]，
    也就是从矩阵的角度来说，dp[i][j] 下一行的数据。 所以遍历i的时候一定要从下到上遍历，这样才能保证，下一行的数据是经过计算的。
    在这里插入图片描述
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        if(s.size()<=1) return s.size();
        vector<vector<int>> dp(s.size() , vector<int>(s.size() ,0));
        int result = 0;
        for(int i=s.size()-1; i>=0 ;i-- )
            for(int j=i ;j<s.size();j++)
            {
                if(s[i]==s[j])
                {
                    if(j==i) dp[i][j] = 1;
                    else if(j-i==1) dp[i][j] = 2;
                    else dp[i][j] = dp[i+1][j-1] + 2;

                    if(dp[i][j] > result) result = dp[i][j];
                }else
                {
                    dp[i][j] = max(dp[i][j-1],dp[i+1][j]);
                }
            }
                
        // for(int i=0;i<s.size();i++)
        // {
        //     for(int j=0;j<s.size();j++)
        //     cout<<dp[i][j]<<' ';
        
        //     cout<<endl;
        // }
        return result;
    }
};

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

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

相关文章

使用 golang 以及 Gin 框架，将上传的图片在不保存至本地的情况下添加水印，并上传至阿里云 OSS

使用 golang 以及 Gin 框架，将上传的图片在不保存至本地的情况下添加水印，并上传至阿里云 OSS

正如标题所述&#xff0c;使用golang对上传图片添加水印&#xff0c;以及将图片上传到阿里云OSS&#xff0c;网上一搜索&#xff0c;便有你想要的结果了&#xff0c;可是&#xff0c;他们却先将上传图片添加水印后保存在本地&#xff0c;而后再将添加了水印的图片上传到阿里云O…
阅读更多...
【个人笔记】python界面美化

【个人笔记】python界面美化

目录 标题栏美化 样例展示 代码 配套鼠标移动 完整展示 标题栏美化 样例展示 代码 import tkinter as tk from tkinter import ttk from PIL import Image, ImageTk import subprocess import sysdef open_buy_quantity():window.destroy()subprocess.run(["p…
阅读更多...
网际协议 - IP

网际协议 - IP

文章目录 目录 文章目录 前言 1 . 网际协议IP 1.1 网络层和数据链路层的关系 2. IP基础知识 2.1 什么是IP地址? 2.2 路由控制 3. IP地址基础知识 3.1 IP地址定义 3.2 IP地址组成 3.3 IP地址分类 3.4 子网掩码 IP地址分类导致浪费? 子网与子网掩码 3.5 CIDR与…
阅读更多...
记录个人学习golang路线（如何学习golang，如何转golang）

记录个人学习golang路线（如何学习golang，如何转golang）

最近好久没更&#xff0c;在看兔兔的博客&#xff0c;学习golang&#xff0c;兔兔的文章&#xff0c;有一定的编程经验 && 初学golang者&#xff0c;一定要看&#xff0c;如果是其他语言转golang&#xff0c;那就必须要看了&#xff0c;可以帮助你了解golang的语法&…
阅读更多...
BC40056 Imports“SolidWorks.Interop.swconst”中指定的命名空间或类型不包含任何公共成员

BC40056 Imports“SolidWorks.Interop.swconst”中指定的命名空间或类型不包含任何公共成员

BC40056 Imports“SolidWorks.Interop.swconst”中指定的命名空间或类型不包含任何公共成员&#xff0c;或者找不到该命名空间或类型。 问题描述原因分析 解决办法 ) 问题描述 严重性 代码 说明 项目 文件 行 警告 BC40056 Imports“SolidWorks.Interop.swconst”中指定的命名…
阅读更多...
单链表就地逆置

单链表就地逆置

算法思想&#xff1a;构建一个带头结点的单链表L&#xff0c;然后访问链表中的每一个数据结点&#xff0c;将访问到的数据结点依此插入到L的头节点之后。 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef s…
阅读更多...
ElasticSearch开发指北和场景题分析

ElasticSearch开发指北和场景题分析

前言 本篇是ES系列的第二篇&#xff0c;继上次的理论篇ElasticSearch理论体系构建后&#xff0c;带来了实战篇。实战篇来自于我对常见操作以及场景的分析总结&#xff0c;详细到每个步骤和理由&#xff0c;下一篇将是性能优化篇。 常用操作 以下操作均使用ES的API进行展示&a…
阅读更多...
金融投贷通--功能测试分析与设计

金融投贷通--功能测试分析与设计

金融投贷通功能测试分析与设计 测试点分析借款业务测试点投资业务测试点 测试用例借款业务测试用例投资业务测试用例 缺陷面试题 测试报告 测试点分析 借款业务测试点 投资业务测试点 测试用例 借款业务测试用例 借款成功&#xff08;主业务&#xff09;、借款成功&#xff…
阅读更多...
Figma：如何在数据库规模四年增长近100倍的挑战中“活”下来？

Figma：如何在数据库规模四年增长近100倍的挑战中“活”下来？

在当今数字化飞速发展的时代&#xff0c;大数据的崛起已成为各行业不可或缺的重要驱动力。然而&#xff0c;随着数据量的激增&#xff0c;许多企业面临着巨大的挑战&#xff0c;尤其是在数据库管理和维护方面。Figma作为一家专注于设计协作领域的领先企业&#xff0c;在过去的四…
阅读更多...
Tron波场区块链 | 使用Java将Tron钱包助记词转私钥 全网独门一份

Tron波场区块链 | 使用Java将Tron钱包助记词转私钥 全网独门一份

如何使用Java将Tron钱包助记词转换为私钥? 本来想着这个问题挺简单&#xff0c;可是查了半天&#xff0c;不是&#xff0c;不止半天查了好长时间&#xff0c;看了半天官网文档&#xff0c;全网Java就没有实现的。 咋办。。。咋办呢&#xff1f; 好巧&#xff0c;官网我看到…
阅读更多...
瑞吉外卖实战学习--5、新增员工功能

瑞吉外卖实战学习--5、新增员工功能

新增员工功能 效果图1、开发流程2、页面发送ajax请求，将新增员工的信息以json的形式提交给服务器2.1、在填写信息的时候会发现身份校验比较麻烦，可以在validate中将全局的校验方式去掉，方便填写2.3、看到接口未employee2.4、前端代码分析3、服务器接收到提交的数据并调用ser…
阅读更多...
Kotlin 中的类和构造方法

Kotlin 中的类和构造方法

Kotlin 中的类与接口和 Java 中的类与接口还是有区别的。例如&#xff0c;Koltin 中的接口可以包含属性声明&#xff0c;与 Java 不同的是。Kotlin 的声明默认是 final 和 public 的。此外&#xff0c;嵌套的类默认并不是内部类&#xff1a;它们并没有包含对其它外部类的隐式引…
阅读更多...
【系统架构师】-第18章-安全架构设计

【系统架构师】-第18章-安全架构设计

(1)信息泄露&#xff1a;信息被泄露或透露给某个非授权的实体。 (2)破坏信息的完整性&#xff1a;数据被非授权地进行增删、修改或破坏而受到损失。 (3)拒绝服务&#xff1a;对信息或其他资源的合法访问被无条件地阻止。 (4)非法使用(非授权访问):某一资源被某个非授权的人或…
阅读更多...
第十五届蓝桥杯模拟考试II_物联网设计

第十五届蓝桥杯模拟考试II_物联网设计

反思&#xff1a; 本次模拟让我惊醒&#xff0c;写这个作品如同搭积木&#xff0c;在拼接的时候都要仔细检查这个积木是否出bug,确保没有问题再将其拼接到之前搭好的大模块之中&#xff0c;因为就是这样的题目我在处理过程中就遇到了BUG&#xff0c;原因竟出在输入模式要上拉&…
阅读更多...
二十四种设计模式与六大设计原则（二）：【门面模式、适配器模式、模板方法模式、建造者模式、桥梁模式、命令模式】的定义、举例说明、核心思想、适用场景和优缺点

二十四种设计模式与六大设计原则（二）：【门面模式、适配器模式、模板方法模式、建造者模式、桥梁模式、命令模式】的定义、举例说明、核心思想、适用场景和优缺点

接上次博客&#xff1a;二十四种设计模式与六大设计原则&#xff08;一&#xff09;&#xff1a;【策略模式、代理模式、单例模式、多例模式、工厂方法模式、抽象工厂模式】的定义、举例说明、核心思想、适用场景和优缺点-CSDN博客 目录 门面模式【Facade Pattern】 定义 举…
阅读更多...
Arthas线上排查问题流程

Arthas线上排查问题流程

入门文档&#xff1a;trace | arthas 1、jar下载和启动 连接curl -O https://arthas.aliyun.com/arthas-boot.jar【wget https://arthas.aliyun.com/arthas-boot.jar】 。.../jdk/bin/java -jar arthas-boot.jar 22336【最好在这个目录启动,port可选】 选择进程序号 enter回车…
阅读更多...
二分（二段性）

二分（二段性）

本文用于记录个人算法竞赛学习&#xff0c;仅供参考 一.二分算法 二分算法一般用于具有二段性的问题&#xff0c;数据不一定具有单调性&#xff0c;所以单调可二分&#xff0c;可二分不一定就要单调。 二.整数二分 1. 模板一&#xff1a;将区间[l, r]划分为[l, mid] 和 [mid…
阅读更多...
学生价，leetcode会员购买分析

学生价，leetcode会员购买分析

最近想要购买leetcode会员&#xff0c;但不知道买啥好&#xff0c;打算用python可视化数据进行一个简单的分析 具体数据如下 curve 1: 首两月79元每月&#xff0c;后续连续包月59curve 2: 90天199curve 3: 365天365&#xff08;学生认证&#xff09; 这么看&#xff0c;数据…
阅读更多...
FA模型切换Stage模型组件切换之ServiceAbility切换DataAbility切换

FA模型切换Stage模型组件切换之ServiceAbility切换DataAbility切换

ServiceAbility切换 FA模型中的ServiceAbility对应Stage模型中的ServiceExtensionAbility。Stage模型下的ServiceExtensionAbility为系统API&#xff0c;只有系统应用才可以创建。因此&#xff0c;FA模型的ServiceAbility的切换&#xff0c;对于系统应用和三方应用策略有所不同…
阅读更多...
AI制作一键生成模特换装照，电商蓝海副业供不应求

AI制作一键生成模特换装照，电商蓝海副业供不应求

在电子商务领域&#xff0c;产品展示和模特试穿照片是至关重要的。在传统流程中&#xff0c;创建一张精美的商品主图通常需要摄影师在摄影棚里进行白底拍摄&#xff0c;接着设计师会进行图像设计处理。 公 重 号&#xff1a;老A程序站 对于更复杂且高端的商品展示&#xff0c…
阅读更多...
最新文章

Copyright @ 2022~2023