-
Notifications
You must be signed in to change notification settings - Fork 53
Expand file tree
/
Copy pathLeetCode_03_35.java
More file actions
131 lines (105 loc) · 3.39 KB
/
LeetCode_03_35.java
File metadata and controls
131 lines (105 loc) · 3.39 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
package com.leecode.week02;
import com.sun.org.apache.xpath.internal.operations.Bool;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
/**
* https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
* 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
*/
public class LeetCode_03_35 {
public void printAllSubstring(String s){
char[] chs=s.toCharArray();
for(int i=0;i<s.length();i++){
for(int j=i+1;j<s.length();j++){
System.out.println(s.substring(i,j));
}
}
}
public static void main(String[] args) {
LeetCode_03_35 lc=new LeetCode_03_35();
System.out.println(lc.lengthOfLongestSubstring("abcabcbb"));
System.out.println(lc.lengthOfLongestSubstring("abc abcbb"));
System.out.println(lc.lengthOfLongestSubstring("bb bbb"));
System.out.println(lc.lengthOfLongestSubstring(" "));
System.out.println(lc.lengthOfLongestSubstring("au"));
System.out.println(lc.lengthOfLongestSubstring("abcabcbb"));
System.out.println(lc.lengthOfLongestSubstring("abbbcd"));
//1.给定一个字符串，先输出看子串都有哪些
//暴力枚举
lc.printAllSubstring("abcabcbb");
}
public int lengthOfLongestSubstring(String s){
if(s.isEmpty()){
return 0;
}
if(s.length()==1){
return 1;
}
int longest=0;
char[] chs=s.toCharArray();
Set<Character> set=new HashSet<>();
for(int i=0;i<s.length();i++){
set.add(chs[i]);
int subLen=1;
for(int j=i+1;j<s.length();j++){
if(set.contains(chs[j])){ //有重复字符,则循环终止
set.clear();
break;
}else{
set.add(chs[j]);
}
subLen++;
}
longest=Math.max(longest,subLen);
set.clear();
}
return longest;
}
public int lengthOfLongestSubstring_v1(String s) {
if(s.isEmpty()){
return 0;
}
if(s.length()==1){
return 1;
}
int longest=0;
char[] chs=s.toCharArray();
Set<Character> set=new HashSet<>();
for(int i=0;i<s.length();i++){
set.add(chs[i]);
int subLen=1;
for(int j=i+1;j<s.length();j++){
if(set.contains(chs[j])){ //有重复字符,则循环终止
set.clear();
break;
}else{
set.add(chs[j]);
}
subLen++;
}
longest=Math.max(longest,subLen);
set.clear();
}
return longest;
}
/*Map<String, Boolean> cache=new HashMap<>();
public boolean hasRepeatingChar(String s){
if(cache.containsKey(s)){
return cache.get(s);
}
char[] chs=s.toCharArray();
Set<Character> characters=new HashSet<>();
for (char ch:chs) {
if(characters.contains(ch)){
cache.put(s,true);
return true;
}else {
characters.add(ch);
}
}
cache.put(s,false);
return false;
}*/
}