当前位置:网站首页>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 .
边栏推荐
- 5.MSDN的下载和使用
- 4.二分查找
- Alibaba cloud microservices (I) service registry Nacos, rest template and feign client
- Data manipulation language (DML)
- 5. Function recursion exercise
- Alibaba cloud microservices (II) distributed service configuration center and Nacos usage scenarios and implementation introduction
- String abc = new String(“abc“),到底创建了几个对象
- MySQL锁总结(全面简洁 + 图文详解)
- View UI Plus 发布 1.2.0 版本,新增 Image、Skeleton、Typography组件
- 最新坦克大战2022-全程开发笔记-3
猜你喜欢
西安电子科技大学22学年上学期《信号与系统》试题及答案
5. Download and use of MSDN
最新坦克大战2022-全程开发笔记-2
6. Function recursion
C语言入门指南
一段用蜂鸣器编的音乐(成都)
甲、乙机之间采用方式 1 双向串行通信,具体要求如下: (1)甲机的 k1 按键可通过串行口控制乙机的 LEDI 点亮、LED2 灭,甲机的 k2 按键控制 乙机的 LED1
Questions and answers of "basic experiment" in the first semester of the 22nd academic year of Xi'an University of Electronic Science and technology
Mortal immortal cultivation pointer-1
View UI plus released version 1.2.0 and added image, skeleton and typography components
随机推荐
View UI Plus 發布 1.3.1 版本,增强 TypeScript 使用體驗
更改VS主题及设置背景图片
C language Getting Started Guide
Floating point comparison, CMP, tabulation ideas
3. C language uses algebraic cofactor to calculate determinant
fianl、finally、finalize三者的区别
arduino+水位传感器+led显示+蜂鸣器报警
Caching mechanism of leveldb
System design learning (I) design pastebin com (or Bit.ly)
西安电子科技大学22学年上学期《射频电路基础》试题及答案
JS interview questions (I)
View UI Plus 发布 1.3.1 版本,增强 TypeScript 使用体验
【九阳神功】2017复旦大学应用统计真题+解析
13 power map
12 excel charts and arrays
用栈实现队列
【九阳神功】2019复旦大学应用统计真题+解析
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
Share a website to improve your Aesthetics
9.指针(上)