2022年2月12日

数据结构

387 字符串中的第一个唯一字符

遍历一次计数，再遍历看出现次数。

class Solution {
public:
    int firstUniqChar(string s) {
        int a[1000];
        memset(a,0,sizeof(a));
        int l=s.length();
        for(int i=0;i<l;i++){
            a[int(s[i])]++;
        }
        for(int i=0;i<l;i++){
            if(a[int(s[i])]==1)
                return i;
        }
        return -1;
    }
};

383 赎金信

与上题思路相同

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int a[1000];
        memset(a,0,sizeof(a));
        int l1=magazine.length();
        int l2=ransomNote.length();
        for(int i=0;i<l1;i++){
            a[int(magazine[i])]++;
        }
        for(int i=0;i<l2;i++){
            a[int(ransomNote[i])]--;
            if(a[int(ransomNote[i])]<0)
                return false;
        }
        return true;
    }
};

242 有效的字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) {
        int a[1000];
        memset(a,0,sizeof(a));
        int l1=s.length();
        int l2=t.length();
        for(int i=0;i<l1;i++){
            a[int(s[i])]++;
        }
        for(int i=0;i<l2;i++){
            a[int(t[i])]--;
            if(a[int(t[i])]<0)
                return false;
        }
        for(int i=0;i<1000;i++){
            if(a[i]!=0)
                return false;
        }
        return true;
    }
};

算法——滑动窗口

3 无重复字符的最长子串

滑动窗口的思想

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        //s[start,end) 前面包含 后面不包含
        int start(0), end(0), length(0), result(0);
        int sSize = int(s.size());
        while (end < sSize)
        {
            char tmpChar = s[end];
            for (int index = start; index < end; index++)
            {
                if (tmpChar == s[index])
                {
                    start = index + 1;
                    length = end - start;
                    break;
                }
            }

            end++;
            length++;
            result = max(result, length);
        }
        return result;
    }
};

作者：pinku-2
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-cshi-xian-/
来源：力扣（LeetCode）

567 字符串的排列

在s2中判定是否存在s1的字串

通过s1的长度n，遍历s2中所有长度为n的字串，然后判定字串中字符数量是否与s1中相同

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n=s1.length(),m=s2.length();
        if(n>m){
        return false;
        }
        vector<int> cnt1(26),cnt2(26);
        for(int i=0;i<n;i++){
            ++cnt1[s1[i]-'a'];
            ++cnt2[s2[i]-'a'];
        }
        if(cnt1==cnt2){
            return true;
        }
        for(int i=n;i<m;++i){
            ++cnt2[s2[i]-'a'];
            --cnt2[s2[i-n]-'a'];
            if(cnt1==cnt2){
                return true;
            }
        }
        return false;
    }
};