leetcode解题思路分析（一百四十）1201 - 1208 题

1201. 丑数3
      给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。丑数是可以被 a 或 b 或 c 整除的 正整数 。

容斥原理+二分法

class Solution {
public:int nthUglyNumber(int n, int a, int b, int c) {long long ab = lcm((long long)a, (long long)b);long long bc = lcm((long long)b, (long long)c);long long ac = lcm((long long)a, (long long)c);long long abc = lcm((long long)ab, (long long)ac);int left = 1, right = 2e9;auto check = [&](int x) {return n <= (long long) x / a + x / b + x / c - x / ab - x / ac - x / bc + x / abc;};while (left < right) {int mid = left + (right - left) / 2;if (check(mid)) {right = mid;} else {left = mid + 1;}}return left;}
};

1202. 交换字符串中的元素
      给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。你可以 任意多次交换 在 pairs 中任意一对索引处的字符。返回在经过若干次交换后，s 可以变成的按字典序最小的字符串

看似是字符串，实际是多个Pairs构成的多个子连通图问题。首先用并查集分割，然后遍历字符串将每个索引位置确定在哪个集合中，然后对每个集合排序，最后输出出来

class Solution {
public:int find(vector<int> &parent, int i) {if (parent[i] == i) {return i;}else {parent[i] = find(parent, parent[i]);return parent[i];}}void unify(vector<int> &parent, int i, int j) {parent[find(parent, i)] = find(parent, j);}string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {int len = s.size();string ans(s);vector<int> parent(len);for (int i = 0; i < len; ++i) {parent[i] = i;}for (int i = 0; i < pairs.size(); ++i) {unify(parent, pairs[i][0], pairs[i][1]);}map<int, priority_queue<char, vector<char>, greater<char>>> charMap;for (int i = 0; i < len; ++i) {charMap[find(parent, i)].push(s[i]);}for (int i = 0; i < len; ++i) {ans[i] = charMap[find(parent, i)].top();charMap[find(parent, i)].pop();}return ans;}
};

1203. 项目管理
      有 n 个项目，每个项目或者不属于任何小组，或者属于 m 个小组之一。group[i] 表示第 i 个项目所属的小组，如果第 i 个项目不属于任何小组，则 group[i] 等于 -1。项目和小组都是从零开始编号的。可能存在小组不负责任何项目，即没有任何项目属于这个小组。
      请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：
      同一小组的项目，排序后在列表中彼此相邻。
      项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。
      如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个 空列表 。

主要是拓扑排序的应用

