最难的不是递归,是这场面试的有缘无分


序言

我第一次接触递归,是在大三的时候。

原谅我,我不是计算机专业学生,大三才开始自学代码。

还记得当时的题目是:一只猴想摘树上的桃,他可以一次摘1个,也可以一次摘2个,总共n个桃,他有多少种摘法?

明显递归可以完美解决,但是当时我想了好几个小时都没想出思路。

那一夜,我就感觉自己就是那条猴。

几年以后,我已经刷了好几遍的《剑指offer》,背了几十道leetcode原题,我相信我已经不是当年的那个猴了。

而今天,也是到一家新公司面试。

我相信,以我精湛的演技,刻苦的记忆,深深印在心中类似JVM原理这样的屠龙之技,即便客场作战,我仍可打通三场技术面试,直达HR之面。

想到这里,我身上的格子衫仿佛更正了一些。

临走前,我又默写了一遍冒泡排序,没有问题。

一切都刚刚好。

到达面试公司后,HR领我穿过层层工位,我一边打量未来我的同事一边感觉自己来到了菜市场,到处是产品和程序员关于排期的讨价还价。

在面试室等待片刻后,面试官来了。

应该是昨晚加班了,面试官头发都是蓬松的,屏幕也是淡黄色的,估计开了护眼模式。

一边看我简历,一边在工作群里疯狂输出。

"淡黄的长群,蓬松的头发",突然感觉这个rap好应景,好好笑,我不禁笑了起来。

面试官一脸懵逼的看着我:"我们可以开始面试了吗?"

我才反应过来,忙说可以可以。

面试官给了我几张白纸,说估计一会用得着。

又是熟悉的徒手写算法,这个我在家练了很久了,应该问题不大。

面试官问题到:"你知道递归吗?"

一刹那我又回到被猴子支配的那个夜晚,不过我现在早已进化了,并且有了自己的思考。

于是面露微笑,答道:"知道啊,其实按照我的理解,递归就好像人生。

人一生都在追求很多东西,比如财富、健康、亲情、爱情,财富又可以来自于主业、副业。

主业要想干好又需求文凭、努力、人脉等等。

有些人呢就会好像递归,一直追求目标下的主要选项,比如一直追求财富,然后一直想干好主业,进而把所有精力又到放到文凭,一直递下去,却不知道,函数栈太多,这样下去归来已不是少年。"

面试官直愣愣看着我:"好清新脱俗的解释,可是我们又不是HR面试,还不需要谈人生。简而言之,你能用一句话说什么是递归吗?"

我尴尬笑了笑,说:"函数调用自身。"

面试官:"这么简单的事说的这么麻烦。那行,我给你出个算法。"

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

我一看,这不是当年的题目吗?

激动的心,颤抖的手。

Talk is cheap,Code 给你show show。

于是,我不到三十秒就写完了代码。

public class Solution {
    public int JumpFloor(int target) {
        if(target == 1){
            return 1;
        }else if(target == 2){
            return 2;
        }else{
            return JumpFloor(target - 1) + JumpFloor(target -2);
        }
    }
}

面试官一脸错愕的看着我,我突然意识到了什么。

我知道自己刷过这道题,面试官也知道了我刷过这道题,我也知道面试官知道我刷过这道题,但是我还想找补一下,我其实是天赋异禀,天纵之才,这个答案是我花了三秒钟思考出来的。

但是显然来不及了,面试官看了一下,直接说没问题,然后开始了另外一道算法。

请完成一个函数,输入一个二叉树,该函数输出它的镜像。

忍不住感叹今天运气真好,连续两次刷到原题。

只不过,我肯定不能像刚才那样,不然那也太尴尬了。算法面试可是考验智力的,都快整成考记忆力的了。

面试官估计也是这样想的,说道:"这样吧,先不着急写代码,你说下递归一般问题的常见思路,然后结合这道题目,一点点来分析"。

这也不怕,我顿了一下,说道:

"递归问题一般都是有套路的,按照我的理解,主要分为三步

  1. 确定递归函数的参数和返回值

本道题中,参数肯定就是root节点,返回值可需要可不需要,因为返回的话也是该root节点。

那问题要求返回,那就函数的返回类型为TreeNode*。

public TreeNode invertTree(TreeNode root) 
  1. 确定终止条件

当前节点为空的时候,无法反转镜像,所以返回。

if (root == null) {
    return root;
}
  1. 确定单层递归的逻辑

因为是先前序遍历,所以先进行交换左右孩子节点,然后反转左子树,反转右子树。

  TreeNode temp = root.left;
  root.left = root.right;
  root.right = temp;
  invertTree(root.left);
  invertTree(root.right);
  return root;

完整的即为

public class Solution {
    /**
     * 翻转二叉树
     * @param root 二叉树的根
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

面试官充满赞赏的点了点头,随后又聊了些什么“负载均衡”,什么“设计模式”之类的,引得我逐渐放松起来,面试室里充满了快活的空气。

差不多聊了一个小时,毕竟才是一面,当前也差不多,临走前面试官还加了我的微信,感觉基本能过。

可能太激动了,最近面试的也太多了,最后的对话确实有点尴尬,朋友们帮我看看,我还能过吗?

我突然觉得自己好像挂了。。。

您的关注、点赞、在看、分享是我创作的最大动力!

创过业,赔过钱。遂转行,程序员。

从外包,到大厂。写代码,写文章。

胡思乱想,文章沙雕。

欢迎关注,与君同好。

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。

  • 分享:
评论
还没有评论
    发表评论 说点什么