LeetCode.3.567(滑动窗口)

3.无重复字符的最长子串

class Solution {
  public:
    /*bool judge(string s) {
        for (int i = 1; i < s.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (s[i] == s[j])
                    return 0;
            }
        }
        return 1;
    }*/
    int lengthOfLongestSubstring(string s) {
        int len = 0;
        vector<int> sElem(128, -1);
        int left = 0, right = 1;
        sElem[s[left]] = 0;
        if (s.size() == 1)
            return 1;
        while (right < s.size()) {
            if (sElem[s[right]] == -1) {
                sElem[s[right]] = right;
                right++;
                len = right - left > len ? right - left : len;
            } else {
                for (; left <= sElem[s[right]]; left++) {
                    sElem[s[left]] = -1;
                }
            }
        }
        return len;
        // 987/987 cases passed (4 ms)
        // Your runtime beats 97.26 % of cpp submissions
        // Your memory usage beats 79.04 % of cpp submissions (7.4 MB)
        //*搜了搜滑动窗口的定义，也不知道这写的是不是滑动窗口的方法，但总之是利用哈希法解出来了
        /*int len = s.length();
        for (; len >= 1; len--) {
            for (int start = 0; start <= s.length() - len; start++) {
                if (judge(s.substr(start, len)))
                    return len;
            }
        }
        return len;*/
        //这次直接超时
        /*int len = 0;
        while (!s.empty()) {
            bool flag = 0;
            for (int i = 0; i < s.length(); i++) {
                if (flag)
                    break;
                for (int j = 0; j < i; j++) {
                    if (s[i] == s[j]) {
                        len = i > len ? i : len;
                        s = s.substr(j + 1);
                        flag = 1;
                        break;
                    }
                }
            }
            if (!flag) {
                len = s.length() > len ? s.length() : len;
                break;
            }
        }
        return len;*/
        // 987/987 cases passed (256 ms)
        // Your runtime beats 8.41 % of cpp submissions
        // Your memory usage beats 4.95 % of cpp submissions (582.7 MB)
    }
};

567.字符串的排列

class Solution {
  public:
    bool checkInclusion(string s1, string s2) {
        if (s1.length() > s2.length())
            return false;
        int windowSize = s1.size();
        vector<int> num1(26, 0);
        vector<int> num2(26, 0);
        for (int i = 0; i < windowSize; i++) {
            num1[s1[i] - 'a']++;
            num2[s2[i] - 'a']++;
        }
        for (int i = 0; i < s2.length() - windowSize; i++) {
            if (num1 == num2)
                return true;
            else {
                //向右滑窗：滑窗对于 hash 表的操作变为对应频率的增减
                num2[s2[i] - 'a']--;
                num2[s2[i + windowSize] - 'a']++;
            }
        }
        return num1 == num2; //最后一个没比较==，搞了我半天
        // 106/106 cases passed (4 ms)
        // Your runtime beats 96.15 % of cpp submissions
        // Your memory usage beats 75.17 % of cpp submissions (7.1 MB)
        /*if (s1.length() > s2.length())
            return false;
        vector<int> num1(26, 0);
        int len = s1.length();
        for (int i = 0; i < len; i++) {
            num1[s1[i] - 'a']++;
        }
        for (int i = 0; i <= (signed int)(s2.length() - len); i++) {
            vector<int> num2(num1.begin(), num1.end());
            int flag = 0;
            for (int j = i; j < i + len; j++) {
                num2[s2[j] - 'a']--;
                if (num2[s2[j] - 'a'] < 0) {
                    flag = 1;
                    break;
                }
            }
            if (flag)
                continue;
            return true;
        }
        return false;*/
        // 106/106 cases passed (260 ms)
        // Your runtime beats 7.38 % of cpp submissions
        // Your memory usage beats 7.01 % of cpp submissions (18.2 MB)
        //淦
    }
};