双指针与字符串压缩：解构力扣500题实例

在力扣LeetCode的题目中，涉及到的几个C++编程挑战涉及了不同的数据结构和算法技巧。让我们逐一解析： 1. **443. 压缩字符串** (双指针+字符串) 此题要求压缩具有重复字符的字符串。通过定义两个指针 `i` 和 `j`，当遇到相同的字符 `s[i]` 时，指针 `j` 循环右移，找到连续重复字符的结束位置。然后更新 `s[k++]` 为 `s[i]`（第一次出现的位置），并计算重复子串的长度 `len = j - i`。若长度大于1，则需要手动将长度转换为字符串形式（例如，`'0' + len % 10`），并插入到原字符串中，确保高位优先（如 `len/10`），再反转这部分子串。最后更新指针 `i` 为 `j - 1`，继续遍历。 2. **442. 数组中重复的数据** (数组) 在这个数组问题中，使用负数标记已访问的元素。遍历数组，如果当前元素等于后续元素，将其设为负数表示存在重复。如果遇到已标记为负数的元素，说明前面出现过，直接添加到结果数组 `res`。此方法利用了数组的空间效率，避免额外数据结构。 3. **386. 字典序排数** (DFS + Trie树) 通过构建一个字典树（Trie）来存储所有可能的数字。遍历输入数组，将数字转换为其在字典树中的路径表示，并将这些路径存储在结果数组中。字典序排序意味着我们按照数字的自然顺序遍历Trie树。时间复杂度取决于字典树的大小，通常是O(n)，其中n是数组长度。 4. **763. 划分字母区间** (哈希 + 双指针) 本题要求将相同字母分隔成区间，使用哈希表（如`unordered_map`）记录每个字符最后一次出现的位置，双指针分别从左和右开始。遇到相同的字符时，更新左指针的区间，直到右指针找到不同的字符。最后返回所有区间的表示，注意保持字符顺序。 这些题目展示了在C++中处理字符串、数组、数据结构（如Trie树）以及哈希技术的应用，有助于提高字符串处理、查找重复元素、排序和区间划分等核心算法技能。通过解决这些题目，可以增强编程逻辑和优化能力。