0%

LeetCode题解3

发表于 更新于 分类于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

LeetCode题解

第3题，无重复字符的最长字串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

原题如上，代码如下：

python版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:return 0
        sw = []
        l = []
        m = 0
        for i in s:
            if i in sw:
                l.append(len(sw))
                while sw[0] != i:
                    sw.pop(0)
                sw.pop(0)
                sw.append(i)
            else:
                sw.append(i)
        l.append(len(sw))
        for j in l:
            if j > m:
                m = j
        return m

1uRWHU.png

c语言版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int lengthOfLongestSubstring(char * s){
    int start = 0, end = 0, max = 0;
    int a[128] = {0};
    while(end < strlen(s)){
        int c = s[end] - ' ';
        while(a[c]>0){ //表示出现重复元素
            a[s[start]-' ']--; //逐个删除start表示的元素在窗口中的出现
            start++;
        }
        a[c]++;
        end++;
        if (end - start > max){
            max = end - start;
        }
    }
    if (end -start > max){
        max = end - start;
    }
    return max;
}

1uhG9J.png

解析：

  1. 原理：

    利用滑动窗口的概念，即设置一个窗口空间，用来保存子串

    遍历源字符串s，并加到子串中，当新加元素在子串中包含时，源子串固化成为没有重复字符的子串(不包括新加重复元素)

    从源子串开头删到重复元素(包括重复元素)，变为新子串的前缀，并将新加元素添加到末尾

    按照上述方式不断获取没有重复字符的子串

    即，窗口的大小在不断变化，其中窗口大小的最大值就是无重复字符的最长字串的长度

  2. 实现：

    python版本

    利用FIFO的队列思想来实现（利用列表的append()和pop(0)来实现）

    1. 遍历源字符串s，将每个元素加入到队列中

    2. 当新加元素队列中重复时，先保存当前队列的大小，并与max比较，数值大者写入到max中，然后队列中队首弹出元素，直到将队列中与新加元素的重复元素弹出，将新加重复元素添加到队尾

    3. 遍历结束完源字符串s后，再将此时队列的长度与max比较，返回最大值

c语言版本

在c语言版本中也用到了滑动窗口的思想，不过具体是用下标来实现的

  1. 用到start和end标记窗口的前后分界

  2. 用end来遍历s，当检测出在end处的字符有在窗口中时，记录 end - start 的长度与max取最大值为max，即max = MAX(max, end - start) ，同时移动start到窗口中重复元素之后的一个位置

    这里用来检测重复元素用的是数组标记法，即用长度为128(之所以128，是因为元素不只是字母，还有特殊字符)的数组保存每个元素在窗口出现的次数，下标映射关系就是 下标 = s[end] - ' '

  3. 最后返回max即可