LeetCode 字符串(3)

Alex_Shen
2021-02-22 / 0 评论 / 0 点赞 / 66 阅读 / 2,918 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-03-31,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

Leetcode 题解 - 字符串

242. 两个字符串包含的字符是否完全相同

242. Valid Anagram (Easy)

Leetcode / 力扣

思路:可以用哈希表来映射字符与出现次数,然后比较两个字符串出现的字符数量是否相同。

    bool isAnagram(string s, string t)
    {
        if (s.length() != t.length())
            return false;
        map<char, int> mp;
        for (char ch : s)
            mp[ch]++;
        for (char ch : t)
        {
            mp[ch]--;
            if (mp[ch] < 0)
                return false;
        }
        return true;
    }

409. 计算一组字符集合可以组成的回文字符串的最大长度

409. Longest Palindrome (Easy)

Leetcode / 力扣

思路:利用哈希表记录字符的出现次数。最长回文串的构成方式是又多组偶数个数字符+一组奇数个数字符(放在回文串最中心)组成的,所以记录总数时就加上每个字符的最大偶数,并检验就否存在奇数个数的字符可以放在最中心。

    int longestPalindrome(string s)
    {
        map<char, int> mp;
        for (char ch : s)
            mp[ch]++;
        bool existOdd = false;
        int cnt = 0;
        for (auto it : mp)
        {
            if (!existOdd)
            {
                if (it.second % 2 == 1)
                    existOdd = true;
            }
            cnt += it.second % 2 == 0 ? it.second : it.second - 1;
        }
        return existOdd ? cnt + 1 : cnt;
    }

205. 字符串同构

205. Isomorphic Strings (Easy)

Leetcode / 力扣

思路:利用两个哈希表记录字符对应关系。(利用一个哈希表在检查时会错过多对一的情况)

    bool isIsomorphic(string s, string t)
    {
        unordered_map<char, char> mp1, mp2;
        int length = s.length();
        for (int i = 0; i < length; i++)
        {
            if (mp1.find(s[i]) == mp1.end() && mp2.find(t[i]) == mp1.end())
            {
                mp1.insert(pair<char, char>(s[i], t[i]));
                mp2.insert(pair<char, char>(t[i], s[i]));
            }
            else
            {
                if (mp1[s[i]] == t[i] && mp2[t[i]] == s[i])
                    continue;
                else
                    return false;
            }
        }
        return true;
    }

647. 回文子字符串个数

647. Palindromic Substrings (Medium)

Leetcode / 力扣

思路:双指针法。
首先确定回文串,就是找中心然后想两边扩散看是不是对称的就可以了。
在遍历中心点的时候,要注意中心点有两种情况。
一个元素可以作为中心点,两个元素也可以作为中心点。三个元素就可以由一个元素左右添加元素得到,四个元素则可以由两个元素左右添加元素得到。
所以我们在计算的时候,要注意一个元素为中心点和两个元素为中心点的情况。

作者:carlsun-2
链接:https://leetcode-cn.com/problems/palindromic-substrings/solution/647-hui-wen-zi-chuan-dong-tai-gui-hua-zh-6f7n/

int count(string s, int i, int j)
    {
        int cnt = 0;
        while (i >= 0 && j < s.length() && s[i] == s[j])
        {
            i--;
            j++;
            cnt++;
        }
        return cnt;
    }

    int countSubstrings(string s)
    {
        int n = s.length(), ans = 0;
        for (int i = 0; i < n; i++)
        {
            ans += count(s, i, i);
            ans += count(s, i, i + 1);
        }
        return ans;
    }

9. 判断一个整数是否是回文数

9. Palindrome Number (Easy)

Leetcode / 力扣

思路:数学方法,从左右获取每一位进行比对。

    bool isPalindrome(int x)
    {
        if (x < 0)
            return false;
        if (x == 0)
            return true;
        int n = int(log10(x)) + 1;
        for (int i = 0; i < n / 2; i++)
        {
            int left = x / pow(10, n - i - 1), right = x / pow(10, i);
            left %= 10, right %= 10;
            if (left != right)
                return false;
        }
        return true;
    }

696. 统计二进制字符串中连续 1 和连续 0 数量相同的子字符串个数

696. Count Binary Substrings (Easy)

Leetcode / 力扣

思路:我们可以将字符串 ss 按照 00 和 11 的连续段分组,存在 $\textit$ 数组中,例如 $s = 00111011$,可以得到这样的 $\textit$ 数组:$\textit$ = ${2, 3, 1, 2}$。

这里 $\textit$ 数组中两个相邻的数一定代表的是两种不同的字符。假设 $\textit$ 数组中两个相邻的数字为 uu 或者 vv,它们对应着 uu 个 00 和 vv 个 11,或者 uu 个 11 和 vv 个 00。它们能组成的满足条件的子串数目为 $\min { u, v }$,即一对相邻的数字对答案的贡献。

我们只要遍历所有相邻的数对,求它们的贡献总和,即可得到答案。

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/count-binary-substrings/solution/ji-shu-er-jin-zhi-zi-chuan-by-leetcode-solution/
来源:力扣(LeetCode)

    int countBinarySubstrings(string s)
    {
        int length = s.length();
        vector<int> count;
        int cnt = 0;
        char ch = s[0];
        for (int i = 0; i < length; i++)
        {
            if (s[i] == ch)
                cnt++;
            else
            {
                ch = s[i];
                count.push_back(cnt);
                cnt = 1;
            }
        }
        count.push_back(cnt);
        int ans = 0;
        for (int i = 1; i < count.size(); i++)
            ans += min(count[i], count[i - 1]);
        return ans;
    }

原项目地址:https://github.com/CyC2018/CS-Notes/edit/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%AD%97%E7%AC%A6%E4%B8%B2.md

0

评论区