↓ Skip to main content
Dawn Magnet’s Site
2021 LeetCode Autumn Team Competition Review

2021 LeetCode Autumn Team Competition Review

·2433 words·5 mins· loading · loading ·
Author
Dawn Magnet
Tech enthusiast & daily solver.

Foreword
#

1
1
This year’s performance was pretty good. Let us do even better next time! I finished Problems 2 and 4 in 30 minutes, while my teammates finished Problems 1 and 3 in a little over an hour. After that came several hours when we had no idea what to do…

Let us try not to end up in this situation again.

Problem 1: Opening Ceremony Fireworks
#

1.1 Problem Statement
#

The opening ceremony of the LeetCode Challenge has begun, and a giant tree-shaped firework has bloomed in the sky.
Given a binary tree root representing the firework, the value of each node represents the color at that position of the giant firework. Help Xiao Kou calculate how many distinct colors appear in the giant firework.

Example 1:

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

Output: 3

Explanation: There are 3 distinct colors in the firework, with values 1, 2, and 3.

Example 2:

Input: root = [3,3,3]

Output: 1

Explanation: Only 1 color appears in the firework, with value 3.

Constraints:

  • 1 <= number of nodes <= 1000
  • 1 <= Node.val <= 1000

1.2 Analysis
#

Store the states in a dp array. Whenever a value has not appeared before, increment the count once.

1.3 Code
#

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool dp[1005];
    int count = 0;
    void deal(TreeNode * root) {
        if (!root) return ;
        if (!dp[root->val]) {
            count++;
            dp[root->val] = true;
        }
        deal(root->left);
        deal(root->right);
    }
    int numColor(TreeNode* root) {
        deal(root);
        return count;
    }
};

Problem 2: Bicycle Stunt Arena
#

2.1 Problem Statement
#

In the N*M-sized bicycle stunt arena of the LeetCode Challenge, the terrain consists of continuous ups and downs. The terrain heights are recorded in the two-dimensional array terrain, and the deceleration values are recorded in the two-dimensional array obstacle.

  • If a contestant rides from a position with height h1 and deceleration value o1 to an adjacent position with height h2 and deceleration value o2 (in one of the four directions: up, down, left, or right), the change in speed is h1-h2-o2 (a negative value slows the contestant down, while a positive value speeds the contestant up).

The contestant starts at coordinate position with an initial speed of 1. Which other positions can the contestant reach while still having speed 1? Return these positions as a two-dimensional array. If there are multiple positions, sort them by row coordinate in ascending order; when the row coordinates are equal, sort by column coordinate in ascending order.

Note: The speed cannot be zero or negative during the ride.

Example 1:

Input: position = [0,0], terrain = [[0,0],[0,0]], obstacle = [[0,0],[0,0]]

Output: [[0,1],[1,0],[1,1]]

Explanation:
Because the current terrain is flat, the rules above let the contestant start at [0,0] and reach every other position with speed 1.

Example 2:

Input: position = [1,1], terrain = [[5,0],[0,6]], obstacle = [[0,6],[7,0]]

Output: [[0,1]]

Explanation:
Starting from [1,1], the contestant has exactly speed 1 upon reaching [0,1].

Constraints:

  • n == terrain.length == obstacle.length
  • m == terrain[i].length == obstacle[i].length
  • 1 <= n <= 100
  • 1 <= m <= 100
  • 0 <= terrain[i][j], obstacle[i][j] <= 100
  • position.length == 2
  • 0 <= position[0] < n
  • 0 <= position[1] < m

2.2 Analysis
#

This is a relatively basic depth-first-search problem. Memoization may be needed to remove duplicate states.

After reading the problem carefully, we can see that arriving at a position does not necessarily imply the same speed every time. Different paths to the same position may produce different speeds.

Therefore, we must record the state. If we reach the same position twice with the same speed, we do not need to continue from it again. Without this check, a cycle can occur, as in Example 1; failing to remove duplicates would lead to an infinite loop.

In summary, the approach is DFS plus memoization for duplicate-state elimination (pruning). The pruning condition is met only when the same position is reached with the same speed.

The code is mainly divided into a main function and a DFS function. The DFS function accepts three parameters: the current x and y coordinates and the current speed. When passed[x][y][speed] is true, the same position has already been traversed at the same speed, so there is no need to traverse it again. When res[x][y] is true, the coordinate is a candidate answer. We then traverse the four directions in the usual way, stopping when the speed is less than 0 and so on.

The main function handles the input and output, stores some global variables, and performs a simple conversion of res into the required answer format.

2.3 C++ Code
#

