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

Q1、好数字之和

1、题目描述

给定一个整数数组 nums 和一个整数 k，假如元素 nums 严酷 大于下标 i - k 和 i + k 处的元素（假如这些元素存在），则该元素 nums 被认为是 好 的。假如这两个下标都不存在，那么 nums 仍旧被认为是 好 的。
返回数组中全部 好 元素的 和。
2、解题思绪

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

• 初始化 ret = 0 用于存储全部 好 元素的和。
  
• 遍历数组 nums，对每个元素 nums：
  
  
  
  • 假如 i - k 不存在，则 nums 只需满足 nums > nums[i + k]（假如 i + k 存在）。
    
  • 假如 i + k 不存在，则 nums 只需满足 nums > nums[i - k]（假如 i - k 存在）。
    
  • 假如 i - k 和 i + k 都存在，则 nums 必要满足：
    
    
    
    • nums > nums[i - k]
      
    • nums > nums[i + k]
      
    
    
  • 满足条件的 nums 加入 ret。
    
  
  
• 返回 ret。
  

3、代码实现

1. class Solution {
2. public:
3.     int sumOfGoodNumbers(vector<int>& nums, int k) {
4.         int ret = 0;         // 用于存储所有"好"元素的总和
5.         int n = nums.size(); // 数组长度
7.         // 遍历数组
8.         for (int i = 0; i < n; ++i) {
9.             // 检查 nums[i] 是否满足 "好" 元素的定义
10.             // 如果 i-k 不存在, 跳过检查; 否则 nums[i] > nums[i - k]
11.             // 如果 i+k 不存在, 跳过检查; 否则 nums[i] > nums[i + k]
12.             if ((i - k < 0 || nums[i] > nums[i - k]) && (i + k >= n || nums[i] > nums[i + k])) {
13.                 ret += nums[i]; // 计算 "好" 元素的和
14.             }
15.         }
16.         return ret;
17.     }
18. };

复制代码

4、复杂度分析

时间复杂度： O(n)，由于我们只必要遍历 nums 一次，每个元素的检查都是 O(1) 。
空间复杂度： O(1)，我们仅仅利用了一个额外变量 ret 存储结果。

Q2、分割正方形 Ⅰ

1、题目描述

