#leetcode刷題之路5-最長迴文子串

来源:https://www.cnblogs.com/biat/archive/2019/02/26/10440644.html
-Advertisement-
Play Games

給定一個字元串 s,找到 s 中最長的迴文子串。你可以假設 s 的最大長度為 1000。 示例 1:輸入: "babad"輸出: "bab"註意: "aba" 也是一個有效答案。 示例 2:輸入: "cbbd"輸出: "bb" 思路一:暴力法,不說了 思路二:動態規劃 參考官方給的思路: How c ...


給定一個字元串 s,找到 s 中最長的迴文子串。你可以假設 s 的最大長度為 1000。

示例 1:
輸入: "babad"
輸出: "bab"
註意: "aba" 也是一個有效答案。

示例 2:
輸入: "cbbd"
輸出: "bb"

思路一:暴力法,不說了

思路二:動態規劃

參考官方給的思路:

How can we reuse a previously computed palindrome to compute a larger palindrome?
If “aba” is a palindrome, is “xabax” and palindrome? Similarly is “xabay” a palindrome?
Complexity based hint:
If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.

#include <iostream>
#include <vector>
using namespace std;

string longestPalindrome(string s) {
    int len=s.length();
    //std::cout << "len="<<len<< std::endl;
    int num=1;//記錄長度
    int flag=0;//記錄起始位置
    if(len==0) return "";
    if(len==1) return s;    //字元串只有一個的話返回那一個字元
    vector< vector<int> > palindrome(len,vector<int>(len));//用於存儲迴文信息,全部初始為0
    //int *palindrome=new int[len][len];
    //首先這裡考慮如果整個字元串都沒有迴文序列,那麼就返回任意一個符號,如果有兩個挨著的字元相同,那麼就返回其中一組
    for(int i=0;i<len;i++)
    {
        palindrome[i][i]=1;
        if((i<len-1)&&s[i]==s[i+1])
        {
            palindrome[i][i+1]=1;
            num=2;
            flag=i;
        }
    }
    for (int new_num = 3; new_num <= len; new_num++)//接著從3開始設置子串的長度
    {
        for (int j = 0; j+new_num-1 < len; j++)//枚舉子串的起始點
        {
            if (s[j] == s[j+new_num-1] && palindrome[j+1][j+new_num-1-1]==1)//有點遞歸的感覺
            {
                palindrome[j][j+new_num-1] = 1;
                flag=j;
                num = new_num;
            }
        }
    }
    return s.substr(flag,num);

}

int main() {
    std::string s="ac";
    string ss=longestPalindrome(s);
    std::cout << ss << std::endl;
    return 0;
}

 C++二維數組動態申請記憶體

 

 

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 一、綜述 類是我們自己定義的數據類型(新類型) 設計類時要考慮的角度: (1)站在設計和實現者的角度來考慮 (2)站在使用者的角度來考慮 (3)父類,子類 二、類基礎 (1)一個類就是一個用戶自己定義的數據類型,把類可以想象為一個命名空間,包著一堆東西(成員函數,成員變數)。 (2)一個類的構成:成 ...
  • 人生苦短,我用 Python —— Life is short, you need Python 目標 Python 的起源 Python 解釋器 是用 C 語言實現的,並能夠調用 C 語言的庫文件. Python(蟒蛇) 為什麼要用 Python? Python 的特點 Python 是完全面向對 ...
  • 策略模式 雖然我本人比較討厭一些很官方的術語定義,因為我經常弄不明白有些定義講了個啥,但是為了讓這篇博文顯得不那麼輕浮,所以我也就不能免俗的先將設計模式之策略模式的定義首先丟到各位看官面前。 策略模式定義了演算法族,分別封裝起來,讓他們之間可以互相替換,此模式讓演算法的變化獨立於使用演算法的客戶。 第一眼 ...
  • 開學兩天,身上的職責直接變為兩個班班長,三個小組組長,哇這事情估計夠我忙活了,想躲都躲不掉啊,看來我還是真招人推薦各種管理職務啊,以後要是有人推薦我當經理啊領導啊該多好哈哈哈哈。記得今天奶奶生日,很開心地給奶奶打了一通電話,這怕是我第一次給奶奶電話送生日祝福了哈哈哈,是啊,很想珍惜身邊的人,但很多時 ...
  • 導師359213571如果你是剛剛玩,我來教教你,如果你已經玩很久了,卻不穩,我來拉拉你,如果你已經遍體鱗傷,我來幫幫你. 我不能保證你一夜致富但希望能細水長流,匯聚江海,先要平穩的心態,不要一盤的失誤影響你心情。 自己有規劃性和目標性。做到這兩點,過來找我我來幫你。 1、死跟計劃。現在很多群里都有 ...
  • Java基礎知識篇 面向對象和麵向過程的區別 面向過程: 優點:性能比面向對象高,因為類調用時需要實例化,開銷比較大,比較消耗資源;比如單片機、嵌入式開發、Linux/Unix等一般採用面向過程開發,性能是最重要的因素。 缺點:沒有面向對象易維護、易復用、易擴展 面向對象: 優點:易維護、易復用、易 ...
  • 導師359213571如果你是剛剛玩,我來教教你,如果你已經玩很久了,卻不穩,我來拉拉你,如果你已經遍體鱗傷,我來幫幫你. 我不能保證你一夜致富但希望能細水長流,匯聚江海,先要平穩的心態,不要一盤的失誤影響你心情。 自己有規劃性和目標性。做到這兩點,過來找我我來幫你。 1、死跟計劃。現在很多群里都有 ...
  • 導師3592135711、死跟計劃。現在很多群里都有計劃,大家都在跟計劃,一起交流但計劃只是一款軟體經過某種運算得出來的數,但大家都在跟計劃,為什麼有的人贏了,有的人輸了,這就是要會跟計劃,計劃不能盲目跟從。不能每期都買,不能每期都跟,每期都跟計劃的,跟的越緊死得越快!切記!不存在一款也已預測未來的 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...