当前位置:网站首页>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 .
边栏推荐
- There is always one of the eight computer operations that you can't learn programming
- 3.输入和输出函数(printf、scanf、getchar和putchar)
- 5.函数递归练习
- string
- 5. Download and use of MSDN
- Data manipulation language (DML)
- C语言入门指南
- 受检异常和非受检异常的区别和理解
- Relational algebra of tyut Taiyuan University of technology 2022 database
- [Topic terminator]
猜你喜欢
View UI plus released version 1.2.0 and added image, skeleton and typography components
Mortal immortal cultivation pointer-1
凡人修仙学指针-2
System design learning (I) design pastebin com (or Bit.ly)
5. Function recursion exercise
Database operation of tyut Taiyuan University of technology 2022 database
5. Download and use of MSDN
MySQL事务及实现原理全面总结,再也不用担心面试
arduino+水位传感器+led显示+蜂鸣器报警
View UI Plus 发布 1.2.0 版本,新增 Image、Skeleton、Typography组件
随机推荐
[中国近代史] 第九章测验
Service ability of Hongmeng harmonyos learning notes to realize cross end communication
这次,彻底搞清楚MySQL索引
3.猜数字游戏
Aurora system model of learning database
Database operation of tyut Taiyuan University of technology 2022 database
西安电子科技大学22学年上学期《信号与系统》试题及答案
[the Nine Yang Manual] 2020 Fudan University Applied Statistics real problem + analysis
Alibaba cloud microservices (III) sentinel open source flow control fuse degradation component
hashCode()与equals()之间的关系
杂谈0516
Share a website to improve your Aesthetics
View UI plus released version 1.3.1 to enhance the experience of typescript
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
最新坦克大战2022-全程开发笔记-1
View UI Plus 發布 1.3.1 版本,增强 TypeScript 使用體驗
仿牛客技术博客项目常见问题及解答(一)
5.MSDN的下载和使用
4. Binary search
C语言实现扫雷游戏(完整版)