学习记录：js算法（七十八）：划分字母区间

时间：2024-10-30 08:11:13

文章目录

    • 划分字母区间
      • 思路一：贪心算法
      • 思路二：双指针
      • 思路三：
      • 思路四：使用数组记录最后出现位置

划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。

示例 1：
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 

示例 2：
输入：s = "eccbbbbdec"
输出：[10]

思路一：贪心算法

function partitionLabels(s) {
    const lastSeen = {};
    // 记录每个字符最后一次出现的位置
    for (let i = 0; i < s.length; i++) {
        lastSeen[s[i]] = i;
    }

    const result = [];
    let start = 0, end = 0;
    for (let i = 0; i < s.length; i++) {
        // 更新end，以便它可以覆盖所有字符的最后一次出现位置
        end = Math.max(end, lastSeen[s[i]]);
        // 当前位置i等于end，表示当前片段结束
        if (i === end) {
            result.push(end - start + 1);
            // 更新下一个片段的起始位置
            start = i + 1;
        }
    }

    return result;
}

讲解
这个问题可以通过贪心算法来解决。核心思想是，我们从左到右扫描字符串s，同时维护一个字典或哈希表来跟踪每个字符最后一次出现的位置。当我们考虑将当前位置i作为某个片段的结束位置时，我们需要确保所有在i之前的字符最后一次出现的位置也在i之前或等于i。如果这个条件满足，那么我们就可以将i作为当前片段的结束位置，并将片段长度加入结果列表中，然后继续寻找下一个片段。

  1. 初始化：创建一个字典lastSeen来记录每个字符最后一次出现的位置，初始化结果列表result。
  2. 遍历字符串：从左到右遍历字符串s，同时更新lastSeen字典。
  3. 确定片段结束位置：对于每个位置i，检查lastSeen字典中所有字符的最后一次出现位置，如果这些位置都小于等于i，那么我们就可以将i作为当前片段的结束位置。
  4. 更新结果：一旦确定了片段的结束位置，就计算片段的长度，并将长度加入结果列表result中。
  5. 重复步骤3和4：继续寻找下一个片段，直到遍历完整个字符串。

思路二：双指针

var partitionLabels = function (s) {
    const lastIndex = {};
    const result = [];

    // 记录每个字符最后出现的位置
    for (let i = 0; i < s.length; i++) {
        lastIndex[s[i]] = i;
    }

    let start = 0;
    let end = 0;

    for (let i = 0; i < s.length; i++) {
        end = Math.max(end, lastIndex[s[i]]);

        if (i === end) {
            result.push(end - start + 1);
            start = i + 1;
        }
    }

    return result;
};

讲解

  1. 初始化对象和数组：
    • 创建一个空对象 lastIndex，用于存储每个字符最后出现的位置。
    • 创建一个空数组 result，用于存储每个片段的长度。
  2. 记录字符最后出现的位置：
    • 使用 for 循环遍历字符串 s，将每个字符及其最后出现的索引存储到 lastIndex 对象中。
  3. 初始化起始和结束索引：
    • 设置 start 和 end 都为 0，start 表示当前片段的起始位置，end 用于确定当前片段的结束位置。
  4. 遍历字符串：
    • 使用另一个 for 循环遍历字符串 s。在每次迭代中，更新 end 为当前字符的最后出现位置与之前的 end 中的较大值。
  5. 判断片段结束：
    • 如果当前索引 i 等于 end，说明当前片段已经结束。计算片段的长度，并将其添加到 result 数组中。
  6. 返回结果：
    • 最后，返回 result 数组，包含所有片段的长度。

思路三：

var partitionLabels = function (s) {
    const lastIndex = {};

    // 记录每个字符最后出现的位置
    for (let i = 0; i < s.length; i++) {
        lastIndex[s[i]] = i;
    }

    const result = [];
    let start = 0;

    while (start < s.length) {
        let end = lastIndex[s[start]];
        let i = start;

        while (i <= end) {
            end = Math.max(end, lastIndex[s[i]]);
            i++;
        }

        result.push(end - start + 1);
        start = end + 1;
    }

    return result;
};

讲解

  • 定义函数 partitionLabels，接收一个字符串 s。
  • 创建一个对象 lastIndex，用于存储每个字符在字符串中最后出现的位置。
  • 遍历字符串 s，记录每个字符最后出现的位置。lastIndex[s[i]] = i 将字符 s[i] 作为键，其最后出现的索引 i 作为值。
  • 初始化结果数组 result，用于存储每个片段的长度。
  • 初始化变量 start 为 0，表示当前片段的起始位置。
  • 使用 while 循环 遍历字符串，直到 start 超过字符串长度。
  • 获取当前字符的最后出现位置 end，初始为 lastIndex[s[start]]。
  • 初始化变量 i 为 start，用于向后遍历。
  • 内部 while 循环：在 i 小于等于 end 的条件下，继续更新 end。
  • 更新结束位置：通过 Math.max 确保 end 是当前片段中所有字符的最后出现位置。
  • i++ 逐步向后移动，检查当前片段中的每个字符。
  • 计算当前片段的长度 end - start + 1，并将其添加到 result 数组中。
  • 更新 start 为 end + 1，准备开始下一个片段的划分。
  • 返回结果 result，包含划分后的每个片段的长度。

思路四：使用数组记录最后出现位置

var partitionLabels = function (s) {
    const lastIndex = new Array(26).fill(-1);

    // 记录每个字符最后出现的位置
    for (let i = 0; i < s.length; i++) {
        lastIndex[s.charCodeAt(i) - 'a'.charCodeAt(0)] = i;
    }

    const result = [];
    let start = 0;

    while (start < s.length) {
        let end = lastIndex[s.charCodeAt(start) - 'a'.charCodeAt(0)];
        let i = start;

        while (i <= end) {
            end = Math.max(end, lastIndex[s.charCodeAt(i) - 'a'.charCodeAt(0)]);
            i++;
        }

        result.push(end - start + 1);
        start = end + 1;
    }

    return result;
};

讲解

  1. 初始化最后出现位置数组

    • 创建一个长度为 26 的数组 lastIndex，用于存储每个字母最后出现的位置。初始化为 -1，表示尚未出现。

  2. 记录每个字符最后出现的位置

    • 遍历字符串 s 的每个字符，使用 charCodeAt 方法获取字符的 Unicode 编码。
    • 通过 s.charCodeAt(i) - 'a'.charCodeAt(0) 计算出当前字符在 lastIndex 数组中的索引。
    • 将该字符最后出现的位置（索引 i）存储在 lastIndex 中。

  3. 初始化结果数组和起始位置

    • 创建一个空数组 result 用于存储每个片段的长度。
    • 初始化变量 start 为 0，表示当前片段的起始位置。

  4. 划分字符串

    • 使用 while 循环遍历字符串，直到 start 超过字符串的长度。
    • 通过 lastIndex 获取当前字符的最后出现位置，赋值给 end。
    • 初始化变量 i 为 start，用于向后遍历。

  5. 更新结束位置

    • 在内部 while 循环中，继续查找当前片段的结束位置。
    • 通过 Math.max 更新 end，确保它是当前片段中所有字符的最后出现位置。
    • i 逐步向后移动，直到超过当前的 end。

  6. 记录片段长度

    • 计算当前片段的长度 end - start + 1，并将其添加到 result 数组中。
    • 更新 start 为 end + 1，准备开始下一个片段的划分。

  7. 返回结果

    • 返回 result 数组，包含划分后的每个片段的长度。

相关文章