算法题详解

embedded/2024/11/15 5:50:39/

关键字标识：

问题描述

你有一个关键词列表和一个字符串。你需要在字符串中用 HTML 标签 <b></b> 标记出所有出现的关键词，并且将所有相邻或交叠的标签合并成一个标签。例如：

  • 如果字符串中有 "opqr" 和 "cd" 这两个关键词，并且它们在字符串中相邻或重叠，那么最终输出的字符串应该是 <b>opqr</b>a<b>cdf</b>g。

解决步骤

  1. 找到关键词在字符串中的所有位置：

    • 对于每个关键词，我们在字符串中找到它的所有出现位置，并记录这些位置。

  2. 合并相邻或交叠的标签：

    • 如果两个标签在字符串中相邻或交叠，我们需要将它们合并成一个标签。比如，<b>op</b><b>qr</b> 应该合并成 <b>opqr</b>。

  3. 生成最终的字符串：

    • 使用合并后的标签创建最终的字符串，确保每个标签都正确地标记了关键词。

代码解析

以下是详细的代码解析：

function mergeIntervals(intervals) {if (intervals.length === 0) return [];// 按照开始位置排序intervals.sort((a, b) => a[0] - b[0]);const merged = [];let [start, end, label] = intervals[0]; // 初始化第一个标签区间for (let i = 1; i < intervals.length; i++) {const [currentStart, currentEnd, currentLabel] = intervals[i];if (currentStart <= end + 1) { // 如果标签区间重叠或相邻end = Math.max(end, currentEnd); // 更新结束位置label = `<b>${inputStr.slice(start, end + 1)}</b>`; // 更新合并后的标签} else {merged.push([start, end, label]); // 将当前标签区间加入结果start = currentStart;end = currentEnd;label = currentLabel;}}merged.push([start, end, label]); // 推入最后一个标签区间return merged;
}function labelKeywords(words, inputStr) {const n = inputStr.length;const labels = [];// 遍历每个关键词，查找其在字符串中的所有位置words.forEach(word => {let start = 0;while (start < n) {start = inputStr.indexOf(word, start);if (start === -1) break;const end = start + word.length - 1;labels.push([start, end, `<b>${word}</b>`]);start += word.length;}});// 合并所有重叠或相邻的标签区间const mergedIntervals = mergeIntervals(labels);// 构建最终输出的字符串let result = '';let lastIndex = 0;mergedIntervals.forEach(([start, end, label]) => {if (lastIndex < start) {result += inputStr.slice(lastIndex, start); // 添加非标签部分}result += label; // 添加标签lastIndex = end + 1;});if (lastIndex < n) {result += inputStr.slice(lastIndex); // 添加字符串剩余部分}return result;
}// 示例输入
const count = 4;
const words = ["cd", "df", "op", "qr"];
const inputStr = "opqracdfg";// 处理并输出结果
console.log(labelKeywords(words, inputStr));

详细解释

  1. 找到关键词的位置：

    • labelKeywords 函数遍历所有关键词，找到它们在字符串中的位置，并记录开始和结束位置以及标签内容。

  2. 合并标签：

    • mergeIntervals 函数接收这些标签区间，按照开始位置排序，然后合并相邻或交叠的标签。合并时，我们更新结束位置并重新构建标签。

  3. 生成最终字符串：

    • 最后，我们在 labelKeywords 函数中，利用合并后的标签生成最终的字符串。在这个过程中，我们将标签区间和非标签部分组合起来，生成最终的结果。

这个问题涉及几个重要的算法和技术概念，主要包括：

1. 字符串查找：

  • 算法：indexOf 方法用于查找关键词在字符串中的位置。这是一个基础的字符串操作算法，用于确定子字符串的起始位置。

2. 区间合并：

  • 算法：这个问题的核心算法是区间合并（Interval Merging）。在解决合并标签的问题时，我们实际上是在处理区间合并问题：
    • 排序：首先，将所有的区间按起始位置排序。
    • 合并：然后，遍历这些区间，合并所有相邻或重叠的区间。合并时，需要更新区间的结束位置，并构建合并后的标签。

区间合并问题通常出现在处理时间段、区间覆盖等问题中。常见的步骤包括：
- 排序：按开始位置对区间进行排序。
- 合并：通过遍历排序后的区间，合并相邻或重叠的区间。

