Zookeeper使用 php delphi vuejs2 bluetooth Backbonejs Keys.js vue过滤器 网络营销视频 sql视频教程 oracle删除字段sql spark数据清洗 mysql修改字段值 java常用的包 excel被保护怎么解除 kafka学习 java时间戳 mysql查询结果拼接 oracle数据库创建表空间 python中的range函数 javasubstring java开发者 java开发学习 java8时间 java编程语言 java将数据写入文件 java运行 linux密码 网页游戏代码 bcdautofix sql综合利用工具 xp系统修复 千千静听绿色版 redis入门指南 m4a转mp3格式转换器 winhex使用教程 数据挖掘原理与算法 博途v14安装教程 还原软件哪个好 茸好珠
当前位置: 首页 > 学习教程  > 编程语言

2020-11-24每日一题3、无重复的最长子串

2020/11/24 10:49:07 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2: 输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”&#…

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

示例 1:

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

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

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

知识补充:哈希集合
哈希集合讲解htt
介绍
哈希表是一种使用哈希函数组织数据,以支持快速插入和搜索的数据结构。

有两种不同类型的哈希表:哈希集合和哈希映射。

哈希集合是集合数据结构的实现之一,用于存储非重复值。
哈希映射是映射 数据结构的实现之一,用于存储(key, value)键值对。
在标准模板库的帮助下,哈希表是易于使用的。大多数常见语言(如Java,C ++ 和 Python)都支持哈希集合和哈希映射。

通过选择合适的哈希函数,哈希表可以在插入和搜索方面实现出色的性能。
原理
哈希表的关键思想是使用哈希函数将键映射到存储桶。更确切地说,

当我们插入一个新的键时,哈希函数将决定该键应该分配到哪个桶中,并将该键存储在相应的桶中;
当我们想要搜索一个键时,哈希表将使用相同的哈希函数来查找对应的桶,并只在特定的桶中进行搜索。
在这里插入图片描述
在示例中,我们使用 y = x % 5 作为哈希函数。让我们使用这个例子来完成插入和搜索策略:

插入:我们通过哈希函数解析键,将它们映射到相应的桶中。

例如,1987 分配给桶 2,而 24 分配给桶 4。
搜索:我们通过相同的哈希函数解析键,并仅在特定存储桶中搜索。

如果我们搜索 1987,我们将使用相同的哈希函数将1987 映射到 2。因此我们在桶 2 中搜索,我们在那个桶中成功找到了 1987。
例如,如果我们搜索 23,将映射 23 到 3,并在桶 3 中搜索。我们发现 23 不在桶 3 中,这意味着 23 不在哈希表中。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合,记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格,移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

本文链接: http://www.dtmao.cc/news_show_400353.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?