美文网首页JAVA后端架构MySQL微服务架构和实践
面试官,求求你不要问我这么简单但又刁难的算法题了

面试官,求求你不要问我这么简单但又刁难的算法题了

作者: AI乔治 | 来源:发表于2019-08-01 15:14 被阅读57次

    有时候面试官往往会问我们一些简单,但又刁难的问题,主要是看看你对问题的处理思路。如果你没接触过这些问题,可能一时之间还真不知道怎么处理才比较好,这种题更重要的是一种思维的散发吧,今天就来分享几道题面试中遇到的算法题(当然,不是我自己遇到过,是别人遇到过,我挑选出来的)

    案例1

    题目描述:求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

    我去,求和居然不让用乘除法,也不准我们用循环,如果单独这两个限制的话还好,我们还可以用地递归,例如:

    int f(int n){
        if(n == 0){
            return n;
        }else{
            return f(n-1) + n;
        }
    }
    

    然后 if, else, case 等各种关键字也不给用,想着那我用三元运算符(A?B:C),然后这种具有判断语句的三元运算符也不给用,我去,这也太刁难了吧(当然,大佬直接秒杀的可以飘过)。

    这道题肯定是必须用递归来解决的,而这递归的核心就是需要判断一下递归条件是否结束了,然而题目不准我们使用条件判断语句。那我们该怎么办呢?大家可以散发思维想一下哦。

    其实我们可以下面这样的语句来代替 A?B:C 这样具有判断能力的三元运算符

    n != 0 && (f(n-1) + n)  != 0;
    

    这个 && 逻辑判断符的作用就是:如果 n != 0 成立的话,那么逻辑判断符后面的判断语句 (f(n-1) + n ) != 0 也会执行,如果 n != 0 不成立的话,那么后面的判断语句 ((f(n-1) + n)) != 0 就不会执行,通过这种方法,就可以达到我们递归结束条件判断的目的了。

    这里说明一下,(f(n-1) + n) != 0 这条判断语句是没有任意其他含义的,我们的目的是为了执行 f(n-1)+n,之所以加上个 != 0 的判断,是因为逻辑判断符号 && 只支持 boolean 类型,不支持 int 类型。

    最后的代码如下

    public int f(int n) {
            int sum = n;
            boolean t = (n != 0) && (sum += f(n - 1))!= 0;
            return sum;
        }
    

    如果你做过这种类型的题,可能就会觉得很简单了,如果没做过,可能就需要思考一下,不过,往后你就可以直接秒杀了。


    案例 2

    题目描述:写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。

    我去,求和不准加减乘除!面试官,能不能别这么任性,好好的加减乘除居然不给用。

    不过我相信大家第一时间都能想到用位运算来解决,可能在大学期间学过电路相关知识的一下就能把代码写出来了,不过有些人也能可能是一个位一个位来处理的。例如我先处理第一个位(这里指的是二进制位哈),看看有没进位,然后处理第二个位,如果第一个位有进位就加到第二个位来,然后处理第三个位.....

    如果你是这种方法处理的,那么恭喜你,看完这道题你能有所收获。实际上上面那种解法也可以,只是太复杂了,可能各种判断。其实这道题可以这样解:这里为了方便讲解,我先给出代码,再给出具体的讲解,你看完代码再来看讲解可能更好理解

    public int Add(int num1,int num2) {
            int tmp = 0;
            while(num1 != 0){
                tmp = num1 ^ num2;
                num1 = (num1 & num2) << 1;
                num2 = tmp;
            }
            return num2;
        }
    

    大家想一个问题,如果我们把两个数进行异或,例如num1 = 101, num2 = 001,做异或运算:tmp = num1 ^ num2,结果是 tmp = 100。那么此时得到的结果 tmp 其实就是两个数(num1,num2)各个二进制位上相加,不算进位的结果。而 num1 = (num1 & num2) << 1 的结果就是两个数相加时那些需要进位的二进制位。例如 (101 & 001)<< 1 = 010,那么两个数第一位相加需要进位,我们需要把进的那一位最后加到第二位上去。

    好像有点绕,,大家可以动手试一下哈,说白就是 a + b = a ^ b + (a & b) << 1。

    代码中,如果 num1 == 0 的话,代表没有进位了,此时就可以退出循环了。

    对于很少用位运算的人来说可能有点懵,那么我建议可以多看几遍,然后一遍动手模拟哈。以后遇到这种题就可以直接秒杀了。


    案例3

    在这里我先声明一下,案例3 也不算一道刁难题,只是我来考考你们而已,大家看到题目之后可以自己想一下哈,看了答案不能打我哈。

    题目描述:实现两个整数的相乘,不能使用乘法运算符和循环

    各位老哥可以想一下哈。

    这道题可能很多人都想到用递归了,好像我说的大部分算法题,都会用到递归,所以说你不懂递归的话,看我的公众号就行了,不懂也得变懂了是不是。代码如下:

    int mul(int a, int b){
        if (a == 0 || b == 0)
            return 0;
        if (b == 1)
            return a;
        if (a == 1)
            return b;
        return a + mul(a, b - 1);
    }
    int mult(int a,int b){
        // 这里我们取 b 的绝对值
        int sum = mul(a, abs(b));
        return (b<0)?(-sum):sum;
    }
    

    你是不是这样做的呢?其实,我们还有更好的方法哦,如下

    我去,不能使用乘法,又没说不能使用除法,那我用除法来代替乘法就得了,例如 a 乘以 b 就相当于 a 除以 b 分之一。代码如下:

    int mult2 (int a,int b){
        return b != 0 ? (int)(a / (1.0 / b) + 0.99 ): 0;
    }
    

    这里需要 int 进行转化类型,并且除法可能会导致后面尾数的丢失,所以我补了个 0.99。注意,进行 int 类型转化时,不是四舍五入的哈,二手小于 1 就行当做 0 处理。当然,我这里用的是 Java 语言,其他语言自己看情况处理。

    总结

    今天的几道题,更多的是一种投机取巧吧,不过看你看到一到陌生的题目时,你会如何处理,点子多不多,这个还是挺重要滴,而多看一些点子,慢慢着你的点子也会变多了。


    以上就是我整理的几道面试题,以下就是我整理的其他面试题与答案。

    面试题答案,获取方式

    请加QQ群:976203838

    获取以上面试题答案传送门:https://shimo.im/docs/R6zZRIikthw8jifV

    重要的话说三遍,先 关注关注关注,然后加群才可拿到参考答案哦!

    注:
    作者:苦逼的码农
    出处:https://www.cnblogs.com/kubidemanong/p/11254542.html?utm_source=tuicool&utm_medium=referral

    相关文章

      网友评论

        本文标题:面试官,求求你不要问我这么简单但又刁难的算法题了

        本文链接:https://www.haomeiwen.com/subject/thoqdctx.html