发布于2019-08-30 11:04 阅读(1245) 评论(0) 点赞(12) 收藏(0)
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
复制代码
示例2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
复制代码
示例3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
复制代码
这里讲述的我自己的解题思路的确是笨的要死,不过也是我自己通过对问题的本质分析总结出来的,暂且记录一下,在有了自己的解题思路后去学习别人更加优秀的解题思想,对于我的提升还是蛮大的。
请看图:
首先对图中的变量做一下介绍:char curchar; // 记录当前读取到的字符
String curMaxStr; // 记录最近最长无重复字符串
int curMaxLen; // 记录最近最长无重复字符串的长度
String totalMaxStr; // 记录总体最长无重复字符串
int totalMaxLen; // 记录总体最长无重复字符串的长度
复制代码
接下来是我对问题的思考:
curChar
记录当前读取到的字符;curMaxStr
中有没有这个字符curChar
,如果没有,就将这个字符拼接到curMaxStr
,并且将curMaxLen
加1,如果curMaxLen
大于等于totalMaxLen
,就将curMaxStr
和curMaxLen
赋值给totalMaxStr
和totalMaxLen
。curMaxStr
有这个字符curChar
,那么从当前位置向前反序遍历,必然能找到与之重复的那个字符的位置,将重复的字符之后到当前curChar
位置的字符串赋值给curMaxStr
,如果curMaxLen
大于等于totalMaxLen
,就将curMaxStr
和curMaxLen
赋值给totalMaxStr
和totalMaxLen
。public static int lengthOfLongestSubstring(String s) {
// 当字符串s的长度为0时,那么就没有最长子串了
char curChar;
String curMaxStr = "", totalMaxStr = "";
int curMaxLen = 0, totalMaxLen = 0;
if(s.length() == 0) {
totalMaxLen = 0;
}
for(int i = 0; i < s.length(); i++) {
curChar = s.charAt(i);
// 当前字符与当前最长字符串中的字符没有重复时
if (!curMaxStr.contains(String.valueOf(curChar))) {
// 将当前字符拼接到当前最长字符串上
curMaxStr += curChar;
// 当前最长长度+1
curMaxLen ++;
if (curMaxLen >= totalMaxLen) {
totalMaxStr = curMaxStr;
totalMaxLen = curMaxLen;
}
//System.out.println("++++curChar:" + curChar + " curMaxStr:" + curMaxStr + " curMaxLen:" + curMaxLen + " totalMaxStr:" + totalMaxStr + " totalMaxLen:" + totalMaxLen);
}
else {
// 记录重复点的位置
int repeatPos = i;
curMaxStr = String.valueOf(curChar);
curMaxLen = 1;
// i没有遍历到开始处,并且从重复位置向前移动的这个字符与重复字符不重复
while(i > 0 && s.charAt(i - 1) != curChar) {
curMaxStr = s.charAt(--i) + curMaxStr;
curMaxLen++;
//System.out.println("----curChar:" + curChar + " curMaxStr:" + curMaxStr + " curMaxLen:" + curMaxLen + " totalMaxStr:" + totalMaxStr + " totalMaxLen:" + totalMaxLen);
if (curMaxLen >= totalMaxLen) {
totalMaxStr = curMaxStr;
totalMaxLen = curMaxLen;
}
}
i = repeatPos;
}
}
return totalMaxLen;
}
复制代码
下面是我在结了这个问题之后,在评论区看到的别人的解法,感觉特别棒,在这里也分享处理,如果读者觉得我的想法太笨,可以看看这段代码:
public static int lengthOfLongestSubstring(String s) {
int maxLength = 0;
String str = "";
for (int i = 0; i < s.length(); i++) {
int index = str.indexOf(s.charAt(i));
str = str + s.charAt(i);
//出现重复
if(index >= 0) {
str = str.substring(index + 1);
} else {
if (str.length() > maxLength) {
maxLength = str.length();
}
}
}
return maxLength;
}
复制代码
作者:放羊人
链接:https://www.pythonheidong.com/blog/article/71004/e6616efd1f562f0d3370/
来源:python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 python黑洞网 All Rights Reserved 版权所有,并保留所有权利。 京ICP备18063182号-1
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!