当前位置:网站首页>Leetcode.3 无重复字符的最长子串——超过100%的解法
Leetcode.3 无重复字符的最长子串——超过100%的解法
2022-07-06 09:21:00 【李孛欢】
题目:给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串 的长度。
示例1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是"abc",所以其长度为 3。
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1
代码如下:
public int lengthOfLongestSubstring(String s) {
if(s == null || s.equals("")){
return 0;
}
//以i结尾往左推多远不重复 (考虑a上次出现的位置以及i-1能推多远)
char[] chars = s.toCharArray();
int n = chars.length;
//0-255的ASCII码 用256长度数组能表示所有字符 ASCii码一个字节 最长256 不过目前是定义了128个字符
//map[i] = v 代表i这个ascii码上次出现在v位置
//char字符放入map数组中会自动转化为int类型 其值就是char字符的ascii码值 比如'a'就是97
int[] map = new int[128];
for(int i = 0; i < map.length; i++){
map[i] = -1;//代表所有字符都在-1位置出现过
}
int ans = 1;//初始答案
int pre = 1;//上一个位置向左推了多长(包括自己)
map[chars[0]] = 0;//第一个字符在
for(int i = 1; i < n; i++){
//考虑字符char[i]上一次出现的位置
//例如adcba 01234那么长度就是字符char[i]现在的位置i减去上一次位置map[char[i]]
// 4 - 0 = 4 也就是dcba
int p1 = i -map[chars[i]];
//考虑前一个位置向左推了多少 加上自己 就是自己能推的位置
int p2 = pre + 1;
//取二者最小值就是现在位置能向前推的长度
int cur = Math.min(p1,p2);
//取所有答案的最大值
ans = Math.max(ans,cur);
//后面继续循环,所以更新pre 和char[i]上一次出现的位置
pre = cur;
map[chars[i]] = i;
}
return ans;
}
主要的思想还是动态规划,考虑的是以i结尾的字符能够往前推多远,这与前一个字符能往前推多远有关,用一个数组map存储该字符上次出现的位置,初始化为-1,是为了在计算距离时,计算式子统一。
边栏推荐
- 5月27日杂谈
- 魏牌:产品叫好声一片,但为何销量还是受挫
- 20220211-CTF-MISC-006-pure_ Color (use of stegsolve tool) -007 Aesop_ Secret (AES decryption)
- Abstract classes and interfaces
- C语言入门指南
- First acquaintance with C language (Part 1)
- 抽象类和接口的区别
- 2. C language matrix multiplication
- 杂谈0516
- Questions and answers of "Fundamentals of RF circuits" in the first semester of the 22nd academic year of Xi'an University of Electronic Science and technology
猜你喜欢
Questions and answers of "signal and system" in the first semester of the 22nd academic year of Xi'an University of Electronic Science and technology
Decomposition relation model of the 2022 database of tyut Taiyuan University of Technology
Rich Shenzhen people and renting Shenzhen people
ABA问题遇到过吗,详细说以下,如何避免ABA问题
2.C语言初阶练习题(2)
arduino+DS18B20温度传感器(蜂鸣器报警)+LCD1602显示(IIC驱动)
一段用蜂鸣器编的音乐(成都)
MPLS experiment
9. Pointer (upper)
Relational algebra of tyut Taiyuan University of technology 2022 database
随机推荐
杂谈0516
【九阳神功】2022复旦大学应用统计真题+解析
arduino+DS18B20温度传感器(蜂鸣器报警)+LCD1602显示(IIC驱动)
TYUT太原理工大学2022数据库大题之E-R图转关系模式
View UI Plus 发布 1.2.0 版本,新增 Image、Skeleton、Typography组件
List set map queue deque stack
TYUT太原理工大学2022数据库大题之概念模型设计
【九阳神功】2020复旦大学应用统计真题+解析
西安电子科技大学22学年上学期《射频电路基础》试题及答案
Quickly generate illustrations
The latest tank battle 2022 full development notes-1
5.MSDN的下载和使用
Cloud native trend in 2022
TYUT太原理工大学2022数据库考试题型大纲
Mortal immortal cultivation pointer-1
Network layer 7 protocol
Cookie和Session的区别
Implement queue with stack
E-R graph to relational model of the 2022 database of tyut Taiyuan University of Technology
TYUT太原理工大学2022“mao gai”必背