数据结构刷题：第六天

目录

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

1，使用哈希表存储频数

思路与算法

复杂度分析

2，使用哈希表存储索引

思路与算法

复杂度分析

3，队列

思路与算法

小贴士

复杂度分析

二，赎金信

1，字符统计 

复杂度分析

三，有效的字母异位词

​编辑1，排序

复杂度分析

2，哈希表

复杂度分析

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

387. 字符串中的第一个唯一字符 - 力扣（LeetCode）https://leetcode.cn/problems/first-unique-character-in-a-string/?plan=data-structures&plan_progress=ggfacv7

1，使用哈希表存储频数

思路与算法

我们可以对字符串进行两次遍历。

在第一次遍历时，我们使用哈希映射统计出字符串中每个字符出现的次数。在第二次遍历时，我们只要遍历到了一个只出现一次的字符，那么就返回它的索引，否则在遍历结束后返回 −1。

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<int, int> frequency;
        for (char ch: s) {
            ++frequency[ch];
        }
        for (int i = 0; i < s.size(); ++i) {
            if (frequency[s[i]] == 1) {
                return i;
            }
        }
        return -1;
    }
};
 

复杂度分析

时间复杂度：O(n)，其中 n 是字符串 s 的长度。我们需要进行两次遍历。

空间复杂度：O(∣Σ∣)，其中 Σ 是字符集，在本题中 s 只包含小写字母，因此 ∣Σ∣≤26。我们需要 O(∣Σ∣) 的空间存储哈希映射。

2，使用哈希表存储索引

思路与算法

我们可以对方法一进行修改，使得第二次遍历的对象从字符串变为哈希映射。

具体地，对于哈希映射中的每一个键值对，键表示一个字符，值表示它的首次出现的索引（如果该字符只出现一次）或者 −1（如果该字符出现多次）。当我们第一次遍历字符串时，设当前遍历到的字符为 c，如果 c 不在哈希映射中，我们就将 cc 与它的索引作为一个键值对加入哈希映射中，否则我们将 c 在哈希映射中对应的值修改为 −1。

在第一次遍历结束后，我们只需要再遍历一次哈希映射中的所有值，找出其中不为 -1 的最小值，即为第一个不重复字符的索引。如果哈希映射中的所有值均为 −1，我们就返回 −1。

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<int, int> position;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (position.count(s[i])) {
                position[s[i]] = -1;
            }
            else {
                position[s[i]] = i;
            }
        }
        int first = n;
        for (auto [_, pos]: position) {
            if (pos != -1 && pos < first) {
                first = pos;
            }
        }
        if (first == n) {
            first = -1;
        }
        return first;
    }
};
 

复杂度分析

时间复杂度：O(n)，其中 n 是字符串 s 的长度。第一次遍历字符串的时间复杂度为 O(n)，第二次遍历哈希映射的时间复杂度为 O(∣Σ∣)，由于 ss 包含的字符种类数一定小于 s 的长度，因此 O(∣Σ∣) 在渐进意义下小于 O(n)，可以忽略。

空间复杂度：O(∣Σ∣)，其中 Σ 是字符集，在本题中 s 只包含小写字母，因此 ∣Σ∣≤26。我们需要 O(∣Σ∣) 的空间存储哈希映射。

3，队列

思路与算法

我们也可以借助队列找到第一个不重复的字符。队列具有「先进先出」的性质，因此很适合用来找出第一个满足某个条件的元素。

具体地，我们使用与方法二相同的哈希映射，并且使用一个额外的队列，按照顺序存储每一个字符以及它们第一次出现的位置。当我们对字符串进行遍历时，设当前遍历到的字符为 c，如果 c 不在哈希映射中，我们就将 c 与它的索引作为一个二元组放入队尾，否则我们就需要检查队列中的元素是否都满足「只出现一次」的要求，即我们不断地根据哈希映射中存储的值（是否为 −1）选择弹出队首的元素，直到队首元素「真的」只出现了一次或者队列为空。

在遍历完成后，如果队列为空，说明没有不重复的字符，返回 −1，否则队首的元素即为第一个不重复的字符以及其索引的二元组。

小贴士

在维护队列时，我们使用了「延迟删除」这一技巧。也就是说，即使队列中有一些字符出现了超过一次，但它只要不位于队首，那么就不会对答案造成影响，我们也就可以不用去删除它。只有当它前面的所有字符被移出队列，它成为队首时，我们才需要将它移除。

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> position;
        queue<pair<char, int>> q;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (!position.count(s[i])) {
                position[s[i]] = i;
                q.emplace(s[i], i);
            }
            else {
                position[s[i]] = -1;
                while (!q.empty() && position[q.front().first] == -1) {
                    q.pop();
                }
            }
        }
        return q.empty() ? -1 : q.front().second;
    }
};
 

 

复杂度分析

