您的位置首页 >要闻 > 人工智能 >

Rust 实现 LeetCode443 字符串压缩算法题解

LeetCode443 是字符串压缩题目,要求直接在原字符数组上完成原地压缩,返回压缩之后数组的新长度,这道题最优解法是双指针法,Rust 写的时候要注意数组可变引用、边界判断、数字转字符的细节,不能额外开辟大数组空间,要满足 O (1) 额外空间的要求。题目规则是连续相同字符,如果重复次数大于 1,就在字符后面追加次数;次数等于 1 的时候只保留字符,不写数字。我们用读指针遍历原数组读取字符,写指针往前面写入压缩结果,遇到连续相同字符统计数量,数量大于 1 就把数字拆成单个字符依次写入,遍历完成后写指针的值就是压缩后的长度,这套思路在 Rust 里用可变切片实现,不需要额外分配容器,时间复杂度 O (n),可以顺利通过全部测试用例。

一、题目简述

LeetCode443 字符串压缩

输入:字符数组 chars: &mut Vec

要求:原地修改数组,按规则压缩,返回压缩后的长度

示例:

输入:["a","a","b","b","c","c","c"]

输出:返回 6,数组变为 ["a","2","b","2","c","3"]

输入:["a"]

输出:返回 1,数组不变

输入:["a","b","b","b","b","b","b","b","b","b","b","b","b"]

输出:返回 4,数组变为 ["a","b","1","2"]

二、Rust 完整代码实现

pub fn compress(chars: &mut Vec) -> i32 {

let mut write = 0;

let n = chars.len();

let mut read = 0;

while read < n {

let current_char = chars[read];

let mut count = 0;

// 统计连续相同字符数量

while read < n && chars[read] == current_char {

read += 1;

count += 1;

}

// 写入字符

chars[write] = current_char;

write += 1;

// 数量大于1,写入数字每一位

if count > 1 {

for c in count.to_string().chars() {

chars[write] = c;

write += 1;

}

}

}

write as i32

}

三、代码逻辑拆解清单

  1. 定义两个指针:read 读指针,用来遍历统计连续字符;write 写指针,用来在原地写入压缩结果
  2. 外层循环:read 没有走到数组末尾就持续执行
  3. 内层循环:统计和当前字符一样的连续字符总数 count
  4. 先把字符写入 write 位置,write 向后移动一格
  5. 如果 count 大于 1,把数字转字符串,逐个字符写入数组,write 同步后移
  6. 循环结束,write 的值就是压缩后的长度,转 i32 返回

四、易错点表格

坑点问题说明Rust 处理方式
数字多位数比如 12,不能直接写 '12',要拆成 '1'、'2'转字符串遍历逐个写入
原地修改不能新建 Vec 保存结果,必须复用原数组直接操作 chars 切片下标
边界溢出read 下标越界内层循环先判断 read < n
count=1 场景只写字符,不追加数字增加 if 判断过滤
类型转换返回值要求 i32write 是 usize,最后强制转 i32

五、复杂度说明

  • 时间复杂度:O (n),每个字符最多被 read、write 各访问一次
  • 空间复杂度:O (1),只使用几个变量,数字转字符串是临时少量开销,符合题目原地压缩要求

【相关 FAQ】

问题 1:Rust 写 LeetCode443 字符串压缩,为什么优先用双指针原地压缩?

回答 1:Rust 写 LeetCode443 字符串压缩,题目强制要求原地修改数组、控制额外空间,双指针方案可以做到 O (1) 额外空间,是本题标准最优解法。

问题 2:Rust 实现 LeetCode443 的时候,遇到重复次数大于 9 怎么处理?

回答 2:Rust 实现 LeetCode443 时,重复次数大于 9 要把数字转为字符串,拆分单个字符依次写入原数组,比如 count=12,依次写入 '1' 和 '2'。

问题 3:LeetCode443 Rust 代码里,返回的数字代表什么?

回答 3:LeetCode443 Rust 代码返回的整数,代表压缩完成之后有效字符的长度,原数组前面这段长度的内容就是压缩结果。

问题 4:Rust 写 LeetCode443 字符串压缩能不能用额外 Vec 暂存结果?

回答 4:Rust 写 LeetCode443 字符串压缩不建议用额外 Vec 暂存,会不满足原地压缩、O (1) 空间的题目要求,判题会不符合题意。

【参考资料】

[2026-10-28](LeetCode 443 字符串压缩 Rust 题解)LeetCode 官方题解社区

[2026-09-15](443. String Compression 双指针思路与 Rust 实现)掘金

[2026-08-02](LeetCode443 字符串压缩原地算法思路讲解)CSDN

[2025-12-20](String Compression 算法边界坑点总结)Rust 算法笔记

【免责声明】

本文为 LeetCode443 算法 Rust 题解学习资料,代码仅用于算法练习,算法思路、测试用例以 LeetCode 原题为准,不同 Rust 版本语法兼容请自行调试。