BAT面试算法进阶(4)- 无重复字符的最长子串(滑动法优化+ASCII码法)
2023-06-13 09:17:38 时间
上一次分享的是滑动窗口解决方法.执行的次数2N个步骤.但是是否还有办法优化了? 答案是肯定的!
一.算法题
题目
Given a string, find the length of the longest substring without repeating characters.
Example
- Given "abcabcbb", the answer is "abc", which the length is 3.
- Given "bbbbb", the answer is "b", with the length of 1.
- Given "pwwkew", the answer is "wke", with the length of
- Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
二.算法题解读
题目大意:给定一个字符串,找出不含有重复字符的最长子串的长度
解读Example
- 给定"abcabcbb",没有重复字符的最长子串是"abc",那么长度就是3
- 给定"bbbbb",最长子串就是"b",长度就是1
- 给定pwwkew,最长子串就是"wke",长度为3,
- 注意,必须是一个子串."pwke",是子序列,而不是子串
三.优化"滑动窗口"解决思路
到底如何在滑动窗口方法上优化了? 实际上我们可以如果采用进一步优化,可以达到只需要N次即可计算成功.我们可以定义字符到索引映射.而不是使用集合来判断这个字符的存在与否.当遇到重复的字符时,我们即可跳过该滑动窗口.
也可以理解为,如果s[j]
在[i,j)
的范围内有与j'
重复的字符.我们不需要逐渐增加i
.而是直接跳过[i,j']
范围内的所有元素.并将i
变成为j'+1
就可以做到.
四.代码实现
Java code
五.使用ASCII 128码 思路
字符串,其实由字符构成.而字符则可以用ASC码来替代.如此,我们可以用整数数组作为直接访问表来替换Map.
常用表如下:
int [26],用于表示字母 "a" - "z" 或 "A" - "Z"
;
int [128],用于表示ASCII码
int [256],用于表示扩展ASCII码
A = 65, a = 97
六.代码实现
java code
相关文章
- ReverseFind的用法 ; 查找字符中最后一个字符
- 三分钟算法修行-无重复字符的最长子串的《四种解法》
- 【Java基础-3】吃透Java IO:字节流、字符流、缓冲流
- 罗马字符转整数(python)
- 【Node.js算法题】数组去重、数组删除元素、数组排序、字符串排序、字符串反向、字符串改大写 、数组改大写、字符替换
- 字符统计(算法)
- BAT面试算法进阶(3)- 无重复字符的最长子串(滑动窗口法)
- 库函数之字符函数与字符串函数(下)
- 字符函数和字符串函数的使用及模拟实现(上)
- mysql实现向某个字段前或后添加字符
- 算法-字符流中第一个不重复的字符详解编程语言
- 字符利用Oracle中冒号转义字符的奇妙之处(oracle冒号转义)
- Linux 中获取输入字符的方法(linux获取输入字符)
- MySQL中实现取字符的函数使用(mysql取字符函数)
- Linux C:优雅处理中文字符编码(linuxc处理中文)
- javascript中使用replaceAll()函数实现字符替换的方法
- Javascript中查找不以XX字符结尾的单词示例代码