using VI = vector<int>;
using VVI = vector<VI>;
const VI direc = {0, 1, 0, -1, 0};
class Solution {
public:
    VVI t, o;
    bool res[100][100] = {};
    bool passed[100][100][105] = {};
    int n, m;
    void dfs(int x, int y, int speed) {
        if (speed == 1) res[x][y] = true;
        if (speed < 1) return;
        if (passed[x][y][speed]) {
            return;
        }
        passed[x][y][speed] = true;
        for (int i = 0; i < 4; ++i) {
            int xt = x + direc[i];
            int yt = y + direc[i + 1];
            if (xt >= 0 && yt >= 0 && xt < n && yt < m)
                dfs(xt, yt, speed + t[x][y] - t[xt][yt] - o[xt][yt]);
        }
    }
    VVI bicycleYard(VI& p, VVI& terrain, VVI& obstacle) {
        t = terrain;
        o = obstacle;
        n = t.size();
        m = t[0].size();
        int x = p[0], y = p[1];
        dfs(x, y, 1);
        VVI res_v;
        res[x][y] = false;
        for (int i = 0; i < 100; ++i)
            for (int j = 0; j < 100; ++j)
                if (res[i][j])
                    res_v.push_back({i, j});
        return res_v;
    }
};

Problem 3: Volunteer Deployment
#

3.1 Problem Statement
#

The LeetCode Challenge has n competition venues (venue IDs start at 0). The distribution of channels between venues is recorded in the two-dimensional array edges, where edges[i]= [x, y] means that channel i connects venue x and venue y (that is, the two venues are adjacent). Initially, each venue has a certain number of volunteers, and the numbers may differ between venues. Over the next m days, the volunteer counts are adjusted each day according to the event's popularity. There are three possible adjustment operations:

  1. Halve the number of volunteers in the venue numbered idx.
  2. Add the number of volunteers in venue idx to the volunteer count of every venue adjacent to venue idx.
  3. Subtract the number of volunteers in venue idx from the volunteer count of every venue adjacent to venue idx.

All adjustment information is recorded in the array plans, where plans[i] = [num,idx] means that on day i, adjustment plan num was applied to venue idx .
During the post-event review, the final volunteer count of venue 0 was accidentally lost. We retained only the initial total number of volunteers across all venues, totalNum, and a one-dimensional array finalCnt containing the final volunteer counts of venues 1 ~ n-1 . Use the available information to calculate the initial volunteer count of every venue, and return the list in venue-number order.

Note:

  • The test data guarantees that a venue's volunteer count is even whenever the first adjustment is applied to it.
  • The test data guarantees that the volunteer count of every neighboring venue is non-negative whenever the third adjustment is applied.
  • The test data guarantees that no venue has more than 10^9 volunteers when the competition begins.
  • The test data guarantees that the given road network contains no self-loops or parallel edges.

Example 1:

image.png
Input:
finalCnt = [1,16], totalNum = 21, edges = [[0,1],[1,2]], plans = [[2,1],[1,0],[3,0]]

Output: [5,7,9]

Explanation:
image.png

Example 2:

Input:
finalCnt = [4,13,4,3,8], totalNum = 54, edges = [[0,3],[1,3],[4,3],[2,3],[2,5]], plans = [[1,1],[3,3],[2,5],[1,0]]

Output: [10,16,9,4,7,8]

Constraints:

  • 2 <= n <= 5*10^4
  • 1 <= edges.length <= min((n * (n - 1)) / 2, 5*10^4)
  • 0 <= edges[i][0], edges[i][1] < n
  • 1 <= plans.length <= 10
  • 1 <= plans[i][0] <=3
  • 0 <= plans[i][1] < n
  • finalCnt.length = n-1
  • 0 <= finalCnt[i] < 10^9
  • 0 <= totalNum < 5*10^13

3.2 Analysis
#

There is only one unknown value: the number of volunteers in venue 0 at the current (final) time.

It is not difficult to see that all three operations are linear operations, and we know the exact operation performed at every step. Therefore, if we know the number of volunteers in venue 0 at the final time, we can reverse the process precisely back to the first step. At that point, the total number of volunteers must equal totalNum exactly.

Let x denote the number of volunteers in venue 0 at the final time. We can reason backwards. After reversing the process to the first step, the count in every venue is a linear function of x. Their sum is also a linear function, and this sum must equal totalNum. Substituting totalNum into that equation gives x; substituting x into each venue’s expression then gives its initial volunteer count.

In the implementation, the two arrays x_param and c_param represent the coefficient of x and the constant term of each venue’s linear function. After reversing all plans, compute x_param_sum and c_param_sum. The equation for x is:

$$ \sum^{n}_{i=1}{x_{param}[i]} * x + \sum^{n}_{i=1}{c_{param}[i]} = totalNum $$

After a simple rearrangement:

$$ x = \frac{(totalNum - \sum^{n}_{i=1}{c_{param}[i]})}{\sum^{n}_{i=1}{x_{param}[i]}} $$

Finally, substitute x into each expression to complete the calculation.

3.3 C++ Code
#

