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

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

image.png

3 分 - 奇数值单元格的数目
4 分 - 重构 2 行二进制矩阵
5 分 - 统计封闭岛屿的数目
6 分 - 得分最高的单词集合

展开讨论

惯例占坑,详细题解稍晚来~:

  • 奇数值单元格的数目
    数据范围小,可以直接模拟每行每列的情况,时间复杂度为 O(n2)O(n^2)。不过也可以只统计行和列的计数情况,我们分别统计被增加偶数次和奇数次的行,以及被增加偶数次和奇数次的列,那么对应的 偶数行奇数列偶数行*奇数列奇数行偶数列奇数行*偶数列 都可以被统计入结果,时间复杂度降为 O(n)O(n)

  • 重构 2 行二进制矩阵
    sum0sum2 的都是固定策略的,重点就是 sum1 的该如何分配,首先如果 upper+lowersum22sum1upper+lower-sum_2*2≠sum_1,那么肯定是无解的。如果有接,我们直接遍历原矩阵列,如果 upper 大于0那么就把1分配给upper行,否则分配给lower行。时间复杂度为 O(n)O(n)
    还有一种无解的情况是 upper<sum2upper<sum_2 或者 lower<sum2lower<sum_2,也需要判断。

  • 统计封闭岛屿的数目
    经典的搜索题目,只是现在我们在搜索的同时还需要记录一个当前是否触碰到边界的状态,如果触碰到边界那么当前岛屿不计入答案。

  • 得分最高的单词集合
    由于单词最多只有 1414 个,我们可以暴力每个单词是否选取来计算当前得分更新结果。比如我们现在枚举选择了 [1,2,4][1,2,4] 单词,那么就统计这三个单词所需要的字母数量,然后看看我们的字典是否能满足,能满足的话就计算得分并更新我们的结果。如果有 nn 个单词,单词平均长度为 mm,时间复杂度为 O(nm2n)O(nm2^n)

4
展开全部 22 讨论