3. 标签生成：

  • 技术：在合并区间时，我们需要重新生成标签。这个操作涉及到将合并后的区间从原始字符串中提取出来，并生成适当的 HTML 标签。在此步骤中，我们利用了字符串切割操作（slice 方法）来构建标签。

示例解析

  1. 查找关键词：

    • 通过遍历每个关键词在字符串中查找其所有位置，生成标签区间。每个标签区间记录了关键词的位置和标签。

  2. 合并区间：

    • 通过 mergeIntervals 函数对这些区间进行排序和合并。合并过程涉及到判断区间是否相邻或重叠，并更新合并后的标签。

  3. 构建最终字符串：

    • 结合合并后的标签区间和原始字符串，生成最终的带有标签的字符串。这需要在合并后的区间之间插入原始字符串的非标签部分。

总结

这个问题结合了字符串处理和区间合并的算法。主要的算法步骤包括字符串查找、区间排序和合并。这些步骤在处理类似的字符串标记、时间段合并和区间覆盖等问题时都非常有用。

最长内存空间

问题

我们有一个数组 arr，里面的元素是 0 和 1。我们允许将最多 n 个 1 转换成 0，我们的目标是找出最长的连续 0 子数组的长度。

思路

我们使用滑动窗口的技术来解决这个问题。滑动窗口是一种高效的数组遍历方法，可以帮助我们在 O(n) 时间复杂度内解决问题。

代码解释

function longestZeroSegment(arr, n) {let left = 0;          // 窗口的左边界let maxLength = 0;     // 记录最长的连续0的长度let countOnes = 0;     // 记录窗口内1的数量for (let right = 0; right < arr.length; right++) {// 如果当前元素是1，增加countOnesif (arr[right] === 1) {countOnes++;}// 当窗口内1的数量超过允许的n时，移动左边界while (countOnes > n) {if (arr[left] === 1) {countOnes--;}left++;}// 更新最大长度maxLength = Math.max(maxLength, right - left + 1);}return maxLength;
}// 示例
const arr = [0,0,1,0,0,1,0,0,1,0,0];
const n = 2;
console.log(longestZeroSegment(arr, n));  // 输出 8

详细步骤

  1. 初始化:

    • left：窗口的左边界，初始值为 0。
    • maxLength：记录最长的连续 0 的长度，初始值为 0。
    • countOnes：记录窗口内 1 的数量，初始值为 0。

  2. 遍历数组:

    • 使用 for 循环遍历数组，每次移动 right 指针（窗口的右边界）。

  3. 处理窗口内的 1:

    • 如果当前元素是 1，增加 countOnes。

  4. 调整窗口:

    • 当窗口内的 1 的数量超过 n 时，通过移动 left 指针来缩小窗口，直到 countOnes 不超过 n。

  5. 更新最长长度:

    • 计算当前窗口的长度 right - left + 1，并更新 maxLength 为更大的值。

  6. 返回结果:

    • 返回 maxLength，即最长的连续 0 的长度。

例子解析

对于数组 [0,0,1,0,0,1,0,0,1,0,0] 和 n = 2：

  • 将最多 2 个 1 转换为 0 后，最长的连续 0 的长度是 8。

这个代码的关键在于滑动窗口的维护，确保在任何时刻窗口内的 1 的数量不超过 n，同时计算出最长的连续 0 的长度。

当然可以！下面我将用图示的方式来帮助你理解滑动窗口的过程。

图示说明

考虑数组 [0,0,1,0,0,1,0,0,1,0,0] 和 n = 2。我们需要找到最长的连续 0，允许最多将 2 个 1 转换成 0。下面是滑动窗口的演示：

