當前位置:網站首頁>LeetCode|3. 無重複字符的最長子串

LeetCode|3. 無重複字符的最長子串

2022-05-13 15:07:53difizuhvovs

根本不懂算法的非科班小白
思路:用dfs暴力搜索先找到所有子串,然後用集合判斷是否有重複字符,再比較長度。
語法
獲取字符串中某一字符:s.charAt(i)
字符串無重複字符個數:

import java.util.HashSet;
import java.util.Set;

public class text {
    
    public static void main(String[] args) {
    
        String s = "sdfgdhsfgs";
        Set set = new HashSet();
        for(int i=0;i<s.length();i++){
    
            set.add(s.charAt(i));
        }
        System.out.println(set.size());
    }
}

寫到這裏發現自己搞錯了子序列子串。。

class Solution {
    
    List<String> res = new ArrayList<String>();
    public List<String> subsetXORSum(String str) {
    
        if(str.length()==1)
            res.add(str);
        else
            dfs(str, 0, "");
        return res;
    }
    public void dfs(String str, int x, String t){
    
        if(x==str.length()){
    
            res.add(t);
            return;
        }
        dfs(str,x+1, t+str.charAt(x));
        dfs(str,x+1, t);
        return;
    }
    public int lengthOfLongestSubstring(String s) {
    
        int max = 0;
        subsetXORSum(s);
        for(int i=0;i<res.size();i++){
    
            Set set = new HashSet();
            for(int j=0;j<res.get(i).length();j++){
    
                set.add(res.get(i).charAt(j));
            }
            if(set.size()==res.get(i).length())
                max = Math.max(max, set.size());
        }
        return max;
    }
}

這樣超時了;;

class Solution {
    
    List<String> res = new ArrayList<String>();
    public List<String> subsetXORSum(String str) {
    
        for(int i=0;i<str.length();i++){
    
            for(int j=i;j<str.length();j++){
    
                String t ="";
                for(int k=i;k<=j;k++){
    
                    t+=str.charAt(k);
                }
                res.add(t);
            }
        }
        return res;
    }
    public int lengthOfLongestSubstring(String s) {
    
        int max = 0;
        subsetXORSum(s);
        for(int i=0;i<res.size();i++){
    
            Set set = new HashSet();
            for(int j=0;j<res.get(i).length();j++){
    
                set.add(res.get(i).charAt(j));
            }
            if(set.size()==res.get(i).length())
                max = Math.max(max, set.size());
        }
        return max;
    }
}

依然曹縣。。

public int lengthOfLongestSubstring(String s) {
    
        int max = 0;
        for(int i=0;i<s.length();i++) {
    
            for (int j = i; j < s.length(); j++) {
    
                String t = "";
                for (int k = i; k <= j; k++)
                    t += s.charAt(k);
                Set set = new HashSet();
                for (int n = 0; n < t.length(); n++)
                    set.add(t.charAt(n));
                if (set.size() == t.length())
                    max = Math.max(max, set.size());
            }
        }
        return max;
    }

一上午過去了。。下午看題解吧=。=


看完題解自己寫的答案:

class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
        int start=0, end=0, max=0;
        Set<Character> occ = new HashSet<Character>();
        int n=s.length();
        while(end<n){
    
            if(!occ.contains(s.charAt(end))){
    
                occ.add(s.charAt(end));
                end++;
            }
            else{
    
                max = Math.max(max, end-start);
                occ.remove(s.charAt(start));
                start++;
            }
        }
        max = Math.max(max, end-start);
        return max;
    }
}

滑動平均。時間複雜度O(n)
找從第0個元素開始的子串,當有重複元素時end。以此類推,找從第1個元素開始的子串。找到各個end-start的最大值。
以“dsdf”為例。

start=end=max=0
while:
	if:
	occ->d
	end->1
	occ->d,s
	end->2
	else:
	max->2
	occ->s
	start->1
	if:
	occ->s,d
	end->3
	occ->s,d,f
	end->4
max=3

版權聲明
本文為[difizuhvovs]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/133/202205131502290396.html

隨機推薦