给你一个二维整数数组 squares ，此中 squares = [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、代码实现

1. class Solution {
2. public:
3.     double separateSquares(vector<vector<int>>& squares) {
4.         // 如果没有正方形, 返回 0.0
5.         if (squares.empty()) {
6.             return 0.0;
7.         }
9.         // 初始化上下界
10.         double down = static_cast<double>(squares[0][1]); // 最小的 y 值
11.         double up = static_cast<double>(squares[0][1] + squares[0][2]); // 最大的 y+l 值
12.         double totalArea = 0.0; // 总面积
14.         // 计算最小/最大 y 值 和 总面积
15.         for (const auto& v : squares) {
16.             double y = static_cast<double>(v[1]); // 左下角的 y 坐标
17.             double l = static_cast<double>(v[2]); // 正方形边长
19.             down = min(down, y); // 更新最小 y
20.             up = max(up, y + l); // 更新最大 y
21.             totalArea += l * l;  // 计算总面积
22.         }
24.         // 二分查找
25.         while (up - down > 1e-5) {
26.             double mid = (up + down) / 2.0; // 计算中点
27.             double areaBelow = 0.0;         // mid 线以下的面积
29.             // 计算当前 mid 线以下的面积
30.             for (const auto& v : squares) {
31.                 double y = static_cast<double>(v[1]); // 左下角 y 坐标
32.                 double l = static_cast<double>(v[2]); // 正方形边长
34.                 if (y < mid) {                       // 仅计算 y < mid 的部分
35.                     double height = min(mid - y, l); // 计算在 mid 下方的高度
36.                     areaBelow += height * l;         // 计算面积并累加
37.                 }
39.                 // 剪枝优化: 如果面积已经大于等于 halfArea, 则提前退出
40.                 if (areaBelow >= totalArea / 2) {
41.                     break;
42.                 }
43.             }
45.             // 二分查找
46.             if (areaBelow >= totalArea / 2) {
47.                 up = mid; // mid 过大, 缩小上界
48.             } else {
49.                 down = mid; // mid 过小, 扩大下界
50.             }
51.         }
53.         return up; // 返回最终答案
54.     }
55. };

复制代码

1. class Solution {
2. public:
3.     double separateSquares(vector<vector<int>>& squares) {
4.         double totalArea = 0.0;
5.         int maxY = 0;
7.         // 计算总面积, 并确定最大 y 坐标
8.         for (const auto& square : squares) {
9.             int x = square[0], y = square[1], side = square[2];
10.             totalArea += static_cast<double>(side) * side;
11.             maxY = max(maxY, y + side);
12.         }
14.         // 判断是否满足条件
15.         auto isValidY = [&](double yLine) -> bool {
16.             double areaBelow = 0.0;
17.             for (const auto& square : squares) {
18.                 int y = square[1], side = square[2];
19.                 if (y < yLine) {
20.                     double effectiveHeight = min(yLine - y, static_cast<double>(side));
21.                     areaBelow += effectiveHeight * side;
22.                 }
23.             }
24.             return areaBelow >= totalArea / 2;
25.         };
27.         // 二分查找满足条件的最小 y
28.         double left = 0.0, right = static_cast<double>(maxY);
29.         while (right - left > 1e-5) {
30.             double mid = (left + right) / 2.0;
31.             if (isValidY(mid)) {
32.                 right = mid;
33.             } else {
34.                 left = mid;
35.             }
36.         }
38.         return right;
39.     }
40. };

复制代码

4、复杂度分析

时间复杂度： O(n logM)

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

空间复杂度： O(1)

• 只利用了常数级变量，不必要额外的存储。
  

Q3、分割正方形 Ⅱ

1、题目描述

给你一个二维整数数组 squares ，此中 squares = [xi, yi, li] 表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。
找到一个最小的 y 坐标，它对应一条水平线，该线必要满足它以上正方形的总面积 等于 该线以下正方形的总面积。
答案假如与实际答案的毛病在 10-5 以内，将视为正确答案。
留意：正方形 可能会 重叠。重叠区域只 统计一次 。
2、解题思绪

• 问题分析：
  
  
  
  • 我们必要找到一个最小的 y 值（即水平线的 y 坐标），使得该线以上的总面积和以下的总面积相等。
    
  • 由于正方形的重叠会导致面积的重复计算，因此我们必要跟踪每个 x 区间内的覆盖长度，计算这些区间的总面积。
    
  
  
• 区间求解：
  
  
  
  • 我们可以利用线段树来处置惩罚区间的覆盖情况。线段树可以在区间更新时有效计算每个区间的覆盖长度。
    
  • 坐标压缩：由于正方形的 x 坐标值范围可能非常大，直接利用这些值作为线段树的索引不切实际。因此我们将 x 坐标压缩到一个较小的范围。
    
  
  
• 步调：
  
  
  
  • 首先，对于每个正方形，提取其上界限和下界限，记录它们在 x 轴上的位置。
    
  • 接着，我们对全部的事件举行排序。每个事件代表一个正方形的开始（下界限）或竣事（上界限）。
    
  • 利用线段树来更新每个正方形的覆盖状态，并计算每一条水平线（y 坐标）下面的总面积。然后通过累积的面积差来找到使总面积均衡的水平线。
    
  
  

3、代码实现

1. // 定义线段树节点的结构
2. struct Node {
3.     int minCover;   // 当前节点的最小覆盖数, 表示该区间内有多少个正方形覆盖
4.     int coveredLen; // 满足 minCover == 0 的线段长度, 表示该区间的实际被覆盖长度
5.     int lazy;       // 懒标记, 用于延迟更新
7.     // 应用懒标记: 通过增加覆盖数来表示区间内正方形的覆盖情况
8.     void apply(int value) {
9.         minCover += value;
10.         lazy += value; // 增加懒标记, 表示区间内的所有覆盖操作
11.     }
12. };
14. class SegmentTree {
15. private:
16.     vector<Node> tree;       // 存储线段树的节点
17.     vector<int> compressedX; // 坐标压缩后的 x 值
18.     int size;                // 线段树的大小
20.     // 合并两个子节点的结果, 返回合并后的节点
21.     Node merge(const Node& left, const Node& right) {
22.         // 合并后最小覆盖数为左右子节点中的最小覆盖数
23.         int minCover = min(left.minCover, right.minCover);
25.         // 如果左右子节点的最小覆盖数为 0, 则累加它们的覆盖长度
26.         int coveredLen = (left.minCover == minCover ? left.coveredLen : 0) + (right.minCover == minCover ? right.coveredLen : 0);
28.         // 返回合并后的节点
29.         return {minCover, coveredLen, 0};
30.     }
32.     // 构建线段树的递归方法
33.     void build(int node, int left, int right) {
34.         if (left == right) {
35.             // 如果当前区间是一个点, 则初始化该节点
36.             tree[node] = {0, compressedX[right] - compressedX[right - 1], 0};
37.         } else {
38.             // 否则递归构建左右子树
39.             int mid = (left + right) / 2;
40.             build(node * 2, left, mid);
41.             build(node * 2 + 1, mid + 1, right);
42.             // 合并左右子树
43.             tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
44.         }
45.     }
47.     // 懒标记下推操作, 更新子节点的懒标记
48.     void pushDown(int node) {
49.         if (tree[node].lazy == 0) {
50.             return; // 如果当前节点没有懒标记, 则不需要下推
51.         }
52.         // 将懒标记下推到左右子节点
53.         tree[node * 2].apply(tree[node].lazy);
54.         tree[node * 2 + 1].apply(tree[node].lazy);
55.         tree[node].lazy = 0; // 清空当前节点的懒标记
56.     }
58.     // 区间更新操作: 更新区间 [ql, qr] 的覆盖数
59.     void modify(int node, int left, int right, int ql, int qr, int value) {
60.         // 如果当前区间完全在查询区间内, 则直接更新当前节点
61.         if (ql <= left && right <= qr) {
62.             tree[node].apply(value);
63.             return;
64.         }
66.         // 如果当前区间与查询区间有交集, 则需要下推懒标记并递归更新左右子树
67.         pushDown(node);
68.         int mid = (left + right) / 2;
69.         if (ql <= mid) {
70.             modify(node * 2, left, mid, ql, qr, value);
71.         }
72.         if (qr > mid) {
73.             modify(node * 2 + 1, mid + 1, right, ql, qr, value);
74.         }
75.         // 合并左右子树的结果
76.         tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
77.     }
79. public:
80.     // 构造函数, 接受压缩后的 x 坐标数组
81.     SegmentTree(const vector<int>& uniqueX) {
82.         size = uniqueX.size();
83.         compressedX = uniqueX;
84.         tree.resize(size * 4); // 为线段树分配空间
85.         build(1, 1, size - 1); // 初始化线段树
86.     }
88.     // 更新区间 [leftIndex, rightIndex] 的覆盖数
89.     void update(int leftIndex, int rightIndex, int value) {
90.         modify(1, 1, size - 1, leftIndex, rightIndex, value);
91.     }
93.     // 获取线段树中当前覆盖数为 0 的区间的总长度
94.     int getCoveredLength() {
95.         // 如果最小覆盖数为 0, 说明该区间没有被任何正方形覆盖
96.         return tree[1].minCover == 0 ? (compressedX.back() - compressedX.front()) - tree[1].coveredLen // 返回该区间未被覆盖的部分长度
97.                    : compressedX.back() - compressedX.front(); // 否则返回整个区间长度
98.     }
99. };
101. // 主要的解题函数
102. class Solution {
103. public:
104.     double separateSquares(vector<vector<int>>& squares) {
105.         // 使用 map 进行坐标压缩: 记录所有正方形的左下角和右上角的 x 坐标
106.         map<int, int> coordMap;
107.         for (const auto& sq : squares) {
108.             coordMap[sq[0]] = 1; // 将正方形的左边 x 坐标添加到坐标映射中
109.             coordMap[sq[0] + sq[2]] = 1; // 将正方形的右边 x 坐标添加到坐标映射中
110.         }
112.         // 为每个唯一的 x 坐标分配一个压缩后的索引
113.         int index = 0;
114.         for (auto& kv : coordMap) {
115.             kv.second = index++;
116.         }
118.         // 将压缩后的 x 坐标存入数组
119.         vector<int> compressedX(index);
120.         for (auto& p : coordMap) {
121.             compressedX[p.second] = p.first;
122.         }
124.         // 生成事件列表: 记录正方形的上边界和下边界
125.         vector<array<int, 4>> events;
126.         for (const auto& sq : squares) {
127.             // 正方形的下边界事件
128.             events.push_back({sq[1], coordMap[sq[0]] + 1, coordMap[sq[0] + sq[2]], 1});
129.             // 正方形的上边界事件
130.             events.push_back({sq[1] + sq[2], coordMap[sq[0]] + 1, coordMap[sq[0] + sq[2]], -1});
131.         }
132.         // 按 y 坐标 (即正方形的上下边界) 排序事件
133.         sort(events.begin(), events.end());
135.         // 使用线段树计算总面积
136.         SegmentTree segTree(compressedX);
137.         long long totalArea = 0;
138.         for (size_t i = 0; i + 1 < events.size(); i++) {
139.             // 更新线段树的覆盖状态
140.             segTree.update(events[i][1], events[i][2], events[i][3]);
141.             // 获取当前覆盖长度
142.             int coveredLength = segTree.getCoveredLength();
143.             // 累加总面积
144.             totalArea += 1LL * coveredLength * (events[i + 1][0] - events[i][0]);
145.         }
147.         // 计算中位水平线的面积
148.         long long accumulatedArea = 0;
149.         segTree = SegmentTree(compressedX); // 重新初始化线段树
150.         for (size_t i = 0; i + 1 < events.size(); i++) {
151.             // 更新线段树
152.             segTree.update(events[i][1], events[i][2], events[i][3]);
153.             // 获取当前覆盖长度
154.             int coveredLength = segTree.getCoveredLength();
155.             // 累加面积
156.             accumulatedArea += 1LL * coveredLength * (events[i + 1][0] - events[i][0]);
158.             // 计算此时累计的面积和剩余面积的差值
159.             long long areaDiff = accumulatedArea - (totalArea - accumulatedArea);
160.             // 如果累计面积大于或等于剩余面积, 则找到平衡线
161.             if (areaDiff >= 0) {
162.                 return events[i + 1][0] - 0.5 * areaDiff / coveredLength;
163.             }
164.         };
165.         return -1; // 如果找不到合适的平衡线, 返回 -1
166.     }
167. };

复制代码

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、代码实现

1. class Solution {
2. private:
3.     // 计算模式串 pattern 的前缀函数 (pi 数组)
4.     vector<int> computePrefixFunction(const string& pattern) {
5.         int n = pattern.size();
6.         vector<int> pi(n, 0); // pi 数组记录每个位置的最长相等前后缀长度
7.         int match = 0;
9.         // 遍历模式串的字符, 通过前缀函数更新匹配位置
10.         for (int i = 1; i < n; ++i) {
11.             while (match > 0 && pattern[match] != pattern[i]) {
12.                 match = pi[match - 1]; // 跳过不匹配部分
13.             }
14.             if (pattern[match] == pattern[i]) {
15.                 match++;
16.             }
17.             pi[i] = match; // 更新前缀函数
18.         }
20.         return pi;
21.     }
23.     // 在文本串 text 中查找模式串 pattern 的所有匹配位置
24.     vector<int> findPatternMatches(const string& text, const string& pattern) {
25.         int n = text.size();
26.         int m = pattern.size();
28.         if (m == 0) {
29.             // 如果模式串为空, pattern 的所有位置都能匹配空串
30.             vector<int> pos(n + 1);
31.             iota(pos.begin(), pos.end(), 0); // 生成从 0 到 n 的位置
32.             return pos;
33.         }
35.         vector<int> pi = computePrefixFunction(pattern); // 取前缀函数
36.         vector<int> matches;                             // 用于存储匹配的位置
37.         int match = 0;
39.         for (int i = 0; i < n; ++i) {
40.             while (match > 0 && pattern[match] != text[i]) {
41.                 match = pi[match - 1]; // 找到最长的匹配前缀
42.             }
43.             if (pattern[match] == text[i]) {
44.                 match++;
45.             }
46.             if (match == m) {
47.                 matches.push_back(i - m + 1); // 匹配成功, 记录匹配的起始位置
48.                 match = pi[match - 1]; // 使用前缀函数回溯, 继续查找下一个匹配
49.             }
50.         }
52.         return matches;
53.     }
55. public:
56.     // 计算最短的匹配子字符串
57.     int shortestMatchingSubstring(const string& s, const string& p) {
58.         // 找到两个 '*' 的位置
59.         int firstStar = p.find('*');
60.         int lastStar = p.rfind('*');
62.         // 获取前三段字符串 (即 '*' 之前、之间和之后的部分)
63.         string prefix = p.substr(0, firstStar); // 第一个 '*' 前的部分
64.         string middle = p.substr(firstStar + 1, lastStar - firstStar - 1); // 两个 '*' 之间的部分
65.         string suffix = p.substr(lastStar + 1); // 第二个 '*' 后的部分
67.         // 分别查找每部分在 s 中的匹配位置
68.         vector<int> prefixMatches = findPatternMatches(s, prefix);
69.         vector<int> middleMatches = findPatternMatches(s, middle);
70.         vector<int> suffixMatches = findPatternMatches(s, suffix);
72.         // 计算每段的长度
73.         int lenPrefix = prefix.size();
74.         int lenMiddle = middle.size();
75.         int lenSuffix = suffix.size();
77.         // 用于记录最短匹配子字符串的长度
78.         int minLength = INT_MAX;
79.         int prefixIdx = 0, suffixIdx = 0;
81.         // 遍历所有的 middle 匹配, 寻找左右两边最近的匹配, 确保没有重叠
82.         for (int middlePos : middleMatches) {
83.             // 处理右边, 找到离 middlePos 最近且不重叠的 suffix 匹配
84.             while (suffixIdx < suffixMatches.size() && suffixMatches[suffixIdx] < middlePos + lenMiddle) {
85.                 suffixIdx++;
86.             }
87.             if (suffixIdx == suffixMatches.size()) {
88.                 break;
89.             }
91.             // 处理左边, 找到离 middlePos 最近且不重叠的 prefix 匹配
92.             while (prefixIdx < prefixMatches.size() && prefixMatches[prefixIdx] <= middlePos - lenPrefix) {
93.                 prefixIdx++;
94.             }
95.             if (prefixIdx > 0) {
96.                 // 计算最短子字符串的长度
97.                 int currentLength = suffixMatches[suffixIdx] + lenSuffix - prefixMatches[prefixIdx - 1];
98.                 minLength = min(minLength, currentLength); // 更新最短长度
99.             }
100.         }
102.         return minLength == INT_MAX ? -1 : minLength; // 如果找不到匹配, 返回 -1
103.     }
104. };

复制代码

4、复杂度分析

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

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



免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。