using VI = vector<int>;
using VVI = vector<VI>;
using ll = long long;
class Solution {
public:
    VI volunteerDeployment(VI& finalCnt, ll totalNum, VVI& edges, VVI& plans) {
        VI m[50005];
        int n = finalCnt.size() + 1;
        // x系数和常数
        int x_param[50005] = {}, c_param[50005] = {};
        for (auto & edge : edges) {
            m[edge[0]].push_back(edge[1]);
            m[edge[1]].push_back(edge[0]);
        }
        x_param[0] = 1;
        for (int i = 0; i < n - 1; ++i)
            c_param[i + 1] = finalCnt[i];
        while (plans.size()) {
            int kind = plans.back()[0];
            int place = plans.back()[1];
            plans.pop_back();
            if (kind == 1) {
                x_param[place] *= 2;
                c_param[place] *= 2;
            } else if (kind == 2) {
                for (auto & nxt : m[place]) {
                    x_param[nxt] -= x_param[place];
                    c_param[nxt] -= c_param[place];
                }
            } else {
                for (auto & nxt : m[place]) {
                    x_param[nxt] += x_param[place];
                    c_param[nxt] += c_param[place];
                }
            }
        }
        ll x_param_sum = 0, c_param_sum = 0;
        for (int i = 0; i < n; ++i) {
            x_param_sum += x_param[i];
            c_param_sum += c_param[i];
        }
        // 方程: x_param_sum * x + c_param_sum = totalNum
        int x = (totalNum - c_param_sum) / x_param_sum;
        vector<int> res(n);
        for (int i = 0; i < n; ++i)
            res[i] = x_param[i] * x + c_param[i];
        return res;
    }
};

Problem 4: Entry Security Check
#

4.1 Problem Statement
#

The entry ceremony of the LeetCode Challenge is about to begin. For security reasons, N security rooms have been set up, with a total capacity of M; capacities[i] records the capacity of security room i. There are two types of security rooms:

  • First in, first out: among all spectators in the room, the spectator who entered earliest leaves first.
  • Last in, first out: among all spectators in the room, the spectator who entered most recently leaves first.

c24754f1a5ff56989340ba5004dc5eda.gif

Exactly M+1 spectators (numbered from 0) need to queue to pass through security in order. The rules are:

  • A spectator must first enter security room 0.
  • When a spectator enters security room i (0 <= i < N ),
    • If the room has not reached its capacity, the spectator may enter directly.
    • If the room has reached capacity, one spectator must leave according to the room type before the new spectator can enter.
  • When a spectator leaves security room i (0 <= i < N-1 ), they enter security room i+1 for the next security check.

If the type of each security room can be chosen arbitrarily, how many assignments make spectator k the first spectator to pass through the final security room and enter?

Note:

  • Spectators cannot leave a security room voluntarily. A spectator can leave only when the room is full and a new spectator needs to enter; the room type then determines who leaves.
  • Since the number of assignments may be large, return the answer modulo 1000000007.

Example 1:

Input: capacities = [2,2,3], k = 2

Output: 2
Explanation:
There are 2 valid assignments:

  • Assignment 1: set rooms 0 and 1 to last-in, first-out, and room 2 to first-in, first-out.
  • Assignment 2: set rooms 0 and 1 to first-in, first-out, and room 2 to last-in, first-out.

The following is an illustration of Assignment 1:
c60e38199a225ad62f13b954872edf9b.gif

Example 2:

Input: capacities = [3,3], k = 3

Output: 0

Example 3:

Input: capacities = [4,3,2,2], k = 6

Output: 2

Constraints:

  • 1 <= capacities.length <= 200
  • 1 <= capacities[i] <= 200
  • 0 <= k <= sum(capacities)

4.2 Analysis
#

Observe that first-in, first-out corresponds to a queue, while last-in, first-out corresponds to a stack.

Looking at the second GIF, when a container (which we will also call a room) is a queue, the first person to enter is the first person to leave. Thus, a queue has no effect on the first person in the process. In contrast, consider a stack: a stack of length 2 must first be filled with one element, and that element is fixed in place and cannot move. Therefore, for the first person in the process, a stack of length c can intercept c-1 people.

The rest is simple. To make person k reach the front, we must use stacks to intercept the first k people.

We can therefore rewrite the problem in a familiar form:

有`N`个硬币，每个的金额都在`cap`数组中给出（需要一个减 1 操作）。我们从前往后选，求最终金额为`k`的方案数。

Does it look much simpler now?

The final solution is a straightforward dynamic program. Because each coin can be used only once, the direction in which we update dp must be controlled.

4.3 C++ Code
#

const int md = 1000000007;
class Solution {
public:
    int securityCheck(vector<int>& cap, int k) {
        for (auto & c : cap) c--;
        int sum = accumulate(cap.begin(), cap.end(), 0);
        if (sum < k) return 0;
        int dp[40005] = {1};
        for (auto & c : cap) {
            for (int i = k - c; i >= 0; --i) {
                (dp[i + c] += dp[i]) %= md;
            }
        }
        return dp[k];
    }
};