leetcode biweekly contest 510

leetcode contest 510

本周的题目还算是比较经典的题目，T3 是个好题目，T4 反而是个非常板的题目

Q1. Number of Elapsed Seconds Between Two Times

You are given two valid times startTime and endTime, each represented as a string in the format "HH:MM:SS".

Return the number of seconds that have elapsed from startTime to endTime.

Example 1:

Input: startTime = “01:00:00”, endTime = “01:00:25”

Output: 25

Explanation:

endTime is 25 seconds ahead of startTime.

Example 2:

Input: startTime = “12:34:56”, endTime = “13:00:00”

Output: 1504

Explanation:

endTime is 25 minutes and 4 seconds ahead of startTime, which equals 1504 seconds.

Constraints:

  • startTime.length == 8
  • endTime.length == 8
  • startTime and endTime are valid times in the format "HH:MM:SS"
  • 00 <= HH <= 23
  • 00 <= MM <= 59
  • 00 <= SS <= 59
  • endTime is not earlier than startTime

地址

https://leetcode.com/contest/weekly-contest-510/problems/number-of-elapsed-seconds-between-two-times/description/

题意

模拟

思路

  1. 直接解析出时间中的数字即可；
  2. 复杂度分析：
  • 时间复杂度：$O(C)$。
  • 空间复杂度：$O(C)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int secondsBetweenTimes(string startTime, string endTime) {
        auto parse = [](string s) -> int {
            int h = stoi(s);
            int m = stoi(s.substr(3));
            int t = stoi(s.substr(6));
            return h * 60 * 60 + m * 60 + t;
        };

        return parse(endTime) - parse(startTime);
    }
};

Q2. Minimum Total Cost to Process All Elements

You are given an integer array nums and an integer k.

Initially, you have k units of resources.

You must process the elements of nums from left to right. To process the ith element, you need nums[i] resources.

If your available resources are less than nums[i], you may perform an operation that increases your available resources by k. The value of k is fixed and does not change throughout the process. The first such operation incurs a cost of 1, the second incurs a cost of 2, and so on.

After processing the ith element, your available resources decrease by nums[i].

Return an integer denoting the minimum total cost required to process all elements. Since the answer may be very large, return it modulo 109 + 7.

Example 1:

Input: nums = [1,2,3,4], k = 4

Output: 3

Explanation:

  • After processing nums[0], we have 4 - 1 = 3 units of resources left.
  • After processing nums[1], we have 3 - 2 = 1 unit of resources left.
  • Since nums[2] = 3 and only 1 unit of resources is available, we perform the first operation costing 1. After processing nums[2], we have 1 + 4 - 3 = 2 units of resources left.
  • Since nums[3] = 4 and only 2 units of resources are available, we perform the second operation costing 2, to have 2 + 4 = 6 units of resources, which is enough to process nums[3].
  • Thus, the total cost is 1 + 2 = 3.

Example 2:

Input: nums = [1,1,7,14], k = 4

Output: 15

Explanation:

  • After processing nums[0], we have 4 - 1 = 3 units of resources left.
  • After processing nums[1], we have 3 - 1 = 2 units of resources left.
  • Since nums[2] = 7 and only 2 units of resources are available, we perform two operations costing 1 + 2 = 3. After processing nums[2], we have 2 + 4 + 4 - 7 = 3 units of resources left.
  • Since nums[3] = 14 and only 3 units of resources are available, we perform three operations costing 3 + 4 + 5 = 12, to have 3 + 4 + 4 + 4 = 15 units of resources, which is enough to process nums[3].
  • Thus, the total cost is 3 + 12 = 15.

Example 3:

Input: nums = [1,2,3,4], k = 10

Output: 0

Explanation:

To process all elements, we can use the initial 10 units of resources without performing any operations. Thus, the total cost required is 0.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 109

地址

https://leetcode.com/contest/weekly-contest-510/problems/minimum-total-cost-to-process-all-elements/description/

题意

模拟

