邵阳建网站多少钱,wordpress简明教程,网站后台生成静态页面,大气黑色女性时尚类网站织梦模板Q1、好数字之和
1、题目描述
给定一个整数数组 nums 和一个整数 k#xff0c;如果元素 nums[i] 严格 大于下标 i - k 和 i k 处的元素#xff08;如果这些元素存在#xff09;#xff0c;则该元素 nums[i] 被认为是 好 的。如果这两个下标都不存在#xff0c;那么 nums…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(vectorint 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]// 如果 ik 不存在, 跳过检查; 否则 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(vectorvectorint squares) {// 如果没有正方形, 返回 0.0if (squares.empty()) {return 0.0;}// 初始化上下界double down static_castdouble(squares[0][1]); // 最小的 y 值double up static_castdouble(squares[0][1] squares[0][2]); // 最大的 yl 值double totalArea 0.0; // 总面积// 计算最小/最大 y 值 和 总面积for (const auto v : squares) {double y static_castdouble(v[1]); // 左下角的 y 坐标double l static_castdouble(v[2]); // 正方形边长down min(down, y); // 更新最小 yup max(up, y l); // 更新最大 ytotalArea 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_castdouble(v[1]); // 左下角 y 坐标double l static_castdouble(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(vectorvectorint 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_castdouble(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_castdouble(side));areaBelow effectiveHeight * side;}}return areaBelow totalArea / 2;};// 二分查找满足条件的最小 ydouble left 0.0, right static_castdouble(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:vectorNode tree; // 存储线段树的节点vectorint 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 vectorint 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(vectorvectorint squares) {// 使用 map 进行坐标压缩: 记录所有正方形的左下角和右上角的 x 坐标mapint, 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 坐标存入数组vectorint compressedX(index);for (auto p : coordMap) {compressedX[p.second] p.first;}// 生成事件列表: 记录正方形的上边界和下边界vectorarrayint, 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 数组)vectorint computePrefixFunction(const string pattern) {int n pattern.size();vectorint 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 的所有匹配位置vectorint findPatternMatches(const string text, const string pattern) {int n text.size();int m pattern.size();if (m 0) {// 如果模式串为空, pattern 的所有位置都能匹配空串vectorint pos(n 1);iota(pos.begin(), pos.end(), 0); // 生成从 0 到 n 的位置return pos;}vectorint pi computePrefixFunction(pattern); // 取前缀函数vectorint 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 中的匹配位置vectorint prefixMatches findPatternMatches(s, prefix);vectorint middleMatches findPatternMatches(s, middle);vectorint 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 为模式串长度。
