February 4, 2026
送分题，简单仿真即可。
时间复杂度：O(n)
空间复杂度：O(1)
|
1 2 3 4 5 6 7 8 9 10 |
// https://zxi.mytechroad.com/blog/string/leetcode-3498-reverse-degree-of-a-string/ class Solution { public: int reverseDegree(string s) { int ans = 0; for (int i = 0; i < s.size(); ++i) ans += ('z' - s[i] + 1) * (i + 1); return ans; } }; |
两个hashtable，一个是index->number，另外一个是number -> {index}，使用treeset，自动排序。
时间复杂度：change O(logn)，find O(1)
空间复杂度：O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class NumberContainers { public: NumberContainers() {} void change(int index, int number) { if (m_.count(index)) { auto it = idx_.find(m_[index]); it->second.erase(index); if (it->second.empty()) idx_.erase(it); } m_[index] = number; idx_[number].insert(index); } int find(int number) { auto it = idx_.find(number); if (it == end(idx_)) return -1; return *begin(it->second); } private: unordered_map<int, int> m_; // index -> num unordered_map<int, set<int>> idx_; // num -> {index} }; |
Hashtable + TreeSet / OrderedSet
用了三个Hashtable…
每个菜系用一个TreeSet来保存从高到低的菜色排名，查询的时候只要拿出第一个就好了。
修改的时候，拿出迭代器，删除原来的评分，再把新的评分加入（别忘了更新迭代器）
时间复杂度：构造O(nlogn)，修改O(logn)，查询O(1)
空间复杂度：O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
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); */ |
青铜 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)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
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的时候直接返回答案就可以了。
时间复杂度和白银是一样的，但会快一些（省去了求合的过程）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
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_; }; |
本题使用了两次 partial sorting / std::nth_element 来进行部分排序，可以作为经典教程了。
速度比全排序或者heap/pq快到不知道哪里去了～
Time complexity: O(m*n)
Space complexity: O(m*n)
不用黑科技就达到99.77%
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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); } }; |