时间复杂度：O(n)，其中 n 是字符串 s 的长度。遍历字符串的时间复杂度为 O(n)，而在遍历的过程中我们还维护了一个队列，由于每一个字符最多只会被放入和弹出队列最多各一次，因此维护队列的总时间复杂度为O(∣Σ∣)，由于 s 包含的字符种类数一定小于 s 的长度，因此 O(∣Σ∣) 在渐进意义下小于 O(n)，可以忽略。

空间复杂度：O(∣Σ∣)，其中Σ 是字符集，在本题中 s 只包含小写字母，因此∣Σ∣≤26。我们需要 O(∣Σ∣) 的空间存储哈希映射以及队列。

二，赎金信

383. 赎金信 - 力扣（LeetCode）https://leetcode.cn/problems/ransom-note/

1，字符统计 

题目要求使用字符串magazine中的字符来构建新的字符串ransomNote,且ransomNote中的每个字符只能使用一次，只需要满足字符串magazine中的每个英文母('a'-'z')的统计次数都大于等于ransomNote中相同字母的统计次数即可。
●如果字符串magazine 的长度小于字符串ransomNote的长度，则我们可以肯定magazine无法构成ransomNote,此时直接返回false。
●首先统计magazine; 中每个英文字母a的次数cnt[a]，再遍历统计ransomNote中每个英文字母
的次数，如果发现ransomNote中存在某个英文字母c的统计次数大于magazir
中该字母统计次数cnt[c],则此时我们直接返回false。
 

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if (ransomNote.size() > magazine.size()) {
            return false;
        }
        vector<int> cnt(26);
        for (auto & c : magazine) {
            cnt[c - 'a']++;
        }
        for (auto & c : ransomNote) {
            cnt[c - 'a']--;
            if (cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};
 

复杂度分析

●时间复杂度: O(m+n)，其中m是字符串ransomNote的长度，n是字符串
magazine的长度，我们只需要遍历两个字符一-次即可。
●空间复杂度: O(|S|)， S是字符集，这道题中S为全部小写英语字母，因此|S|= 26。
 

三，有效的字母异位词

242. 有效的字母异位词 - 力扣（LeetCode）https://leetcode.cn/problems/valid-anagram/?plan=data-structures&plan_progress=ggfacv7

1，排序

t 是 s 的异位词等价于「两个字符串排序后相等」。因此我们可以对字符串 s 和 t 分别排序，看排序后的字符串是否相等即可判断。此外，如果 s 和 t 的长度不同，t 必然不是 s 的异位词。

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};
 

复杂度分析

●时间复杂度: O(nlogn), 其中n为s的长度。排序的时间复杂度为O(n logn),比较两个字符串是否相等时间复杂度为O(n),因此总体时间复杂度为O(nlogn+ n) = O(n logn)。
●空间复杂度: O(logn)。 排序需要O(logn)的空间复杂度。注意，在某些语言(比如Java&JavaScript)中字符串是不可变的，因此我们需要额外的O(n)的空间来拷贝字符串。但是我们
忽略这一复杂度分析，因为:
。这依赖于语言的细节;
。这取决于函数的设计方式，例如，可以将函数参数类型更改为char[] 。
 

2，哈希表

从另一个角度考虑，t 是 s 的异位词等价于「两个字符串中字符出现的种类和次数均相等」。由于字符串只包含 26 个小写字母，因此我们可以维护一个长度为 26 的频次数组 table，先遍历记录字符串 s 中字符出现的频次，然后遍历字符串 t，减去 table 中对应的频次，如果出现 table[i]<0，则说明 t 包含一个不在 s 中的额外字符，返回 false 即可。

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }
        vector<int> table(26, 0);
        for (auto& ch: s) {
            table[ch - 'a']++;
        }
        for (auto& ch: t) {
            table[ch - 'a']--;
            if (table[ch - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};
 

对于进阶问题，Unicode 是为了解决传统字符编码的局限性而产生的方案，它为每个语言中的字符规定了一个唯一的二进制编码。而 Unicode 中可能存在一个字符对应多个字节的问题，为了让计算机知道多少字节表示一个字符，面向传输的编码方式的 UTF−8 和 UTF−16 也随之诞生逐渐广泛使用，具体相关的知识读者可以继续查阅相关资料拓展视野，这里不再展开。

回到本题，进阶问题的核心点在于「字符是离散未知的」，因此我们用哈希表维护对应字符的频次即可。同时读者需要注意 Unicode 一个字符可能对应多个字节的问题，不同语言对于字符串读取处理的方式是不同的。

复杂度分析

• 时间复杂度：O(n)O(n)，其中 n 为 s 的长度。

• 空间复杂度：O(S)，其中 S 为字符集大小，此处S=26。

class Solution {
public:
    bool isAnagram(string s, string t) {
        int freq[26] {};
        for (char ch : s) ++freq[ch - 'a'];
        for (char ch : t) --freq[ch - 'a'];
        return all_of(begin(freq), end(freq), [](int x) { return x == 0; });
    }
};