讨论/题目交流/🏆 第 172 场力扣周赛/
🏆 第 172 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛】

image.png

3 分 - 6 和 9 组成的最大数字
4 分 - 竖直打印单词
5 分 - 删除给定值的叶子节点
6 分 - 灌溉花园的最少水龙头数目

展开讨论

前3题,半小时不到就写完了...
第4题,开始想水龙头有开关两种状态,用位压缩看看....瞄了一眼数据...不可能了...
贪心,从覆盖最广的开始?还是动态规划,每个都检查一下?
后来把每个水龙头的覆盖范围都求出来[[L, R].....],排了个序...答案就出来了.
0-n1, 0是必须要有的,就从0开始往右推,
第一次 0-n1, n1要取最大,因为已经排序,遍历所有L<=n1的水龙头,如果[L,R]的L>n1, 就计数一次,把之前的水龙头的[L, R]中的R赋给n1,
然后求下一次的n1,
找R的过程中, 如果n1已经全部覆盖了,就返回当前的计数.
如[[0, 1], [0, 3], [1, 3], [2, 6], [4, 6], [6, 7]]
第一次 0,3 n1 = 3 L <= 0 的有 [0, 1], [0, 3] 取最大的[0, 3] n1 = 3
第二次 0,6 n1 = 6 L <= 3 的有 [1, 3], [2, 6], 取最大的[2, 6] n1 = 6
第三次 0,7 n1 = 7 L <= 6 的有 [4, 6], [6, 7] 取最大的[6, 7] n1 = 7 已经覆盖范围,返回计数 3.

1
展开全部 9 讨论