pq优先处理最优候选|桶排序

lc2335

用大根堆每次抓最多的两种水各装一杯

装完剩一种水就直接把剩余杯数算成时间，最快装满所有杯子

class Solution {
public:
int fillCups(vector<int>& a) {
priority_queue<int> q;
for (int x : a) if (x) q.push(x);

int t = 0;
while (q.size() >= 2) {
int f = q.top(); q.pop();
int s = q.top(); q.pop();
f--; s--; t++;
if (f) q.push(f);
if (s) q.push(s);
}
if (!q.empty()) t += q.top();
return t;
}
};

lc1057 选自行车

piii dist_pq模拟+贪心

pq优先处理最优候选

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

class Solution {
public:
vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
int n = workers.size(), m = bikes.size();
priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
vector<int> ans(n, -1);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
int dist = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
heap.push({dist, {i, j}});//init
}
}

vector<int> remain(m, 1);
int cnt = 0;
while(cnt < n) {
auto t = heap.top();
heap.pop();
int i = t.second.first, j = t.second.second;
if(remain[j] && ans[i] == -1) {
ans[i] = j;
remain[j] = 0;
cnt++; //choice
}
}
return ans;
}
};

有迪杰斯特拉“贪心+优先队列”的感觉：

迪杰斯特拉是用小根堆每次选“当前最短路径”的节点

这里是用小根堆每次选“当前距离最小的工人-单车对”；两者都是通过优先队列优先处理“最优候选”，再逐步确定最终结果，核心思路是一致的。

不过这个解法有个小问题：它把所有（工人-单车）对都入堆，时间复杂度是 O(nm\log nm)（n 是工人数，m 是单车数），当 n、m 很大时会比较耗时~

还有一种桶排序的tricks

计算距离时，外循环从小到大遍历worker，内循环从小到大遍历bike，然后依次添加到指定桶的末尾，这样同一个桶（距离相同的）的工人自行车对，一定是工人id小的在前，若工人id相同的，则自行车编号小的在前

正好符合题意，后面只需要线性遍历就可以了，省掉了耗时的排序过程

class Solution {
public:
vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
int n = workers.size(), m = bikes.size();
// 桶的下标是距离，桶内存储 (工人id, 单车id)
vector<vector<pair<int, int>>> buckets(2001);

// 外循环遍历工人（从小到大），内循环遍历单车（从小到大）
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int dist = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
buckets[dist].emplace_back(i, j);
}
}

vector<int> ans(n, -1);
vector<bool> bike_used(m, false);
int cnt = 0;

// 按距离从小到大遍历桶
for (int d = 0; d <= 2000 && cnt < n; ++d) {
// 遍历当前距离桶内的所有 (工人, 单车) 对
for (auto& p : buckets[d]) {
int worker_id = p.first;
int bike_id = p.second;
// 工人未分配 且 单车未被用
if (ans[worker_id] == -1 && !bike_used[bike_id]) {
ans[worker_id] = bike_id;
bike_used[bike_id] = true;
cnt++;
if (cnt == n) break;
}
}
}

return ans;
}
};

lc1430

bfs

1.if (i == n - 1)
return !t->left && !t->right;

2.

if (!hasMatch) return false; //cut

class Solution {
public:
bool isValidSequence(TreeNode* root, vector<int>& arr)
{
int n = arr.size();
if (!root) return false;
queue<TreeNode*> q;
q.push(root);

int i = 0;
while (q.size())
{
int sz = q.size();
bool hasMatch = false;
while (sz--)
{
auto t = q.front();
q.pop();

if (arr[i] == t->val)
{
hasMatch = true;
// i是最后一个元素时，必须是叶子节点
if (i == n - 1)
return !t->left && !t->right;

if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
}
if (!hasMatch) return false; //cut
i++;
}
return false;
}
};