Posts tagged as “leetcode”

花花酱 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 Weekly Contest 134 (1033,1034,1035,1036)

By zxi on April 27, 2019

1033. Moving Stones Until Consecutive

Solution: Math

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua, running time: 4 ms / 8.3 MB

class Solution {

public:

vector<int> numMovesStones(int a, int b, int c) {

if (a > c) swap(a, c);

if (a > b) swap(a, b);

if (b > c) swap(b, c);

int u = c - b - 1 + (b - a -1);

int l = 0;

if (a + 1 == b && b + 1 == c) l = 0;

else if (a + 2 >= b || b + 2 >= c) l = 1;

else l = 2;

return {l, u};

}

};

1034. Coloring A Border

Solution: DFS

Time complexity: O(mn)
Space complexity: O(mn)

C++

// Author: Huahua, 52 MB / 12.6 MB

class Solution {

public:

vector<vector<int>> colorBorder(vector<vector<int>>& grid, int r0, int c0, int color) {

vector<vector<int>> b(grid.size(), vector<int>(grid[0].size()));

dfs(grid, r0, c0, grid[r0][c0], b);

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

for (int j = 0; j < b[0].size(); ++j)

if (b[i][j] > 0) grid[i][j] = color;

return grid;

}

private:

bool dfs(const vector<vector<int>>& grid, int r, int c, int color, vector<vector<int>>& b) {

if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size()) return true;

if (grid[r][c] != color) return true;

if (b[r][c]) return false;

b[r][c] = -1;

bool valid = dfs(grid, r + 1, c, color, b) |

dfs(grid, r - 1, c, color, b) |

dfs(grid, r, c + 1, color, b) |

dfs(grid, r, c - 1, color, b);

if (valid) b[r][c] = 1;

return false;

}

};

1035. Uncrossed Lines

Solution: LCS

Time complexity: O(nm)
Space complexity: O(mn)

C++

// Author: Huahua, 12 ms / 12.1 MB

class Solution {

public:

int maxUncrossedLines(vector<int>& A, vector<int>& B) {

const int m = A.size();

const int n = B.size();

vector<vector<int>> dp(m + 1, vector<int>(n + 1));

dp[0][0] = 0;

for (int i = 1; i <= m; ++i)

for (int j = 1; j <= n; ++j) {

if (A[i - 1] == B[j - 1])

dp[i][j] = dp[i-1][j-1] + 1;

else

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

}

return dp[m][n];

}

};

1036. Escape a Large Maze

Solution: limited search

Time complexity: O(b^2)
Space complexity: O(b^2)

C++

// Author: Huahua, running time: 168 ms, 49.7 MB class Solution { public: bool isEscapePossible(vector>& blocked, vector& source, vector& target) { for (const auto& p : blocked) b.insert(static_cast(p[0]) << 32 | p[1]); seen = 0; t = target; bool first = dfs(source[0], source[1]); t = source; bool second = dfs(target[0], target[1]); return first && second; } private: const static int kMaxN = 1000000; const static int kMaxSeen = 20000; unordered_set b; vector t; int seen; int tx; int ty; bool dfs(int x, int y) { if (x < 0 || y < 0 || x >= kMaxN || y >= kMaxN) return false; if (x == t[0] && y == t[1]) return true; long key = static_cast(x) << 32 | y; if (b.find(key) != b.end()) return false; b.insert(key); if (++seen > kMaxSeen) return true; return dfs(x + 1, y) || dfs(x – 1, y) || dfs(x, y + 1) || dfs(x, y – 1); } };

花花酱 LeetCode Weekly Contest 131 (1021, 1022, 1023, 1024)

By zxi on April 7, 2019

LeetCode 1021. Remove Outermost Parentheses

Solution: Track # of opened parentheses

Let n denote the # of opened parentheses after current char, keep ‘(‘ if n > 1 and keep ‘)’ if n > 0

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string removeOuterParentheses(string S) {

string ans;

int n = 0;

for (char c : S) {

if (c == '(' && n++) ans += c;

if (c == ')' && --n) ans += c;

}

return ans;

}

};

LeetCode 1022. Sum of Root To Leaf Binary Numbers

Solution: Recursion + Math

Keep tracking the number from root to current node.

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

C++

class Solution {

public:

int sumRootToLeaf(TreeNode* root) {

return sums(root, 0);

}

private:

static constexpr int kMod = 1e9 + 7;

int sums(TreeNode* root, int c) {

if (!root) return 0;

c = ((c << 1) | root->val) % kMod;

if (!root->left && !root->right) {

return c;

}

return sums(root->left, c) + sums(root->right, c);

}

};

