LeetCode--最長(zhǎng)不含重復(fù)字符的子字符串

博客說明

文章所涉及的資料來自互聯(lián)網(wǎng)整理和個(gè)人總結(jié)，意在于個(gè)人學(xué)習(xí)和經(jīng)驗(yàn)匯總，如有什么地方侵權(quán)，請(qǐng)聯(lián)系本人刪除，謝謝！

說明

leetcode題，面試48

最長(zhǎng)不含重復(fù)字符的子字符串

題目

請(qǐng)從字符串中找出一個(gè)最長(zhǎng)的不包含重復(fù)字符的子字符串，計(jì)算該最長(zhǎng)子字符串的長(zhǎng)度。

示例 1:

輸入: "abcabcbb"
輸出: 3 
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。

示例 2:

輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1。

示例 3:

輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "wke"，所以其長(zhǎng)度為 3。
     請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度，"pwke" 是一個(gè)子序列，不是子串。

Go語言

思路

遍歷字符串，使用map記錄重復(fù)元素出現(xiàn)的位置，對(duì)比子串的長(zhǎng)度，發(fā)現(xiàn)最長(zhǎng)的及時(shí)更新

代碼

func lengthOfLongestSubstring(s string) int {
    //創(chuàng)建一個(gè)map集合
    lastOccured := make(map[byte]int)
    //計(jì)數(shù)器
    startI := 0
    //長(zhǎng)度
    maxLength := 0

    //遍歷string
    for i, ch := range []byte(s) {
        //判斷集合不為空
        if lastI, ok := lastOccured[ch]; ok && lastI >= startI {
            startI = lastI + 1
        }
        //計(jì)算最長(zhǎng)的子串
        if i-startI+1 > maxLength {
            maxLength = i - startI + 1
        }
        //記錄最后一次出現(xiàn)的位置
        lastOccured[ch] = i
    }
    return maxLength
}

Python語言

思路一（滑動(dòng)窗口）

• 初始化頭尾指針 head，tail；

• tail 指針右移，判斷 tail 指向的元素是否在 [head:tail] 的窗口內(nèi)；

  • 如果窗口中沒有該元素，則將該元素加入窗口，同時(shí)更新窗口長(zhǎng)度最大值，tail 指針繼續(xù)右移；

  • 如果窗口中存在該元素，則將 head 指針右移，直到窗口中不包含該元素。

• 返回窗口長(zhǎng)度的最大值。

代碼

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        head = 0
        tail = 0
        # 判斷是否為邊界
        if len(s) < 2:
            return len(s)
        # 兩個(gè)指針停留在第一個(gè)元素的位置，初始長(zhǎng)度為1
        res = 1
        while tail < len(s) - 1:
            tail += 1
            if s[tail] not in s[head:tail]:
                res = max(tail-head + 1,res)
            else:
                while s[tail] in s[head:tail]:
                    head += 1
        return res

思路二（哈希表）

• tail 指針向末尾方向移動(dòng)；
• 如果尾指針指向的元素存在于哈希表中：
  • head 指針跳躍到重復(fù)字符的左邊一位；
• 更新哈希表和窗口長(zhǎng)度。

代碼

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        hashmap = {}
        head,res = 0,0
        for tail in range(n):
            # 如果說尾指針存在哈希表中，把頭指針跳轉(zhuǎn)到開始重復(fù)元素的上一位
            if s[tail] in hashmap:
                head = max(hashmap[s[tail]],head)
            # 更新哈希表
            hashmap[s[tail]] = tail +1
            # 更新長(zhǎng)度
            res = max(res,tail-head+1)
        return res

C++

• r 指針向末尾方向移動(dòng)；
• 如果尾指針指向的元素存在于哈希表中：
  • l 指針跳躍到重復(fù)字符的左邊一位；
• 更新哈希表和窗口長(zhǎng)度（時(shí)刻返回最大的值）。

代碼

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char,int> m;
        int ret = 0,l = 0, r=0;
        while(r<s.size()){
            //判斷邊界
            if(m.find(s[r]) != m.end()){
                l = max(l,m[s[r]]+1);
            }
            m[s[r++]] = r;
            ret = max(r-l,ret);
        }
        return ret;
    }
};

C語言

思路

滑動(dòng)窗口

代碼

int lengthOfLongestSubstring(char* s){
    int count[95]; // ASCII中存在95個(gè)可打印的字符，記錄遍歷s時(shí)遇到的字符
    memset(count, 0, 95 * sizeof(int)); // 將count的值全部置為0
    int max_lenght = 0; // 不含重復(fù)字符的子字符串的最大長(zhǎng)度
    int temp = 0; // 存儲(chǔ)遍歷s時(shí)所尋找到的不含重復(fù)字符的子字符串的長(zhǎng)度
    int p1 = 0, p2 = 0;
    while(s[p1] != '\0' && s[p2] != '\0'){

        if(count[s[p2] - ' '] == 0){ // 沒有遇到重復(fù)字符
            count[s[p2] - ' '] = 1; // 記錄遇到的字符
            p2 += 1;
            temp = p2 - p1;
        }
        else{ // 遇到重復(fù)字符
            temp = p2 - p1;
            count[s[p1] - ' '] = 0; // 刪除對(duì)p1位置字符的記錄
            p1 += 1; // p1右移
        }

        if(temp > max_lenght){
            max_lenght = temp;
        }
    }
    return max_lenght;
}

感謝

leetcode

以及勤勞的自己