初始状态
窗口: [0,0,1,0,0,1,0,0,1,0,0]^leftright
过程演示

  1. 扩展右边界：

    • 初始时，left = 0，right = 0。
    • countOnes 为 0（窗口内的 1 的数量）。

  2. 移动右边界：

    • 右边界扩展到 right = 1（arr[right] = 0，不增加 countOnes）。
    • countOnes 仍然是 0。
    • 当前窗口内最长连续 0 的长度是 2 (right - left + 1 = 2)，更新 maxLength 为 2。
    窗口: [0,0,1,0,0,1,0,0,1,0,0]^left^right

  3. 继续扩展右边界：

    • 右边界扩展到 right = 2（arr[right] = 1，增加 countOnes 为 1）。
    • countOnes 现在是 1。
    • 当前窗口内最长连续 0 的长度是 3 (right - left + 1 = 3)，更新 maxLength 为 3。
    窗口: [0,0,1,0,0,1,0,0,1,0,0]^left^right

  4. 继续扩展右边界：

    • 右边界扩展到 right = 3（arr[right] = 0，countOnes 不变）。
    • countOnes 仍然是 1。
    • 当前窗口内最长连续 0 的长度是 4 (right - left + 1 = 4)，更新 maxLength 为 4。
    窗口: [0,0,1,0,0,1,0,0,1,0,0]^left^right

  5. 继续扩展右边界：

    • 右边界扩展到 right = 4（arr[right] = 0，countOnes 不变）。
    • countOnes 仍然是 1。
    • 当前窗口内最长连续 0 的长度是 5 (right - left + 1 = 5)，更新 maxLength 为 5。
    窗口: [0,0,1,0,0,1,0,0,1,0,0]^left^right

  6. 继续扩展右边界：

    • 右边界扩展到 right = 5（arr[right] = 1，增加 countOnes 为 2）。
    • countOnes 现在是 2。
    • 当前窗口内最长连续 0 的长度是 6 (right - left + 1 = 6)，更新 maxLength 为 6。
    窗口: [0,0,1,0,0,1,0,0,1,0,0]^left^right

  7. 继续扩展右边界：

    • 右边界扩展到 right = 6（arr[right] = 0，countOnes 不变）。
    • countOnes 仍然是 2。
    • 当前窗口内最长连续 0 的长度是 7 (right - left + 1 = 7)，更新 maxLength 为 7。
    窗口: [0,0,1,0,0,1,0,0,1,0,0]^left^right

  8. 继续扩展右边界：

    • 右边界扩展到 right = 7（arr[right] = 0，countOnes 不变）。
    • countOnes 仍然是 2。
    • 当前窗口内最长连续 0 的长度是 8 (right - left + 1 = 8)，更新 maxLength 为 8。
    窗口: [0,0,1,0,0,1,0,0,1,0,0]^left^right

  9. 继续扩展右边界：

    • 右边界扩展到 right = 8（arr[right] = 1，增加 countOnes 为 3，超过 n）。
    • 移动左边界 left 直到 countOnes 不超过 n。
    • 移动 left 到 left = 1，countOnes 变为 2，窗口内长度是 7。
    • 继续调整窗口，直到 countOnes 符合要求。
    • 最大长度保持 8。
    窗口: [0,0,1,0,0,1,0,0,1,0,0]^left^right

  10. 继续扩展右边界：

    • 右边界扩展到 right = 9（arr[right] = 0，countOnes 不变）。
    • countOnes 仍然是 2。
    • 当前窗口内最长连续 0 的长度是 8 (right - left + 1 = 8)，maxLength 仍然是 8。
窗口: [0,0,1,0,0,1,0,0,1,0,0]^left^right
  1. 继续扩展右边界：
    • 右边界扩展到 right = 10（arr[right] = 0，countOnes 不变）。
    • countOnes 仍然是 2。
    • 当前窗口内最长连续 0 的长度是 9 (right - left + 1 = 9)，更新 maxLength 为 9。
窗口: [0,0,1,0,0,1,0,0,1,0,0]^left^right

结果

最终，maxLength 是 8，即最长的连续 0 的长度为 8。

最大负载：
要解决这个问题，我们可以按照以下步骤来实现：

步骤解析

  1. 循环分配服务器：每次消息到达时，我们按照顺序循环分配服务器。
  2. 检查服务器的繁忙状态：如果当前要分配的服务器繁忙，则跳过它，分配给下一个空闲的服务器。
  3. 计算每个服务器的总负载：记录每个服务器处理的负载总和。
  4. 找出处理负载最高的服务器：最后，找出那些处理负载最多的服务器，并按编号升序返回。

JavaScript 实现

