每日一题:LeetCode-LCR 016. 无重复字符的最长子串

这篇具有很好参考价值的文章主要介绍了每日一题:LeetCode-LCR 016. 无重复字符的最长子串。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

每日一题系列(day 15)

前言:

🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈

   🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉算法👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇,我们要做的,就是斩妖除魔💥💥,打怪升级!💪💪当然切记不可😈走火入魔😈,每日打怪,拾取经验,终能成圣🙏🙏!开启我们今天的斩妖之旅吧!✈️✈️


题目:

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

示例:

每日一题:LeetCode-LCR 016. 无重复字符的最长子串,每日一题,LeetCode,刷题

提示:

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

解法一:

  思路:

  这道题目让我们求出最长子串的长度,我们先来使用暴力来解决这道题目,要判断是否有重复字符的最长子串我们首先会想到用双指针来解决。
  1、设置左右指针,让右指针前进,将右指针遍历过得元素用哈希表记录,当右指针指向的元素在哈希表里出现了两次,则右指针停止前进。
  2、这时记录出本次无重复子串的长度,然后左指针向后移动一位,右指针回退到左指针位置,再将哈希表清空,重新开始记录。
  3、这样不断枚举出所有不重复子串,最后就能得到最长子串,这里需要注意的是,右指针长度不能超过数组s的长度。

  代码实现:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = { 0 };//用数组模拟哈希表
        int len = s.size();//求出字符串s的长度
        if(len == 1) return 1;
        
        int ret = 0, right = 0, left = 0;//设置左右指针以及ret记录最长子串
        while(left < len)//左指针在数组范围内
        {
            again://防止右指针多加一次
            hash[s[right]]++;//将右指针的值在哈希表中对应位置++

            while(hash[s[right]] > 1)//表示右指针遇到了重复值
            {
                left++;//遇到重复值本次结束将左指针向右移动一位开启下一轮比较
                ret = max(ret, right - left + 1);//记录下本次无重复子串长度
                right = left;//右指针回退到左指针位置
                memset(hash, 0, sizeof(hash));//将hash表重置
                goto again;//防止right多加一次
            }
            if(right != len)//保证右指针不越界
            right++;
        }
        
        return ret;//返回最长子串即可
    }
};

每日一题:LeetCode-LCR 016. 无重复字符的最长子串,每日一题,LeetCode,刷题
  这样的暴力似乎还不错,但是有没有更好的写法了呢?其实是有的,在我们的暴力的基础上进行优化。


解法二:

  思路:

  如果你理解透了暴力解法,那么就可以在此基础上进行进阶—— 滑动窗口 问题:

  1、其实我们在使用右指针时,回退那一步操作完全没有必要进行,因为回退之后再次向后遍历,遍历到的新的重复字符一定是要比上一次右指针最远位置相等或者更远的,因为遇到了两个相等的字符,我们右指针就会停下,那么右指针前面扫描过的区域就一定不会存在重复字符问题,所以我们并不需要回退这部操作
  2、既然不需要回退这步操作,那么我们哈希表也不用每次使用都要清零再记录了,当左指针移动之前,我们就将左指针对应位置的哈希值-1,这样就能继续保证左右指针区间内无重复字符了。
  3、第二步操作有些问题,当数组为大量重复数据时,如果仅仅判断一次,那么就会造成长度误判,所以只要我们右指针指向元素的哈希值>1,那么我们就一直执行第二步操作
  3、左指针移动之后,我们就与上一次记录的不重复子串进行比较,返回较大值。这些做完之后,开始新一轮查询,右指针自增。当右指针遍历完整个数组后,最长子串也就出来了。

每日一题:LeetCode-LCR 016. 无重复字符的最长子串,每日一题,LeetCode,刷题

  代码实现:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = { 0 };//数组代替哈希表
        int left = 0, right = 0, n = s.size();
        int ret = 0;//返回值
        while(right < n)
        {
            hash[s[right]]++;
            while(hash[s[right]] > 1)//防止重复数据
            {
                hash[s[left++]]--;
            }
            ret = max(ret, right - left + 1);
            right++;
        }
    return ret;
    }
};

