Leetcode 第 367 场周赛题解

题解"/>

Leetcode 第 367 场周赛题解

Leetcode 第 367 场周赛题解

• Leetcode 第 367 场周赛题解
• • 题目1：2903. 找出满足差值条件的下标 I
  • • 思路
    • 代码
    • 复杂度分析
  • 题目2：2904. 最短且字典序最小的美丽子字符串
  • • 思路1：枚举
    • 代码
    • 复杂度分析
    • 思路2：滑动窗口
  • 题目3：2905. 找出满足差值条件的下标 II
  • • 思路
    • 代码
    • 复杂度分析
  • 题目4：2906. 构造乘积矩阵
  • • 思路
    • 代码
    • 复杂度分析

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};}
};

复杂度分析

时间复杂度：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;}
};

复杂度分析

时间复杂度：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;}
};

时间复杂度：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 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

复杂度分析

时间复杂度：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 id=2906 lang=cpp** [2906] 构造乘积矩阵*/// @lc code=start// 前后缀分解
// 同 LeetCode 238class 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

复杂度分析

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

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