function findBusiestServers(k, requests) {const servers = new Array(k).fill(0);  // 记录每个服务器的总负载const busyUntil = new Array(k).fill(0);  // 记录每个服务器的繁忙截止时间let maxLoad = 0;  // 记录最高负载值const result = [];  // 记录处理最高负载的服务器编号for (let i = 0; i < requests.length; i++) {const [time, load] = requests[i];let assigned = false;for (let j = 0; j < k; j++) {const server = (i + j) % k;  // 计算当前应该检查的服务器if (busyUntil[server] <= time) {  // 检查服务器是否空闲servers[server] += load;  // 记录服务器处理的负载busyUntil[server] = time + load;  // 更新服务器繁忙截止时间maxLoad = Math.max(maxLoad, servers[server]);  // 更新最高负载值assigned = true;break;}}// 如果所有服务器都繁忙，这条消息就被丢弃，不处理}// 找出处理负载最多的服务器for (let i = 0; i < k; i++) {if (servers[i] === maxLoad) {result.push(i + 1);  // 服务器编号从1开始}}return result;
}// 示例输入
const k = 3;
const requests = [[1, 15],[2, 10],[12, 10],[5, 10],[6, 10],[30, 15],[32, 10]
];// 计算并输出结果
console.log(findBusiestServers(k, requests)); // 输出 [1, 3]

代码解释

  1. 初始化：

    • servers 数组用来记录每个服务器处理的总负载。
    • busyUntil 数组用来记录每个服务器处理完当前任务的时间，即何时变得空闲。
    • maxLoad 记录当前服务器中处理的最高负载值。

  2. 循环处理每条消息：

    • 对于每条消息，按照顺序尝试将其分配给一个空闲的服务器。
    • 如果找到空闲的服务器，就将消息分配给该服务器，并更新该服务器的负载和繁忙截止时间。

  3. 查找最高负载的服务器：

    • 最后，遍历 servers 数组，找出负载等于 maxLoad 的服务器，将其编号加入结果中。

  4. 返回结果：

    • 返回处理负载最高的服务器编号，按照升序排序。

这个实现逻辑清晰且简洁，能够有效地解决问题。在时间和空间限制内，性能也是可以接受的。

优化版：
没问题，让我用更简单的方式解释一下，并且简化实现。

问题理解

假设我们有 k 台服务器，每台服务器按顺序循环接收请求消息。如果一台服务器忙碌，就跳过它分配给下一台空闲的服务器。如果所有服务器都忙碌，那么这个请求就会被丢弃。我们要找出处理负载最多的服务器，并返回它们的编号。

步骤分解

  1. 初始化状态：

    • 创建一个数组来记录每台服务器的负载总和。
    • 创建一个数组记录每台服务器何时会空闲。

  2. 循环处理每个请求：

    • 根据当前请求的时间，找出可以处理该请求的服务器（即空闲的服务器）。
    • 如果找到空闲的服务器，更新它的负载和下次空闲时间。
    • 如果没有找到空闲服务器，这个请求就被丢弃。

  3. 找出处理负载最多的服务器：

    • 遍历所有服务器，找出负载最多的服务器。

简化版 JavaScript 实现

function findBusiestServers(k, requests) {const loads = new Array(k).fill(0); // 记录每个服务器的总负载const busyUntil = new Array(k).fill(0); // 记录每个服务器的忙碌截止时间requests.forEach(([time, load], i) => {let assigned = false;// 尝试分配给服务器for (let j = 0; j < k; j++) {const server = (i + j) % k; // 循环找到服务器if (busyUntil[server] <= time) { // 检查是否空闲loads[server] += load; // 更新服务器负载busyUntil[server] = time + load; // 更新服务器忙碌到的时间assigned = true;break;}}// 如果没有空闲服务器，消息被丢弃});const maxLoad = Math.max(...loads); // 找到最大负载值const result = [];for (let i = 0; i < k; i++) {if (loads[i] === maxLoad) {result.push(i + 1); // 服务器编号从1开始}}return result;
}// 示例输入
const k = 3;
const requests = [[1, 15],[2, 10],[12, 10],[5, 10],[6, 10],[30, 15],[32, 10]
];// 计算并输出结果
console.log(findBusiestServers(k, requests)); // 输出 [1, 3]

代码详细解释

  1. 初始化：

    • loads 数组用于记录每台服务器处理的总负载。
    • busyUntil 数组用于记录每台服务器处理完当前任务后什么时候会空闲。

  2. 处理请求：

    • 对于每个请求，按顺序检查服务器是否空闲，如果空闲则分配给它。
    • 使用 (i + j) % k 来找到合适的服务器，这样可以实现循环分配。

  3. 找到最大负载的服务器：

    • 计算每台服务器的负载，找到负载最大的服务器并返回它们的编号。

