面试遇到算法简单题,如何秀?

原创
2021/09/08 08:48
阅读数 231

你好,我是yes。

事情是这样的,今天日常打开 LeetCode 刷题,然后刷到了这题

我一看,我去这题目也太简单的了吧,不就是替换字符串嘛,看不起谁呢?想都没想,直接一个:

那理所当然,肯定是通过的,但是击败了 100%?

我顿时就来了兴趣了,JDK的库竟然能击败 100%?我个人认为这个还是比较少见的。

为什么我会诧异呢,一共有两个原因:

  1. 首先 JDK 的库需要考虑很多情况,属于一种普适性的工程上的严谨实现, 避免不了会有很多判断

举个简单的例子,比如ArrayList#get,这个方法我们常用吧,里面会有范围的判断:

所以一般类库要考虑的东西比较多,所以要处理的逻辑会多一些。

  1. 然后 LeetCode 上有些人,为了击败 100% 会做一些奇怪的操作。比如有人会把测试用例的答案列成一个表,然后你输入什么,他直接返回结果...还有些会针对题目做一些特制的实现。简单来说就是投机倒把,不知道在想什么。

基于此,我就对 String 的 replace 的实现产生了兴趣,看看它为啥能击败 100% ,遂查看之。

这一看,确实有很多细节,JDK 就是 JDK,咱们学习之。

不过在看 JDK 实现之前,我们先来看看题解区别人的实现,对比来看,效果更佳。

我们直接来一个 LeetCode 官方题解:

很简单,题目要求用 %20 替换空格,一个字符变三个字符,那就保险点 new 个三倍的新数组,然后遍历 String 判断替换之。

再来看另一种题解,基本上就是用 StringBuilder 来实现:

很简单吧。

然后我们再来看看 JDK 的实现,这时候就有感觉了。

  1. 细节一:这个其实和题目没关系,题目是写明了把空格替换成 %20 ,所以不需要这个判断,不过我们需要学习这种思想:在方法的开头就把 null、明显错误、不需要操作的输入直接处理了,这样就不会做无用功,浪费资源,这是我们需要学习的地方。

  2. 细节二:其实注解已经解释了: avoid getfield opcode。如果你看了挺多源码,或者开源框架的源码,你会发现这种操作非常多,它的作用就是把实例变量赋值给局部变量,这样在多次调用此变量的时候就不需要执行多次 getfield这个操作码了。

我们来看一下实验,代码很简单,方法里面调用三次实例变量的获取,字节码就有三次的 getfield:

如果把代码改一下,把实例变量赋值给局部变量,然后再执行,字节码只有一次 getfield:

所以把实例变量赋值给局部变量,这样就少操作了几次 getfield ,提高了性能。

所以这招学会了嘛?

  1. 细节三,我标注了两处,这个就和题目强相关了,不过也有其它借鉴意义。

根据这个题目的意思,遇到老的字符就用新的字符替换,那需求正常的实现逻辑如下:

char buf[] = new char[len];
for (int j = 0; j < len; j++) {
  if (val[j] == oldChar) {
    buf[j] = newChar;
  } else {
    buf[j] = val[j];
  }
}

这个操作看起来没问题,但是你想一下如果遍历整个数组都没找到一个 oldChar ,那这波 new 了个新数组,并且每个都赋值过去,是不是就是白给了,万一数组很长,这不就血亏了吗?

比如输入的 s 没有一个空格,这得得得得得的循环下来,白给。

所以 JDK 的实现是先探个底,看看到底有没有 oldChar,如果找到,那才 new 个新数组,然后进行操作。

我们重温一下细节三的代码:

所以,从中我们也可以 get 到和细节一类似的思想,预判一下逻辑,没必要就不要执行,不然就是浪费。

这个就类似于 fail-fast 的思想。

好了,分析结束。

没想到做个简单题有意外之获~所以,如果你面试遇到这个题,不要直接 str.replace,你可以把 replace 的实现写上去,这波就有点小秀,对吧,面试不就是为了秀吗?

欢迎关注我的公众号【yes的练级攻略】,更多硬核文章等你来读。

本文分享自微信公众号 - yes的练级攻略(yes_java)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
jdk
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部