Java小白必须会的一道面试算法题
前言
今天在群里面看消息，突然看到一个哥们发了一个关于算法的题目。我乍一看，感觉挺简单的。群里面有的哥们说用
map去做，然后我自己尝试用map去写，发现掉到思维陷阱了，硬是出不来。感觉自己逻辑思考上还有欠缺，于是总结一波。
image.png
重要性
-
逛牛客网的试题广场，也发现了这一道题的存在。
image.png
-
逛知乎的时候，发现了一个帖子围绕的话题是
IT公司应聘应届生的标准是什么。看到一位大佬的回答就有这一道题的存在，可见这道题的重要性。废物不多说，贴图。
image.png
image.png
image.png
说实话，我基础不是特别好，做这道题还是有点吃力，主要是掉进思维陷阱了，虽然有些Java理论可以满嘴跑火车跑出来，但是真碰到稍微灵活的算法，估计就GG了。
image.png
解题思路
-
首先定义一个变量
element，默认是字符串的第一个字符。以element为基准元素，去判断某个字符是否重复。然后再去定义一个变量count去记录重复的次数，初始值应该为1。 -
然后我们去遍历整个字符串，应该从第
1号位置的字符开始遍历。如果当前字符等于element，就说明该字符在当前字符串中出现过，已经重复了。那么count就应该自增。 -
如果当前字符不等于
element，就说明上一个字符连续的重复次数已经计算完毕，可以进行拼接操作。接下来我们就可以操作当前字符了，count还原到初始值1。 -
遍历结束时，进行拼接操作。为什么不在第二步进行拼接操作? 因为当前字符在整个字符串中重复的次数还没有统计完，如果记录一次重复的次数，就进行拼接的操作的话，肯定不能达到预期效果。假如字符串是
“ppppp”，如果这样做了，输出结果会是"p2p3p4p5"。所以必须要统计完某一个字符的重复次数，才能进行拼接操作。我们只需要计算一个字符连续的重复次数。当我们遍历某一个字符时，发现它不等于element，就说明它上一个字符重复次数已经统计好，这时候我们才可以进行拼接字符串操作。
应该注意的问题
-
先一般，后特殊。进行边界控制，我们要去判断字符串是否为
null或者“”，然后去做相应的判断。 -
每次必须在前推进循环不变式中涉及到的变量值。
-
比如一个字符
a在该字符串中出现过1次，那么应该输出a，而不是a1。 -
不要使用字符串拼接的形式拼接数据，
String是不可变对象，每次拼接会生成新的String对象。使用StringBuffer是线程安全的，还是可变对象。每次调用append()并不会生成一个新的字符串。
手写代码
public class Demo {
public static void main(String[] args) {
encode("aaabbcaa");
encode("a");
encode("abcabc");
encode("ppppp");
encode("");
encode(null);
}
public static void encode(String str) {
if (str == null || str.equals("")) {
System.out.println("");
return;
}
StringBuffer sb = new StringBuffer();
int count = 1;
char element = str.charAt(0);
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == element) {
count++;
} else {
sb.append(element);
sb.append(count == 1 ? "" : count);
element = str.charAt(i);
count = 1;
}
}
sb.append(element);
sb.append(count == 1 ? "" : count);
System.out.println(sb.toString());
}
}
- 在编写测试数据的时候，应该考虑到空值，特殊值，边界值。运行
demo，看输出结果。
image.png
尾言
自己还是太菜了。
Java小白，还需努力。
