欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【算法题】无重复字符的最长子串

程序员文章站 2024-02-25 09:45:04
...
问题:

给定一个字符串,找出不含有重复字符的最长子串的长度。

示例:

给定 "abcabcbb" ,没有重复字符的最长子串是 "abc" ,那么长度就是3。

给定 "bbbbb" ,最长的子串就是 "b" ,长度是1。

给定 "pwwkew" ,最长子串是 "wke" ,长度是3。请注意答案必须是一个子串"pwke" 是 子序列  而不是子串。

思路:

首先要保存遍历到未重复的字符,这里可以用哈希表,当然python里可以用字典,C/C++可以用128位的数组标志ascii码中的128位字符。这道题主要就是考虑子串的起点和终点在哪里,起点不能简单地从重复字符开始算,因为重复字符之间肯定没有其他重复字符了,所以这里需要用两个标志标注子串的起点和终点,当重复了以后,则从上一个起点的下一个字符开始遍历。

代码:c/C++

#include <iostream>
#include <vector>
using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

int lengthOfLongestSubstring(string s) {
	int zimu[256] = {0};
	int len = 0;
	int max = len;
	int n_iter = 0;
	int pre = n_iter;
	while( n_iter < s.size())//直到整个字符串都遍历完成
	{
		
		if(zimu[s[n_iter]] == 1)//如果当前的子串有该字符
		{
			
			if(max < len)//找到最大的长度
			{
				max =len;
			}
			
		
			for(int j = 0;j<256;j++)//清空标志位
			{
				zimu[j] = 0;
				
			}
			
			n_iter = pre +1;//从上一个起点的下一个字符开始
			pre = n_iter;//更新起点为现在开始遍历的位置
			zimu[s[n_iter]] =1;
			len = 1;
		}
		else
		{
			len ++;if(len>max) max =len;//找到最大的长度
			zimu[s[n_iter]] =1;
		}
		n_iter ++;
	}
	return max;
}

int main()
{
	printf("%d\n",lengthOfLongestSubstring("dvdf"));
	return 0;
}

相关标签: 算法