Databricks codesignal 面筋

来自APP · 2021-9-3 16:49:27

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

1、2题很简单

第三题是模拟俄罗斯方块，给一个二维矩阵，然后上面有obstacles，空，和当前的方

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

（2，6）（4，8），只被一个区间覆盖的点是1，7，8 答案是3

guori12321

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

ZJUThomasCU

这个可以用前缀和的想法来做，dp初始都为0，size为n，只要离散处理区间端点就行，对于区间[i,j], dp[i] += 1, dp[j] -= 1。这样得到的dp其实就是出现次数的差分，把dp的前缀和求出来后扫描一遍，累加dp[i] == 1的个数即可。

guori12321

wjlwb 发表于 2021-9-3 08:31
哇大佬牛逼！

因为我是数据库方向的，databricks我一直没敢投...但是已经9月了，赶紧刷题目赶紧投.....

wjlwb

guori12321 发表于 2021-09-03 03:35:29
题目：给出一堆闭区间，然后要求只被一个区间覆盖的点的个数，比如（1，5）（2，6）（4，8），只被一个区间覆盖的点是1，7，8 答案是3

我的第一反应是枚举所有的点，然后检查这个点是不是只在

哇大佬牛逼！

ghu97

ZJUThomasCU 发表于 2021-9-6 21:01
这个可以用前缀和的想法来做，dp初始都为0，size为n，只要离散处理区间端点就行，对于区间, dp += 1, dp[j] ...

楼上正解，这道题类似的题目有很多，这道题算是一种巧妙的变型。