亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

Java?C++題解leetcode字符串輪轉(zhuǎn)KMP算法詳解

 更新時(shí)間：2022年09月29日 15:51:44   作者：AnjaVon  
這篇文章主要為大家介紹了Java?C++題解leetcode字符串輪轉(zhuǎn)KMP算法詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目要求

思路一：雙指針（模擬）

Java

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if (s1.length() != s2.length())
            return false;
        int n = s1.length();
        if (n == 0)
            return true;
        for (int i = 0; i < n; i++) {
            boolean res = true;
            for (int j = 0; j < n; j++) {
                if (s1.charAt((i + j) % n) != s2.charAt(j)) {
                    res = false;
                    break;
                }
            }
            if (res)
                return true;
        }
        return false;
    }
}
  • 時(shí)間復(fù)雜度：O(n^2)
  • 空間復(fù)雜度：O(1)

C++

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        if (s1.size() != s2.size())
            return false;
        int n = s1.size();
        if (n == 0)
            return true;
        for (int i = 0; i < n; i++) {
            bool res = true;
            for (int j = 0; j < n; j++) {
                if (s1[(i + j) % n] != s2[j]) {
                    res = false;
                    break;
                }
            }
            if (res)
                return true;
        }
        return false;
    }
};
  • 時(shí)間復(fù)雜度：O(n^2)
  • 空間復(fù)雜度：O(1)

思路二：子串

手寫KMP

KMP的思路可以參考KMP 算法詳解和詳解KMP算法

Java

get_next

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if (s1.length() != s2.length())
            return false;
        int n = s1.length();
        if (n == 0)
            return true;
        int[] nxt = new int[n];
        nxt[0] = -1;
        int j = 0; // pat指針
        int k = -1; // 跳轉(zhuǎn)位置
        while (j &lt; n - 1) {
            if (k == -1 || s2.charAt(j) == s2.charAt(k)) {
                if (s2.charAt(++j) == s2.charAt(++k))
                    nxt[j] = nxt[k]; // 連續(xù)相同
                else
                    nxt[j] = k;
            }
            else
                k = nxt[k];
        }
        String txt = s1 + s1;
        j = 0;
        for (int i = 0; i &lt; 2 * n; i++) {
            if (j &lt; n &amp;&amp; txt.charAt(i) == s2.charAt(j))
                j++;
            else {
                j = nxt[j];
                if (j == -1)
                    j++;
            }
            if (j == n)
                return true;
        }
        return false;
    }
}

dp

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if (s1.length() != s2.length())
            return false;
        int n = s1.length();
        if (n == 0)
            return true;
        int[][] dp = new int[n][256]; // dp[state][char] = nxt state
        dp[0][s2.charAt(0)] = 1;
        int x = 0; // 影子狀態(tài)
        for (int s = 1; s < n; s++) {
            for (int c = 0; c < 256; c++)
                dp[s][c] = dp[x][c];
            dp[s][s2.charAt(s)] = s + 1;
            x = dp[x][s2.charAt(s)];
        }
        String txt = s1 + s1;
        int state = 0;
        for (int i = 0; i < 2 * n; i++) {
            state = dp[state][txt.charAt(i)];
            if (state == n)
                return true;
        }
        return false;
    }
}
  • 時(shí)間復(fù)雜度：O(n)
  • 空間復(fù)雜度：O(n)

C++

get_next

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        if (s1.size() != s2.size())
            return false;
        int n = s1.size();
        if (n == 0)
            return true;
        int nxt[n];
        nxt[0] = -1;
        int j = 0; // pat指針
        int k = -1; // 跳轉(zhuǎn)位置
        while (j < n - 1) {
            if (k == -1 || s2[j] == s2[k]) {
                if (s2[++j] == s2[++k])
                    nxt[j] = nxt[k]; // 連續(xù)相同
                else
                    nxt[j] = k;
            }
            else
                k = nxt[k];
        }
        string txt = s1 + s1;
        j = 0;
        for (int i = 0; i < 2 * n; i++) {
            if (j < n && txt[i] == s2[j])
                j++;
            else {
                j = nxt[j];
                if (j == -1)
                    j++;
            }
            if (j == n)
                return true;
        }
        return false;
    }
};

dp

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        if (s1.size() != s2.size())
            return false;
        int n = s1.size();
        if (n == 0)
            return true;
        int dp[n][256]; // dp[state][char] = nxt state
        memset(dp, 0, sizeof(dp));
        dp[0][s2[0]] = 1;
        int x = 0; // 影子狀態(tài)
        for (int s = 1; s < n; s++) {
            for (int c = 0; c < 256; c++)
                dp[s][c] = dp[x][c];
            dp[s][s2[s]] = s + 1;
            x = dp[x][s2[s]];
        }
        string txt = s1 + s1;
        int state = 0;
        for (int i = 0; i < 2 * n; i++) {
            state = dp[state][txt[i]];
            if (state == n)
                return true;
        }
        return false;
    }
};
  • 時(shí)間復(fù)雜度：O(n)
  • 空間復(fù)雜度：O(n)

