LeetCode算法题-String Compression(Java实现)

时间:2021-10-22 18:43:08

这是悦乐书的第230次更新,第242篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第97题(顺位题号是443)。给定一组字符,就地压缩它。压缩后的长度必须始终小于或等于原始数组。数组的每个元素都应该是长度为1的字符(不是int)。在就地修改输入数组后,返回数组的新长度。例如:

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

输出:返回6,输入数组的前6个字符应为:["a","2","b","2","c","3"]

说明:"aa"被"a2"取代。"bb"被"b2"取代。"ccc"被"c3"取代。

输入:["a"]

输出:返回1,输入数组的前1个字符应为:["a"]

说明:什么都没有被取代。

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

输出:返回4,输入数组的前4个字符应为:["a","b","1","2"]。

说明:由于字符"a"不重复,因此不会压缩。 "bbbbbbbbbbbbb"被"b12"取代。请注意,每个数字在数组中都有自己的条目。

注意:

  • 所有字符在[35,126]中都有ASCII值。
  • 1 <= len(字符)<= 1000。

跟进:你能用O(1)额外空间解决它吗?

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 解题

此题我们需要做两件事,一是将重复的字符进行替换,二是计算被替换后新数组的长度。此题是不需要先将元素排序的,定义一个从0开始的索引,判断当前元素是否是连续出现,如果是单个,直接使用新索引进行替换,如果是多次出现,把次数记录下来,先将当前元素保留一个坑位,然后将出现的次数先变成字符串,再变成字符数组,紧跟着该元素后面进行替换,最后一次进行替换的索引就行新数组的长度。

public int compress(char[] chars) {
int sum = 0, index = 0;
while (index < chars.length) {
char current = chars[index];
int num = 0;
while (index < chars.length && chars[index] == current) {
index++;
num++;
}
chars[sum++] = current;
if (num != 1) {
for (char ch : (num+"").toCharArray()) {
chars[sum++] = ch;
}
}
}
return sum;
}

03 小结

算法专题目前已连续日更三个月,算法题文章97+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!