压缩字符串
# 📃 题目描述
题目链接:443. 压缩字符串 (opens new window)
# 🔔 解题思路
常规思路,快慢指针,快指针用来找和慢指针相同的数
需要注意的是这题需要添加一个写指针,用来在 chars 数组上进行原地修改。
class Solution {
public int compress(char[] chars) {
// 左指针
int left = 0;
// 右指针,用于遍历和 left 相同的数
int right = 1;
// 写指针,用于在 chars 中写最终结果
int write = 0;
// 这里 right 取到 chars.length 是为了处理最后一串连续数
while (right <= chars.length) {
// 遇到相等数,右指针 ++
if (right != chars.length && chars[left] == chars[right]) {
right ++;
}
else {
chars[write] = chars[left];
write ++;
int len = right - left;
int anchor = write;
if (len > 1) {
// 如果组长度为 10 或 10 以上,则在 chars 数组中会被拆分为多个字符
while (len > 0) {
chars[write] = (char)(len % 10 + '0');
len /= 10;
write ++;
}
// 反转 chars[anchro, write - 1];
reverse(chars, anchor, write - 1);
}
// 进入下一个数字的处理
left = right;
right = left + 1;
}
}
// 返回该数组的新长度
return write;
}
public void reverse(char[] chars, int left, int right) {
while (left < right) {
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
left++;
right--;
}
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10