每日一题:LeetCode-LCR 016. 无重复字符的最长子串,每日一题,LeetCode,刷题


  这题使用双指针暴力写法也不是很简单,尤其是在右指针回退那里,一不小心就容易出错,而我们使用滑动窗口来解决问题,虽然代码量很少,但是却很不好想,滑动双指针的题做多了可能你觉得滑动双指针不难,可是我认为,我们能想到这题使用滑动双指针更加重要。文章来源地址https://www.toymoban.com/news/detail-777268.html

到了这里,关于每日一题:LeetCode-LCR 016. 无重复字符的最长子串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • ( 动态规划) 674. 最长连续递增序列 / 718. 最长重复子数组——【Leetcode每日一题】

    难度:简单 给定一个未经排序的整数数组,找到最长且 连续递增的子序列 ,并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r(l r) 确定,如果对于每个 l = i r ,都有 nums[i] nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

    2024年02月05日
    浏览(52)
  • 【五一创作】( 字符串) 409. 最长回文串 ——【Leetcode每日一题】

    难度:简单 给定一个包含大写字母和小写字母的字符串 s ,返回 通过这些字母构造成的 最长的回文串 。 在构造过程中,请注意 区分大小写 。比如 \\\"Aa\\\" 不能当做一个回文字符串。 示例 1: 输入:s = “abccccdd” 输出:7 解释: 我们可以构造的最长的回文串是\\\"dccaccd\\\", 它的长度是

    2024年02月01日
    浏览(56)
  • 【LeetCode每日一题】2182. 构造限制重复的字符串

    2024-1-13 2182. 构造限制重复的字符串 思路: 按照字符出现次数从高到低的顺序进行重复,通过维护一个指针 j 来寻找下一个非零出现次数的字母。同时,利用 StringBuilder 对象可以高效地构建字符串,避免频繁的字符串拼接操作 首先,创建一个长度为26的数组 cnt ,用于统计字

    2024年01月18日
    浏览(48)
  • (字符串 ) 459. 重复的子字符串——【Leetcode每日一题】

    难度:简单 给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。 示例 1: 输入: s = “abab” 输出: true 解释: 可由子串 “ab” 重复两次构成。 示例 2: 输入: s = “aba” 输出: false 示例 3: 输入: s = “abcabcabcabc” 输出: true 解释: 可由子串 “abc” 重复四次构

    2024年02月07日
    浏览(48)
  • (栈和队列) 1047. 删除字符串中的所有相邻重复项 ——【Leetcode每日一题】

    难度:简单 给出由小写字母组成的字符串 S , 重复项删除操作 会选择两个相邻且相同的字母,并删除它们。 在 S 上反复执行重复项删除操作,直到无法继续删除。 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。 示例: 输入 :“abbaca” 输出 :“ca” 解释

    2024年02月08日
    浏览(53)
  • ( 动态规划) 516. 最长回文子序列 ——【Leetcode每日一题】

    难度:中等 给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 示例 1: 输入:s = “bbbab” 输出:4 解释:一个可能的最长回文子序列为 “bbbb” 。 示例

    2024年02月06日
    浏览(44)
  • 【每日一题】构造限制重复的字符串

    【贪心】【字符串】【2024-01-13】 2182. 构造限制重复的字符串 思路 解题思想比较简单,利用贪心思想,每次选择当前剩余字符串中字典序最大的字符加到答案字符串末尾,如果答案字符串末尾的字符已经连续出现了 repeatLimit 次,则将字典序次大的字符加到答案字符串,随后

    2024年01月22日
    浏览(44)
  • 【Leetcode】3. 无重复字符的最长子串

    给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 示例1: 示例2: 示例3: 提示 : 0 = s . l e

    2024年02月10日
    浏览(37)
  • LeetCode 3. 无重复字符的最长子串

    力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 我们需要找的是含重复元素的最长子串,当然直接暴力求解固然简单。但是可能引发的情况是超时,而且面试官想看到的也不是让你去暴力解决这类问题。因此我们使用哈希+滑动窗口的思想来解决。 使用哈希表的缘故是更

    2024年02月09日
    浏览(41)
  • leetcode:无重复字符的最长字串(详解)

    给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 HashMapCharacter, Integer map = new HashMap();创建一个HashMap,用于存储字符及其最后一次出现的位置。 int max = 0;: 用于记录最长子串的长度。 int start = 0;: 用于记录当前子串的起始位置。 for (int i = 0; i s.length(); i

    2024年02月22日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包