LeetCode 56,57,60,连刷三题不费劲

本文始发于个人公众号:TechFlow,原创不易,求个关注

今天是LeetCode专题的第34篇文章,刚好接下来的题目比较简单,很多和之前的做法类似。所以我们今天出一个合集,一口气做完接下来的57、59和60这三题。

再次申明一下,为了节约篇幅,保证文章的质量,我跳过了LeetCode当中所有的Easy以及少量没什么营养的Medium和Hard的问题。Easy的问题都不是很难,即使是新手一般来说也不需要看题解,仔细想想也应该能搞定。所以就不占用篇幅了,如果大家有比较感兴趣的Easy问题,可以在下方的小程序处给我留言。

LeetCode 57 插入区间

第一题是57题Insert Interval,插入区间。题意会给定一组区间和一个单独的区间,要求将这个单独的区间插入区间集合,如果有两个区间存在交叉的情况,需要将它们合并,要求合并之后的最终结果。从题意上来看,基本上和我们上一篇文章讲的区间合并问题完全一样。唯一不同的是,在这题当中给定的这一组区间都是天然有序的,我们不需要对它进行排序。

区间已经有序了,剩下的就很简单了,我们只需要进行插入即可。区间插入的判断条件还是和之前一样,如果A区间的左端点在B区间左端点左侧,那么只要A区间的右侧端点在B区间左端点的右侧即可。所以这题基本上没有难度,就是一道裸题,我也不明白为什么官方给定的难度是Hard。

我们直接放出代码:

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        ret = []
        # l, r记录待插入区间
        l, r = newInterval
        # 记录待插入区间是否完成插入
        flag = False

        for x, y in intervals:
            # x, y记录当前区间
            # 如果当前区间在待插入区间左侧,那么将当前区间插入答案
            if y < l:
                ret.append([x, y])
            # 如果当前区间在待插入区间右侧,那么将两个区间都插入答案
            elif r < x:
                if not flag:
                    flag = True
                    ret.append([l, r])
                ret.append([x, y])
            # 否则,说明当前区间与待插入区间可以合并
            # 更新待插入区间的范围
            else:
                l, r = min(l, x), max(r, y)
        # 如果最后还没有完成插入,说明待插入区间大于所有区间
        # 手动插入,防止遗漏
        if not flag:
            ret.append([l, r])
        return ret

只要理解了区间合并的条件,这题真的没有难度。

LeetCode 59 螺旋矩阵II

前不久我们刚出过螺旋矩阵I的题解,在螺旋矩阵I当中,我们给定了一个矩阵让我们螺旋形去遍历它。这题则相反,给定我们矩阵的长和宽,让我们生成一个这样的螺旋矩阵

我们来看下样例:

LeetCode 56,57,60,连刷三题不费劲

在这题当中,我们使用54题的思路也完全可以解出来,但是这题更加简单了一些。由于是让我们构造一个矩阵,那么我们其实没有必要维护每个方向的边界了。只要出现出界或者是遇到了已经填好的数字那么就说明应该转向了。某种程度上来说,这题应该是I,之前的54题应该是II,因为这题更简单一些。

如果对54题解法不熟悉的同学,可以点击下方的传送门,学习一下方向数组的使用方法。

传送门

由于我们不需要维护每个方向的边界,并且移动的步数是固定的,更重要的是,转向每次最多只会发生一次,所以这个流程非常简单,我们直接来看代码即可。

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        # 初始化答案
        ret = [[0 for _ in range(n)] for _ in range(n)]
        # 初始化方向数组
        fx = [[0, 1], [1, 0], [0, -1], [-1, 0]]

        # 初始化方向以及起始点
        dt = 0
        x, y = 0, 0

        # n*n的方阵,一共需要填入n*n个数字
        for i in range(n*n):
            ret[x][y] = i+1
            # 移动的下一个位置
            x_, y_ = x+fx[dt][0], y+fx[dt][1]
            # 如果发生超界或者是遇到的数字大于0,说明需要转向
            if x_ < 0 or x_ >= n or y_ < 0 or y_ >= n or ret[x_][y_] > 0:
                dt = (dt + 1) % 4
            # 转向之后的位置
            x, y = x+fx[dt][0], y+fx[dt][1]

        return ret

LeetCode 60 第K个排列

这题是一个排列组合问题,给定一个整数n,它代表[1,2,3,...,n]这n个元素的序列。然后还有一个整数K,要求这n个元素从小到大第K个排列。

这题其实蛮有意思,我觉得可以上hard,但遗憾的是它有一个讨巧的办法,大概也许是这样,所以才被降级成Medium的吧。这个讨巧的办法应该蛮容易想到的,很明显,由于n个数字是确定的,所以最小的排列一定是[1,2,3,...,n]。而我们之前做过一道LeetCode31题,它求的是给定一个排列,然后生成字典序比它大刚好一位的下一个排列。

既然如此,我们可以重复使用这个算法K-1次,就得到了答案了。对于做过31题的同学而言,这题毫无难度。如果对于31题解法不熟悉的同学可以点击下方传送门,回去复习一下。

传送门

但其实可以不用这么麻烦,因为Python当中有自带的排列组合的工具库,我们可以直接调用,只用5行代码就可以搞定。

