Java小白必须会的一道面试算法题

前言

今天在群里面看消息,突然看到一个哥们发了一个关于算法的题目。我乍一看,感觉挺简单的。群里面有的哥们说用map去做,然后我自己尝试用map去写,发现掉到思维陷阱了,硬是出不来。感觉自己逻辑思考上还有欠缺,于是总结一波。

image.png

重要性

  • 逛牛客网的试题广场,也发现了这一道题的存在。

image.png

  • 逛知乎的时候,发现了一个帖子围绕的话题是IT公司应聘应届生的标准是什么。看到一位大佬的回答就有这一道题的存在,可见这道题的重要性。废物不多说,贴图。

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小白,还需努力。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端正义联盟

我来重新学习 javascript 的面向对象(part 5)

这是最后的最后了,我会顺便总结一下各种继承方式的学习和理解。(老板要求什么的,管他呢)

9710
来自专栏IT可乐

Java数据结构和算法(七)——链表

  前面博客我们在讲解数组中,知道数组作为数据存储结构有一定的缺陷。在无序数组中,搜索性能差,在有序数组中,插入效率又很低,而且这两种数组的删除效率都很低,并且...

50670
来自专栏落影的专栏

程序员进阶之算法练习(十六)

前言 正文6道题目来自leetcode––为求职为生的编程网站,目的是工作闲暇之时锤炼代码功底。 没有捷径,但手熟尔; 一步领先,步步领先。 正文 5. L...

40650
来自专栏猿人谷

常见排序算法分析

一.常见排序算法的实现 1.冒泡排序 冒泡排序是非常容易理解和实现,,以从小到大排序举例: 设数组长度为N。 1.比较相邻的前后二个数据,如果前面数据大于后面...

21480
来自专栏java思维导图

【一分钟知识】面对对象、基本类型

【一分钟回顾】系列 很多知识都是概念性的东西,有时候你知道这个技术的用法,但未必就能准确地说出它代表的含义与思想。一分钟回顾系列文章会从基础开始到后期的高级,带...

30750
来自专栏java一日一条

面试中的 10 大排序算法总结

查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只...

23030
来自专栏怀英的自我修炼

Java漫谈6

今天这篇想聊聊数组。 在聊数组之前先聊个别的,如果想在Java中实现一个 数字-月份 转换,那我该怎么做呢?就比如数字1代表了一月份,数字2代表了二月份…数字1...

37690
来自专栏chenjx85的技术专栏

leetcode-605-Can Place Flowers

11230
来自专栏Python爬虫与算法进阶

学点算法之字符串的乱序检查

问题 字符串的乱序检查。 一个字符串是另一个字符串的乱序。如果第二个字符串只是第一个的重新排列,例如,’heart’ 和 ‘earth’ 就是乱序字符串。’py...

42080
来自专栏Java成长之路

【天梯 - Wikioi】2235 机票打折

9010

扫码关注云+社区

领取腾讯云代金券