Leetcode 第 140 场双周赛题解

题目1：3300. 替换为数位和以后的最小元素

思路

遍历，维护数位之和的最小值。

代码

class Solution {
public:int minElement(vector<int>& nums) {int minElem = INT_MAX;for (int &num : nums)minElem = min(minElem, digitSum(num));return minElem;}// 辅函数 - 求数位之和int digitSum(int x){int sum = 0;while (x) {sum += x % 10;x /= 10;}return sum;}
};

复杂度分析

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

空间复杂度：O(1)。

题目2：3301. 高度互不相同的最大塔高和

思路

将数组 maximumHeight 从大到小排序。

使用一个变量 mx 表示当前能用的最大高度，初始化为 maximumHeight[0]。

遍历数组 maximumHeight，如果 maximumHeight[i] >= mx，基于贪心的思想，maximumHeight[i] 最多保留到 mx - 1，更新 mx = maximumHeight[i]。

因为题目要求 maximumHeight[i] 要是一个正整数，所以如果 mx <= 0，可以提前得知没有合法的设置，返回 -1。

代码

/** @lc app=leetcode.cn id=3301 lang=cpp** [3301] 高度互不相同的最大塔高和*/// @lc code=start
class Solution
{
public:long long maximumTotalSum(vector<int> &maximumHeight){sort(maximumHeight.begin(), maximumHeight.end(), greater<>());int mx = maximumHeight[0];for (int i = 1; i < maximumHeight.size(); i++){if (maximumHeight[i] >= mx)maximumHeight[i] = mx - 1;mx = maximumHeight[i];if (mx <= 0)return -1;}return accumulate(maximumHeight.begin(), maximumHeight.end(), 0LL);}
};
// @lc code=end

复杂度分析

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

空间复杂度：O(1)。

题目3：3302. 字典序最小的合法序列

思路

题解：https://leetcode.cn/problems/find-the-lexicographically-smallest-valid-sequence/solutions/2934051/qian-hou-zhui-fen-jie-zi-xu-lie-pi-pei-t-le8d/

代码

/** @lc app=leetcode.cn id=3302 lang=cpp** [3302] 字典序最小的合法序列*/// @lc code=start
class Solution
{
public:vector<int> validSequence(string word1, string word2){int n = word1.length(), m = word2.length();vector<int> suf(n + 1);suf[n] = m;for (int i = n - 1, j = m - 1; i >= 0; i--){if (j >= 0 && word1[i] == word2[j])j--;suf[i] = j + 1;}vector<int> ans(m);bool changed = false; // 是否修改过for (int i = 0, j = 0; i < n; i++){if (word1[i] == word2[j] || !changed && suf[i + 1] <= j + 1){if (word1[i] != word2[j])changed = true;ans[j++] = i;if (j == m)return ans;}}return {};}
};
// @lc code=end

复杂度分析

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

空间复杂度：O(n)，其中 n 是 word1 的长度。

题目4：3303. 第一个几乎相等子字符串的下标

思路

现在变成了两个问题：

第一个问题：对于每个从 s[i] 开始的字符串 s[i…]，计算它能匹配 pattern 多长的前缀。
第二个问题：对于每个以 s[j] 结尾的字符串 s[…j]，计算它能匹配 pattern 多长的后缀。

代码

/** @lc app=leetcode.cn id=3303 lang=cpp** [3303] 第一个几乎相等子字符串的下标*/// @lc code=start
class Solution
{
public:int minStartingIndex(string s, string pattern){int n = s.length(), m = pattern.length();string rev_s = string(s.rbegin(), s.rend());string rev_pattern = string(pattern.rbegin(), pattern.rend());vector<int> preZ = getZ(pattern + s);vector<int> sufZ = getZ(rev_pattern + rev_s);reverse(sufZ.begin(), sufZ.end());for (int i = 0; i <= n - m; i++)if (preZ[i + m] + sufZ[i + m - 1] >= m - 1)return i;return -1;}// 辅函数vector<int> getZ(string s){int n = s.length();vector<int> z(n);int box_l = 0, box_r = 0; // z-box 左右边界for (int i = 1; i < n; i++){if (i <= box_r)z[i] = min(z[i - box_l], box_r - i + 1);while (i + z[i] < n && s[z[i]] == s[i + z[i]]){box_l = i;box_r = i + z[i];z[i]++;}}return z;}
};
// @lc code=end

复杂度分析

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

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