当前位置:首页 > 算法 > 正文内容

(LeetCode刷题)3. 无重复字符的最长子串

chanra1n3个月前 (03-22)算法204

题目:

image.png

解法一:

class Solution(object):
    def lengthOfLongestSubstring(self,s):
        # 哈希集合,记录每个字符是否出现过
        occ = set()
        n = len(s)
        # 右指针,初始值为-1,相当于我们在字符串的左边界的左侧,还没有开始移动
        rk = -1
        ans = 0
        # 枚举左指针的位置,初始值随便设置
        for i in range(n):
            if i != 0:
                # 左指针向右移动一格,移除一个字符
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                # 不断地移动右指针
                occ.add(s[rk + 1])
                rk += 1
            # 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1)
        return ans

image.png

解法二:

#include <string.h>
#define MAX(a,b) ((a)>(b)?(a):(b))

int lengthOfLongestSubstring(char* s) {
    int lastIndex[128];    // 保存字符最后出现的位置
    memset(lastIndex, -1, sizeof(int) * 128);
    int maxLength = 0;     // 存储最大无重复子串的长度
    int startPosition = -1; // 滑动窗口起始位置
    for(int i=0; s[i]; ++i) {
        startPosition = MAX(startPosition, lastIndex[s[i]]);
        maxLength = MAX(maxLength, i - startPosition);
        lastIndex[s[i]] = i;
    }
    return maxLength;
}


这是一个经典的滑动窗口问题,其主要思想是创建一个窗口,在遍历过程中,不断地调整窗口的大小使窗口内的内容符合我们的要求。这个问题中的“窗口”是指原始输入字符串 s 的一个子串。
让我们仔细解析一下这段代码:
  1. int lastIndex[128]; :定义了一个长度为 128 的数组,用于存储每个 ASCII 字符在字符串中最后出现的位置。数组全部初始化为 -1,表示字符串的初始滑动窗口不含有任何字符。
  2. startIndex :用于标记滑动窗口的起始位置。初始化为 -1 表示还没有开始滑动。
  3. int maxLength = 0; :用于记录最长无重复字符子串的长度。
  4. 在 for 循环中:
    • startPosition = MAX(startPosition, lastIndex[s[i]]); ,这个语句在调整窗口的起始位置。如果当前字符 s[i] 在之前已经出现过(即 lastIndex[s[i]] 的值大于 startPosition),窗口起始位置就需要向前移动一位,以保证窗口内没有重复字符。

    • maxLength = MAX(maxLength, i - startPosition); ,这个语句在更新最长无重复字符子串的长度。如果 i - startPosition(当前子串长度)更大就进行更新。

    • lastIndex[s[i]] = i; ,这个语句在更新当前字符 s[i] 在字符串 s 中最后出现的位置。


这段代码的主要思想就是,通过控制滑动窗口的起始位置 startPosition 和截止位置 i ,保证窗口内没有重复字符,并在此过程中不断更新最长无重复字符子串的长度 maxLength 。通过这种方式,我们可以在一次遍历中解决问题。

image.png


扫描二维码推送至手机访问。

版权声明:本文由我的FPGA发布,如需转载请注明出处。

本文链接:https://myfpga.cn/index.php/post/397.html

分享给朋友:
返回列表

上一篇:(LeetCode刷题)2. 两数相加

没有最新的文章了...

“(LeetCode刷题)3. 无重复字符的最长子串” 的相关文章

​Fibonacci数列的初步实现-递归

​Fibonacci数列的初步实现-递归

Fibonacci数列为:1、1、2、3、5、8、13、21、…,即 Fibonacci(1)=1; Fibonacci(2)=1;Fibonacci(n)=Fibonacci(n-1)+ Fibonacci(n-2)(当n>2时)。#include <stdio.h>...

Hanoi Tower问题的简单实现

Hanoi Tower问题的简单实现

设A,B,C是3个塔座。开始时,在塔座A上有一叠共n个圆盘,这些圆盘自上而下,由小到大地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座A上的这一叠圆盘移到塔座C上,并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则:(1)每次只能移动1个圆盘;(2)任何时刻都不允许将较大的圆盘压在较小的...

常见算法的C语言实现(带题目、分析和答案) 穷举 递归 迭代 递推 分治 回溯 动态规划 贪心

常见算法的C语言实现(带题目、分析和答案) 穷举 递归 迭代 递推 分治 回溯 动态规划 贪心

1.1   基本思想1.1.1  穷举穷举(又称枚举)算法的基本思想是从所有可能的情况中搜索正确的答案。a)      题一查找数组中的两个元素,它们的和等于给定的目标值。给定一个包含 n 个整数的数组和一个目标值,找出...

(LeetCode刷题)1. 两数之和

(LeetCode刷题)1. 两数之和

题目解答一:/**  * Note: The returned array must be malloced, assume caller calls free(). &nbs...

(LeetCode刷题)2. 两数相加

(LeetCode刷题)2. 两数相加

题目解答一:简单实现思路:先遍历完两个链表,把各自的数字存入两个数组,然后对应位置的数相加,若结果大于10就进位到更高位的数。/**  * Definition for singly-linked list->  * s...