class Solution {
public:vector<int> topologicalSort(vector<vector<int>> &Adj, vector<int> &Indegree, int n){vector<int> res;queue<int> q;for(int i = 0;i<n;i++){if(Indegree[i]==0){q.push(i);}}while(!q.empty()){int front = q.front();q.pop();res.push_back(front);for(int successor: Adj[front]){Indegree[successor]--;if(Indegree[successor]==0){q.push(successor);}}}if(res.size()==n){return res;}return vector<int>();}vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {// 第 1 步：数据预处理，给没有归属于一个组的项目编上组号for(int i=0;i<group.size();i++){if(group[i] == -1){group[i] = m;m++;}}// 第 2 步：实例化组和项目的邻接表vector<vector<int>> groupAdj(m, vector<int>());vector<vector<int>> itemAdj(n, vector<int>());// 第 3 步：建图和统计入度数组vector<int> groupsIndegree(m, 0);vector<int> itemIndegree(n, 0);int len = group.size();for(int i=0;i<len;i++){int currentGroup = group[i];for(int beforeItem: beforeItems[i]){int beforeGroup = group[beforeItem];if(beforeGroup!=currentGroup){groupAdj[beforeGroup].push_back(currentGroup);groupsIndegree[currentGroup]++;}}}for(int i=0;i<n;i++){for(int item: beforeItems[i]){itemAdj[item].push_back(i);itemIndegree[i]++;}}// 第 4 步：得到组和项目的拓扑排序结果vector<int> groupList = topologicalSort(groupAdj, groupsIndegree, m);if(groupList.size()==0){return vector<int> ();}vector<int> itemList = topologicalSort(itemAdj, itemIndegree, n);if(itemList.size()==0){return vector<int> ();}// 第 5 步：根据项目的拓扑排序结果，项目到组的多对一关系，建立组到项目的一对多关系// key：组，value：在同一组的项目列表map<int, vector<int>> group2Items;for(int item: itemList){group2Items[group[item]].push_back(item);}// 第 6 步：把组的拓扑排序结果替换成为项目的拓扑排序结果vector<int> res;for(int groupId: groupList){vector<int> items = group2Items[groupId];for(int item: items){res.push_back(item);}}return res;} 
};

1204. 最后一个能进入电梯的人
      有一群人在等着上公共汽车。然而，巴士有1000 公斤的重量限制，所以可能会有一些人不能上。写一条 SQL 查询语句查找 最后一个 能进入电梯且不超过重量限制的 person_name 。题目确保队列中第一位的人可以进入电梯，不会超重。

将每一条记录的 weight 按照 turn 的顺序和自定义变量相加并生成新的记录。生成临时表并处理。

# Write your MySQL query statement below
SELECT a.person_name
FROM (SELECT person_name, @pre := @pre + weight AS weightFROM Queue, (SELECT @pre := 0) tmpORDER BY turn
) a
WHERE a.weight <= 1000
ORDER BY a.weight DESC
LIMIT 1

1206. 设计跳表

constexpr int MAX_LEVEL = 32;
constexpr double P_FACTOR = 0.25;struct SkiplistNode {int val;vector<SkiplistNode *> forward;SkiplistNode(int _val, int _maxLevel = MAX_LEVEL) : val(_val), forward(_maxLevel, nullptr) {}
};class Skiplist {
private:SkiplistNode * head;int level;mt19937 gen{random_device{}()};uniform_real_distribution<double> dis;public:Skiplist(): head(new SkiplistNode(-1)), level(0), dis(0, 1) {}bool search(int target) {SkiplistNode *curr = this->head;for (int i = level - 1; i >= 0; i--) {/* 找到第 i 层小于且最接近 target 的元素*/while (curr->forward[i] && curr->forward[i]->val < target) {curr = curr->forward[i];}}curr = curr->forward[0];/* 检测当前元素的值是否等于 target */if (curr && curr->val == target) {return true;} return false;}void add(int num) {vector<SkiplistNode *> update(MAX_LEVEL, head);SkiplistNode *curr = this->head;for (int i = level - 1; i >= 0; i--) {/* 找到第 i 层小于且最接近 num 的元素*/while (curr->forward[i] && curr->forward[i]->val < num) {curr = curr->forward[i];}update[i] = curr;}int lv = randomLevel();level = max(level, lv);SkiplistNode *newNode = new SkiplistNode(num, lv);for (int i = 0; i < lv; i++) {/* 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点 */newNode->forward[i] = update[i]->forward[i];update[i]->forward[i] = newNode;}}bool erase(int num) {vector<SkiplistNode *> update(MAX_LEVEL, nullptr);SkiplistNode *curr = this->head;for (int i = level - 1; i >= 0; i--) {/* 找到第 i 层小于且最接近 num 的元素*/while (curr->forward[i] && curr->forward[i]->val < num) {curr = curr->forward[i];}update[i] = curr;}curr = curr->forward[0];/* 如果值不存在则返回 false */if (!curr || curr->val != num) {return false;}for (int i = 0; i < level; i++) {if (update[i]->forward[i] != curr) {break;}/* 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳 */update[i]->forward[i] = curr->forward[i];}delete curr;/* 更新当前的 level */while (level > 1 && head->forward[level - 1] == nullptr) {level--;}return true;}int randomLevel() {int lv = 1;/* 随机生成 lv */while (dis(gen) < P_FACTOR && lv < MAX_LEVEL) {lv++;}return lv;}
};

1207. 独一无二的出现次数
      给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

两次哈希统计数量就行了

class Solution {
public:bool uniqueOccurrences(vector<int>& arr) {std::unordered_map<int, int> CntMap;std::set<int> OccurSet;std::unordered_map<int, int>::iterator iter;for (auto n: arr){CntMap[n]++;}for (iter = CntMap.begin(); iter != CntMap.end(); ++iter){OccurSet.insert(iter->second);}return OccurSet.size() == CntMap.size();}
};

1208. 尽可能使字符串相等
      给你两个长度相同的字符串，s 和 t。将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

题意中很重要的一点是只能第i位互换，降低了难度。所以这里可以先求出数组每一位的差值，diff[]。然后采用滑动窗口的方式去找寻满足maxCost以内的最大窗口。

class Solution {
public:int equalSubstring(string s, string t, int maxCost) {int n = s.length();vector<int> diff(n, 0);for (int i = 0; i < n; i++) {diff[i] = abs(s[i] - t[i]);}int maxLength = 0;int start = 0, end = 0;int sum = 0;while (end < n) {sum += diff[end];while (sum > maxCost) {sum -= diff[start];start++;}maxLength = max(maxLength, end - start + 1);end++;}return maxLength;}
};