class Solution:
    # 引入包
    from itertools import permutations
    def getPermutation(self, n: int, k: int) -> str:
        # 由于最后返回的结果要是string
        # 生成['1','2','3',...,'n']的序列用来计算下一个排列
        base = [str(i) for i in range(1, n+1)]
        # 调用permutations会得到一个按顺序计算排列的生成器
        perms = permutations(base, n)
        for i in range(k):
            # 我们调用k-1次next就能获得答案了
            ret = next(perms)
        return ''.join(ret)

这个方法虽然写起来短平快,但是也有一个重大的问题,就是耗时很长。这个其实很容易算,根据当前排列生成下一个排列的复杂度是\(O(n)\)。我们一共需要计算k-1次,所以整体的复杂度就是\(O(nk)\),极端情况下k=n!,所以最差复杂度是\(n \cdot n!\)。要知道n个物体的排列一共有n!种,如果k很大,这个复杂度是爆表的。不过这题没有过多为难人,这样的复杂度也能AC。我个人觉得这是一个很遗憾的事情,因为简单的算法也可以AC会导致很多人没有斗志再去研究复杂的算法了。

最后,我们来看正解。

正解其实不涉及任何新的算法和数据结构,甚至说穿了一文不值,但是很多人就是很难想到。还是老话题,它需要我们对问题进行深入的思考。

既然我们一个一个地求下一个排列非常慢,那么我们能不能有快速一点的办法呢?加快速度大概有两种办法,第一种增加步幅,比如之前的方法是每次获取字典序+1的排列, 我们能不能生成字典序+k的排列?第二种想法是我们能不能直接求解答案,直接生成出这个排列?

简单分析一下会发现第一种是不可行的,或者说是伪命题。因为如果说我们可以想出一个求解字典序+k的算法,那么我们令这个k等于题目中要求的k不就是直接求解答案了?所以说,如果可能存在更好的办法,一定只能是第二种,也就是直接构造答案的方法。那么问题就剩下了,我们怎么直接构造这个答案呢?这就需要我们对排列组合的理解了。

如果你亲手写过某个集合的全排列,你会发现一些规律。比如说123的全排列好了。我们都知道,它的全排列一共是123,132,213,231,31和321。这个很简单,我们观察一下会发现,123一共三个数字,6种排列。每个数字打头的都是2种,如果换成1234的排列呢?列一下就会知道是6种。如果你找规律你会发现,每个数字开头的种数是(n-1)!。

如果要推导也很简单,因为每个数字都是公平的,所以每个数字开头的种数都是一样的。而全排列一共有n!种,所以分摊到每个数字头上剩下(n-1)!种。那如果我们已经知道了第一个数字是1,请问第二个数字是2的种类数有多少种?同样的方法可以算出是(n-2)!种。到这里有没有火花闪过的感觉?

我们来举个例子吧,假设我们现在n=5,我们算一下会知道,一共有120种排列。假设我们要求第100个排列,由于从0开始,所以也就是第99大的排列。那么根据我们刚才说的,我们已经知道每个数字开头的情况都是4!也就是24种,那么我们用99/24得到4,所以开头的数字是第4大的数(第0大的是1),也就是5。答案一下子缩小了很多,那接下来呢?接下来我们用99减去5之前的所有情况,也就是96种,得到3。也就说答案是5开头的第3个排列,那么我再问,第二个数字是多少?

同样的办法,除去5之后还剩下4个数字,每个数字排第二都有3!也就是6种,我们用3/6=0,应该是第0大的数,也就是1。我们继续,除去5和1之后,还剩3个数字。每个数字排第三的情况有2种,我们用3/2=1,我们应该选择第1大的数,这里剩下的数是2,3,4,所以第三位应该是3。以此类推,我们可以得到每一位的数字。整体的复杂度是O(n),和上面的方法相比,有了质的突破。

我把整个计算过程做成了图,有看不懂的小伙伴可以结合一下下图理解:

LeetCode 56,57,60,连刷三题不费劲

最后,我们把这个方法实现即可:

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        frac = [1 for _ in range(n+1)]
        # 生成一个序列存放所有的元素
        nums = [i for i in range(1, n+1)]
        # 计算每一位的种类数
        for i in range(1, n):
            frac[i] = i * frac[i-1]

        ret = ''
        k -= 1
        for i in range(n-1, -1, -1):
            # 计算第i位的数字是当前第几大的数
            cur = k // frac[i]
            # 放完之后取模,表示去除掉之前的所有情况数
            k %= frac[i]
            # 求出当前元素之后,需要从序列当中移除
            ret += str(nums[cur])
            nums.remove(nums[cur])

        return ret

结尾

到这里三题就算是讲完了,今天的这三道题目或多或少的都和之前的问题有关,这也是我把这三题放在一篇文章当中阐述的原因。

这三题当中我个人最喜欢第三题,尤其是完美解法。它的整个思路和代码都不复杂,也没有什么特殊的技巧或者是方法,但是如果没有对题目有足够深入的了解是很难想到这个算法的。这其实也是算法题的精髓所在,比赛当中多的是知道解法也做不出来的题目。所以我们要提升算法水平,光学算法是不够的,也需要对题目有深入理解才行。

今天的文章就到这里,原创不易,需要你的一个关注,你的举手之劳对我来说很重要。

LeetCode 56,57,60,连刷三题不费劲

上一篇:Leetcode OJ 刷题


下一篇:ubuntu下man帮助文档不全怎么办?如何解决?