九色国产,午夜在线视频,新黄色网址,九九色综合,天天做夜夜做久久做狠狠,天天躁夜夜躁狠狠躁2021a,久久不卡一区二区三区

📢前言

• 🌲 每天打卡一道算法題，既是一個(gè)學(xué)習(xí)過(guò)程，又是一個(gè)分享的過(guò)程😜
• 🌲 提示：本專欄解題 編程語(yǔ)言一律使用 C# 和 Java 兩種進(jìn)行解題
• 🌲 要保持一個(gè)每天都在學(xué)習(xí)的狀態(tài)，讓我們一起努力成為算法大神吧🧐！
• 🌲 今天是力扣算法題持續(xù)打卡第15天🎈！

🌲原題樣例

實(shí)現(xiàn) strStr()函數(shù)。

給你兩個(gè)字符串 haystack和 needle，請(qǐng)你在 haystack 字符串中找出 needle字符串出現(xiàn)的第一個(gè)位置（下標(biāo)從 0 開(kāi)始）。

如果不存在，則返回 -1。

說(shuō)明:

當(dāng) needle是空字符串時(shí)，我們應(yīng)當(dāng)返回什么值呢？這是一個(gè)在面試中很好的問(wèn)題。

對(duì)于本題而言，當(dāng) needle是空字符串時(shí)我們應(yīng)當(dāng)返回 0 。這與 C 語(yǔ)言的 strstr()以及 Java 的 indexOf() 定義相符。

示例 1：

輸入：haystack = "hello", needle = "ll"
輸出：2

示例 2：

輸入：haystack = "aaaaa", needle = "bba"
輸出：-1

示例 3：

輸入：haystack = "", needle = ""
輸出：0

提示：

• 0 <= haystack.length, needle.length <= 5 * 104
• haystack 和 needle 僅由小寫(xiě)英文字符組成

🌻C#方法一：暴力法

思路解析

我看到題目的第一想法是使用IndexOf直接就可以返回第一個(gè)下標(biāo)了

但是這樣毫無(wú)算法可言哈哈，后面也把代碼貼上~

暴力法，使用雙層for循環(huán)，讓字符串needle 與字符串 haystack的所有長(zhǎng)度為 m 的子串均匹配一次。

為了減少不必要的匹配，我們每次匹配失敗即立刻停止當(dāng)前子串的匹配，對(duì)下一個(gè)子串繼續(xù)匹配。

如果當(dāng)前子串匹配成功，我們返回當(dāng)前子串的開(kāi)始位置即可。如果所有子串都匹配失敗，則返回 ?1。

代碼：

    public int strStr(string haystack, string needle)
    {
        int n = haystack.Length, m = needle.Length;
        for (int i = 0; i + m <= n; i++)
        {
            bool flag = true;
            for (int j = 0; j < m; j++)
            {
                if (haystack.Substring(i + j,1) != needle.Substring(j,1))
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                return i;
            }
        }
        return -1;
    }

執(zhí)行結(jié)果

通過(guò)
執(zhí)行用時(shí)：1373 ms，在所有 C# 提交中擊敗了13.13%的用戶
內(nèi)存消耗：38.2 MB，在所有 C# 提交中擊敗了61.91%的用戶

復(fù)雜度分析

時(shí)間復(fù)雜度：O(n * m)
空間復(fù)雜度：O(1)

🌻C#方法二：傻瓜解法

此方法使用C#的IndexOf方法直接拿到符合條件的索引，體現(xiàn)不出算法的精髓。。

代碼：

public class Solution {
    public int StrStr(string haystack, string needle)
    {
        if (needle == "")
            return 0;
        int test = haystack.IndexOf(needle);
        return test;
    }
}

執(zhí)行結(jié)果

通過(guò)
執(zhí)行用時(shí)：920 ms，在所有 C# 提交中擊敗了30.06%的用戶
內(nèi)存消耗：24.3 MB，在所有 C# 提交中擊敗了13.88%的用戶

🌻Java 方法一：暴力法

此方法跟C#第一種解題思路一致

代碼：

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; i++) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }
}

執(zhí)行結(jié)果

通過(guò)
執(zhí)行用時(shí)：1373 ms，在所有 Java  提交中擊敗了13.03%的用戶
內(nèi)存消耗：38.2 MB，在所有 Java 提交中擊敗了61.91%的用戶

復(fù)雜度分析

時(shí)間復(fù)雜度：O(n*m)
空間復(fù)雜度：O((1)

🌻Java 方法二： KMP 解法

思路解析

只能說(shuō)我還不懂。。從力扣大佬參考過(guò)來(lái)的！

代碼：

class Solution {
    // KMP 算法
    // ss: 原串(string)  pp: 匹配串(pattern)
    public int strStr(String ss, String pp) {
        if (pp.isEmpty()) return 0;
        
        // 分別讀取原串和匹配串的長(zhǎng)度
        int n = ss.length(), m = pp.length();
        // 原串和匹配串前面都加空格，使其下標(biāo)從 1 開(kāi)始
        ss = " " + ss;
        pp = " " + pp;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // 構(gòu)建 next 數(shù)組，數(shù)組長(zhǎng)度為匹配串的長(zhǎng)度（next 數(shù)組是和匹配串相關(guān)的）
        int[] next = new int[m + 1];
        // 構(gòu)造過(guò)程 i = 2，j = 0 開(kāi)始，i 小于等于匹配串長(zhǎng)度 【構(gòu)造 i 從 2 開(kāi)始】
        for (int i = 2, j = 0; i <= m; i++) {
            // 匹配不成功的話，j = next(j)
            while (j > 0 && p[i] != p[j + 1]) j = next[j];
            // 匹配成功的話，先讓 j++
            if (p[i] == p[j + 1]) j++;
            // 更新 next[i]，結(jié)束本次循環(huán)，i++
            next[i] = j;
        }

        // 匹配過(guò)程，i = 1，j = 0 開(kāi)始，i 小于等于原串長(zhǎng)度 【匹配 i 從 1 開(kāi)始】
        for (int i = 1, j = 0; i <= n; i++) {
            // 匹配不成功 j = next(j)
            while (j > 0 && s[i] != p[j + 1]) j = next[j];
            // 匹配成功的話，先讓 j++，結(jié)束本次循環(huán)后 i++
            if (s[i] == p[j + 1]) j++;
            // 整一段匹配成功，直接返回下標(biāo)
            if (j == m) return i - m;
        }

        return -1;
    }
}
鏈接：https://leetcode-cn.com/problems/implement-strstr/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/

執(zhí)行結(jié)果

通過(guò)
執(zhí)行用時(shí)：3 ms，在所有 Java  提交中擊敗了72.84%的用戶
內(nèi)存消耗：38.5 MB，在所有 Java 提交中擊敗了29.32%的用戶

復(fù)雜度分析

時(shí)間復(fù)雜度：O(m+n)
空間復(fù)雜度：O((m)

💬總結(jié)

• 今天是力扣算法題打卡的第十五天！
• 文章采用 C#和 Java 兩種編程語(yǔ)言進(jìn)行解題
• 一些方法也是參考力扣大神寫(xiě)的，也是邊學(xué)習(xí)邊分享，再次感謝算法大佬們
• 那今天的算法題分享到此結(jié)束啦，明天再見(jiàn)！