Emove

  • 首页
  • 归档
  • 分类
  • 标签

  • 搜索
context 反射 channel LRU BeanDefinition JVM 装饰者模式 MyBatis 快慢指针 归并排序 链表 hash表 栈 回溯 贪心 主从复制 二分查找 双指针 动态规划 AOF RDB 规范 BASE理论 CAP B树 RocketMQ Sentinel Ribbon Eureka 命令模式 访问者模式 迭代器模式 中介者模式 备忘录模式 解释器模式 状态模式 策略模式 职责链模式 模板方法模式 代理模式 享元模式 桥接模式 外观模式 组合模式 适配器模式 建造者模式 原型模式 工场模式 单例 UML 锁 事务 sql 索引

最长子串

发表于 2020-03-28 | 分类于 算法题 | 18 | 阅读次数 138

题目:给定一个字符串,找出其中无重复字符串的最长子串长度。

例如 :
输入:“abcabcbb”
输出: 3
说明: “abc”为其中的最长无重复子串,长度为3

题解:

  1. 使用两个指针,左指针指向当前子串起始下标,右指针指向当前子串尾部下标。右指针每移动一位,计算当前的子串长度。
  2. 在指针移动过程中,需要记录当前子串以存在的字符和下标,比如用Map存储。
  3. 当右指针每移动一次,需判断当前子串中是否已经存在当前指向的字符。若已存在,需将左指针移动到当当前字符的下标。再继续移动右指针,直至遍历完字符串。

题解代码如下:

public class Solution {

    public static int lengthOfLongestSubstring(String s) {
        int length = s.length();
        int ans = 0;
        // current index of character
        Map<Character, Integer> map = new HashMap<>();
        // try to extend the range [left, right]
        int left = 0;
        for (int right = 0; right < length; right++) {
            Character c = s.charAt(right);
            if (map.containsKey(c)) {
                left = Math.max(map.get(c), left);
            }
            ans = Math.max(ans, right - left + 1);
            map.put(c, right + 1);
        }
        return ans;
    }

}

该题还另外一种更优解法,在上方解法中,借助了Map。但在使用Map的同时,也造成了性能的损耗。换个思路,因为给出的字符串中,均为英文字母,a-z或A-Z。其在ASCII表中,A-Z对应65-90,a-z对应97-122。因此可借助ASCII表,使用基本数据类型数据来代替Map。其做法如下:

public class Solution {
    public static int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        // current index of character
        int[] index = new int[128];
        // try to extend the range [left, right]
        for (int right = 0, left = 0; right < n; right++) {
            // if index[s.charAt(right)] > left , means current char is repeat
            left = Math.max(index[s.charAt(right)], left);
            ans = Math.max(ans, right - left + 1);
            index[s.charAt(right)] = right + 1;
        }
        return ans;
    }
}

# context # 反射 # channel # LRU # BeanDefinition # JVM # 装饰者模式 # MyBatis # 快慢指针 # 归并排序 # 链表 # hash表 # 栈 # 回溯 # 贪心 # 主从复制 # 二分查找 # 双指针 # 动态规划 # AOF # RDB # 规范 # BASE理论 # CAP # B树 # RocketMQ # Sentinel # Ribbon # Eureka # 命令模式 # 访问者模式 # 迭代器模式 # 中介者模式 # 备忘录模式 # 解释器模式 # 状态模式 # 策略模式 # 职责链模式 # 模板方法模式 # 代理模式 # 享元模式 # 桥接模式 # 外观模式 # 组合模式 # 适配器模式 # 建造者模式 # 原型模式 # 工场模式 # 单例 # UML # 锁 # 事务 # sql # 索引
两数之和
  • 文章目录
  •   |  
  • 概览
林亦庭

林亦庭

less can be more

87 文章
11 分类
54 标签
RSS
Github
Creative Commons
© 2021 林亦庭
粤ICP备20029050号