Huahua’s Tech Road

花花酱 LeetCode 2353. Design a Food Rating System

By zxi on March 29, 2025

Hashtable + TreeSet / OrderedSet

用了三个Hashtable…

菜名 -> 菜系
菜系 -> Treemap
菜名 -> 所在Treemap中的迭代器

每个菜系用一个TreeSet来保存从高到低的菜色排名，查询的时候只要拿出第一个就好了。

修改的时候，拿出迭代器，删除原来的评分，再把新的评分加入（别忘了更新迭代器）

时间复杂度：构造O(nlogn)，修改O(logn)，查询O(1)

空间复杂度：O(n)

class FoodRatings {

public:

FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {

const int n = foods.size();

for (int i = 0; i < n; ++i) {

n_[foods[i]] = cuisines[i];

m_[foods[i]] = c_[cuisines[i]].emplace(-ratings[i], foods[i]).first;

}

void changeRating(string food, int newRating) {

const string& cuisine = n_[food];

c_[cuisine].erase(m_[food]);

m_[food] = c_[cuisine].emplace(-newRating, food).first;

}

string highestRated(string cuisine) {

return begin(c_[cuisine])->second;

}

private:

unordered_map<string, set<pair<int, string>>> c_; // cuisine -> {{-rating, name}}

unordered_map<string, string> n_; // food -> cuisine

unordered_map<string, set<pair<int, string>>::iterator> m_; // food -> set iterator

};

/**

* Your FoodRatings object will be instantiated and called as such:

* FoodRatings* obj = new FoodRatings(foods, cuisines, ratings);

* obj->changeRating(food,newRating);

* string param_2 = obj->highestRated(cuisine);

花花酱 LeetCode 3242. Design Neighbor Sum Service

By zxi on March 29, 2025

青铜 Brute Force：每次需要花费O(n*n)的时间去查找query所在的格子，求和是O(1)。总的时间复杂度达到O(n^4)，肯定会超时。

白银 Hashtable：由于所有元素的值的唯一的，我们可以使用hashtable（或者数组）来记录value所在的格子坐标，这样每次Query都是O(1)时间。
时间复杂度：初始化O(n^2)，query O(1)。
空间复杂度：O(n^2)

class NeighborSum {

public:

NeighborSum(vector<vector<int>>& grid):

n_(grid.size()), g_(&grid), xy_(n_ * n_) {

for (int i = 0; i < n_; ++i)

for (int j = 0; j < n_; ++j)

xy_[grid[i][j]] = {j, i};

}

int adjacentSum(int value) {

auto [x, y] = xy_[value];

return val(x, y - 1) + val(x, y + 1) + val(x + 1, y) + val(x - 1, y);

}

int diagonalSum(int value) {

auto [x, y] = xy_[value];

return val(x - 1, y - 1) + val(x - 1, y + 1) + val(x + 1, y - 1) + val(x + 1, y + 1);

}

private:

inline int val(int x, int y) const {

if (x < 0 || x >= n_ || y < 0 || y >= n_) return 0;

return (*g_)[y][x];

}

int n_;

vector<vector<int>>* g_;

vector<pair<int, int>> xy_;

};

黄金 Precompute：在初始化的时候顺便求合，开两个数组一个存上下左右的，一个存对角线的。query的时候直接返回答案就可以了。
时间复杂度和白银是一样的，但会快一些（省去了求合的过程）。

class NeighborSum {

public:

NeighborSum(vector<vector<int>>& grid) {

int n = grid.size();

adj_.resize(n * n);

dia_.resize(n * n);

auto v = [&](int x, int y) -> int {

if (x < 0 || x >= n || y < 0 || y >= n)

return 0;

return grid[y][x];

};

for (int y = 0; y < n; ++y)

for (int x = 0; x < n; ++x) {

adj_[grid[y][x]] = v(x, y - 1) + v(x, y + 1) + v(x + 1, y) + v(x - 1, y);

dia_[grid[y][x]] = v(x - 1, y - 1) + v(x - 1, y + 1) + v(x + 1, y - 1) + v(x + 1, y + 1);

}

int adjacentSum(int value) {

return adj_[value];

}

int diagonalSum(int value) {

return dia_[value];

}

private:

vector<int> adj_;

vector<int> dia_;

};

花花酱 LeetCode 3462. Maximum Sum With at Most K Elements

By zxi on March 27, 2025

本题使用了两次 partial sorting / std::nth_element 来进行部分排序，可以作为经典教程了。

速度比全排序或者heap/pq快到不知道哪里去了～

Time complexity: O(m*n)
Space complexity: O(m*n)

不用黑科技就达到99.77%

class Solution {

public:

long long maxSum(vector<vector<int>>& grid, vector<int>& limits, int k) {

// Step 1: Sort each row using fast parition, collect largest limits[i] elements.

vector<int> nums;

nums.reserve(grid.size() * grid[0].size());

for (int i = 0; i < grid.size(); ++i) {

nth_element(begin(grid[i]), begin(grid[i]) + limits[i], end(grid[i]), std::greater{});

nums.insert(nums.end(), begin(grid[i]), begin(grid[i]) + limits[i]);

}

// Setp 2: fast partition to find the largest k elements. O(m*n).

nth_element(begin(nums), begin(nums) + k, end(nums), std::greater{});

// Step 3: Sum them up. O(k)

return accumulate(begin(nums), begin(nums) + k, 0LL);

}

};

花花酱 LeetCode 3408. Design Task Manager

By zxi on March 27, 2025

pq_ 使用std::map充当优先队列，存储(priority, taskId) -> userId
m_ 使用std::unordered_map，存储taskId -> pq_的迭代器

所有操作都是O(logn)

class TaskManager {

public:

TaskManager(vector<vector<int>>& tasks) {

for (const auto& task : tasks)

add(task[0], task[1], task[2]);

}

void add(int userId, int taskId, int priority) {

m_[taskId] = pq_.emplace(make_pair(priority, taskId), userId).first;

}

void edit(int taskId, int newPriority) {

const int userId = m_[taskId]->second;

rmv(taskId);

add(userId, taskId, newPriority);

}

void rmv(int taskId) {

auto it = m_.find(taskId);

pq_.erase(it->second);

m_.erase(it);

}

int execTop() {

if (pq_.empty()) return -1;

auto it = pq_.rbegin();

const int userId = it->second;

const int taskId = (it->first.second);

rmv(taskId);

return userId;

}

private:

map<std::pair<int,int>, int> pq_; // (priority, taskId) -> userId;

unordered_map<int, map<std::pair<int,int>, int>::iterator> m_; // taskId -> pq iterator

};

花花酱 LeetCode 3489. Zero Array Transformation IV

By zxi on March 16, 2025

一道不错的DP题目！

首先看到每次可以取任意一个nums[l] ~ nums[r]的子集

不能用贪心（无法找到全局最优解）
不能用搜索（数据规模太大，(2^10) ^ 1000）

那只能用动态规划了

状态定义: dp[k][i][j] 能否通过使用前k个变换使得第i个数的值变成j

边界条件: dp[0][i][nums[i]] = 1，不使用任何变换，第i个数可以达到的数值就是nums[i]本身。

状态转移：dp[k][i][j] = dp[k-1][i][j] | (dp[k – 1][i][j + val[k]] if l[k] <= i <= r[k] else 0)

简单来说如果第k-1轮第i个数可以变成j + val[k]，那么第k轮就可以通过减去val[k]变成j。

上面是拉的公式，我们也可以写成推的:

dp[k][i][j – val[k]] = dp[k-1][i][j – vak[k]] | (dp[k – 1][i][j] if l[k] <= i <= r[k] else 0)

当然这么定义的话空间复杂度太高O(10^7)，由于第k轮的初始状态就等于k-1轮的状态，我们可以使用滚动数组来降维，空间复杂度降低到O(10^4)。

时间复杂度：O(k*n*MaxV) = O(10^7)。

class Solution {

public:

int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {

if (accumulate(begin(nums), end(nums), 0) == 0) return 0;

constexpr int kMaxV = 1000;

const int n = nums.size();

const int K = queries.size();

vector<bitset<kMaxV + 1>> dp(n);

for (int i = 0; i < n; ++i)

dp[i][nums[i]] = 1;

for (int k = 0; k < K; ++k) {

int l = queries[k][0];

int r = queries[k][1];

int v = queries[k][2];

for (int i = l; i <= r; ++i)

for (int j = 0; j <= kMaxV - v; ++j)

if (dp[i][j + v]) dp[i][j] = 1;

bool found = true;

for (int i = 0; i < n; ++i)

if (!dp[i][0]) found = false;

if (found) return k + 1;

}

return -1;

}

};

剪枝优化

上面我们把整个数组看作一个整体，一轮一轮来做。但如果某些数在第k轮能到变成0了，就没有必要参与后面的变化了，或者说它用于无法变成0，那么就是无解，其他数也就不需要再计算了。

所以，我们可以对每个数单独进行dp。即对于第i个数，计算最少需要多少轮才能把它变成0。然后对所有的轮数取一个最大值。总的时间复杂度不变（最坏情况所有数都需要经过K轮）。空间复杂度则可以再降低一个纬度到O(MaxV) = O(10^3)。

class Solution {

public:

int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {

constexpr int kMaxV = 1000;

const int n = nums.size();

const int K = queries.size();

auto rounds = [&](int i) -> int {

if (!nums[i]) return 0;

bitset<kMaxV + 1> dp;

dp[nums[i]] = 1;

for (int k = 0; k < K; ++k) {

int l = queries[k][0];

int r = queries[k][1];

int v = queries[k][2];

if (l > i || r < i) continue;

for (int j = 0; j <= kMaxV - v; ++j)

if (dp[j + v]) dp[j] = 1;

if (dp[0]) return k + 1;

}

return INT_MAX;

};

int ans = 0;

for (int i = 0; i < n && ans <= K; ++i)

ans = max(ans, rounds(i));

return ans == INT_MAX ? -1 : ans;

}

};

再加速：我们可以使用C++ bitset的右移操作符，dp >> v，相当于把整个集合全部剪去v，再和原先的状态做或运算（集合并）来达到新的状态。时间复杂度应该是一样的，只是代码简单，速度也会快不少。注: dp>>v 会创建一个临时对象，大小为O(MaxV)。

举个例子：
dp = {2, 3, 7}
dp >> 2 -> {0, 1, 5}
dp |= dp >> v -> {0, 1, 2, 3, 5, 7]

class Solution {

public:

int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {

constexpr int kMaxV = 1000;

const int n = nums.size();

const int K = queries.size();

auto rounds = [&](int i) -> int {

if (!nums[i]) return 0;

bitset<kMaxV + 1> dp;

dp[nums[i]] = 1;

for (int k = 0; k < K; ++k) {

int l = queries[k][0];

int r = queries[k][1];

int v = queries[k][2];

if (l > i || r < i) continue;

dp |= dp >> v; // magic

if (dp[0]) return k + 1;

}

return INT_MAX;

};

int ans = 0;

for (int i = 0; i < n && ans <= K; ++i)

ans = max(ans, rounds(i));

return ans == INT_MAX ? -1 : ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2353. Design a Food Rating System

花花酱 LeetCode 3242. Design Neighbor Sum Service

花花酱 LeetCode 3462. Maximum Sum With at Most K Elements

花花酱 LeetCode 3408. Design Task Manager

花花酱 LeetCode 3489. Zero Array Transformation IV