第150场双周赛：好数字之和、分割正方形Ⅰ、分割正方形Ⅱ、最短匹配字符串

Q1、好数字之和 1、题目描述

给定一个整数数组 nums 和一个整数 k，如果元素 nums[i] 严格 大于下标 i - k 和 i + k 处的元素（如果这些元素存在），则该元素 nums[i] 被认为是 好 的。如果这两个下标都不存在，那么 nums[i] 仍然被认为是 好 的。

返回数组中所有 好 元素的 和。

2、解题思路

遍历 nums 数组，检查每个元素是否满足 好 元素的定义，满足条件就累加到结果 ret 中。

具体步骤： 初始化 ret = 0 用于存储所有 好 元素的和。遍历数组 nums，对每个元素 nums[i]： 如果 i - k 不存在，则 nums[i] 只需满足 nums[i] > nums[i + k]（如果 i + k 存在）。如果 i + k 不存在，则 nums[i] 只需满足 nums[i] > nums[i - k]（如果 i - k 存在）。如果 i - k 和 i + k 都存在，则 nums[i] 需要满足： nums[i] > nums[i - k]nums[i] > nums[i + k] 满足条件的 nums[i] 加入 ret。 返回 ret。 3、代码实现 class Solution { public: int sumOfGoodNumbers(vector<int>& nums, int k) { int ret = 0; // 用于存储所有"好"元素的总和 int n = nums.size(); // 数组长度 // 遍历数组 for (int i = 0; i < n; ++i) { // 检查 nums[i] 是否满足 "好" 元素的定义 // 如果 i-k 不存在, 跳过检查; 否则 nums[i] > nums[i - k] // 如果 i+k 不存在, 跳过检查; 否则 nums[i] > nums[i + k] if ((i - k < 0 || nums[i] > nums[i - k]) && (i + k >= n || nums[i] > nums[i + k])) { ret += nums[i]; // 计算 "好" 元素的和 } } return ret; } };

4、复杂度分析

时间复杂度： O(n)，因为我们只需要遍历 nums 一次，每个元素的检查都是 O(1) 。

空间复杂度： O(1)，我们仅仅使用了一个额外变量 ret 存储结果。

Q2、分割正方形 Ⅰ 1、题目描述

给你一个二维整数数组 squares ，其中 squares[i] = [xi, yi, li] 表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。

找到一个最小的 y 坐标，它对应一条水平线，该线需要满足它以上正方形的总面积 等于 该线以下正方形的总面积。

答案如果与实际答案的误差在 10-5 以内，将视为正确答案。

注意：正方形 可能会 重叠。重叠区域应该被 多次计数 。

2、解题思路

1. 计算搜索范围

首先，我们需要确定 y 的 上下边界：

down（最小的 y）：所有正方形左下角 y 的最小值。up（最大的 y）：所有正方形的最高点 y + l 的最大值。

这样，答案 mid 必须在 down ~ up 之间。

2. 计算总面积

遍历所有正方形，计算它们的总面积：

​ totalArea = ∑ side 2 \text{totalArea} = \sum \text{side}^2 totalArea=∑side2

目标是找到一条水平线，使得：

​ 上半部分面积 = 下半部分面积 = totalArea 2 \text{上半部分面积} = \text{下半部分面积} = \frac{\text{totalArea}}{2} 上半部分面积=下半部分面积=2totalArea​

3. 二分查找水平线

二分查找 mid（即 y 轴上的某个水平线）：

计算 该水平线以下的面积 areaBelow。如果 areaBelow 大于等于 totalArea / 2，说明 mid 过大，应该尝试更小的 mid，即 上界 up = mid。否则，说明 mid 过小，应该尝试更大的 mid，即 下界 down = mid。

终止条件：up - down <= 1e-5（精度要求）。

4. 计算 mid 以下的面积

对于每个正方形：

判断是否完全位于 mid 之下： 如果 y + l <= mid，整个正方形都在 mid 以下，直接加上 l × l 的面积。 部分位于 mid 之下： 计算 height = min(mid - y, l)（mid 线以下的部分）。这部分面积为 height × l。 3、代码实现 class Solution { public: double separateSquares(vector<vector<int>>& squares) { // 如果没有正方形, 返回 0.0 if (squares.empty()) { return 0.0; } // 初始化上下界 double down = static_cast<double>(squares[0][1]); // 最小的 y 值 double up = static_cast<double>(squares[0][1] + squares[0][2]); // 最大的 y+l 值 double totalArea = 0.0; // 总面积 // 计算最小/最大 y 值 和 总面积 for (const auto& v : squares) { double y = static_cast<double>(v[1]); // 左下角的 y 坐标 double l = static_cast<double>(v[2]); // 正方形边长 down = min(down, y); // 更新最小 y up = max(up, y + l); // 更新最大 y totalArea += l * l; // 计算总面积 } // 二分查找 while (up - down > 1e-5) { double mid = (up + down) / 2.0; // 计算中点 double areaBelow = 0.0; // mid 线以下的面积 // 计算当前 mid 线以下的面积 for (const auto& v : squares) { double y = static_cast<double>(v[1]); // 左下角 y 坐标 double l = static_cast<double>(v[2]); // 正方形边长 if (y < mid) { // 仅计算 y < mid 的部分 double height = min(mid - y, l); // 计算在 mid 下方的高度 areaBelow += height * l; // 计算面积并累加 } // 剪枝优化: 如果面积已经大于等于 halfArea, 则提前退出 if (areaBelow >= totalArea / 2) { break; } } // 二分查找 if (areaBelow >= totalArea / 2) { up = mid; // mid 过大, 缩小上界 } else { down = mid; // mid 过小, 扩大下界 } } return up; // 返回最终答案 } }; class Solution { public: double separateSquares(vector<vector<int>>& squares) { double totalArea = 0.0; int maxY = 0; // 计算总面积, 并确定最大 y 坐标 for (const auto& square : squares) { int x = square[0], y = square[1], side = square[2]; totalArea += static_cast<double>(side) * side; maxY = max(maxY, y + side); } // 判断是否满足条件 auto isValidY = [&](double yLine) -> bool { double areaBelow = 0.0; for (const auto& square : squares) { int y = square[1], side = square[2]; if (y < yLine) { double effectiveHeight = min(yLine - y, static_cast<double>(side)); areaBelow += effectiveHeight * side; } } return areaBelow >= totalArea / 2; }; // 二分查找满足条件的最小 y double left = 0.0, right = static_cast<double>(maxY); while (right - left > 1e-5) { double mid = (left + right) / 2.0; if (isValidY(mid)) { right = mid; } else { left = mid; } } return right; } };

4、复杂度分析

时间复杂度： O(n logM)

n 是正方形的个数。M 是 y 的搜索范围（最大 y 减去最小 y）。二分查找大约进行 logM 轮，每轮 O(n) 遍历正方形，最终 复杂度是 O(n logM)。

空间复杂度： O(1)

只使用了常数级变量，不需要额外的存储。 Q3、分割正方形 Ⅱ 1、题目描述

给你一个二维整数数组 squares ，其中 squares[i] = [xi, yi, li] 表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。

找到一个最小的 y 坐标，它对应一条水平线，该线需要满足它以上正方形的总面积 等于 该线以下正方形的总面积。

答案如果与实际答案的误差在 10-5 以内，将视为正确答案。

注意：正方形 可能会 重叠。重叠区域只 统计一次 。

2、解题思路

问题分析：

我们需要找到一个最小的 y 值（即水平线的 y 坐标），使得该线以上的总面积和以下的总面积相等。

由于正方形的重叠会导致面积的重复计算，因此我们需要跟踪每个 x 区间内的覆盖长度，计算这些区间的总面积。

区间求解：

我们可以利用线段树来处理区间的覆盖情况。线段树可以在区间更新时有效计算每个区间的覆盖长度。

坐标压缩：由于正方形的 x 坐标值范围可能非常大，直接使用这些值作为线段树的索引不切实际。因此我们将 x 坐标压缩到一个较小的范围。

步骤：

首先，对于每个正方形，提取其上边界和下边界，记录它们在 x 轴上的位置。

接着，我们对所有的事件进行排序。每个事件代表一个正方形的开始（下边界）或结束（上边界）。

使用线段树来更新每个正方形的覆盖状态，并计算每一条水平线（y 坐标）下面的总面积。然后通过累积的面积差来找到使总面积平衡的水平线。

3、代码实现 // 定义线段树节点的结构 struct Node { int minCover; // 当前节点的最小覆盖数, 表示该区间内有多少个正方形覆盖 int coveredLen; // 满足 minCover == 0 的线段长度, 表示该区间的实际被覆盖长度 int lazy; // 懒标记, 用于延迟更新 // 应用懒标记: 通过增加覆盖数来表示区间内正方形的覆盖情况 void apply(int value) { minCover += value; lazy += value; // 增加懒标记, 表示区间内的所有覆盖操作 } }; class SegmentTree { private: vector<Node> tree; // 存储线段树的节点 vector<int> compressedX; // 坐标压缩后的 x 值 int size; // 线段树的大小 // 合并两个子节点的结果, 返回合并后的节点 Node merge(const Node& left, const Node& right) { // 合并后最小覆盖数为左右子节点中的最小覆盖数 int minCover = min(left.minCover, right.minCover); // 如果左右子节点的最小覆盖数为 0, 则累加它们的覆盖长度 int coveredLen = (left.minCover == minCover ? left.coveredLen : 0) + (right.minCover == minCover ? right.coveredLen : 0); // 返回合并后的节点 return {minCover, coveredLen, 0}; } // 构建线段树的递归方法 void build(int node, int left, int right) { if (left == right) { // 如果当前区间是一个点, 则初始化该节点 tree[node] = {0, compressedX[right] - compressedX[right - 1], 0}; } else { // 否则递归构建左右子树 int mid = (left + right) / 2; build(node * 2, left, mid); build(node * 2 + 1, mid + 1, right); // 合并左右子树 tree[node] = merge(tree[node * 2], tree[node * 2 + 1]); } } // 懒标记下推操作, 更新子节点的懒标记 void pushDown(int node) { if (tree[node].lazy == 0) { return; // 如果当前节点没有懒标记, 则不需要下推 } // 将懒标记下推到左右子节点 tree[node * 2].apply(tree[node].lazy); tree[node * 2 + 1].apply(tree[node].lazy); tree[node].lazy = 0; // 清空当前节点的懒标记 } // 区间更新操作: 更新区间 [ql, qr] 的覆盖数 void modify(int node, int left, int right, int ql, int qr, int value) { // 如果当前区间完全在查询区间内, 则直接更新当前节点 if (ql <= left && right <= qr) { tree[node].apply(value); return; } // 如果当前区间与查询区间有交集, 则需要下推懒标记并递归更新左右子树 pushDown(node); int mid = (left + right) / 2; if (ql <= mid) { modify(node * 2, left, mid, ql, qr, value); } if (qr > mid) { modify(node * 2 + 1, mid + 1, right, ql, qr, value); } // 合并左右子树的结果 tree[node] = merge(tree[node * 2], tree[node * 2 + 1]); } public: // 构造函数, 接受压缩后的 x 坐标数组 SegmentTree(const vector<int>& uniqueX) { size = uniqueX.size(); compressedX = uniqueX; tree.resize(size * 4); // 为线段树分配空间 build(1, 1, size - 1); // 初始化线段树 } // 更新区间 [leftIndex, rightIndex] 的覆盖数 void update(int leftIndex, int rightIndex, int value) { modify(1, 1, size - 1, leftIndex, rightIndex, value); } // 获取线段树中当前覆盖数为 0 的区间的总长度 int getCoveredLength() { // 如果最小覆盖数为 0, 说明该区间没有被任何正方形覆盖 return tree[1].minCover == 0 ? (compressedX.back() - compressedX.front()) - tree[1].coveredLen // 返回该区间未被覆盖的部分长度 : compressedX.back() - compressedX.front(); // 否则返回整个区间长度 } }; // 主要的解题函数 class Solution { public: double separateSquares(vector<vector<int>>& squares) { // 使用 map 进行坐标压缩: 记录所有正方形的左下角和右上角的 x 坐标 map<int, int> coordMap; for (const auto& sq : squares) { coordMap[sq[0]] = 1; // 将正方形的左边 x 坐标添加到坐标映射中 coordMap[sq[0] + sq[2]] = 1; // 将正方形的右边 x 坐标添加到坐标映射中 } // 为每个唯一的 x 坐标分配一个压缩后的索引 int index = 0; for (auto& kv : coordMap) { kv.second = index++; } // 将压缩后的 x 坐标存入数组 vector<int> compressedX(index); for (auto& p : coordMap) { compressedX[p.second] = p.first; } // 生成事件列表: 记录正方形的上边界和下边界 vector<array<int, 4>> events; for (const auto& sq : squares) { // 正方形的下边界事件 events.push_back({sq[1], coordMap[sq[0]] + 1, coordMap[sq[0] + sq[2]], 1}); // 正方形的上边界事件 events.push_back({sq[1] + sq[2], coordMap[sq[0]] + 1, coordMap[sq[0] + sq[2]], -1}); } // 按 y 坐标 (即正方形的上下边界) 排序事件 sort(events.begin(), events.end()); // 使用线段树计算总面积 SegmentTree segTree(compressedX); long long totalArea = 0; for (size_t i = 0; i + 1 < events.size(); i++) { // 更新线段树的覆盖状态 segTree.update(events[i][1], events[i][2], events[i][3]); // 获取当前覆盖长度 int coveredLength = segTree.getCoveredLength(); // 累加总面积 totalArea += 1LL * coveredLength * (events[i + 1][0] - events[i][0]); } // 计算中位水平线的面积 long long accumulatedArea = 0; segTree = SegmentTree(compressedX); // 重新初始化线段树 for (size_t i = 0; i + 1 < events.size(); i++) { // 更新线段树 segTree.update(events[i][1], events[i][2], events[i][3]); // 获取当前覆盖长度 int coveredLength = segTree.getCoveredLength(); // 累加面积 accumulatedArea += 1LL * coveredLength * (events[i + 1][0] - events[i][0]); // 计算此时累计的面积和剩余面积的差值 long long areaDiff = accumulatedArea - (totalArea - accumulatedArea); // 如果累计面积大于或等于剩余面积, 则找到平衡线 if (areaDiff >= 0) { return events[i + 1][0] - 0.5 * areaDiff / coveredLength; } }; return -1; // 如果找不到合适的平衡线, 返回 -1 } };

4、复杂度分析

时间复杂度：

坐标压缩和事件排序：O(n log n)，其中 n 是正方形的个数。线段树的构建和查询：O(n log n)。总体时间复杂度 Q4、最短匹配字符串 1、题目描述

给你一个字符串 s 和一个模式字符串 p，其中 p 恰好 包含 两个 '*' 字符。

p 中的 '*' 匹配零个或多个字符的任何序列。

返回 s 中与 p 匹配的 最短 子字符串的长度。如果没有这样的子字符串，返回 -1。

子字符串 是字符串中的一个连续字符序列（空子字符串也被认为是合法字符串）。

2、解题思路

此问题的核心是利用字符串匹配的技巧来拆解模式字符串并在 s 中寻找匹配。由于 '*' 可以匹配任意字符序列，因此我们将模式字符串拆解为三个部分：

* 前的前缀部分；两个 * 之间的部分；* 后的后缀部分。

我们可以分别在 s 中查找这些部分的匹配，然后合并它们来获得最短匹配的子字符串。

具体步骤如下：

拆解模式字符串：将模式字符串 p 拆分为三个部分： 前缀部分：位于第一个 * 前；中间部分：位于两个 * 之间；后缀部分：位于第二个 * 后。 字符串匹配：分别在 s 中查找这三部分的匹配位置。 对于前缀和后缀部分，我们可以使用字符串匹配算法来查找其在 s 中的所有匹配位置。对于中间部分，我们可以从 s 中查找所有匹配位置，并确保它与前缀和后缀部分的匹配不重叠。 计算最短子字符串：通过遍历所有匹配的中间部分，尝试找到最短的匹配子字符串。 3、代码实现 class Solution { private: // 计算模式串 pattern 的前缀函数 (pi 数组) vector<int> computePrefixFunction(const string& pattern) { int n = pattern.size(); vector<int> pi(n, 0); // pi 数组记录每个位置的最长相等前后缀长度 int match = 0; // 遍历模式串的字符, 通过前缀函数更新匹配位置 for (int i = 1; i < n; ++i) { while (match > 0 && pattern[match] != pattern[i]) { match = pi[match - 1]; // 跳过不匹配部分 } if (pattern[match] == pattern[i]) { match++; } pi[i] = match; // 更新前缀函数 } return pi; } // 在文本串 text 中查找模式串 pattern 的所有匹配位置 vector<int> findPatternMatches(const string& text, const string& pattern) { int n = text.size(); int m = pattern.size(); if (m == 0) { // 如果模式串为空, pattern 的所有位置都能匹配空串 vector<int> pos(n + 1); iota(pos.begin(), pos.end(), 0); // 生成从 0 到 n 的位置 return pos; } vector<int> pi = computePrefixFunction(pattern); // 取前缀函数 vector<int> matches; // 用于存储匹配的位置 int match = 0; for (int i = 0; i < n; ++i) { while (match > 0 && pattern[match] != text[i]) { match = pi[match - 1]; // 找到最长的匹配前缀 } if (pattern[match] == text[i]) { match++; } if (match == m) { matches.push_back(i - m + 1); // 匹配成功, 记录匹配的起始位置 match = pi[match - 1]; // 使用前缀函数回溯, 继续查找下一个匹配 } } return matches; } public: // 计算最短的匹配子字符串 int shortestMatchingSubstring(const string& s, const string& p) { // 找到两个 '*' 的位置 int firstStar = p.find('*'); int lastStar = p.rfind('*'); // 获取前三段字符串 (即 '*' 之前、之间和之后的部分) string prefix = p.substr(0, firstStar); // 第一个 '*' 前的部分 string middle = p.substr(firstStar + 1, lastStar - firstStar - 1); // 两个 '*' 之间的部分 string suffix = p.substr(lastStar + 1); // 第二个 '*' 后的部分 // 分别查找每部分在 s 中的匹配位置 vector<int> prefixMatches = findPatternMatches(s, prefix); vector<int> middleMatches = findPatternMatches(s, middle); vector<int> suffixMatches = findPatternMatches(s, suffix); // 计算每段的长度 int lenPrefix = prefix.size(); int lenMiddle = middle.size(); int lenSuffix = suffix.size(); // 用于记录最短匹配子字符串的长度 int minLength = INT_MAX; int prefixIdx = 0, suffixIdx = 0; // 遍历所有的 middle 匹配, 寻找左右两边最近的匹配, 确保没有重叠 for (int middlePos : middleMatches) { // 处理右边, 找到离 middlePos 最近且不重叠的 suffix 匹配 while (suffixIdx < suffixMatches.size() && suffixMatches[suffixIdx] < middlePos + lenMiddle) { suffixIdx++; } if (suffixIdx == suffixMatches.size()) { break; } // 处理左边, 找到离 middlePos 最近且不重叠的 prefix 匹配 while (prefixIdx < prefixMatches.size() && prefixMatches[prefixIdx] <= middlePos - lenPrefix) { prefixIdx++; } if (prefixIdx > 0) { // 计算最短子字符串的长度 int currentLength = suffixMatches[suffixIdx] + lenSuffix - prefixMatches[prefixIdx - 1]; minLength = min(minLength, currentLength); // 更新最短长度 } } return minLength == INT_MAX ? -1 : minLength; // 如果找不到匹配, 返回 -1 } };

4、复杂度分析 计算前缀函数的时间复杂度为 O(m)，其中 m 为模式串的长度。在文本 s 中查找每个部分的匹配位置的时间复杂度为 O(n)，其中 n 为文本串的长度。最终合并各部分匹配位置并找到最短匹配的时间复杂度为 O(n)。

因此，整体时间复杂度为 O(n + m)，其中 n 为文本串长度，m 为模式串长度。