classSolution { private: vector<int> vec; intfind(int root){ if (vec[root] != root) vec[root] = find(vec[root]); return vec[root]; } voidunion_root(int r1, int r2){ vec[find(r1)] = vec[find(r2)]; return; } public: intminSwapsCouples(vector<int>& row){ int n = row.size(); int m = n / 2; vec.resize(m, 0); for (int i = 0; i < m; i++) vec[i] = i; for (int i = 1; i <= m; i++) { union_root(row[2 * i - 2] / 2, row[2 * i - 1] / 2); } int cnt = 0; for (int i = 0; i < m; i++) { if (find(i) == i) cnt++; } return m - cnt; } };
在代码中，我们用某个人的 ID 除以 2 来表示ta和ta对象共同的 情侣ID，然后把实际上挨着坐的人都 union 起来。如果他们本来就是情侣，则最终他们所在集合就只会有一个元素，表示这个集合中的人不需要交换。 union 到最后，我们得到的并查集中每个集合的情侣都坐混了，需要互相发生交换；而不同集合中的情侣之间则不需要发生交换。
voidQuickSort(vector<int>& nums, int left, int right){ if (left >= right) return; //递归终止条件 int i = left; int j = right; int key = left; while (i < j) { while (nums[j] >= nums[key] && i < j) j--; while (nums[i] <= nums[key] && i < j) i++; swap(nums[i], nums[j]); } swap(nums[key], nums[i]); QuickSort(nums, left, i - 1); QuickSort(nums, i + 1, right); }
下面通过两个例题来介绍标题里的两个算法。
例题 1
LeetCode 215. 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1：
1 2
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
示例 2：
1 2
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4
题解 1
这道题就是快速选择算法的经典应用场景了，它可以在 O(n) 的时间复杂度下找到这个数组第K大的数。我前面之所以说快速选择是阉割版的快速排序，是因为这两个算法的思路是一毛一样的，快速选择解决的问题可以说是快排的子问题。在快速排序中，每轮排序可以确定基准数在排序后数组中的位置，就相当于它的大小排序。例如在某一轮排序中，我们确定了基准数 a 是数组中第 k' 大的数，那么：
如果 k' = k ，说明当前的基准数就是数组第 k 大的数。
如果 k' < k ，说明我们要找的数比当前的基准数要小一些，所以我们递归地在基准数左边的区间里继续查找，而右边的区间就可以放着不动了。
如果 k' > k ，说明我们要找的数比当前的基准数要大一些，所以我们递归地在基准数右边的区间里继续查找，而左边的区间就可以放着不动了。
classSolution { private: intpartition(vector<int>& nums, int l, int r, int k){ int i = l; int j = r; while (i < j) { while (nums[j] >= nums[l] && i < j) j--; while (nums[i] <= nums[l] && i < j) i++; swap(nums[i], nums[j]); } swap(nums[l], nums[i]); if (i == k) return nums[i]; elseif (i > k) returnpartition(nums, l, i - 1, k); elsereturnpartition(nums, i + 1, r, k); } public: intfindKthLargest(vector<int>& nums, int k){ int n = nums.size(); returnpartition(nums, 0, n - 1, n - k); } };
注意： 每轮排序时，要先减小 j 的值，再增大 i 的值，这样可以保证 i 和 j 重合时对应的值一定是小于 key 的，这样就可以拿 key 和 nums[i] 直接交换。
classSolution { private: intQuickSelect(vector<int>& nums, int l, int r, int k){ int i = l; int j = r; while (i < j) { while (nums[j] >= nums[l] && i < j) j--; while (nums[i] <= nums[l] && i < j) i++; swap(nums[i], nums[j]); } swap(nums[l], nums[i]); if (i == k) return nums[i]; elseif (i > k) returnQuickSelect(nums, l, i - 1, k); elsereturnQuickSelect(nums, i + 1, r, k); } public: voidwiggleSort(vector<int>& nums){ int n = nums.size(); if (n == 1) return; int key = QuickSelect(nums, 0, n - 1, n - n / 2); int left = 0; int right = n - 1; int mid = 0; while (mid < right) { if (nums[mid] < key) { swap(nums[mid], nums[left]); left++; mid++; } elseif (nums[mid] > key) { swap(nums[mid], nums[right]); right--; } else mid++; } int m = n - n / 2; vector<int> temp1(nums.begin(), nums.begin() + m); vector<int> temp2(nums.begin() + m, nums.end()); for (int i = 0; i < temp1.size(); i++) nums[i * 2] = temp1[temp1.size() - i - 1]; for (int i = 0; i < temp2.size(); i++) nums[i * 2 + 1] = temp2[temp2.size() - i - 1]; return; } };
classSolution { private: vector<int> dist; int m; int n; intf(int start, int end){ //计算曼哈顿距离 int x1 = start / n; int y1 = start % n; int x2 = end / n; int y2 = end % n; returnabs(x1 - x2) + abs(y1 - y2); } intAStar(int start, int end, vector<vector<int>>& forest){ priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; q.push({ f(start,end),start }); fill(dist.begin(), dist.end(), INT_MAX); dist[start] = 0; vector<int> dirs = { -1,0,1,0,-1 }; while (!q.empty()) { //每轮从优先队列中弹出到起点和终点距离之和最短的点进行扩展。 int state = q.top().second; q.pop(); if (state == end) return dist[state]; for (int i = 0; i < 4; i++) { int x = state / n + dirs[i]; int y = state % n + dirs[i + 1]; if (0 <= x && x<m && 0 <= y && y < n && forest[x][y]>0 && dist[x * n + y]>dist[state] + 1) { /* 如果当前节点已经被查找到过（即已经记录过dist值）， * 并且当前计算的到起点的距离比此前查到的距离更短， * 就用当前的距离值代替原来的距离值，并将其放回到优先队列。 */ dist[x * n + y] = dist[state] + 1; q.push({ dist[x * n + y] + f(x * n + y,end),x * n + y }); } } } return-1; } public: intcutOffTree(vector<vector<int>>& forest){ m = forest.size(); n = forest[0].size(); dist.resize(m * n); vector<pair<int, int>> trees; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (forest[i][j] > 1) { trees.push_back({ forest[i][j],i * n + j }); } } } sort(trees.begin(), trees.end()); int start = 0; int res = 0; for (pair<int, int> tree : trees) { int end = tree.second; int subdist = AStar(start, end, forest); if (subdist == -1) return-1; else res += subdist; start = end; } return res; } };
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] 输出：[]
示例 3：
1 2
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出：[6,9,12]
题解 2
由于题目说 words 里的单词长度都是相同的（记为len ），那么我们就可以每次滑动 len 的距离。考虑到 s 中的单词不一定是整倍整倍出现的，比如 s="aababab" ，words=["ab","ab","ab"] 如果只从 0 开始构建移动窗口的话会刚好错过全部的 ab 。所以我们应该把 [0,len] 中的全部数都做一遍开头。
另外一个小tips就是因为题目里是不考虑 words 中元素出现的顺序的，所以可以直接使用哈希表计数，方便统计。
intget(int key){ if (map.count(key) > 0) { Node* cur = map[key]; cur->cnt++; int res = cur->val; refresh(cur); return res; } return-1; }
voidput(int key, int value){ if (cap == 0) return; if (map.count(key) > 0) { Node* cur = map[key]; cur->cnt++; cur->val = value; refresh(cur); } else { Node* newnode = newNode(value, key); if (now == cap) { for (int i = 1; i <= buckets.size(); i++) { Bucket* buck = buckets[i]; if (buck->head->next != buck->end) { map.erase(buck->head->next->key); buck->head->next->next->prev = buck->head; buck->head->next = buck->head->next->next; break; } } now--; } newnode->prev = buck1->end->prev; buck1->end->prev->next = newnode; newnode->next = buck1->end; buck1->end->prev = newnode; map[key] = newnode; now++; } return; } };
有的没的
为什么是冬眠舱
“冬眠”是《三体》中的设定。人可以通过“冬眠”来跨越漫长的时间。
重逢的欢喜中，他们交换了自己的经历。罗辑得知史强是两个月前苏醒的，他的白血病已经治好了，医生还发现他的肝脏病变的几率很高，可能是喝酒的原因，也顺便处理好了。其实，在他们的感觉中，两人分别到时间并不是太长，就是四五年的样子，冬眠中是没有时间感的，但在两个世纪后的新时代相遇，还是多了一层亲切感。——《三体 II · 黑暗森林》
