[算法]leetcode-02:计算字符串中最大无重复子字符串长度

leetcode中有这样一道算法题:
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.
大意是求字符串中的最大无重复字符串,因为leetcode并不支持php,所有这里用C++给出算法,代码如下:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> map;
		int len = s.length();
		int start = 0;
		int max   = 0;
		int cur   = 0;
		for(int i=0; i<len; i++) {
		
			char ch = s[i];
			if(map.find(ch) != map.end()) {

				start = start > (map[ch] + 1) ? start : (map[ch] + 1);
			}
			cur = i - start + 1;
			map[ch] = i;
			max = cur > max ? cur : max;

		}
        //cout<<max<<endl;
		return max;
    }
};

背景:
这里用到了C++中的 unordered_map,其中的map.find()函数是查找这个map中是否保存了这个值。结果可以用auto类型保存。
例如:auto res = map.find(‘a’);而res->first 是其中的key, res->second 是value.
如果在php中,随意的一个array类型都可以实现如上效果,通过isset($str[‘a’])也可以判断是否保存了此变量。
算法:
代码比较短,通过一次遍历O(n),查找字符串中这个值是否在map中,如果没在,存入这个map中,计算长度。如果在map中,start位置变为该map值和start的较大者,防止(“abba”)这种情况。然后计算长度。
总结:
改算法题并不是很难,主要考察是否会应用map这种数据结构类型。当然在php代码中,一个array可以代替同样的效果。

发表评论

邮箱地址不会被公开。 必填项已用*标注


*