【Leetcode】3. Longest Substring Without RepeatingCharacters无重最长子串

news/2024/6/16 8:02:45

1. 题目

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

https://leetcode.com/problems...

2. 思路

遍历计算s[i:j]的以i为起点的最长j,通过hashset判重来计算是否独立。找到一个最大的j之后,计算当前找到的以i为起点的是不是更大值,是则保持。然后冲i开始往后跳跃到等于s[j+1]字符的位置的下一个位置作为新的i起点。跳跃时经过的字符从hashset中清除。
整体复杂度是O(N)

3. 代码

耗时:16ms

#include <string>
//#include <unordered_set>

class HashSet {
public:
    HashSet() {
        clear();
    }
    void clear() {
        for (int i = 0; i < 256; i++) {
            _s[i] = false;
        }
    }
    bool has(char c) {
        return _s[c + 128];
    }
    bool insert(char c) {
        int i = c + 128;
        bool ret = _s[i];
        _s[i] = true;
        return ret;
    }
    void erase(char c) {
        _s[c + 128] = false;
        return ;
    }
    
private:
    bool _s[256];
};

class Solution {
public:
    int lengthOfLongestSubstring(const string& s) {
        h.clear();
        int i = 0; 
        int j = 0;
        int len = s.length();
        int max = 0;
        int max_i = 0;
        while (i < len - max && j < len) {
            char cj = s[j];
            //if (h.insert(cj).second) {
            if (!h.insert(cj)) {
                ++max_i;
                ++j;
                continue;
            }
            if (max_i > max) {
                max = max_i;
            }
            while (i < j + 1) {
                char ci = s[i];
                h.erase(ci);
                --max_i;
                if (ci != cj) {
                    ++i;
                } else {
                    ++i;
                    break;
                }
            }
        }
        if (max_i > max) {
            max = max_i;
        }
        return max;
    }
    
private:
//    std::unordered_set<char> h;
    HashSet h;
};

http://www.niftyadmin.cn/n/2148652.html

相关文章

【jzoj1596】【GDKOI2004】石子游戏

题目描述 小勇和小实是对好朋友&#xff0c;他们经常一起游戏。 今天他们玩的游戏是这样的&#xff1a;有一个由正方形石头铺成的地板&#xff0c;它的高是2&#xff0c;长度是N。 例如以下是N3的情况&#xff1a; 现在他们轮流在上面放上长宽分别是1和2的矩形石块&#xff0…

212. 单词搜索 II

212. 单词搜索 II 原始题目链接&#xff1a;https://leetcode.cn/problems/word-search-ii/ 给定一个 m x n 二维字符网格 board 和一个单词&#xff08;字符串&#xff09;列表 words&#xff0c; 返回所有二维网格上的单词 。 单词必须按照字母顺序&#xff0c;通过 相邻的…

ThinkCMF 解决xss攻击问题

最近使用ThinkCMF给某政府开发的一个平台,因为他们需要通过国家二级信息安全等级测试所以自己先使用Appscan测试了一下&#xff0c;结果扫描出一个xss安全问题测试的网址:http://www.xxxx.com/portal/list/index/id/1/p/index.php?%3E%27%22%3E%3Cscript%3Ealert%2881998%29%3…

【jzoj1597】【GDKOI2004】汉诺塔

题目描述 古老的汉诺塔问题是这样的&#xff1a;用最少的步数将N个半径互不相等的圆盘从1号柱利用2号柱全部移动到3号柱&#xff0c;在移动的过程中小盘要始终在大盘的上面。 现在再加上一个条件&#xff1a;不允许直接把盘从1号柱移动到3号柱&#xff0c;也不允许直接把盘从3…

【jzoj1598】【GDKOI2004】城市统计

题目描述 中山市的地图是一个nn的矩阵&#xff0c;其中标号为1的表示商业区&#xff0c;标号为0的表示居民区。为了考察市内居民区与商业区的距离&#xff0c;并对此作出评估&#xff0c;市长希望你能够编写一个程序完成这一任务。 居民区i到商业区的距离指的是到距离它最近的…

php empty方法是个语法结构不能传递方法参数,不想百度了

2019独角兽企业重金招聘Python工程师标准>>> 昨天下午在敲代码的时候遇到一个问题&#xff0c;在一个判读代码中empty(intval($data[id]))。本地环境php的版本可能要比服务器的高&#xff0c;所有没有报错&#xff0c;但是更新到服务器以后&#xff0c;就出问题了。…

idea打包jar和源码到maven私服

2019独角兽企业重金招聘Python工程师标准>>> 如何发布一个pom项目且打包maven源码&#xff0c;将源码包与jar包一同deploy到mavenserver 需要在要发布的pom项目里的pom.xml里添加如下内容: <project> <build><plugins><!-- 要将源码放上去&a…

【jzoj1599】【GDKOI2004】香樟树

题目描述 被誉为江南四大名木之一的香樟树很有特色&#xff0c;它的树皮粗糙&#xff0c;质地却很均匀&#xff0c;从来没有白杨树的斑斑驳驳、没有柳树的肿瘤结节&#xff1b;树枝树干一分为二、二分为四一路长去&#xff0c;不会偷工减料也不会画蛇添足&#xff1b;树冠的形…