LeetCode #3

本贴最后更新于 2031 天前,其中的信息可能已经时移世改

问题:给定一个字符串,找出不含有重复字符的最长子串的长度。
示例:

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

思路:

  1. 暴破,从位置 0 开始,把遇到的字符放到 Set 中,如果有重复则向前推进
  2. 空间换时间,记录各个字符的位置,在遇到重复字符时向前推进,但直接跳到已有的重复字符之后一个字符开始计算
  3. 思路 2 的实现上的优化,直接用 String.charAt()获取单个字符,不先把整个字符串转换成数组(因为 String 底层就是字符数组了)

1000 万个随机字符的字符串耗时:

  1. cost: 3489 ms
  2. cost: 312 ms
  3. cost: 305 ms
    思路 3 有较大概率略微快于思路 2,但都比思路 1 快 10 倍以上,理论上字符串越长差别越明显

代码:

package xyz.quxiao.play.lab.leetcode;

import com.google.common.base.Stopwatch;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.TimeUnit;
import java.util.stream.Collectors;
import org.apache.commons.collections4.CollectionUtils;
import org.apache.commons.collections4.MapUtils;
import org.apache.commons.lang3.RandomStringUtils;

/**
 * 给定一个字符串,找到最长不含相同字符的字串长度 * * @author 作者 :quxiao 创建时间:2017/11/7 18:21
 */public class Problem3 {

  public static void main(String[] args) {
    String s = randomStr();
    Stopwatch sw = Stopwatch.createStarted();
    int r1 = lengthOfLongestSubstring(s);
    sw.stop();
    System.out.println(r1 + " cost: " + sw.elapsed(TimeUnit.MILLISECONDS) + " ms");
    sw.reset();

    sw.start();
    int r2 = lengthOfLongestSubstring2(s);
    sw.stop();
    System.out.println(r2 + " cost: " + sw.elapsed(TimeUnit.MILLISECONDS) + " ms");
    sw.reset();

    sw.start();
    int r3 = lengthOfLongestSubstring3(s);
    sw.stop();
    System.out.println(r3 + " cost: " + sw.elapsed(TimeUnit.MILLISECONDS) + " ms");
    sw.reset();

  }

  public static String randomStr() {
    int max = 10000000;
    return RandomStringUtils.randomAlphabetic(max);
  }

  // 思路1:暴破,从0开始遍历每个字符加到set中,如果成功了比较当前长度与max大小;否则推进
  public static int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
      return 0;
    }

    int max = 0;
    char[] chars = s.toCharArray();
    int len = chars.length;
    int idx = 0;
    while (idx < len) {
      // 计算该idx的最长字串
  int start = idx;
      Set set = Sets.newHashSet();
      while (start < len && set.add(chars[start++])) {
      }
      if (set.size() > max) {
        max = set.size();
      }
      idx++;
    }

    return max;
  }

  // 思路2:空间换时间,记录各个字符的位置,在遇到重复字符时向前推进,但直接跳到已有的重复字符之后一个字符开始计算
  public static int lengthOfLongestSubstring2(String s) {
    if (s == null || s.length() == 0) {
      return 0;
    }

    int max = 0;
    char[] chars = s.toCharArray();
    int len = chars.length;
    int i = 0;
    // 已经清除的最后一个idx,初始时-1表示未清除任何字符
  int lastClearIdx = -1;

    Map cMap = new HashMap<>();

    while (i < len) {
      char c = chars[i];
      // 不存在
  if (!cMap.containsKey(c)) {
        cMap.put(c, i);
        max = Math.max(max, cMap.size());
        i++;
      } else {
        int exist = cMap.get(c);
        // 清除 cur - exist之间的字符串
  for (int j = lastClearIdx + 1; j <= exist; j++) {
          cMap.remove(chars[j]);
        }
        lastClearIdx = exist;
      }
    }
    return max;
  }

  // 思路3,但是直接利用string.charAt(),不转换成arr
  public static int lengthOfLongestSubstring3(String s) {
    if (s == null || s.length() == 0) {
      return 0;
    }

    int max = 0;
    int len = s.length();
    int i = 0;
    // 已经清除的最后一个idx,初始时-1表示未清除任何字符
  int lastClearIdx = -1;

    Map cMap = new HashMap<>();

    while (i < len) {
      char c = s.charAt(i);
      // 不存在
  if (!cMap.containsKey(c)) {
        cMap.put(c, i);
        max = Math.max(max, cMap.size());
        i++;
      } else {
        int exist = cMap.get(c);
        // 清除 cur - exist之间的字符串
  for (int j = lastClearIdx + 1; j <= exist; j++) {
          cMap.remove(s.charAt(j));
        }
        lastClearIdx = exist;
      }
    }
    return max;
  }
}
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖
  • 算法
    388 引用 • 254 回帖 • 21 关注

