内容简介:上周末因为五一调休加班,我没有参加比赛,现在来看一下这个比赛吧。做完做了这四道题,顺便使用了一下 LeetCode 互动项目。操作之后,发现杜宇首次使用 github 来协同工作的人来说,还是蛮有难度的。
一、背景
上周末因为五一调休加班,我没有参加比赛,现在来看一下这个比赛吧。
做完做了这四道题,顺便使用了一下 LeetCode 互动项目。
操作之后,发现杜宇首次使用 github 来协同工作的人来说,还是蛮有难度的。
如果你想学习算法的话,建议参考上一篇文章《 启动Leetcode算法互动编程项目 》来尝试一下。
如果你参与这个项目了,并参与了几轮互动编程。以后也可以说自己在 github 上参与过公开项目了,而且还多次进行 pull request 贡献代码了。
二、移动石子直到连续
题号:5039
题意:数轴上有三个不重复的数字 x<y<z
,每一步可以选择 x
或者 z
数字来移动,移动位置后的新位置是 k
,需要满足 x<k<z && k!=y
,直到无法移动,结束移动。
要求输出最大移动步数和最小移动步数。
思路:首先需要明白,无法移动的条件是三个数字连续,即 x+1 == y && y+1 == z
。
而对于最大步数和最小步数,方案有两种。
第一种方案是DP或记忆化搜索。
但是看到这道题难度是 easy,搜索和DP的难度至少是 Medium 或者 hard 的。
所以这道题肯定可以更简单的方法。
第二种方案就是贪心计算。
先开最大步数,每移动一下, x
和 z
的距离至少减一,这样移动到距离是2的时候,就不能移动了。
所以最大步数是 z-x-2
。
对于最小步数,通常两步即可完成。
起始是x, y,z
第一步之后是
x,x+1,y
第二步之后是 x,x+1,x+2
但是,有时候需要一步就可以达到三个数字连续。 大概分这样几种情况:
1. x,x+1,x+2+n
,此时最后一个数字移动到 x+2
即可。
2. x,x+2,x+2+n
,此时最后一个数字移动到 x+1
即可。
3.两种对称情况,即后两个数字连续或者间隔为1。
只有一种情况需要0步,即三个数字本身就是连续数字。
小技巧:对于只有一步的情况较多,可以使用排除法,两步和零步的都计算了,其他的就是一步的。
三、边框着色
题号:5040
题意:给一个矩阵和一个坐标,求将坐标值相等的联通区域染色,这里只需要染色边界。
思路:如果是纯粹的染色,大家应该都会做,一个 DFS 或者 BFS 即可。
那只染色边界怎么办呢?
染色前判断一下是不是边界即可。
小技巧:新染色的值可能在矩阵上是存在的,有些人不知道怎么区分。
我经常使用的方法时先染色为矩阵上不存在的特殊值,最后再全部替换为目标值。
四、不相交的线
题号:5041
题意:给两个数组,两个数组之间相等的值可以相连。问不相交的线可以画几条。
思路:这道题就是一个赤裸裸的最长公共子序列题。
直接两层循环 DP 即可。
五、逃离大迷宫
题号:5042
题意:告诉你一个 10^6 x 10^6
大小的网格,以及一些坐标代表障碍物,问是否可以从一个起点到达一个终点。
思路:以前做过类似的题,不过矩阵较小,直接暴力搜索即可。
这里矩阵很大,没办法暴力搜索了。
那怎么判断两个点是否可到达呢?这个不好判断。
但是反过来,我们可以判断这个点是否不可达。
当障碍物将其中一个点围起来的时候,这个点就会变成不可达。
看看障碍物的个数,最多两百个。
不考虑边界,那这些障碍物最大可以围城一个 50*50
的闭环空间。
结合上边界,这些障碍物最大可以围城 200*100
的闭环空间。
看到这里,这道题的解决方案也就出来了。
我们分别查找两个点,如果在 200*100
步内依旧还有搜索空间,则认为这个点是开放的。
如果两个点都是开放的,则认为两个点是可以互相到达的。
六、最后
这次四道题还算简单,尤其是介绍思路后,大家都可以实现一下。
和几个人简单的互动后,发现 github 上的 network 图很好看,可以清晰的记录大家的互动情况。
你可以来尝试一下。
-EOF-
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- Leetcode 第126场比赛回顾
- Leetcode 第127场比赛回顾
- Leetcode 第94场比赛回顾
- Leetcode 第133场比赛回顾
- Leetcode第135场比赛回顾
- Leetcode第95场比赛回顾
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
PHP高级程序设计
Kevin McArthur / 汪泳 等 / 人民邮电出版社出版 / 2009.7 / 45.00元
今天,PHP已经是无可争议的Web开发主流语言。PHP 5以后,它的面向对象特性也足以与Java和C#相抗衡。然而,讲述PHP高级特性的资料一直缺乏,大大影响了PHP语言的深入应用。 本书填补了这一空白。它专门针对有一定经验的PHP程序员,详细讲解了对他们最为重要的主题:高级面向对象、设计模式、文档、测试和标准PHP库等内容。同时,为适应目前Web开发的新趋势,作者还全面探讨了MVC架构和Z......一起来看看 《PHP高级程序设计》 这本书的介绍吧!