当前位置:网站首页>Leetcode. 3. Longest substring without repeated characters - more than 100% solution
Leetcode. 3. Longest substring without repeated characters - more than 100% solution
2022-07-06 13:36:00 【Li bohuan】
subject : Given a string s
, Please find out that there are no duplicate characters in it Longest substrings The length of .
Example 1:
Input : s = "abcabcbb" Output : 3 explain : Because the longest substring without repeating characters is"abc", So its The length is 3.
Input : s = "bbbbb" Output : 1 explain : Because the longest substring without repeating characters is "b", So its length is 1
The code is as follows :
public int lengthOfLongestSubstring(String s) {
if(s == null || s.equals("")){
return 0;
}
// With i How far to the left do you push the end without repeating ( consider a The location of the last occurrence and i-1 How far can we push )
char[] chars = s.toCharArray();
int n = chars.length;
//0-255 Of ASCII code use 256 The length array can represent all characters ASCii Code a byte The longest 256 But now it is defined 128 Characters
//map[i] = v representative i This ascii Code last appeared in v Location
//char Put characters in map The array will be automatically converted to int type Its value is char Character ascii Code value such as 'a' Namely 97
int[] map = new int[128];
for(int i = 0; i < map.length; i++){
map[i] = -1;// Means that all characters are in -1 The position has appeared
}
int ans = 1;// Initial answer
int pre = 1;// How long did the previous position push to the left ( Including myself )
map[chars[0]] = 0;// The first character is in
for(int i = 1; i < n; i++){
// Consider the character char[i] Where it was last seen
// for example adcba 01234 Then length is character char[i] The present position i Subtract the last position map[char[i]]
// 4 - 0 = 4 That is to say dcba
int p1 = i -map[chars[i]];
// Consider how much the previous position pushed to the left Add yourself Is the position you can push
int p2 = pre + 1;
// The minimum value of the two is the length that the current position can be pushed forward
int cur = Math.min(p1,p2);
// Take the maximum of all the answers
ans = Math.max(ans,cur);
// Continue the cycle later , So update pre and char[i] Where it was last seen
pre = cur;
map[chars[i]] = i;
}
return ans;
}
The main idea is dynamic planning , Considering that i How far can the ending character be pushed forward , This is related to how far the previous character can be pushed forward , Use an array map Store the last occurrence of this character , Initialize to -1, In order to calculate the distance , The calculation formula is unified .
边栏推荐
- 【九阳神功】2018复旦大学应用统计真题+解析
- Redis cache obsolescence strategy
- [the Nine Yang Manual] 2017 Fudan University Applied Statistics real problem + analysis
- Set container
- View UI Plus 發布 1.3.1 版本,增强 TypeScript 使用體驗
- Share a website to improve your Aesthetics
- 5. Function recursion exercise
- 【九阳神功】2019复旦大学应用统计真题+解析
- Leetcode.3 无重复字符的最长子串——超过100%的解法
- 【手撕代码】单例模式及生产者/消费者模式
猜你喜欢
C语言实现扫雷游戏(完整版)
西安电子科技大学22学年上学期《射频电路基础》试题及答案
关于双亲委派机制和类加载的过程
There is always one of the eight computer operations that you can't learn programming
2.初识C语言(2)
受检异常和非受检异常的区别和理解
Decomposition relation model of the 2022 database of tyut Taiyuan University of Technology
3. C language uses algebraic cofactor to calculate determinant
最新坦克大战2022-全程开发笔记-1
5. Function recursion exercise
随机推荐
Quickly generate illustrations
3.猜数字游戏
2. C language matrix multiplication
自定义RPC项目——常见问题及详解(注册中心)
9.指针(上)
3.C语言用代数余子式计算行列式
View UI plus released version 1.3.1 to enhance the experience of typescript
There is always one of the eight computer operations that you can't learn programming
1.C语言初阶练习题(1)
View UI plus releases version 1.1.0, supports SSR, supports nuxt, and adds TS declaration files
【手撕代码】单例模式及生产者/消费者模式
一段用蜂鸣器编的音乐(成都)
2. Preliminary exercises of C language (2)
Aurora system model of learning database
(原创)制作一个采用 LCD1602 显示的电子钟,在 LCD 上显示当前的时间。显示格式为“时时:分分:秒秒”。设有 4 个功能键k1~k4,功能如下:(1)k1——进入时间修改。
hashCode()与equals()之间的关系
受检异常和非受检异常的区别和理解
View UI plus released version 1.2.0 and added image, skeleton and typography components
[中国近代史] 第五章测验
View UI plus released version 1.3.0, adding space and $imagepreview components