Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1435272
  • 博文数量: 241
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 2253
  • 用 户 组: 普通用户
  • 注册时间: 2012-04-11 22:27
个人简介

--

文章分类

全部博文(241)

文章存档

2021年(3)

2019年(6)

2018年(1)

2017年(9)

2016年(21)

2015年(50)

2014年(125)

2013年(26)

我的朋友

分类: C/C++

2013-12-25 19:22:49

题目:Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
分析:从头开始记录每个字母出现次数,如果出现过则计算目前子串长度,并从此处开始新的子串检测。
参考链接:http://blog.csdn.net/ojshilu/article/details/12168533
代码:

点击(此处)折叠或打开

  1. #include <iostream>

  2. using namespace std;

  3. class Test
  4. {
  5.     public:
  6.         int exsit_status[30] ;

  7.         bool IsExisit(char alp)
  8.         {
  9.             if ( (alp >= 'a') && (alp<= 'z') )
  10.             {
  11.                 if (exsit_status[alp - 'a'] == 0)
  12.                     return false;
  13.                 else
  14.                     return true;
  15.             }
  16.         }
  17.         void addStatus(char alp)
  18.         {
  19.             if ( (alp >= 'a') && (alp<= 'z') )
  20.             {
  21.                exsit_status[alp - 'a'] = 1;
  22.             }
  23.         }
  24.         void clearStatus()
  25.         {
  26.             char alp;
  27.             for (alp='a'; alp<='z'; alp++)
  28.             {
  29.                 exsit_status[alp-'a'] = 0;
  30.             }
  31.         }
  32.         int LongestSubstr(string str)
  33.         {
  34.             if (str == "")
  35.                 return 0;

  36.             int len = str.length();
  37.             int max_len = 0;
  38.             int i,j;

  39.             clearStatus();
  40.             for (i=0; i<len; i++)
  41.             {
  42.                 for (j=i; j<len; j++)
  43.                 {
  44.                     if ( IsExisit(str[j]) == true )
  45.                     {
  46.                         if (max_len < j-i)
  47.                         {
  48.                             max_len = j-i;
  49.                         }
  50.                         clearStatus();
  51.                         i = j-1;
  52.                         break;
  53.                     }
  54.                     else
  55.                     {
  56.                         addStatus(str[j]);
  57.                     }
  58.                 }
  59.                 if (max_len < j-i)
  60.                 {
  61.                     max_len = j-i;
  62.                     break;
  63.                 }
  64.             }
  65.             return max_len;
  66.         }
  67. };


  68. int main()
  69. {
  70.     class Test my_test;
  71.     cout<<my_test.LongestSubstr("abcdcabc")<<endl;
  72.     return 0;
  73. }

阅读(837) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~