相关帖子

回帖

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • Mac

    Mac 是苹果公司自 1984 年起以“Macintosh”开始开发的个人消费型计算机,如:iMac、Mac mini、Macbook Air、Macbook Pro、Macbook、Mac Pro 等计算机。

    164 引用 • 594 回帖 • 1 关注
  • 微信

    腾讯公司 2011 年 1 月 21 日推出的一款手机通讯软件。用户可以通过摇一摇、搜索号码、扫描二维码等添加好友和关注公众平台,同时可以将自己看到的精彩内容分享到微信朋友圈。

    129 引用 • 791 回帖
  • SEO

    发布对别人有帮助的原创内容是最好的 SEO 方式。

    35 引用 • 200 回帖 • 15 关注
  • Telegram

    Telegram 是一个非盈利性、基于云端的即时消息服务。它提供了支持各大操作系统平台的开源的客户端,也提供了很多强大的 APIs 给开发者创建自己的客户端和机器人。

    5 引用 • 35 回帖 • 2 关注
  • Gitea

    Gitea 是一个开源社区驱动的轻量级代码托管解决方案,后端采用 Go 编写,采用 MIT 许可证。

    4 引用 • 16 回帖 • 6 关注
  • DevOps

    DevOps(Development 和 Operations 的组合词)是一组过程、方法与系统的统称,用于促进开发(应用程序/软件工程)、技术运营和质量保障(QA)部门之间的沟通、协作与整合。

    37 引用 • 24 回帖
  • 创业

    你比 99% 的人都优秀么?

    82 引用 • 1397 回帖 • 1 关注
  • Solo

    Solo 是一款小而美的开源博客系统,专为程序员设计。Solo 有着非常活跃的社区,可将文章作为帖子推送到社区,来自社区的回帖将作为博客评论进行联动(具体细节请浏览 B3log 构思 - 分布式社区网络)。

    这是一种全新的网络社区体验,让热爱记录和分享的你不再感到孤单!

    1424 引用 • 10041 回帖 • 469 关注
  • Wide

    Wide 是一款基于 Web 的 Go 语言 IDE。通过浏览器就可以进行 Go 开发,并有代码自动完成、查看表达式、编译反馈、Lint、实时结果输出等功能。

    欢迎访问我们运维的实例: https://wide.b3log.org

    30 引用 • 218 回帖 • 594 关注
  • Ngui

    Ngui 是一个 GUI 的排版显示引擎和跨平台的 GUI 应用程序开发框架,基于
    Node.js / OpenGL。目标是在此基础上开发 GUI 应用程序可拥有开发 WEB 应用般简单与速度同时兼顾 Native 应用程序的性能与体验。

    7 引用 • 9 回帖 • 339 关注
  • 区块链

    区块链是分布式数据存储、点对点传输、共识机制、加密算法等计算机技术的新型应用模式。所谓共识机制是区块链系统中实现不同节点之间建立信任、获取权益的数学算法 。

    91 引用 • 751 回帖 • 3 关注
  • 链书

    链书(Chainbook)是 B3log 开源社区提供的区块链纸质书交易平台,通过 B3T 实现共享激励与价值链。可将你的闲置书籍上架到链书,我们共同构建这个全新的交易平台,让闲置书籍继续发挥它的价值。

    链书社

    链书目前已经下线,也许以后还有计划重制上线。

    14 引用 • 257 回帖 • 1 关注
  • 快应用

    快应用 是基于手机硬件平台的新型应用形态;标准是由主流手机厂商组成的快应用联盟联合制定;快应用标准的诞生将在研发接口、能力接入、开发者服务等层面建设标准平台;以平台化的生态模式对个人开发者和企业开发者全品类开放。

    15 引用 • 127 回帖 • 1 关注
  • Android

    Android 是一种以 Linux 为基础的开放源码操作系统,主要使用于便携设备。2005 年由 Google 收购注资,并拉拢多家制造商组成开放手机联盟开发改良,逐渐扩展到到平板电脑及其他领域上。

    331 引用 • 315 回帖 • 83 关注
  • TensorFlow

    TensorFlow 是一个采用数据流图(data flow graphs),用于数值计算的开源软件库。节点(Nodes)在图中表示数学操作,图中的线(edges)则表示在节点间相互联系的多维数据数组,即张量(tensor)。

    20 引用 • 19 回帖
  • Kotlin

    Kotlin 是一种在 Java 虚拟机上运行的静态类型编程语言,由 JetBrains 设计开发并开源。Kotlin 可以编译成 Java 字节码,也可以编译成 JavaScript,方便在没有 JVM 的设备上运行。在 Google I/O 2017 中,Google 宣布 Kotlin 成为 Android 官方开发语言。

    19 引用 • 33 回帖 • 20 关注
  • TGIF

    Thank God It's Friday! 感谢老天,总算到星期五啦!

    284 引用 • 4481 回帖 • 651 关注
  • 书籍

    宋真宗赵恒曾经说过:“书中自有黄金屋,书中自有颜如玉。”

    76 引用 • 390 回帖 • 1 关注
  • CAP

    CAP 指的是在一个分布式系统中, Consistency(一致性)、 Availability(可用性)、Partition tolerance(分区容错性),三者不可兼得。

    11 引用 • 5 回帖 • 553 关注
  • 机器学习

    机器学习(Machine Learning)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。

    76 引用 • 37 回帖 • 1 关注
  • Git

    Git 是 Linux Torvalds 为了帮助管理 Linux 内核开发而开发的一个开放源码的版本控制软件。

    204 引用 • 357 回帖 • 1 关注
  • MySQL

    MySQL 是一个关系型数据库管理系统,由瑞典 MySQL AB 公司开发,目前属于 Oracle 公司。MySQL 是最流行的关系型数据库管理系统之一。

    673 引用 • 535 回帖
  • 星云链

    星云链是一个开源公链,业内简单的将其称为区块链上的谷歌。其实它不仅仅是区块链搜索引擎,一个公链的所有功能,它基本都有,比如你可以用它来开发部署你的去中心化的 APP,你可以在上面编写智能合约,发送交易等等。3 分钟快速接入星云链 (NAS) 测试网

    3 引用 • 16 回帖 • 2 关注
  • RYMCU

    RYMCU 致力于打造一个即严谨又活泼、专业又不失有趣,为数百万人服务的开源嵌入式知识学习交流平台。

    4 引用 • 6 回帖 • 38 关注
  • Sym

    Sym 是一款用 Java 实现的现代化社区(论坛/BBS/社交网络/博客)系统平台。

    下一代的社区系统,为未来而构建

    522 引用 • 4581 回帖 • 687 关注
  • Tomcat

    Tomcat 最早是由 Sun Microsystems 开发的一个 Servlet 容器,在 1999 年被捐献给 ASF(Apache Software Foundation),隶属于 Jakarta 项目,现在已经独立为一个顶级项目。Tomcat 主要实现了 JavaEE 中的 Servlet、JSP 规范,同时也提供 HTTP 服务,是市场上非常流行的 Java Web 容器。

    163 引用 • 529 回帖
  • SpaceVim

    SpaceVim 是一个社区驱动的模块化 vim/neovim 配置集合,以模块的方式组织管理插件以
    及相关配置,为不同的语言开发量身定制了相关的开发模块,该模块提供代码自动补全,
    语法检查、格式化、调试、REPL 等特性。用户仅需载入相关语言的模块即可得到一个开箱
    即用的 Vim-IDE。

    3 引用 • 31 回帖 • 66 关注