Leetcode 第 367 场周赛题解

Leetcode 第 367 场周赛题解

题目1：2903. 找出满足差值条件的下标 I

思路

模拟一下，属于秒杀题。

代码

class Solution
{
public:
    vector<int> findIndices(vector<int> &nums, int indexDifference, int valueDifference)
    {
        int n = nums.size();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                if (abs(i - j) >= indexDifference && abs(nums[i] - nums[j]) >= valueDifference)
                    return {i, j};
            }
        return {-1, -1};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复杂度分析

时间复杂度：O(n²)，其中 n 是数组的长度。

空间复杂度：O(1)。

题目2：2904. 最短且字典序最小的美丽子字符串

思路1：枚举

模拟。

1. 枚举美丽子字符串：getBeautifulSubstring() 函数从下标 begin 开始截取美丽子字符串 temp。
2. 更新答案：如果是第一个美丽子字符串，直接赋值给ans。后续将 ans 更新为最短且字典序最小的美丽子字符串。

代码

class Solution
{
public:
    string shortestBeautifulSubstring(string s, int k)
    {
        string ans = "";
        int n = s.size();
        for (int i = 0; i <= n - k; i++)
        {
            string temp = getBeautifulSubstring(s, i, k);
            if (temp.size() > 0)
            {
                if (ans.empty())
                    ans = temp;
                else
                {
                    if (temp.size() < ans.size())
                        ans = temp;
                    else if (temp.size() == ans.size())
                    {
                        if (compare(temp, ans))
                            ans = temp;
                    }
                }
            }
        }
        return ans;
    }
    // 辅函数 - 从下标 begin 开始截取美丽子字符串
    string getBeautifulSubstring(string &s, int begin, int k)
    {
        int n = s.size(), count_one = 0;
        string bss = "";
        for (int i = begin; i < n; i++)
        {
            bss += s[i];
            if (s[i] == '1')
                count_one++;
            if (count_one == k)
                return bss;
        }
        return "";
    }
    // 辅函数 - 比较 字符串 s 和字符串 t 的字典序
    bool compare(string &s, string &t)
    {
        int n = s.size();
        for (int i = 0; i < n; i++)
        {
            if (s[i] > t[i])
                return false;
            else if (s[i] < t[i])
                return true;
        }
        return true;
    }
};
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

复杂度分析

时间复杂度：O(n³)，其中 n 是字符串 s 的长度。

空间复杂度：O(n)，其中 n 是字符串 s 的长度。

思路2：滑动窗口

class Solution
{
public:
    string shortestBeautifulSubstring(string s, int k)
    {
        // 特判
        if (count(s.begin(), s.end(), '1') < k)
            return "";
        string ans = s;
        int n = s.size();
        int left = 0, count_one = 0;
        for (int right = 0; right < n; right++)
        {
            count_one += s[right] - '0';
            while (count_one > k || s[left] == '0')
            {
                count_one -= s[left] - '0';
                left++;
            }
            if (count_one == k)
            {
                string temp = s.substr(left, right - left + 1);
                if (temp.size() < ans.size() || (temp.size() == ans.size() && temp < ans))
                    ans = move(temp);
            }
        }
        return ans;
    }
};
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

时间复杂度：O(n²)，其中 n 是字符串 s 的长度。

空间复杂度：O(n)，其中 n 是字符串 s 的长度。

题目3：2905. 找出满足差值条件的下标 II

思路

双指针+维护最大值、最小值下标。

我们可以在枚举 j 的同时，维护最大值的下标 max_index 和最小值的下标 min_index。

那么只要满足下面两个条件中的一个，就可以返回答案了。

• abs(nums[max_index] - nums[j]) >= valueDifference
• abs(nums[min_index] - nums[j]) >= valueDifference

代码

/*
 * @lc app=leetcode.cn id=2905 lang=cpp
 *
 * [2905] 找出满足差值条件的下标 II
 */

// @lc code=start
class Solution
{
public:
    vector<int> findIndices(vector<int> &nums, int indexDifference, int valueDifference)
    {
        int n = nums.size();
        int max_index = 0, min_index = 0;
        for (int j = indexDifference; j < n; j++)
        {
            int i = j - indexDifference;
            if (nums[i] > nums[max_index])
                max_index = i;
            if (nums[i] < nums[min_index])
                min_index = i;
            if (abs(nums[max_index] - nums[j]) >= valueDifference)
                return {max_index, j};
            if (abs(nums[min_index] - nums[j]) >= valueDifference)
                return {min_index, j};
        }
        return {-1, -1};
    }
};
// @lc code=end
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

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。

空间复杂度：O(1)。

题目4：2906. 构造乘积矩阵

思路

前后缀分解

LeetCode 238 的矩阵版本。

构建前缀乘积和后缀乘积矩阵，L 和 R 分别表示左右两侧的乘积列表。

则 ans[i][j] = L[i][j] * R[i][j] % MOD。

代码

/*
 * @lc app=leetcode.cn id=2906 lang=cpp
 *
 * [2906] 构造乘积矩阵
 */

// @lc code=start

// 前后缀分解
// 同 LeetCode 238

class Solution
{
private:
    const int MOD = 12345;

public:
    vector<vector<int>> constructProductMatrix(vector<vector<int>> &grid)
    {
        if (grid.empty())
            return {};
        int n = grid.size(), m = n ? grid[0].size() : 0;
        vector<vector<int>> ans(n, vector<int>(m, 0));
        // L 和 R 分别表示左右两侧的乘积列表
        vector<vector<int>> L(n, vector<int>(m, 0)), R(n, vector<int>(m, 0));
        long prev = 1; // 前缀乘积
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
            {
                L[i][j] = prev;
                prev = prev * grid[i][j] % MOD;
            }
        long suffix = 1; // 后缀乘积
        for (int i = n - 1; i >= 0; i--)
            for (int j = m - 1; j >= 0; j--)
            {
                R[i][j] = suffix;
                suffix = suffix * grid[i][j] % MOD;
            }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                ans[i][j] = L[i][j] * R[i][j] % MOD;
        return ans;
    }
};
// @lc code=end
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

复杂度分析

时间复杂度：O(n*m)，其中 n 和 m 分别为 grid 的行数和列数。

空间复杂度：O(n*m)，其中 n 和 m 分别为 grid 的行数和列数。