当前位置：网站首页>Leetcode skimming -- bit by bit record 022

Leetcode skimming -- bit by bit record 022

2022-07-23 10:44:00 【Robust least squares support vector machine】

22. The finger of the sword Offer 48. The longest substring without repeating characters

requirement

Please find the longest substring in the string that does not contain duplicate characters , Calculate the length of the longest substring .

Ideas

Dynamic programming ：

State definition ： Set up a dynamic programming list dp ,dp[j] Represents with the character s[j] For the end of “ The longest non repeating substring ” The length of
Transfer equation ： Fixed right border j, Set character s[j] The same character nearest to the left is s[i], namely s[i]=s[j]
When dp[j - 1] < j - i , Description character s[i] In substring dp[j-1] Out of range , be dp[j] = dp[j - 1] + 1
When dp[j−1] ≥ j−i , Description character s[i] In substring dp[j-1] In the interval , be dp[j] The left boundary of is bounded by s[i] decision , namely dp[j] = j - i
Return value ： max(dp) , That is, the overall situation “ The longest non repeating substring ” The length of

Problem solving

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

class Solution {
    
public:
    int lengthOfLongestSubstring(string s) {
    
        int len = s.size();
        if (s.empty()) 
            return 0;
        vector<int> dp(len + 1, 0);
        for (int j = 1; j < len; j++)
        {
    
            int i = j - 1;
            while (i >= 0 && s[i] != s[j]) 
                i--;                //  Linear search i
            dp[j] = dp[j - 1] < j - i ? dp[j - 1] + 1 : j - i;  // dp[j - 1] -> dp[j]
        }
        return *max_element(dp.begin(), dp.end());    //  Maximum , Dereference value  max(dp[j - 1], dp[j])
    }
};


void test01()
{
    
    Solution solution;
    string s = "abcabcbb";
    cout << solution.lengthOfLongestSubstring(s) << endl;
}

int main()
{
    
    test01();

    system("pause");
    return 0;
}