LeetCode_Subject3
在写这篇文章的时候我对这个题目的官方解释还不太明白， 我希望可以在我写出来 编辑文字的时候 顿悟一些东西吧有些事情，从你开始做的时候，就成功了一半！！！！
题目:给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例：
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
先来展示我自己写的吧 不喜勿喷，还在慢慢进步
public static int lengthOfLongestSubstring(String str) {
if (str.length() == 1) return 1;
if (str.length() == 0) return 0;
HashMap<Integer, Integer> result = new HashMap<>();
int index = 0;
List<String> list = Stream.iterate(0, n -> ++n).limit(str.length())
.map(n -> "" + str.charAt(n)).collect(Collectors.toList());
while (index != str.length() - 1) {
ArrayList<String> strings = new ArrayList<>();
int a = 1;
for (int i = index; i < list.size(); i++) {
if (strings.contains(list.get(i))) {
index++;
break;
}
if (i == list.size() - 1) {
result.put(index, a);
index++;
break;
}
strings.add(list.get(i));
result.put(index, a);
a++;
}
}
int length = result.size();
Object[] obj = result.values().toArray();
Arrays.sort(obj);
return (int) obj;
}
这道题目的核心是找到最长的两个相同字符的距离 于是我们用左边和右边来代替这两个字符
先把字符串拆到list里面，然后，啪上来就是两个循环，很快啊。第一层循环是为了卡住左边
第二层循环是寻找右边，每循环一次 新建一个list 用来装不重复的字符，然后判断当前字符是否已经出现过
1.如果没出现过，我们拿一个字段a来记录它的不重复长度 a++;
2.出现过之后就需要跳出第二级循环 此时result 里面已经存了重复字符之间的距离
3.如果右边循环到了最后一位，此时说明之前的循环一直没遇到重复字符 。循环到头了把它放到result里面 break 就进行下个循环了
左边一直是++的状态 然后挨个循环过去
最后给result按照大小排个序 取出最大值。虽然写的极其臃肿。但是这是我自己想出来 理清楚 的做法
下面是官方给的解题方法
其实和我的方法相差无几 比较通俗易懂
卡住左边 然后往右边查 查到重复的 就stop
public static int lengthOfLongestSubstring(String s) {
// 哈希集合，记录每个字符是否出现过
Set<Character> occ = new HashSet<Character>();
int n = s.length();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.remove(s.charAt(i - 1));
}
while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
// 不断地移动右指针
occ.add(s.charAt(rk + 1));
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
}
接下来带大家欣赏正确姿势
题目中提示的所有的字符都是比较正常的字符 所以用对应的 ASCII码值 也可以操作
public static int lengthOfLongestSubstring(String s) {
// 记录字符上一次出现的位置
int[] last = new int;
int n = s.length();
// 最大不重复长度
int res = 0;
// 最后一个重复字符上一次出现的位置
int start = 0;
// 循环字符串
for (int i = 0; i < n; i++) {
int index = s.charAt(i);
start = Math.max(start, last);
res = Math.max(res, i - start);
last = i;
}
return res;
}
这边学到的一个东西就是s.charAt(i); 取出i下标对应的字符 用int接收的话 就会转换为它的ASCII码值
这个方法的核心是 当前字符距离(上一个重复字符的左边+1 ,当前字符重复的左边) 两者取最大的 就可以取出字符到左边的最大不重复长度
跟着方法走一遍代码
因为题目中规定的字符 都是比较正常的字符 用ASCII码值可以覆盖 但如果是比较特殊的字符 这个方法可能会有一些问题
直接上才艺（循环）
取出当前字符的ASCII码值 取出 它对应下标里面的值 和上一次重复的值 相比最大的一个取出的这个值是左边的下标 为了下面计算右边和左边的距离
下面的max是取当前字符到左边的距离和之前的最大值
这个是我一个好同事好大哥写的我觉得这个代码可以适用任何字符
public static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new LinkedHashMap<>();
// 初始长度为0
int ans = 0;
for (int i = 0, j = 0; j < s.length(); j++) {
if (map.containsKey(s.charAt(j))) {
// 如果有重复字符,那么i就变为j+1
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
// 替换重复的字符,更新最新的位置
map.put(s.charAt(j), j + 1);
}
return ans;
}
把字符存到map里面 然后还是用上面讲过的核心方法
这道题两种思路
1.卡左边 找右边 找到有重复的stop
2.遍历每个字符 找上一个重复字符 或者字符本身 重复的位置然后再比较是否是最大不重复距离
这道题 看了一周 实属愚钝，，，，
希望以后可以再接再厉 感谢分享算法思路
页:
[1]