LeetCode 156周赛解题

LeetCode 156 周赛解题

5205. 独一无二的出现次数

给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

示例 1：

输入：arr = [1,2,2,1,1,3] 输出：true 解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。

示例 2：

输入：arr = [1,2] 输出：false

示例 3：

输入：arr = [-3,0,1,-3,1,1,1,-3,10,0] 输出：true

提示：

1 <= arr.length <= 1000-1000 <= arr[i] <= 1000

解题思路：

使用map通过将每个值依次计数， 将每个值的个数添加到set中，而set是无重复的，如果set的长度小于map长度说明出现次数存在重复。

解题代码：

class Solution { public: bool uniqueOccurrences(vector<int>& arr) { map<int, int> m; set<int> s; for (int i = 0; i < arr.size(); i++) m[arr[i]]++; for (auto it = m.begin(); it != m.end(); it++) s.insert(it->second); if (m.size() == s.size()) return true; else return false; } };

5207.尽可能使字符串相等

给你两个长度相同的字符串，s 和 t。

将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。

如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

示例 1：

输入：s = "abcd", t = "bcdf", cost = 3 输出：3 解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。

示例 2：

输入：s = "abcd", t = "cdef", cost = 3 输出：1 解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。

示例 3：

输入：s = "abcd", t = "acde", cost = 0 输出：1 解释：你无法作出任何改动，所以最大长度为 1。

提示：

1 <= s.length, t.length <= 10^50 <= maxCost <= 10^6s 和 t 都只含小写英文字母。

解题代码

class Solution { public: int equalSubstring(string s, string t, int maxCost) { int n = s.size(), ans = 0, cur = 0, right = 0; //左端点向左移动 for (int i = 0; i < n; i++){ if (i > 0){ cur -= abs(s[i - 1] - t[i - 1]); if (right <= i){ cur = 0; right = i; } } //右端点向右移动尽量添加多的字符 while(right < n && maxCost - cur >= abs(s[right] - t[right])){ cur += abs(s[right] - t[right]); right++; } ans = max(right - i, ans); } return ans; } };

5206. 删除字符串中的所有相邻重复项 II

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。

在执行完所有删除操作后，返回最终得到的字符串。

本题答案保证唯一。

示例 1：

输入：s = "abcd", k = 2 输出："abcd" 解释：没有要删除的内容。

示例 2：

输入：s = "deeedbbcccbdaa", k = 3 输出："aa" 解释： 先删除 "eee" 和 "ccc"，得到 "ddbbbdaa" 再删除 "bbb"，得到 "dddaa" 最后删除 "ddd"，得到 "aa"

示例 3：

输入：s = "pbbcggttciiippooaais", k = 2 输出："ps"

提示：

1 <= s.length <= 10^52 <= k <= 10^4s 中只含有小写英文字母。

解题思路

使用stack解题， 将给定的字符串依次压入栈中，如果相同的数量达到了K，那么就这K个字符弹出栈中，直到遍历完所有的字符串。

解题代码：

class Solution { public: string removeDuplicates(string str, int k) { stack<pair<char, int>> s; for (auto c : str){ if (s.empty()){ s.push(make_pair(c, 1)); }else{ int cnt = 0; pair<char, int> cur = s.top(); if (cur.first == c) cnt = cur.second; s.push(make_pair(c, cnt + 1)); } while (!s.empty() && s.top().second == k) for (int i = 0; i < k; i++) s.pop(); } int m = s.size(); char st[m + 1]; for (int i = m - 1; i >= 0; i--){ st[i] = s.top().first; s.pop(); } st[m] = 0; string ans(st); return ans; } };