動態規劃學習——回文子串系列問題【C++】

一，回文子串

題目鏈接：LCR 020. 回文子串 - 力扣（LeetCode）

?【問題描述】

求一個字符串中有多少個回文子串，其中一個字符也算是一個回文子串。

【解法】

動態規劃

求一個字符串中回文子串的個數，我么可以找到每個回文子串，然后統計個數即可。

首先定義狀態表示：

dp[i]：表示子串[i-j]，是否是回文串。其中下標i<=j。

狀態轉移方程的推導：

當s[i]!=s[j]時，也就是子串的第一個字符和最后一個字符不相等，那么肯定不是回文串，所以dp[i][j]=false。

當s[i]==s[j]時，在該情況下，又細分三種情況：

  • 如果i==j，那么該子串就是一個字符，是回文串，所以dp[i][j]=true。
  • 如果i+1==j，也就是該字符串由兩個字符構成，且s[i]==s[j]，是回文串，所以dp[i][j]=true。
  • 如果i+1<j，表示s[i]和s[j]中還有一些字符，那么dp[i][j]=dp[i+1][j-1]。

初始化dp表時，根據狀態表示的定義，我們只會用到dp表主對角線的右上部分，左下部分不會用到，對于狀態轉移dp[i][j]=dp[i+1][j-1]，我們不需要考慮越界的問題，因為前兩種情況已經做了判斷。

?最后，只需統計dp表中dp[i][j]==true的數量即可。

【代碼】

