文档章节

LeetCode[Day 3] Longest Substring Without... 题解

yamamaki
 yamamaki
发布于 2014/04/22 07:26
字数 274
阅读 42
收藏 0

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.


思路

这道题比之前的两题都要简单,思路就是一句话:用数组记录下来每个字符最后出现的位置。

要注意的地方有两个

  1. 数组的大小应该是256,那是因为对应的ASCII码有256个。

  2. 每次更新字符最后出现位置时,同时也要更新当前子串长度,要考虑上一次该字符是否出现在当前子串中。

    比如"assdfgha"和"asdfgd"这两种情况下更新子串长度的方法是不一样的。


代码

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        int ret = 0;
        int len = 0;
        int idx = -1;
        int alphabet[256] = {0};
        for (int i=0; i<256; ++i) alphabet[i] = -1;
        const char* c = s.c_str();
        while (*c)
        {
            idx = idx+1;
            if (alphabet[*c] == -1)
            {
                len = len+1;
                alphabet[*c] = idx;
            }
            else
            {
                len = (len+1>idx-alphabet[*c])?(idx-alphabet[*c]):(len+1); //important!
                alphabet[*c] = idx;
            }
            ret = (len>ret)?len:ret;
            c = c+1;
        }
        return ret;
    }
};



© 著作权归作者所有

yamamaki
粉丝 0
博文 7
码字总数 3384
作品 0
黄浦
私信 提问
LeetCode 攻略 - 2019 年 8 月上半月汇总(109 题攻略)

LeetCode 汇总 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently revised in 2019-08-15 16:37:20 一 目录 不折腾的前端,和咸鱼有什么区别 目录 一 目录 二 前言 三 汇总 ...

jsliang
前天
0
0
Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", whic......

jdflyfly
2014/06/24
1K
0
[leetcode] Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. ht......

jdflyfly
2014/06/24
627
0
leetcode-algorithms-3 Longest Substring Without Repeating Characters

leetcode-algorithms-3 Longest Substring Without Repeating Characters Given a string, find the length of the longest substring without repeating characters. Example 1: Example 2:......

mathli
2018/11/15
0
0
leetcode刷题,没想到这么难搞!

leetcode之前提交的代码不见了,所以在这里记一下 https://leetcode.com/problems/longest-substring-without-repeating-characters/...

fromdtor
2016/10/13
29
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Cloud 笔记之Spring cloud config client

观察者模式它的数据的变化是被动的。 观察者模式在java中的实现: package com.hxq.springcloud.springcloudconfigclient;import org.springframework.context.ApplicationListener;i...

xiaoxiao_go
今天
4
0
CentOS7.6中安装使用fcitx框架

内容目录 一、为什么要使用fcitx?二、安装fcitx框架三、安装搜狗输入法 一、为什么要使用fcitx? Gnome3桌面自带的输入法框架为ibus,而在使用ibus时会时不时出现卡顿无法输入的现象。 搜狗和...

技术训练营
今天
4
0
《Designing.Data-Intensive.Applications》笔记 四

第九章 一致性与共识 分布式系统最重要的的抽象之一是共识(consensus):让所有的节点对某件事达成一致。 最终一致性(eventual consistency)只提供较弱的保证,需要探索更高的一致性保证(stro...

丰田破产标志
今天
7
0
docker 使用mysql

1, 进入容器 比如 myslq1 里面进行操作 docker exec -it mysql1 /bin/bash 2. 退出 容器 交互: exit 3. mysql 启动在容器里面,并且 可以本地连接mysql docker run --name mysql1 --env MY...

之渊
今天
7
0
python数据结构

1、字符串及其方法(案例来自Python-100-Days) def main(): str1 = 'hello, world!' # 通过len函数计算字符串的长度 print(len(str1)) # 13 # 获得字符串首字母大写的...

huijue
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部