总结

这个简化版代码通过简单的循环和数组操作，轻松实现了服务器的负载均衡分配。每个请求只需要遍历最多 k 个服务器，因此在时间和空间上都非常高效。


http://www.ppmy.cn/embedded/94862.html

相关文章

spring注册DispatcherServlet的过程

spring注册DispatcherServlet的过程

先看下servlet注入到tomcat服务器的过程&#xff0c; DispatcherServletAutoConfiguration$DispatcherServletConfiguration类中声明了Bean方法&#xff0c;会创建DispatcherServlet类型的Bean&#xff0c;然后作为dispatcherServletRegistration方法的参数注入到DispatcherSer…
阅读更多...
react-antive 項目報錯 [CXX1429] error when building with cmake using

react-antive 項目報錯 [CXX1429] error when building with cmake using

react-antive 項目報錯 [CXX1429] error when building with cmake using修复 错误现场分析原因解决方案举一反三技巧引用参考&#xff08;感谢作者提供思路&#xff09; 错误现场 [CXX1429] error when building with cmake using /Users/sebastiangarcia/Desktop/work/flm/…
阅读更多...
算法板子：容斥原理——求出 1∼n 中能被质数 p1,p2,…,pm 中的至少一个数整除的整数有多少个

算法板子：容斥原理——求出 1∼n 中能被质数 p1,p2,…,pm 中的至少一个数整除的整数有多少个

1. 题目要点 1. 设&#xff1a;求1~10中能被质数2和3中至少一个数整除的数有多少个。1~10中能被质数2整除的数的集合记为S1{2,4,6,8,10}&#xff0c;能被质数3整除的数的集合记为S2{3,6,9}&#xff0c;能同时被质数2和3整数的数的集合为S1∩S2{6} 2. 这道题的目的是求S1∪S2∪S…
阅读更多...
Python 报错：ModuleNotFoundError: No module named ‘Crypto‘

Python 报错：ModuleNotFoundError: No module named ‘Crypto‘

Crypto报错解决方案 Python 报错&#xff1a;ModuleNotFoundError: No module named Crypto前言问题解决方案 Python 报错&#xff1a;ModuleNotFoundError: No module named ‘Crypto’ 前言 Crypto是一个加密模块&#xff0c;它包含了多种加密算法&#xff0c;如 AES、DES、…
阅读更多...
AI大模型赋能游戏：更智能、更个性化的NPC

AI大模型赋能游戏：更智能、更个性化的NPC

参考论文&#xff1a;https://arxiv.org/abs/2403.10249 在传统游戏中&#xff0c;NPC&#xff08;非玩家角色&#xff09;的行为往往是预先设定好的&#xff0c;缺乏灵活性和变化性。然而&#xff0c;基于大模型的NPC可以利用其强大的推理和学习能力&#xff0c;实时生成对话…
阅读更多...
在HTML中固定表格表头的简单方法

在HTML中固定表格表头的简单方法

在HTML中&#xff0c;表格元素自身无法提供滚动以及固定表头的配置。借助第三方工具&#xff08;如jQuery的表头固定插件&#xff09;或者结合JavaScrip&#xff0c;是可以实现表格的表头固定的&#xff0c;除此之外&#xff0c;本文还想讨论一种更简单的方式来实现。 从思路上…
阅读更多...
macOS 关闭系统更新以及相关提示

macOS 关闭系统更新以及相关提示

在 macOS 上&#xff0c;关闭系统更新以及相关提示可以通过以下步骤实现&#xff1a; 1. 通过系统偏好设置关闭自动更新 打开 系统偏好设置。点击 软件更新。取消勾选 “自动检查更新”&#xff0c;以及 “下载新的可用更新” 等选项。这样可以关闭自动检查更新和自动下载更新…
阅读更多...
odoo17 翻译一个小bug

odoo17 翻译一个小bug

odoo17 翻译一个小bug 用户界面的没译过来 标红处&#xff0c;但在zh_CN.po中明显已经翻译过来了&#xff0c;采取暴力点的&#xff0c;直接把base下的base.pot删除&#xff0c;再更新一下&#xff0c;可以正常显示了
阅读更多...
最新文章

Copyright @ 2022~2023