思路

  1. 我们直接模拟即可，由于无法满足当前 $nums[i]$ ，则将当前值加上 $k$, 直到当前值满足大于等于 $nums[i]$ 即可；
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示给定数组的长度。
  • 空间复杂度：$O(1)$；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minimumCost(vector<int>& nums, int k) {
        int n = nums.size();
        long long mod = 1e9 + 7;
        long long curr = k;
        long long cnt = 0;
        for (int x : nums) {
            if (curr < x) {
                long long diff = (x - curr + k - 1) / k;
                curr = curr + diff * k - x;
                cnt += diff;
            } else {
                curr -= x;
            }
        }

        long long total = ((cnt % mod) * ((1 + cnt) % mod) / 2) % mod;

        return total % mod;
    }
};

Q3. Create Grid With Exactly K Paths I

You are given three integers m, n, and k.

Construct any m x n grid consisting only of the characters '.' and '#', where:

  • '.' represents a free cell.
  • '#' represents an obstacle cell.

A valid path is a sequence of free cells that:

  • Starts at the top-left cell (0, 0).
  • Ends at the bottom-right cell (m - 1, n - 1).
  • Moves only:
    • Right, from (i, j) to (i, j + 1), or
    • Down, from (i, j) to (i + 1, j).

Return any grid such that there are exactly k valid paths from the top-left cell to the bottom-right cell. If no such grid exists, return an empty array.

Example 1:

Input: m = 2, n = 3, k = 2

Output: [“…”,”#..”]

Explanation:

img

There are exactly k = 2 valid paths from (0, 0) to (1, 2):

  • (0, 0) → (0, 1) → (0, 2) → (1, 2)
  • (0, 0) → (0, 1) → (1, 1) → (1, 2)

Example 2:

Input: m = 3, n = 3, k = 4

Output: [“..#”,”…”,”#..”]

Explanation:

img

There are exactly k = 4 valid paths from (0, 0) to (2, 2):

  • (0, 0) → (0, 1) → (1, 1) → (1, 2) → (2, 2)
  • (0, 0) → (0, 1) → (1, 1) → (2, 1) → (2, 2)
  • (0, 0) → (1, 0) → (1, 1) → (1, 2) → (2, 2)
  • (0, 0) → (1, 0) → (1, 1) → (2, 1) → (2, 2)

Example 3:

Input: m = 1, n = 4, k = 2

Output: []

Explanation:

No grid exists with exactly k = 2 valid paths for a 1 x 4 grid, so the answer is an empty array.

Constraints:

  • 1 <= m, n <= 10
  • 1 <= k <= 4

地址

https://leetcode.com/contest/weekly-contest-510/problems/create-grid-with-exactly-k-paths-i/description/

题意

1
构造题目

思路

  1. 我们分类讨论如下，我们直到对于 $m \times n$ 的网格中由于第一步和最后一步是确定的，因此最多可以有 $T = C_{m+n-2}^{m-1}$ 条合法路径，此时我们分类讨论如下：

    • 如果给定的 $k > T$ ，此时一定不存在合法的填充方案；

    • 如果给定的 $k = T$，此时我们所有的格子均填充为 “.” 即可；

    • 如果满足 $k < T$, 此时的关键在于 $1 \le k \le 4$，此时我们分类如下：

      • 如果 $k = 1$：此时就只有一条固定路径，很容易构造；

      • 如果满足 $m \ge k, n \ge 2$：此时我们可以在某两个相邻的列，选择一块 $k \times 2$ 的区域全部填充为 “.” 即可，其余的位置有且只有唯一的路径，由于 $k \times 2$ 的区域，我们可以选择的合法路径数目刚好为 $k$；

      • 如果满足 $m \ge 2, n \ge 2$：此时我们可以在某两个相邻的列，选择一块 $2 \times k$ 的区域全部填充为 “.” 即可，其余的位置有且只有唯一的路径，由于 $2 \times k$ 的区域，我们可以选择的合法路径数目刚好为 $k$；

      • 特殊情况：当满足 $m = 3, n = 3, k = 4$ 时，此时我们直接构造即可；

        1
        2
        3
        ..#
        ...
        #..
  1. 复杂度分析：
  • 时间复杂度：$𝑂(mn)$，其中 $mn$ 表示给定的数字 $mn$;
  • 空间复杂度：$𝑂(1)$;

代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public:
    vector<string> createGrid(int m, int n, int k) {
        auto comb = [](int a, int b) -> long long {
            if (b > a) return 0;
            if (a == 0 || b == 0) {
                return 1;
            }
            long long res = 1;
            for (int i = 1; i <= b; i++) {
                res = res * (a - b + i) / i;
            }
            return res;
        };

        long long maxComb = comb(m + n - 2, m - 1);
        if (k > maxComb) {
            return {};
        }
        if (k == maxComb) {
            return vector<string>(m, string(n, '.'));
        }

        vector<string> grid(m, string(n, '#'));
        if (m >= 2 && n >= k) {
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < k; j++) {
                    grid[i][j] = '.';
                }
            }
            for (int i = 2; i < m; i++) {
                grid[i][k - 1] = '.';
            }
            for (int j = k; j < n; j++) {
                grid[m - 1][j] = '.';
            }

            return grid;
        }

        if (m >= k && n >= 2) {
            for (int i = 0; i < k; i++) {
                for (int j = 0; j < 2; j++) {
                    grid[i][j] = '.';
                }
            }
            for (int i = k; i < m; i++) {
                grid[i][1] = '.';
            }
            for (int j = 2; j < n; j++) {
                grid[m - 1][j] = '.';
            }

            return grid;
        }

        if (m == 3 && n == 3 && k == 4) {
            return {"..#", "...", "#.."};
        }

        return {};
    }
};

