Huahua’s Tech Road

花花酱 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;

}

};

逆转裁判 Ace Attorney | GBA遮罩 Overlay | RG556

By zxi on February 10, 2025

最近在玩《逆转裁判》，在iOS上买了合集 Ace Attorney Trilogy（花了我$24.99大洋呢，今天降到$14.99了）。虽然画面重绘过了，高清了不少，官方中文版也加入了中文语音(异议!)，但本人不太喜欢搓玻璃，所以又开始倒腾模拟器，手上有周哥的RG35XX H和RG556（悄悄说RG34XX还在路上，不过它就不用遮罩了）。给556做了个遮罩（其实就是张图片，PS水平实在有限），应该也适用于其他1920×1080，GBA 6倍点对点的屏幕，只考虑掌机，所以没有加按钮，喜欢的可以自行拿走。

gba_ace_attorney_overlay Download

效果预览

Update: 2/24/2025

1-3终于全部通关了，最后一个故事太精彩了！送上几幅截屏，给这段旅程画上一个顿号。

花花酱 LeetCode 3319. K-th Largest Perfect Subtree Size in Binary Tree

By zxi on October 12, 2024

You are given the root of a binary tree and an integer k.

Return an integer denoting the size of the k^th largest perfect binary

subtree, or -1 if it doesn’t exist.

A perfect binary tree is a tree where all leaves are on the same level, and every parent has two children.

Example 1:

Input: root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2

Output: 3

Explanation:

The roots of the perfect binary subtrees are highlighted in black. Their sizes, in decreasing order are [3, 3, 1, 1, 1, 1, 1, 1].
The 2^nd largest size is 3.

Example 2:

Input: root = [1,2,3,4,5,6,7], k = 1

Output: 7

Explanation:

The sizes of the perfect binary subtrees in decreasing order are [7, 3, 3, 1, 1, 1, 1]. The size of the largest perfect binary subtree is 7.

Example 3:

Input: root = [1,2,3,null,4], k = 3

Output: -1

Explanation:

The sizes of the perfect binary subtrees in decreasing order are [1, 1]. There are fewer than 3 perfect binary subtrees.

Constraints:

The number of nodes in the tree is in the range [1, 2000].
1 <= Node.val <= 2000
1 <= k <= 1024

Solution: DFS

Write a function f() to return the perfect subtree size at node n.

def f(TreeNode n):
if not n: return 0
l, r = f(n.left), f(n.right)
return l + r + 1 if l == r && l != -1 else -1

Time complexity: O(n + KlogK)
Space complexity: O(n)

class Solution {

public:

int kthLargestPerfectSubtree(TreeNode* root, int k) {

vector<int> ss;

function<int(TreeNode*)> PerfectSubtree = [&](TreeNode* node) -> int {

if (node == nullptr) return 0;

int l = PerfectSubtree(node->left);

int r = PerfectSubtree(node->right);

if (l == r && l != -1) {

ss.push_back(l + r + 1);

return ss.back();

}

return -1;

};

PerfectSubtree(root);

sort(rbegin(ss), rend(ss));

return k <= ss.size() ? ss[k - 1] : -1;

}

};

WiFi 7? Who cares?

By zxi on August 23, 2024

I was using Google’s Nest Wifi Pro (three pack). Since we don’t have ethernet cables in our home, we’re using the wireless mesh setting. The network speed and coverage are OK, ~100Mbps at most places and drop to 10-20Mbps at some corners. The only annoying bit is Chrome Cast / Airplay. It works when I just got the device, it becomes unstable afer a couple months, now it’s almost unusable.

I have to deprecate them and upgrade to TP-Link BE series, more spesificily the BE11000, tri-band / WiFi 7. Also a three pack from Costco which is on sell for $399.99! It’s a day and night difference, casting is seemless, speed and coverage also got improved, 300-500Mbps everywhere, even in garage and restrooms. I’m paying Xfinify $135/m for 1Gbps plan, measured 900Mbps down and 30Mbps up, which is ridiculous. Three month fee vs a couple of years of usage!

You have to use the Deco app to setup the device, which is pretty smooth and friendly for newbies, but some pro users might found it less features packed compared to a web-base maganement system. I have a lot of IoT devices connected to system. None of them has a single problem, just making sure you use the same SSID and password as before, resetting all IoT devices can be a nightmare!

It features WiFi7 but who cares? I don’t even have a single device supports that. 500Mbps is more than enough for me who just do streaming most of the time. Yesterday, I was downloading Black Myth: WuKong 128GB, took about half an hour. I’d hope it could be faster!

Is Wifi7 future proof? Time well say.

Huahua's Tech Road

花花酱 LeetCode 3408. Design Task Manager

花花酱 LeetCode 3489. Zero Array Transformation IV

逆转裁判 Ace Attorney | GBA遮罩 Overlay | RG556

花花酱 LeetCode 3319. K-th Largest Perfect Subtree Size in Binary Tree

Solution: DFS

WiFi 7? Who cares?