专栏首页Share猿内功修炼-算法02

内功修炼-算法02

1.题目:无重复字符的最长子串

1.1题目描述

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

示例 1:

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

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

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

1.2.题目分析

1.2.1关键点

  • 不含有重复字符的最大字符串长度

1.2.2思路梳理

1.2.2.1.我的解题思路
  • 1.把字符串转换为字符数组
  • 2.把字符串逐个放入set集合(set),同时记录放入集合的数量(j)
  • 2.如果set集合长度和放入数量不符,记录该长度(l),清空set集合,把j设置为0,放入刚才放入的值,继续循环
  • 3.如果继续出现上述清空,和上面记录的长度进行对比,小于清空继续,大于更新记录长度

总结:上述解题思路忽略了空格字符串的情况,存在问题.

1.2.2.2.正确的解题思路:滑动窗口

时间窗移动原理

  • 1.定义一个map集合(map),用于存储字符值和位置,key为字符,value为字符位置加1
  • 2.定义一个变量ans,用于记录时间窗最大长度
  • 3.定义时间窗起点start和时间窗结束点end
  • 4.然后把end向右滑动,最大长度为(end-start+1),如果map集合中存在该元素,说明遇到了重复的元素
    • 4.1.记录时间窗最大值ans
    • 4.2.移动时间窗start到重复元素第一个之后的位置
  • 5.继续滑动,直到j=字符串长度

1.2.题目解答

1.2.1我的解答

/**
 * 思路一:
 *
 *      1.把字符串转换为字符数组
 *      2.把字符串逐个放入set集合(set),同时记录放入集合的数量(j)
 *      2.如果set集合长度和放入数量不符,记录该长度(l),清空set集合,把j设置为0,放入刚才放入的值,继续循环
 *      3.如果继续出现上述清空,和上面记录的长度进行对比,小于清空继续,大于更新记录长度
 *
 *      时间复杂度:T(N) 空间复杂度:O(1)
 *
 * 测试情况:不通过
 *
 * 总结分析:
 *
 *      1.没有考虑到空格字符串的情况
 */
public int lengthOfLongestSubstring1(String s) {
    char [] chars = s.toCharArray();
    Set set = new HashSet();
    int l=0;
    for (int i=0,j=0;i<chars.length;i++){
       set.add(chars[i]);
       j++;
       if (set.size()<j){
           l = Math.max(set.size(),l);
           set.clear();
           j = 1;
           set.add(chars[i]);
       }
    }
    return l;

}

1.2.2.正确的解答

/**
 * 思路二: 滑动窗口
 *
 *      1.定义一个map集合(map),用于存储字符值和位置,key为字符,value为字符位置加1
 *      2.定义一个变量ans,用于记录时间窗最大长度
 *      3.定义时间窗起点start和时间窗结束点end
 *      4.然后把end向右滑动,最大长度为(end-start+1),如果map集合中存在该元素,说明遇到了重复的元素
 *          4.1.记录时间窗最大值ans
 *          4.2.移动时间窗start到重复元素第一个之后的位置
 *      5.继续滑动,直到j=字符串长度
 *
 */
public int lengthOfLongestSubstring2(String s) {
    int n = s.length(), ans = 0;
    Map<Character, Integer> map = new HashMap<>();
    for (int end = 0, start = 0; end < n; end++) {
        char alpha = s.charAt(end);
        if (map.containsKey(alpha)) {
            start = Math.max(map.get(alpha), start);
        }
        ans = Math.max(ans, end - start + 1);
        map.put(s.charAt(end), end + 1);
    }
    return ans;
}

1.3.题目总结

在做这道题目的过程中,没有考虑到空格字符串的情况,这是基础不扎实导致的,null/“”/“ “,这三个还是有很大的区别的,如果大家也遇到和我一样的问题,可以当做是一个教训。

还有就是滑动窗口,这个理解比较麻烦,最好可以看我上面画的那种图,或者你可以自己画一个出来,滑动窗口是一个常用的办法,我们要深入理解。记得在有一次做限流的时候也用到了滑动窗口的概念。

▌本文来源:share猿

本文分享自微信公众号 - Share猿(ShareYuan-1)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 02.redis的线程IO和通讯协议

    Redis是个单线程程序!但是他有高并发特性,单个节点可以支持10w的QPS。除了redis是单线程,Nginx也是单线程的。单线程为什么如此之快?单线程有如何...

    Share猿
  • 招式修炼-redis持久化和管道

    快照是一次全量备份,顾名思义可以理解为拍照一样,把整个内存数据映射到硬盘中,保存一份到硬盘,因此恢复数据起来比较快,把数据映射回去即可,不像AOF,一条条的执行...

    Share猿
  • 招式修炼-redis事务和发布订阅

    这个命令唯一做的就是, 将客户端的 REDIS_MULTI 选项打开, 让客户端从非事务状态切换到事务状态。

    Share猿
  • Lua-原表

    __index元方法 Lua 查找一个表元素时的规则,其实就是如下 3 个步骤:

    祝你万事顺利
  • 英特尔拟10亿美元收购AI芯片创企Habana Labs,曾领投其B轮融资

    媒体报道称,英特尔正在进行高级谈判,拟以10亿至20亿美元的价格收购以色列AI芯片创企Habana Labs。若该笔交易能够通过,这将成为英特尔历史上在以色列的...

    镁客网
  • 世界互联网大会蓝皮书发布:中国数字经济总量达27.2万亿元

     11月8日上午,由中国网络空间研究院编写的《世界互联网发展报告2018》和《中国互联网发展报告2018》蓝皮书在第五届世界互联网大会上正式发布。这是大会的一项...

    钱塘数据
  • Java 避免空指针错误常用规范

    这时候status可能为null会出现空指针异常,可以把常量放前面,就能避免空指针异常。

    Kindear
  • 【.net】未在本地计算机上注册“microsoft.ACE.oledb.12.0”提供程序解决办法 目录

      在开发.net项目中,通过microsoft.ACE.oledb读取excel文件信息时,报错:

    庞小明
  • 为视频增加中文字幕---Amazon Transcribe

    语音识别技术,也被称为自动语音识别(Automatic Speech Recognition,简称ASR),其目标是将人类的语音中的词汇内容转换为计算机可读的输...

    我被狗咬了
  • jquery导航选中按钮颜色变化

    今天写一个前端页面的小功能,选中某个按钮或者菜单的时候颜色发生变化,以便用户区分自己选中的选项,这也是一种前端日常工作之中优化项。 效果是这样的:

    祈澈菇凉

扫码关注云+社区

领取腾讯云代金券