Q4. Maximum Consistent Columns in a Grid

You are given a 2D integer array grid of size m x n, and an integer limit.

You may remove zero or more columns from the grid, but at least one column must remain. The relative order of the remaining columns must be preserved.

A grid is called consistent if for every row i, and for every pair of adjacent remaining columns a and b with a < b, the following holds: |grid[i][b] - grid[i][a]| <= limit.

Return the maximum number of columns that can remain such that the resulting grid is consistent.

Example 1:

Input: grid = [[-2,0,3]], limit = 2

Output: 2

Explanation:

  • Remove column 2 and keep columns 0 and 1, which gives |grid[0][1] − grid[0][0]| = |0 − (−2)| = 2 <= limit.
  • Thus, the maximum number of columns that can remain is 2.

Example 2:

Input: grid = [[1,-1,1],[2,2,2]], limit = 1

Output: 2

Explanation:

  • Remove column 1 and keep columns 0 and 2, which gives
    • |grid[0][2] − grid[0][0]| = |1 − 1| = 0 <= limit and
    • |grid[1][2] − grid[1][0]| = |2 − 2| = 0 <= limit.
  • Thus, the maximum number of columns that can remain is 2.

Example 3:

Input: grid = [[-5,5]], limit = 9

Output: 1

Explanation:

  • Remove either column 0 or column 1, since |grid[0][1] − grid[0][0]| = |5 − (−5)| = 10 > limit.
  • Thus, the maximum number of columns that can remain is 1.

Constraints:

  • 1 <= m == grid.length <= 250
  • 1 <= n == grid[i].length <= 250
  • -105 <= grid[i][j] <= 105
  • 0 <= limit <= 105

地址

https://leetcode.com/contest/weekly-contest-510/problems/maximum-consistent-columns-in-a-grid/description/

题意

动态规划

思路

  1. 题目要求去掉列以后，剩余的列中满足相邻的列元素差的绝对值不超过 $limit$，我们提前计算列 $i$ 是否可以满足与列 $j$ 相邻即可；设 $dp[i]$ 表示保留第 $i$ 且满足题目要求时最大保留的列的数目，此时我们可以得到递推公式如下：

    此时我们遍历所有以 $j$ 结尾且 $(i,j)$ 列可以满足相邻即可；

  2. 复杂度分析：

  • 时间复杂度：$𝑂(mn^2)$，其中 $m,n$ 表示给定矩阵的行数与列数.
  • 空间复杂度：$𝑂(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
28
29
30
31
class Solution {
public:
    int maxConsistentColumns(vector<vector<int>>& grid, int limit) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<bool>> valid(n, vector<bool>(n, false));

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int diff = 0;
                for (int k = 0; k < m; k++) {
                    diff = max(diff, abs(grid[k][i] - grid[k][j]));
                }
                if (diff <= limit) {
                    valid[i][j] = true;
                }
            }
        }

        vector<int> dp(n, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (valid[j][i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }

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

欢迎关注和打赏，感谢支持！

力扣周赛
#题解 #力扣周赛赛
leetcode biweekly contest 510
http://example.com/2026/09/08/力扣周赛题解/233/
Author
Mike Meng
Posted on
September 8, 2026
Licensed under