LeetCode 1023. Camelcase Matching

Solution: String…

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

C++

// Author: Huahua

class Solution {

public:

vector<bool> camelMatch(vector<string>& queries, string p) {

vector<bool> ans;

for (const string& q : queries)

ans.push_back(match(q, p));

return ans;

}

private:

bool match(const string& q, const string& p) {

int m = p.length();

int n = q.length();

int i = 0;

int j = 0;

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

if (j == m && isupper(q[i])) return false;

if ((j == m || isupper(p[j])) && islower(q[i])) continue;

if ((isupper(p[j]) || isupper(q[i])) && p[j] != q[i]) return false;

if (islower(p[j]) && p[j] != q[i]) continue;

++j;

}

return i == n && j == m;

}

};

LeetCode 1024. Video Stitching

Solution 1: DP

Time complexity: O(nT^2)
Space complexity: O(T^2)

C++

// Author: Huahua, 16 ms / 9.5 MB

class Solution {

public:

int videoStitching(vector<vector<int>>& clips, int T) {

constexpr int kInf = 101;

// dp[i][j] := min clips to cover range [i, j]

vector<vector<int>> dp(T + 1, vector<int>(T + 1, kInf));

for (const auto& c : clips) {

int s = c[0];

int e = c[1];

for (int l = 1; l <= T; ++l) {

for (int i = 0; i <= T - l; ++i) {

int j = i + l;

if (s > j || e < i) continue;

if (s <= i && e >= j) dp[i][j] = 1;

else if (e >= j) dp[i][j] = min(dp[i][j], dp[i][s] + 1);

else if (s <= i) dp[i][j] = min(dp[i][j], dp[e][j] + 1);

else dp[i][j] = min(dp[i][j], dp[i][s] + 1 + dp[e][j]);

}

return dp[0][T] == kInf ? -1 : dp[0][T];

}

};

C++/V2

// Author: Huahua, running time: 20 ms / 9.4 MB

class Solution {

public:

int videoStitching(vector<vector<int>>& clips, int T) {

constexpr int kInf = 101;

// dp[i][j] := min clips to cover range [i, j]

vector<vector<int>> dp(T + 1, vector<int>(T + 1));

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

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

dp[i][j] = i < j ? kInf : 0;

for (const auto& c : clips) {

const int s = min(c[0], T);

const int e = min(c[1], T);

for (int l = 1; l <= T; ++l)

for (int i = 0, j = l; j <= T; ++i, ++j)

dp[i][j] = min(dp[i][j], dp[i][s] + 1 + dp[e][j]);

}

return dp[0][T] == kInf ? -1 : dp[0][T];

}

};

花花酱 LeetCode 145. Binary Tree Postorder Traversal

By zxi on September 8, 2017

Problem:

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

vector<int> ans;

postorderTraversal(root, ans);

return ans;

}

void postorderTraversal(TreeNode* root, vector<int>& ans) {

if (!root) return;

postorderTraversal(root->left, ans);

postorderTraversal(root->right, ans);

ans.push_back(root->val);

}

};

Solution 2:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

if (!root) return {};

vector<int> ans;

const vector<int> l = postorderTraversal(root->left);

const vector<int> r = postorderTraversal(root->right);

ans.insert(ans.end(), l.begin(), l.end());

ans.insert(ans.end(), r.begin(), r.end());

ans.push_back(root->val);

return ans;

}

};

Solution 3:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

if (!root) return {};

deque<int> ans;

stack<TreeNode*> s;

s.push(root);

while (!s.empty()) {

TreeNode* n = s.top();

s.pop();

ans.push_front(n->val); // O(1)

if (n->left) s.push(n->left);

if (n->right) s.push(n->right);

}

return vector<int>(ans.begin(), ans.end());

}

};

花花酱 LeetCode 422. Find All Duplicates in an Array

By zxi on March 18, 2017

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

<b>Input:</b>

[4,3,2,7,8,2,3,1]

<b>Output:</b>

[2,3]

class Solution {

public:

vector<int> findDuplicates(vector<int>& nums) {

vector<int> ans;

for(auto num : nums) {

int index = abs(num)-1;

if (nums[index] < 0)

ans.push_back(index+1);

nums[index]*=-1;

}

return ans;

}

};