LeetCode刷题--点滴记录003

要求

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

解题

#include 
using namespace std;
#include 

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        if (s.size() == 0) 
            return 0;
        int max_len = 0;             //用来保存最长子串长度
        set book;             //记录窗口中已经出现的字符
        int left = 0;               // 维护滑动窗口的起始位置
        for (int right = 0; right < s.length(); ++right)
        {
            // 当新加入窗口右侧的字符是重复字符，让窗口左边界（左指针）右移
            while (book.find(s[right]) != book.end()) {
                book.erase(s[left]);
                ++left;
            }
            
            book.insert(s[right]); // 将右指针处的字符加入窗口
            max_len = max(max_len, right - left + 1); //更新最大长度
        }
        return max_len;
    }
};


void test01()
{
    Solution s;
    string s1 = "abcabcbb";
    cout << s1 << endl;
    int l1 = s.lengthOfLongestSubstring(s1);
    cout << l1 << endl;
}

void test02()
{
    Solution s;
    string s2 = "bbbbb";
    cout << s2 << endl;
    int l2 = s.lengthOfLongestSubstring(s2);
    cout << l2 << endl;
}

void test03()
{
    Solution s;
    string s3 = "pwwkew";
    cout << s3 << endl;
    int l3 = s.lengthOfLongestSubstring(s3);
    cout << l3 << endl;
}

int main()
{
    test01();
    cout << "------------------" << endl;
    test02();
    cout << "------------------" << endl;
    test03();

    system("pause");
    return 0;
}

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s: 
            return 0
        max_len = 0             # 最大长度
        book = []                 # 放字符串的一个队列    
        for a in s:
            while a in book:
                del book[0]       # 删除队列左边第一个，直到没有重复的字符串
            book.append(a)       
            max_len = max(max_len,len(book)) 
        return max_len
                       
           
def test01():
    solution = Solution()
    s1 = "abcabcbb"
    print(s1)
    l1 = solution.lengthOfLongestSubstring(s1)
    print(l1)
    
def test02():
    solution = Solution()
    s2 = "bbbbb"
    print(s2)
    l2 = solution.lengthOfLongestSubstring(s2)
    print(l2)
    
def test03():
    solution = Solution()
    s3 = "pwwkew"
    print(s3)
    l3 = solution.lengthOfLongestSubstring(s3)
    print(l3)
            
if __name__=="__main__":
    test01()
    print("--------------")
    test02()
    print("--------------")
    test03()

package com.hailei_01;

import java.util.HashMap;
import java.util.Map;

public class LongestSubstringWithoutRepeatingCharacters {
    public static void main(String[] args) {
        String s1 = "abcabcbb";
        System.out.println(s1);
        int l1 = lengthOfLongestSubstring(s1);
        System.out.println(l1);
        System.out.println("----------------");
        String s2 = "bbbbb";
        System.out.println(s2);
        int l2 = lengthOfLongestSubstring(s2);
        System.out.println(l2);
        System.out.println("----------------");
        String s3 = "pwwkew";
        System.out.println(s3);
        int l3 = lengthOfLongestSubstring(s3);
        System.out.println(l3);
    }

    public static int lengthOfLongestSubstring(String s) {
        int max_len = 0;//用于记录最大不重复子串的长度
        Map map = new HashMap();
        for (int right = 0, left = 0; right < s.length(); right++) {
            if (map.containsKey(s.charAt(right))) {
                left = Math.max(map.get(s.charAt(right)), left);
            }
            max_len  = Math.max(max_len , right - left + 1);
            map.put(s.charAt(right), right + 1);//下标 + 1 代表 i 要移动的下个位置
        }
        return max_len;
    }

}

希望本文对大家有帮助，上文若有不妥之处，欢迎指正

分享决定高度，学习拉开差距