LeetCode 3. Longest Substring Without Repeating Characters

╰半橙微兮° 2022-05-27 07:50 259阅读 0赞

Given a string, find the length of the longest substring without repeating characters.

Examples:

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 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

解题思路：题中所描述的字符包括所有128个ASCII字符，定义一个数组alph记录每个字符出现的位置，并且用一个变量mark记录当前子串起点的位置，变量maxlen记录当前最长的子串的长度，字符的位置随着循环不断往后进行更新，如果出现字符的上一个位置在当前子串起点之后，更新起点的位置为当前字符上一个位置的后一位作为起点，同时判断是否需要更新maxlen。

C/C++

  1. int lengthOfLongestSubstring(char* s) {
  2.     int i = -1;
  3.     int alph[128] = {0};
  4.     for(int i=0;i<128;i++)alph[i]=-1;
  5.     int mark = -1;
  6.     int maxlen = 0;
  7.     while(s[i+1])
  8.     {
  9.         i++;
  10.         int tmp = s[i];
  11.         if(alph[tmp]>mark)
  12.         {
  13.             if(maxlen<i-mark-1)maxlen=i-mark-1;
  14.             mark = alph[tmp];
  15.         }
  16.         alph[tmp] = i;
  17.     }
  18.     if(maxlen<i-mark)maxlen=i-mark;
  19.     return maxlen;
  20. }

Java

  1. class Solution {
  2.     public int lengthOfLongestSubstring(String s) {
  3.         int[] alph = new int[128];
  4.         for(int i=0;i<128;i++)alph[i]=-1;
  5.         int i = -1;
  6.         int mark = -1;
  7.         int maxlen = 0;
  8.         while(i+1<s.length()) {
  9.             i++;
  10.             int tmp = s.charAt(i);
  11.             if(alph[tmp]>mark) {
  12.                 if(maxlen<i-mark-1)maxlen=i-mark-1;
  13.                 mark = alph[tmp];
  14.             }
  15.             alph[tmp] = i;
  16.         }
  17.         if(maxlen<i-mark)maxlen=i-mark;
  18.         return maxlen;
  19.     }
  20. }

Python

  1. class Solution:
  2.     def lengthOfLongestSubstring(self, s):
  3.         """
  4.         :type s: str
  5.         :rtype: int
  6.         """
  7.         alph = []
  8.         for i in range(128):alph.append(-1)
  9.         i = -1
  10.         mark = -1
  11.         maxlen = 0
  12.         while i+1<len(s):
  13.             i += 1
  14.             tmp = ord(s[i])#字符转整型要用函数，不可直接赋值
  15.             if alph[tmp]>mark:
  16.                 if maxlen<i-mark-1:maxlen=i-mark-1
  17.                 mark = alph[tmp]
  18.             alph[tmp] = i;
  19.         if maxlen<i-mark:maxlen=i-mark
  20.         return maxlen

发表评论

表情：
评论列表 （有 0 条评论，259人围观）

还没有评论，来说两句吧...

相关阅读