class Solution {
public:int countSubstrings(string s) {//dp[i]:子串[i-j]是否是回文串int n=s.size();int sum=0;//統計結果vector<vector<bool>> dp(n,vector<bool>(n,false));for(int i=n-1;i>=0;i--)for(int j=i;j<n;j++){if(s[i]!=s[j]){dp[i][j]=false;}else{dp[i][j]=i+1<j?dp[i+1][j-1]:true;}if(dp[i][j])sum++;}return sum;}
};

時間復雜度O(N^2），空間復雜度O(N^2）?

二，最長回文子串

題目鏈接：5. 最長回文子串 - 力扣（LeetCode）

【題目描述】

?求字符串中最長的回文子串。

【解法1】

動態規劃

上一題是求回文子串的個數，我們用一個dp表來表示【i-j】是否是回文串。

本題可以直接使用上題 的思路，如果dp[i][j]是回文串，也就是dp[i][j]==true，那么看看該子串的長度是否是最大的，該子串的長度是j-i+1。可以使用一個變量len來記錄最長的回文子串的長度，begin來記錄該回文串的開始位置i。最后使用substr就可以獲取到該子串。

【代碼】

class Solution {
public:string longestPalindrome(string s) {int n=s.size();vector<vector<bool>> dp(n,vector<bool>(n));int len=0,begin=0;for(int i=n-1;i>=0;i--)for(int j=i;j<n;j++){if(s[i]==s[j])dp[i][j]=i+1<j?dp[i+1][j-1]:true;if(dp[i][j]){if(len<j-i+1){len=j-i+1;begin=i;}}}return s.substr(begin,len);}
};

時間復雜度：O(N^2），空間復雜度O(N^2)

【解法2】

中心擴展算法

求最長的回文子串。我們可以從一個字符出發，求出它作為中心所能形成的最長回文串的長度。

用一個變量i來記錄遍歷到字符串的哪一個為位置。

每遍歷到一個位置，向兩邊擴展，用兩個變量left和right來記錄擴展位置的下標。

回文子串的長度可能是奇數，也可能是偶數，所以需要計算兩次：

1，回文子串的長度是奇數，讓left=i-1，right=i+1，向兩邊擴展，如果s[left]==s[right]，

left--，right++。最后回文子串的長度就是right-left-1。

2，回文子串的長度是偶數，讓left=i-1，right=i（left=i，right=i+1也可以），同理，如果s[left]==s[right]，left--,right++。最后回文子串的長度就是right-left-1。

記錄這兩種情況下回文子串最長的長度，以及該回文子串開始的下標。

【代碼】

class Solution {
public:string longestPalindrome(string s) {int n=s.size();int begin=0,len=0;for(int i=0;i<n;i++){//奇數擴展int left=i,right=i;while(left>=0&&right<n&&s[left]==s[right]){left--;right++;}if(len<right-left-1){len=right-left-1;begin=left+1;}//偶數擴展left=i-1,right=i;while(left>=0&&right<n&&s[left]==s[right]){left--;right++;}if(len<right-left-1){len=right-left-1;begin=left+1;}}return s.substr(begin,len);}
};

時間復雜度O(N)，空間復雜度O(1)?

三，回文串分割IV

題目鏈接：1745. 分割回文串 IV - 力扣（LeetCode）

?【題目描述】

對于一個字符串，將他分為任意的三個子串，如果存在這三個子串都是回文串，返回true，否則返回false

【解法】

將一個字符串分割成三個子串，可以想象成在一個字符串中，切兩刀，分成三部分，而這兩“刀”就是下標，我們用下標i,j將字符串分成三個部分，[0,i-1]，[i,j]，[j+1,n-1]，n為字符串長度。

所以只需判斷這三個子串是否是回文串即可。而在第一道題中我們使用一個dp表來表示[i-j]子串是否是回文串。所以，在本題中，我們可以使用dp表來做預處理，然后枚舉這三個子串：

[0,i-1]，[i,j]，[j,n-1]，判斷這三個子串是否是回文串。

【代碼】

class Solution {
public:bool checkPartitioning(string s) {//dp表存儲回文信息【i,j】int n=s.size();vector<vector<bool>> dp(n,vector<bool>(n));for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(s[i]==s[j])dp[i][j]=i+1<j?dp[i+1][j-1]:true;}}for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(dp[i][j]&&i-1>=0&&j+1<n)if(dp[0][i-1]&&dp[j+1][n-1])return true;}return false;}
};

四，回文串分割II

題目鏈接：LCR 094. 分割回文串 II - 力扣（LeetCode）

【解法】

動態規劃

首先定義狀態表示：

dp[i]：表示【0-i】區間的子串，最少的切割次數。

狀態轉移方程的推導：

如果子串【0-i】本身就是回文串，就不需要切割，即dp[i]=0.

如果子串【0-i】不是回文串，需要切割，我們可以枚舉切割的位置j，0<j<=i。其中不用枚舉j=0，因為j=0，也就是【0-i】區間。j從i開始枚舉，接下來判斷【j-i】是否是回文串：

  • 如果【j-i】是回文串，那么就找到了一個分割點，dp[i]就等于【0，j-1】區間的最少分割次數+1，
  • 即dp[i]=dp[j-1]+1。
  • 如果【j-i】不是回文串，就不是一個分割點，繼續找分割點。

其中求的是最少的分割次數，所以

dp[i]=min(dp[i],dp[j-1]+1)。

上面的過程 中，會一直判斷某一段區間是否是回文串，所以可以用第一道題的思路，用一張表來記錄區間【i-j】是否是回文串。

初始化dp表：

不用判斷數組越界的問題，因為j是大于0的。

由于求的是最小值，所以不能將數組的初始值設為0，會影響最終結果。需要設為無窮大。

【代碼】

class Solution {
public:int minCut(string s) {int n=s.size();//i-j區間是否是回文串vector<vector<bool>> isPal(n,vector<bool>(n,false));for(int i=n-1;i>=0;i--)for(int j=i;j<n;j++){if(s[i]!=s[j]){isPal[i][j]=false;}else{isPal[i][j]=i+1<j?isPal[i+1][j-1]:true;}}//0-i區間最少分割次數vector<int> dp(n,INT_MAX);for(int i=0;i<n;i++){//0-i是回文串if(isPal[0][i]){dp[i]=0;continue;}//枚舉分割點，求最少分割次數for(int j=i;j>0;j--){//j-i是回文串if(isPal[j][i]){dp[i]=min(dp[i],dp[j-1]+1);}}}return dp[n-1];}
};

?時間復雜度O(N^2)，空間復雜度O(N^2)

五，最長回文子序列

題目鏈接：516. 最長回文子序列 - 力扣（LeetCode）

【題目描述】

本題與上面的題不同，本題是求最長的回文子序列的長度，子序列是指元素可以不連續，而前面的子串問題，都是要求元素是連續的。

?【解法】

按照常規的思路，我們會定義如下的狀態方程：
dp[i]：表示以第i個元素為結尾的所有子序列中，最長的回文子序列的長度。

要想推導dp[i]，一定會與dp[i-1]，dp[i-2]，dp[i-3]......有關，因為是子序列問題，第i個字符可以拼接到第i-1個字符的后面，也可以拼接到第i個字符的后面......所以會需要前面的dp值來更新dp[i]的值。比如需要通過dp[i-1]來推導dp[i]的值，但是dp[i-1]表示的以第i-1個元素為結尾的最長回文子序列的長度，我們將第i個元素拼接到第i-1個元素的后面，無法判斷拼接后的子序列是否是回文串，所以無法推導，所以這樣的狀態表示是不行的。

在“回文子串”題中，我們判斷一段區間【i-j】是否是回文串，對于這段區間，我們只關心兩個端點的狀態，也就是s[i]和s[j]的關系。本題也類似。

首先定義狀態標識：

dp[i][j]：表示【i-j】區間中最長的回文子序列的長度。

狀態轉移方程的推導：

【i? ? ?i+1? ? ? ?j-1? ? j】? ??

如果s[i]==s[j]，有三種情況：

  • i==j，表示一個字符，是回文串，長度為1，所以dp[i]=1。
  • i+1==j，表示兩個 字符相鄰并且相等，那么回文串的長度就是2，即dp[i]=2。
  • i+1<j，表示i和j之間還有其他字符，我們需要求出區間【i+1,j-1】的最長回文子序列的長度，然后再在前面和后面分別拼上s[i]和s[j]即可。所以dp[i]=dp[i+1][j-1]+2。

如果s[i]!=s[j]：

從整體上來看這整個區間【i-j】，【i-j】的回文子序列包含兩部分：

【i,j-1】的回文子序列和【i+1,j】的子序列。所以dp[i][j]=max(dp[i][j-1],dp[i+1][j])。

初始化dp表示：

只需關心dp[i][j]=max(dp[i][j-1],dp[i+1][j])這個表達式中的每一項是否會越界。

前提條件還是i<j，也就是我們只會用到dp表主對角線的右上部分。

而dp[i][j]的更新會用到左邊和下邊的值：

可以發現，這兩個位置其實是主對角線上的元素，滿足i==j，而這種情況我們在前面已經判斷過了，所以不需要初始化。

?

class Solution {
public:int longestPalindromeSubseq(string s) {int n=s.size();//i-j區間的最長回文子序列vector<vector<int>> dp(n,vector<int>(n,0));for(int i=n-1;i>=0;i--)for(int j=i;j<n;j++){if(s[i]==s[j]){if(i==j)dp[i][j]=1;else if(i+1==j)dp[i][j]=2;elsedp[i][j]=dp[i+1][j-1]+2;}else{dp[i][j]=max(dp[i][j-1],dp[i+1][j]);}}return dp[0][n-1];}
};

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/74263.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/74263.shtml
英文地址，請注明出處：http://en.pswp.cn/web/74263.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

My first day in QT programming

My first day in QT programming

My first QT code this->setWindowTitle("HelloWorld"); //設置窗口名稱 this->resize(400, 300); //設置窗口大小 QPushButton* btn new QPushButton; //新建按鈕組件 btn->setParent(this); //為按鈕指定父對象 …
閱讀更多...
基于python開發的郵箱合并群發工具

基于python開發的郵箱合并群發工具

智能郵件群發系統 一個基于Python和PyQt5開發的智能郵件群發工具&#xff0c;支持Word模板和Excel數據源的自動匹配&#xff0c;具有現代化UI界面和友好的用戶體驗。 Github項目地址&#xff1a;https://github.com/liugang926/Auto-mail-sent.git dist目錄有編譯好的exe程序&…
閱讀更多...
大模型-提示詞（Prompt）技巧

大模型-提示詞（Prompt）技巧

1、什么是提示詞&#xff1f; 提示詞&#xff08;Prompt&#xff09;是用戶發送給大語言模型的問題、指令或請求&#xff0c;用來明確地告訴模型用戶想要解決的問題或完成的任務&#xff0c;是大語言模型理解用戶需求并據此生成相關、準確回答或內容的基礎。對于大語言模型來說…
閱讀更多...
Android開發：support.v4包與AndroidX

Android開發：support.v4包與AndroidX

Android中的support.v4包與AndroidX support.v4包概述 Android Support Library中的android.support.v4包是Google為保持Android應用向后兼容而提供的重要支持庫集合。它主要解決以下問題&#xff1a; API版本兼容&#xff1a;讓新版API能在舊版Android系統上使用功能增強&a…
閱讀更多...
TCP-IP模型

TCP-IP模型

書接上回&#xff08;OSI通信模型&#xff09; TCP-IP協議結構 &#xff08;略講&#xff09; ARP&#xff1a;IP-->MAC RARP&#xff1a;MAC-->IP ICMP&#xff1a;控制報文信息協議&#xff0c;主要是涉及到主機就去連接路由器時控制傳輸報文&#xff08…
閱讀更多...
雪花算法生成的主鍵存在哪些問題，為什么不能使用自增ID或者UUID做MySQL的主鍵

雪花算法生成的主鍵存在哪些問題，為什么不能使用自增ID或者UUID做MySQL的主鍵

MySQL 分布式架構中的主鍵選擇&#xff1a;自增ID、UUID與雪花算法 為什么MySQL分布式架構中不能使用自增主鍵&#xff1f; 在分布式架構中&#xff0c;自增主鍵存在以下問題&#xff1a; 主鍵沖突風險&#xff1a;多個數據庫實例同時生成自增主鍵會導致ID重復分片不均勻&am…
閱讀更多...
RapidJSON 處理 JSON（高性能 C++ 庫）（四）

RapidJSON 處理 JSON（高性能 C++ 庫）（四）

第四部分：RapidJSON 處理 JSON（高性能 C++ 庫） ?? 快速掌握 JSON！文章 + 視頻雙管齊下 ?? 如果你覺得閱讀文章太慢，或者更喜歡 邊看邊學 的方式，不妨直接觀看我錄制的 RapidJSON 課程視頻！?? 視頻里會用更直觀的方式講解 RapidJSON 的核心概念、實戰技巧，并配有…
閱讀更多...
chromem-go + ollama + bge-m3 進行文檔向量嵌入和查詢

chromem-go + ollama + bge-m3 進行文檔向量嵌入和查詢

Ollama 安裝 https://ollama.com/download Ollama 運行嵌入模型 bge-m3:latest ollama run bge-m3:latestchromem-go 文檔嵌入和查詢 package mainimport ("context""fmt""runtime""github.com/philippgille/chromem-go" )func ma…
閱讀更多...
【LeetCode 題解】數據庫：180. 連續出現的數字

【LeetCode 題解】數據庫：180. 連續出現的數字

一、問題描述 給定一個Logs表&#xff0c;包含自增 ID 和數字字段&#xff1a; CREATE TABLE Logs (id INT PRIMARY KEY AUTO_INCREMENT,num VARCHAR(50) );要求編寫 SQL 查詢&#xff0c;找出所有至少連續出現三次的數字。例如&#xff1a; --------- | id | num | -------…
閱讀更多...
MaxEnt模型進階：基于R語言自動化與GIS空間建模的物種棲息地精準預測

MaxEnt模型進階：基于R語言自動化與GIS空間建模的物種棲息地精準預測

生物多樣性的空間分布規律及其對環境變化的響應機制&#xff0c;是生態學與地理學研究的前沿議題。在氣候變化加劇和人類活動干擾的雙重壓力下&#xff0c;如何精準預測物種潛在分布范圍、識別關鍵環境驅動因子&#xff0c;已成為制定生物保護策略的核心科學問題。物種分布模型…
閱讀更多...
緩存雪崩解決方案：二級緩存VS隨機TTL

緩存雪崩解決方案：二級緩存VS隨機TTL

背景 在學習緩存雪崩的時候&#xff0c;了解到有二級緩存和隨機TTL兩個解決方案&#xff0c;但是在學習之后&#xff0c;個人認為二級緩存本質上還是利用兩層緩存的過期時間不一致來實現緩存過期時間隨機化&#xff0c;這不就是和隨機TTL一樣嗎&#xff0c;故有了這篇思考&…
閱讀更多...
Android View事件分發機制深度解析

Android View事件分發機制深度解析

在Android面試中&#xff0c;關于View事件分發機制的考察往往不僅限于基礎流程&#xff0c;更關注底層原理、性能優化和實際應用場景。以下是針對面試的全面回答策略&#xff1a; 一、基礎回答框架 核心三要素&#xff1a; 傳遞流程 "事件分發遵循Activity → Window →…
閱讀更多...
2829. k-avoiding 數組的最小總和

2829. k-avoiding 數組的最小總和

2829. k-avoiding 數組的最小總和 題目鏈接&#xff1a;2829. k-avoiding 數組的最小總和 代碼如下&#xff1a; class Solution { public:int minimumSum(int n, int k) {int m min(k / 2, n);return (m * (m 1) (k * 2 n - m - 1) * (n - m)) / 2;} };
閱讀更多...
phpStorm2021.3.3在windows系統上配置Xdebug調試

phpStorm2021.3.3在windows系統上配置Xdebug調試

開始 首先根據PHP的版本下載并安裝對應的Xdebug擴展在phpStorm工具中找到設置添加服務添加php web page配置完信息后 首先根據PHP的版本下載并安裝對應的Xdebug擴展 我使用的是phpStudy工具&#xff0c;直接在php對應的版本中開啟xdebug擴展&#xff0c; 并在php.ini中添加如下…
閱讀更多...
LabVIEW永磁同步電機性能測試系統

LabVIEW永磁同步電機性能測試系統

開發了一種基于LabVIEW的永磁同步電機&#xff08;PMSM&#xff09;性能測試系統的設計及應用。該系統針對新能源汽車使用的電機進行穩態性能測試&#xff0c;解決了傳統測試方法成本高、效率低的問題&#xff0c;實現了測試自動化&#xff0c;提高了數據的準確性和客觀性。 ?…
閱讀更多...
谷粒商城：Redisson

谷粒商城：Redisson

目錄 Redisson 整合Redisson RLock RReadWriteLock RSemaphore RCountDownLatch 優化三級分類緩存 緩存一致性問題 雙寫模式 失效模式 臟數據解決 Redisson 提供redis分布式鎖&#xff08;Distributed locks with Redis&#xff09;的java客戶端 整合Redisson 引入 …
閱讀更多...
Linux系統調用編程

Linux系統調用編程

目錄 一. 理解進程和線程的概念。并在Linux系統下進行相應操作 1.1概念 1.1.1進程(Process) 1.1.2 線程(Thread) 1.2操作 1.2.1用 ps -a 命令查看系統中各進程的編號pid 1.2.2用kill 命令終止一個進程pid 二. 解釋Linux的“虛擬內存管理”&#xff0c;它與stm32中的 真…
閱讀更多...
25-智慧旅游系統（協同算法）三端

25-智慧旅游系統（協同算法）三端

介紹 技術&#xff1a; 基于 B/S 架構 SpringBootMySQLLayuivue 環境&#xff1a; Idea mysql maven jdk1.8 node 管理端功能 首頁展示圖表&#xff1a;以數據可視化方式展示關鍵業務數據。 用戶管理&#xff1a;管理系統用戶&#xff0c;包括查看、編輯等操作。 供應商管…
閱讀更多...
【stm32--HAL庫DMA+USART+空閑中斷不定長收發數據】

【stm32--HAL庫DMA+USART+空閑中斷不定長收發數據】

串口通信-Hal庫實現不定長度收發&#xff0c;DMAUSART DMA串口STM32CUBEMX配置&#xff08;工程創建&#xff09;基礎配置時鐘配置工程配置 代碼編寫現象 DMA 在正式配置之前&#xff0c;我們先來一起簡單了解一下DMA。DMA&#xff08;Direct Memory Access&#xff0c;直接內…
閱讀更多...
沉浸式體驗測評｜AI Ville：我在Web3小鎮“生活”了一周

沉浸式體驗測評｜AI Ville：我在Web3小鎮“生活”了一周

最近&#xff0c;我在朋友的推薦下&#xff0c;體驗了 aivillebot 的項目。起初&#xff0c;我只是抱著試試看的心態&#xff0c;心想這不就是個 Web3 版的《星露谷物語》嗎&#xff1f; 但是一周下來&#xff0c;我發現這個虛擬小鎮也沒那么簡單——里面的居民不是目前端游或鏈…
閱讀更多...
最新文章

Copyright @ 2022~2023