潍坊新闻网独家:LeetCode 56,57,60,连刷三题不费劲

admin 2个月前 (02-28) 科技 124 1

本文始发于小我私家民众号: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当中,我们给定了一个矩阵让我们螺旋形去遍历它。这题则相反,给定我们矩阵的长和宽,让我们天生一个这样的螺旋矩阵

我们来看下样例:

在这题当中,我们使用54题的思绪也完全可以解出来,然则这题加倍简朴了一些。由于是让我们组织一个矩阵,那么我们实在没有必要维护每个偏向的界限了。只要泛起出界或者是遇到了已经填好的数字那么就说明应该转向了。某种程度上来说,这题应该是I,之前的54题应该是II,由于这题更简朴一些。

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

LeetCode54 螺旋矩阵,问题不主要,主要的是这个技巧

由于我们不需要维护每个偏向的界限,而且移动的步数是牢固的,更主要的是,转向每次最多只会发生一次,以是这个流程异常简朴,我们直接来看代码即可。

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题解法不熟悉的同砚可以点击下方传送门,回去温习一下。

LeetCode 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),和上面的方式相比,有了质的突破。

我把整个盘算历程做成了图,有看不懂的小伙伴可以连系一下下图明白:

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

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

末端


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

这三题当中我小我私家最喜欢第三题,尤其是完善解法。它的整个思绪和代码都不庞大,也没有什么特殊的技巧或者是方式,然则若是没有对问题有足够深入的领会是很难想到这个算法的。这实在也是算法题的精髓所在,竞赛当中多的是知道解法也做不出来的问题。以是我们要提升算法水平,光学算法是不够的,也需要对问题有深入明白才行。

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

,

Sunbet

www.tggzfm.com展望2019年,将用完善的服务体系,创新的技术应用,雄厚的资金实力,贴心的服务品质,成为Sunbet会员、 *** 的首选平台。

allbet声明:该文看法仅代表作者自己,与本平台无关。转载请注明:潍坊新闻网独家:LeetCode 56,57,60,连刷三题不费劲

网友评论

  • (*)

最新评论

  • 欧博代理 2021-02-28 00:20:51 回复

    联博API接口www.326681.com采用以太坊区块链高度哈希值作为统计数据,联博以太坊统计数据开源、公平、无任何作弊可能性。联博统计免费提供API接口,支持多语言接入。实力很强啊

    1

标签列表

    文章归档

      站点信息

      • 文章总数:1270
      • 页面总数:0
      • 分类总数:8
      • 标签总数:1517
      • 评论总数:1257
      • 浏览总数:117242