我是如何把easy级别的算法题做成hard级别的。

来自:苦逼的码农(微信号:di201805),作者:帅地

我们平时在刷题的时候,我觉得大致可分为以下几类题

1、这道题的暴力解法很简单,几乎人人都会做,但最优解却很难。

2、如果你懂某些算法思想,这道题很简单,如果不懂,那么这道题顿时很难,例如有些需要dp来处理的。

3、这种题型没做过,没啥思路,但接触过好几道之后,便会觉得异常简单,例如不能使用加减乘除运算符来完成加法运算

4、最后一种是属于真正的难题,思路难想 ,就算知道了思想,编码也很难,因为临界点之类的特别多,逻辑特别复杂。

而我今天要强调的就是第一类题,我这里给的建议是,我们要追求极致,并且我今天会给出2道例题,大家也可以想想这2道题的解法。如果这2道题你不懂怎么做,那么看完一篇文章会有所收获。

我在牛客网刷题的时候,发现有些题的解法,如果你是采用暴力的话,是异常简单的,但是每次遇到这种题,我都不会轻易马上写代码,而是苦思一会,看看有没有优雅的解法。不过我去看很多通过的代码,发现大部分人的解法都是很普通,几乎算是暴力法,可能那些人看到这道题的时候心想:我去,又秒杀一道题了,三分钟撸好了代码,一次就ac了这道题,心里满满的快感,马上接着下一题走起。

但是,这种做法我是不支持的,因为这道题如果你草草了事,那么你没有任何优势,因为你这种解法别人也会;而且,做完这道题,你可能没有任何收获,估计只收获了快感。也就是说,做完这道题,你并没有收获到这道题最核心的解法。

所以,我觉得,对于这种题,我们一定要追求极致,不能“得过且过”。把这道题的精华吸收进来,有些题的精华、技巧,是可以开拓你的思路的,进而影响 你对其他题的解法的

当然,收获快感提升下解题的动力也是挺好的,而且最普通的解法对部分人来说也是收获满满的。我这里只是一个建议,如果可以,请追求极致。

下面我举几个例子,也算是顺便一起来刷几道题。

案例1:构建乘积数组

题目描述:给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]A[i-1]A[i+1]A[n-1]。不能使用除法。

这道题简单吗?就算不能使用除法,也是挺简单的,每次算 B[i],都全部遍历一下数组,两个 for 循环就搞定了,时间复杂度是 O(n^2)。

但是,我敢保证,这种做法95%的人都会做,没有任何优势。所以我们想想是否有更加优雅的解法,有人说,想不出来怎么办?

很简单,想不出来就看看别人怎么做,百度搜索 or 讨论区看答案。看别人的解法,一点也不丢人

所以对于这道题,更好的解法应该是这样的:

1、先算出 B[i] = A[0] * …A[i-1]。

2、接着算 B[i] = A[i+1]…A[n-1] * B[i](B[i]是步骤1 算出来的值)

代码如下

    public int[] multiply(int[] A) {
        int len = A.length;
        int[] B = new int[len];
        B[0] = 1;
        //分两步求解,先求 B[i] = A[0]*..A[i-1];
        for(int i = 1; i < len; i++){
            B[i] = B[i-1] * A[i-1];
        }
        //再求B[i]=A[i+1]*...A[n-1];
        int tmp = A[len-1];
        for(int i = len - 2; i >= 0; i--){
            B[i] *= tmp;
            tmp *= A[i];
        }

        return B;
    }

时间复杂度是 O(n)。有人可能会问,那我怎么知道这个解法是否就为最优解了呢?我觉得这个可以自己判断,加上多看一些点赞高的人的解法,如果时间复杂度、空间复杂度都和你差不多,那么几乎就可以认为是最优解了。就算实际上不是,而大佬们也都这样解,那么也可以姑且认为是最优解了。最重要的是,比你最开始想的解法好多了就行了。

案例2:数组中重复的数字

题目描述:在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么2和3就是重复的数字了,那么可以随意返回2或者返回3都可以了,任意选择一个即可。

解法

这道题简单吗?如果只是想 ac 过去的话,那么挺简单,例如以下两种解法

1、给数组排序下,然后从左到右遍历,看看有相邻的数有没有相等即可。时间复杂度是 O(nlogn),空间复杂度O(1).

2、用一个哈希表来存放这些数组,把数组元素值作为 key,相同元素的个数作为 value。遍历的过程中,只要发现某个 key 的 value 超过 1,那么这个数就是重复的了,直接返回。时间复杂度是 O(n),空间复杂度是 O(n)。

这两种解法相信都不难,也很容易想到,不过请记住,很容易想到的解法大多数时候都不是最优解。那么有更好的解法吗?答是有的,更好的解法是时间复杂度是 O(n),空间复杂度是 O(1)。方法如下:

由于数字的范围是 0-n-1,那么我们可以这样做:从左到右遍历数组arr,对于 arr[i],我们可以把arr[i]放到数组下标为arr[i]的位置上,即arr[arr[i]] = arr[i]。例如 arr[0] = 4,那么我们就把arr[0]与arr[4]进行交换。假如数组中没有重复的数,那么遍历完成后的结果是 arr[i] = i。如果数组有重复的元素,那么当我们要把 arr[i] 与 arr[arr[i]] 进行交换的时候,会发现 arr[arr[i]] 的值已经为arr[i]了,并且arr[i] != i。

没看懂?那我做个演示吧,例如数组为 arr = {2, 3, 3, 0}。步骤如下

1、从左到右遍历,此时数组下标i = 0,即arr[i] = 2。把 arr[0] 与 arr[2] 进行交换,交换的结果为 arr = [3, 3, 2, 0}。

2、i = 0,由于 arr[0] = 3,不满足 arr[i] = i,所以我们的下标还是不能右移,还是得继续交换。即把 arr[0] 与 arr[3] 进行交换,结果为 arr[0, 3, 2, 3}。

3、i = 0,此时 arr[i] = i。故下标右移,即 令 i = 1。此时 arr[i] = arr[1] = 3。把arr[1] 和 arr[3] 进行交换,但是这时候 arr[3] = 3.即此时出现了 arr[arr[1]] = arr[3]并且 arr[i] != i 的情况,故出现了重复的元素了,直接把 3 返回,遍历结束。

如果看不懂,多看两遍就能看懂了,代码如下:

   public int duplicate(int arr[],int length) {
        int i = 0;
        while(i < length){
            if(arr[arr[i]] == arr[i]){
                if(arr[i] == i){
                    i++;
                }else{
                    return arr[i];
                }
            }else{
                int tmp = arr[arr[i]];
                arr[arr[i]] = arr[i];
                arr[i] =  tmp;
            }
        }
        return false;
    }

这种方法建议大家掌握,我有好几道是遇到这种方法来处理的,例如我之前分享的几道题:【算法精讲】分享一道很不错的算法题

总结

今天 姑且分享一些对追求极致的一些看法以及举了两道题,这两道题也是自己精挑细选的,希望大家能够有所收获,并且以后做题的时候能够严格要求自己。后面我会分享后面的几类题,每次都会分享一些不过的例题,力求至少让你看完这些例题,能够有所收获。

推荐↓↓↓
算法与数据结构
上一篇:设计 Twitter:合并 k 个有序链表和面向对象设计 下一篇:记一道阿里笔试题:我是如何用一行代码解决约瑟夫环问题的