調(diào)API

Java

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        return s1.length() == s2.length() && (s1 + s1).contains(s2);
    }
}
  • 時(shí)間復(fù)雜度：O(n)，取決于語(yǔ)言匹配子字符串機(jī)制
  • 空間復(fù)雜度：O(n)

C++

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        return s1.size() == s2.size() && (s1 + s1).find(s2) != string::npos;
    }
};
  • 時(shí)間復(fù)雜度：O(n)，取決于語(yǔ)言匹配子字符串機(jī)制
  • 空間復(fù)雜度：O(n)
impl Solution {
    pub fn is_fliped_string(s1: String, s2: String) -> bool {
        s1.len() == s2.len() && s2.repeat(2).contains(&s1)
    }
}
  • 時(shí)間復(fù)雜度：O(n)，取決于語(yǔ)言匹配子字符串機(jī)制
  • 空間復(fù)雜度：O(n)

總結(jié)

做過(guò)了輪轉(zhuǎn)的題就能很快意識(shí)到拼接然后找子串，本來(lái)調(diào)個(gè)API結(jié)束結(jié)果發(fā)現(xiàn)了KMP算法，就淺學(xué)一下~

時(shí)間耗在算法了就掠過(guò)rust各種辣~

以上就是Java C++題解leetcode字符串輪轉(zhuǎn)KMP算法詳解的詳細(xì)內(nèi)容，更多關(guān)于Java C++ 字符串輪轉(zhuǎn)KMP算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

相關(guān)文章

  • java 方法重寫與權(quán)限修飾符以及多態(tài)和抽象類詳解概念和用法

    java 方法重寫與權(quán)限修飾符以及多態(tài)和抽象類詳解概念和用法

    重寫是子類對(duì)父類的允許訪問(wèn)的方法的實(shí)現(xiàn)過(guò)程進(jìn)行重新編寫, 返回值和形參都不能改變。即外殼不變，核心重寫，權(quán)限修飾符用于控制被修飾變量、方法、類的可見范圍，說(shuō)明了面向?qū)ο蟮姆庋b性，所以我們要適用他們盡可能的讓權(quán)限降到最低，從而安全性提高
    2021-10-10
  • mybatis連接數(shù)據(jù)庫(kù)實(shí)現(xiàn)雙表查詢

    mybatis連接數(shù)據(jù)庫(kù)實(shí)現(xiàn)雙表查詢

    本文主要介紹了mybatis連接數(shù)據(jù)庫(kù)實(shí)現(xiàn)雙表查詢,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2024-09-09
  • SpringBoot實(shí)現(xiàn)elasticsearch 查詢操作(RestHighLevelClient 的案例實(shí)戰(zhàn))

    SpringBoot實(shí)現(xiàn)elasticsearch 查詢操作(RestHighLevelClient 

    這篇文章主要給大家介紹了SpringBoot如何實(shí)現(xiàn)elasticsearch 查詢操作，文中有詳細(xì)的代碼示例和操作流程，具有一定的參考價(jià)值,需要的朋友可以參考下
    2023-07-07
  • Java基于redis實(shí)現(xiàn)分布式鎖代碼實(shí)例

    Java基于redis實(shí)現(xiàn)分布式鎖代碼實(shí)例

    這篇文章主要介紹了Java基于redis實(shí)現(xiàn)分布式鎖代碼實(shí)例,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-04-04
  • spring?boot集成redisson的最佳實(shí)踐示例

    spring?boot集成redisson的最佳實(shí)踐示例

    這篇文章主要為大家介紹了spring?boot集成redisson的最佳實(shí)踐示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪
    2022-03-03
  • spring使用aspect注解切面不起作用的排查過(guò)程及解決

    spring使用aspect注解切面不起作用的排查過(guò)程及解決

    這篇文章主要介紹了spring使用aspect注解切面不起作用的排查過(guò)程及解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
    2021-06-06
  • Quartz之Job與JobDetail深入解析

    Quartz之Job與JobDetail深入解析

    下面小編就為大家?guī)?lái)一篇Quartz之Job與JobDetail深入解析。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2017-06-06
  • Spring如何基于aop實(shí)現(xiàn)操作日志功能

    Spring如何基于aop實(shí)現(xiàn)操作日志功能

    這篇文章主要介紹了Spring如何基于aop實(shí)現(xiàn)操作日志功能,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-11-11
  • 詳談Spring對(duì)IOC的理解(推薦篇)

    詳談Spring對(duì)IOC的理解(推薦篇)

    下面小編就為大家?guī)?lái)一篇詳談Spring對(duì)IOC的理解(推薦篇)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2017-10-10
  • spring用戶通過(guò)交互界面登錄成功的實(shí)現(xiàn)

    spring用戶通過(guò)交互界面登錄成功的實(shí)現(xiàn)

    本文主要介紹了spring用戶通過(guò)交互界面登錄成功的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2023-07-07

最新評(píng)論