剑指offer(C++)-JZ48:最长不含重复字符的子字符串(算法-动态规划)

简介: 剑指offer(C++)-JZ48:最长不含重复字符的子字符串(算法-动态规划)

题目描述:

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

数据范围:

s.length≤40000 s.length≤40000

示例:

输入:

"abcabcbb"


返回值:

3


说明:

因为无重复字符的最长子串是"abc",所以其长度为 3。

解题思路:

本题是动态规划的经典题目。有两个解题思路。

思路一:滑动窗口

  1. 设计一个滑动窗口,窗口的右边界先行,用哈希表统计字符出现次数。
  2. 当出现重复字符时,左边界出发缩小窗口直到重复字符消失。
  3. 持续刷新最值就可以了。


思路二:动态规划


  1. 用哈希表存放字符上次出现的位置下标;用长度比字符串大1的vector,存放截止到第i个字符时,能继续维持的子串长度,比如v[0]=0,v[1]=1,v[2]可能为1可能为2。
  2. 执行遍历。用哈希表判断当前字符是否为重复字符,如果不是重复字符,那就在前面子串长度基础上加1;若出现了重复字符,则该字符与其重复字符的距离为i-m[s[i]],但如果两者之间有别的重复字符,则需要考虑此类情况,可以认为在其重复字符之后的子串中,该字符未出现过,则有v[i]+1;所以,比较v[i]+1和i-m[s[i]]谁小取谁,因为小的子串没断开,后续可以继续连接,而断开的子串虽然长度大,但不可以继续增加了。
  3. 持续更新字符最新下标以及子串长度最大值。

测试代码:

思路一:滑动窗口

class Solution {
public:
    // 最长子串
    int lengthOfLongestSubstring(string s) {
        // 定义哈希表
        unordered_map<char, int> m;
        // 滑动窗口遍历
        int result = 0;
        for(int left = 0, right = 0; right < s.length(); ++right){
            // 窗口右边界先行,统计字符出现次数
            m[s[right]]++;
            // 当出现重复字符,窗口左边界右移缩小窗口直到重复字符消失
            while(m[s[right]] > 1){
                m[s[left]]--;
                left++;
            }
            // 持续刷新子串最大长度
            result = max(result, right - left + 1);
        }
        return result;
    }
};

思路二:动态规划

class Solution {
public:
    // 最长子串
    int lengthOfLongestSubstring(string s) {
        // 定义哈希表,存放的是字符出现的位置下标
        unordered_map<char, int> m;
        int result = 0;
        // v[i]表示截止到i个字符时,能继续维持的子串长度
        // 所以v[0]=0,v[1]=1
        vector<int> v = vector<int>(s.length() + 1, 0);
        // i是字符串中字符下标
        for(int i = 0; i < s.length(); ++i){
            // 当哈希表中没发现重复字符,那就在前面最长子串长度基础上+1
            if(m.find(s[i]) == m.end())
                v[i + 1] = v[i] + 1;
            // 若出现了重复字符,该字符与其重复字符的距离为i-m[s[i]]
            // 但如果两者之间有别的重复字符,那要考虑这类情况
            // 可以认为在其重复字符之后的子串中,该字符未出现过,则有v[i]+1
            // 所以v[i]+1和i-m[s[i]]谁小,取谁,因为小的这个子串没断开
            else
                v[i + 1] = min(v[i] + 1, i - m[s[i]]);
            // 刷新该字符最新下标
            m[s[i]] = i;
            // 刷新最值
            result = max(result, v[i + 1]);
        }
        return result;
    }
};


目录
打赏
0
0
0
0
17
分享
相关文章
|
14天前
|
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
36 1
Windows共享文件:探秘C++实现的B树索引算法奇境
在数字化时代,Windows共享文件的高效管理至关重要。B树算法以其自平衡多路搜索特性,在文件索引与存储优化中表现出色。本文探讨B树在Windows共享文件中的应用,通过C++实现具体代码,展示其构建文件索引、优化数据存储的能力,提升文件检索效率。B树通过减少磁盘I/O操作,确保查询高效,为企业和个人提供流畅的文件共享体验。
解读 C++ 助力的局域网监控电脑网络连接算法
本文探讨了使用C++语言实现局域网监控电脑中网络连接监控的算法。通过将局域网的拓扑结构建模为图(Graph)数据结构,每台电脑作为顶点,网络连接作为边,可高效管理与监控动态变化的网络连接。文章展示了基于深度优先搜索(DFS)的连通性检测算法,用于判断两节点间是否存在路径,助力故障排查与流量优化。C++的高效性能结合图算法,为保障网络秩序与信息安全提供了坚实基础,未来可进一步优化以应对无线网络等新挑战。
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中,迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点,确保高效稳定的网络环境。该算法通过计算最短路径,提升数据传输速率与稳定性,实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用,为企业信息化建设提供有力支持。
85 15
公司局域网管理中的哈希表查找优化 C++ 算法探究
在数字化办公环境中,公司局域网管理至关重要。哈希表作为一种高效的数据结构,通过哈希函数将关键值(如IP地址、账号)映射到数组索引,实现快速的插入、删除与查找操作。例如,在员工登录验证和设备信息管理中,哈希表能显著提升效率,避免传统线性查找的低效问题。本文以C++为例,展示了哈希表在局域网管理中的具体应用,包括设备MAC地址与IP分配的存储与查询,并探讨了优化哈希函数和扩容策略,确保网络管理高效准确。
基于 C++ 哈希表算法的局域网如何监控电脑技术解析
当代数字化办公与生活环境中,局域网的广泛应用极大地提升了信息交互的效率与便捷性。然而,出于网络安全管理、资源合理分配以及合规性要求等多方面的考量,对局域网内计算机进行有效监控成为一项至关重要的任务。实现局域网内计算机监控,涉及多种数据结构与算法的运用。本文聚焦于 C++ 编程语言中的哈希表算法,深入探讨其在局域网计算机监控场景中的应用,并通过详尽的代码示例进行阐释。
49 4
企业员工数据泄露防范策略:基于 C++ 语言的布隆过滤器算法剖析[如何防止员工泄密]
企业运营过程中,防范员工泄密是信息安全领域的核心议题。员工泄密可能致使企业核心数据、商业机密等关键资产的流失,进而给企业造成严重损失。为应对这一挑战,借助恰当的数据结构与算法成为强化信息防护的有效路径。本文专注于 C++ 语言中的布隆过滤器算法,深入探究其在防范员工泄密场景中的应用。
55 8
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
90 15
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
97 12
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
52 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等