LeetCode——无重复字符的最长子串

栏目: 编程工具 · 发布时间: 4年前

内容简介:给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:示例2:示例3:

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
复制代码

示例2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
复制代码

示例3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
复制代码

解题思路

这里讲述的我自己的解题思路的确是笨的要死,不过也是我自己通过对问题的本质分析总结出来的,暂且记录一下,在有了自己的解题思路后去学习别人更加优秀的解题思想,对于我的提升还是蛮大的。

请看图:

LeetCode——无重复字符的最长子串

首先对图中的变量做一下介绍:

char curchar; // 记录当前读取到的字符
String curMaxStr; // 记录最近最长无重复字符串
int curMaxLen; // 记录最近最长无重复字符串的长度
String totalMaxStr; // 记录总体最长无重复字符串
int totalMaxLen; // 记录总体最长无重复字符串的长度
复制代码

接下来是我对问题的思考:

  1. 对字符串进行for循环遍历,使用 curChar 记录当前读取到的字符;
  2. 判断 curMaxStr 中有没有这个字符 curChar ,如果没有,就将这个字符拼接到 curMaxStr ,并且将 curMaxLen 加1,如果 curMaxLen 大于等于 totalMaxLen ,就将 curMaxStrcurMaxLen 赋值给 totalMaxStrtotalMaxLen
  3. 如果 curMaxStr 有这个字符 curChar ,那么从当前位置向前反序遍历,必然能找到与之重复的那个字符的位置,将重复的字符之后到当前 curChar 位置的字符串赋值给 curMaxStr ,如果 curMaxLen 大于等于 totalMaxLen ,就将 curMaxStrcurMaxLen 赋值给 totalMaxStrtotalMaxLen

具体代码

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;

    }
复制代码

以上所述就是小编给大家介绍的《LeetCode——无重复字符的最长子串》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Namo Webeditor5.5一看就懂.

Namo Webeditor5.5一看就懂.

吳聲毅 / 金禾資訊 / 20040214 / NT$ 169

一看就懂系列書全以初學者的角度切入,全書以STEP BY STEP方式撰寫,並以豐富的圖片搭配教學,在最後更加上日常生活實例運用講解,一路學來一氣呵成。為了增進學習的效率更採用高級紙品全彩印刷,這麼好的書,您還在等什麼,一看就懂系列書保證是您最佳入門學習好伙伴。 本書特色: 1、一看就懂:Step by Step操作詳盡說明、讓您一看就懂 2、精選範例:精彩實務範例生動活......一起来看看 《Namo Webeditor5.5一看就懂.》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具