提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
目录
提示:以下是本篇文章正文内容,下面案例可供参考
给定一组字符,使用原地算法将其压缩。
压缩后的长度必须始终小于或等于原数组长度。
数组的每个元素应该是长度为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","12"]。
说明:由于字符"a"不重复,所以不会被压缩。"bbbbbbbbbbbb"被“b12”替代
解题思路:
处理这个问题,我们要记录下来当前比较的对象(两个)、要写入的位置(为了原地替换)、相同元素的个数,额外要注意最后一个节点的处理,元素的数量是1的处理。
代码示例:
public void test() {
// String[] array = {"a","a","b","b","c","c","c"};
// String[] array = {"a"};
String[] array = {"a","b","b","b","b","b","b","b","b","b","b","b","b"};
// 当前写入的位置
int write = 0;
// 记录当前元素相同的数量
int count = 1;
// 记录当前从哪个位置开始计算
int head = 0;
// 记录当前计算的截止位置
int end = 0;
for (int i = 0; i < array.length; i++) {
// end向后移动
end = i + 1;
// 整个数组遍历完之后的操作
if (end == array.length) {
// 首先设置元素
array[write] = array[head];
write++;
// 如果元素个数大于1, 则接着设置元素的个数
if (count > 1) {
array[write] = String.valueOf(count);
write++;
}
continue;
}
// 元素相同, 计数+1
if (Objects.equals(array[head], array[end])) {
count++;
continue;
}
array[write] = array[head];
write++;
// head指向下一个不同元素, 作为新的起点
head = end;
// 相邻两个元素不同, 且前一个元素的计数大于1, 则追加设置个数值
if (count > 1) {
array[write] = String.valueOf(count);
write++;
// 重置计数
count = 1;
}
}
// 为了便于观察结果, 将余下的空位全部置空
for (int i = array.length - 1; i >= write; i--) {
array[i] = null;
}
// 输出加密之后的结果
System.out.println(JSON.toJSONString(array));
}
先写大骨架,然后再针对特殊场景和细节,进行弥补,最后就形成了初版代码,有了初版代码,就可以对代码进行精简和优化。
代码加了详细的注释,动动手试一下,简单到有手就行!