medium – Page 2 – Huahua’s Tech Road

花花酱 LeetCode 646. Maximum Length of Pair Chain

By zxi on April 9, 2025

这题我选DP，因为不需要证明，直接干就行了。

方法1: DP

首先还是需要对pairs的right进行排序。一方面是为了方便chaining，另一方面是可以去重。

然后定义 dp[i] := 以pairs[i]作为结尾，最长的序列的长度。

状态转移：dp[i] = max(dp[j] + 1) where pairs[i].left > pairs[j].right and 0 < j < i.

解释：对于pairs[i]，找一个最优的pairs[j]，满足pairs[i].left > pairs[j].right，这样我就可以把pairs[i]追加到以pairs[j]结尾的最长序列后面了，长度+1。

边检条件：dp[0:n] = 1，每个pair以自己作为序列的最后元素，长度为1。

时间复杂度：O(n²)
空间复杂度：O(n)

class Solution {

public:

int findLongestChain(vector<vector<int>>& pairs) {

sort(begin(pairs), end(pairs), [](const auto& p1, const auto& p2){

return p1[1] < p2[1];

});

const int n = pairs.size();

vector<int> dp(n, 1);

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

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

if (pairs[i][0] > pairs[j][1])

dp[i] = max(dp[i], dp[j] + 1);

return *max_element(begin(dp), end(dp));

}

};

方法2: 贪心

和DP一样，对数据进行排序。

每当我看到 cur.left > prev.right，那么就直接把cur接在prev后面。我们需要证明这么做是最优的，而不是跳过它选后面的元素。

Case 0: cur已经是最后一个元素了，跳过就不是最优解了。

假设cur后面有next, 因为已经排序过了，我们可以得知 next.right >= cur.right。

Case 1: next.right == cur.right。这时候选cur和选next对后面的决策来说是一样的，但由于Case 0的存在，我必须选cur。

Case 2: next.right > cur.right。不管left的情况怎么样，由于right更小，这时候选择cur一定是优于next。

综上所述，看到有元素可以连接起来就贪心的选它就对了。

时间复杂度：O(nlogn)
空间复杂度：O(1)

class Solution {

public:

int findLongestChain(vector<vector<int>>& pairs) {

sort(begin(pairs), end(pairs), [](const auto& p1, const auto& p2){

return p1[1] < p2[1];

});

int right = INT_MIN;

int ans = 0;

for (const auto& p : pairs)

if (p[0] > right) {

right = p[1];

++ans;

}

return ans;

}

};

花花酱 LeetCode 2349. Design a Number Container System

By zxi on March 30, 2025

两个hashtable，一个是index->number，另外一个是number -> {index}，使用treeset，自动排序。

时间复杂度：change O(logn)，find O(1)
空间复杂度：O(n)

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}

};

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

}

};

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

}

};

Posts tagged as “medium”

花花酱 LeetCode 646. Maximum Length of Pair Chain

花花酱 LeetCode 2349. Design a Number Container System

花花酱 LeetCode 3408. Design Task Manager

花花酱 LeetCode 3489. Zero Array Transformation IV

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

Solution: DFS