参加考试的最大学生数(LeetCode日记)

发布时间:2023年12月26日

LeetCode-1349-参加考试的最大学生数

题目信息:

给你一个 m ? n m * n m?n 的矩阵 s e a t s seats seats 表示教室中的座位分布。如果座位是坏的(不可用),就用 ‘#’ 表示;否则,用 ‘.’ 表示。

学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷,但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的同时参加考试且无法作弊的 最大 学生人数。

学生必须坐在状况良好的座位上。

  • 示例1:
    在这里插入图片描述

输入:seats =
[[“#”,“.”,“#”,“#”,“.”,“#”],
[“.”,“#”,“#”,“#”,“#”,“.”],
[“#”,“.”,“#”,“#”,“.”,“#”]]
输出:4
解释:教师可以让 4 个学生坐在可用的座位上,这样他们就无法在考试中作弊。

  • 示例2:

输入:seats =
[[“.”,“#”],
[“#”,“#”],
[“#”,“.”],
[“#”,“#”],
[“.”,“#”]]
输出:3
解释:让所有学生坐在可用的座位上。

  • 示例3:

输入:seats =
[[“#”,“.”,“.”,“.”,“#”],
[“.”,“#”,“.”,“#”,“.”],
[“.”,“.”,“#”,“.”,“.”],
[“.”,“#”,“.”,“#”,“.”],
[“#”,“.”,“.”,“.”,“#”]]
输出:10
解释:让学生坐在第 1、3 和 5 列的可用座位上。

提示:

  • seats 只包含字符 ‘.’ 和’#’
  • m == seats.length
  • n == seats[i].length
  • 1 <= m <= 8
  • 1 <= n <= 8

相关标签 :位运算、数组、动态规划、状态压缩

题解

今天的问题是一个较为复杂的动态规划问题,还是稍有难度的。

方法:动态规划

学生在选择座位时,必须满足四个指定的位置都没有人坐,而这四个位置,要不位于当前排,要不位于前一排。因此,某一排的座位上,学生可以选择的座位取决于上一排的落座情况。这提醒我们可以以排为单位来进行动态规划。同时,每一个座位,学生可以选择坐或者不坐,我们可以用一个长为 n n n 的二进制数字来表示某一排的落座情况,从低到高的第 j j j 位,如果为 1 1 1 则表示这一排的第 j j j 个位置有人落座,为 0 0 0 则表示无人落座。

构造函数 d p ( r o w , s t a t u s ) dp(row,status) dp(row,status),用来表示当第 r o w row row 排学生落座情况为 s t a t u s status status 时,第 r o w row row 排及其之前所有座位能够容纳最多的学生数。首先判断第 r o w row row 排的落座情况是否可能为 s t a t u s status status 时,我们可以构造一个函数 i s S i n g l e R o w C o m p l i a n t isSingleRowCompliant isSingleRowCompliant 来辅助判断,主要是判断是否有学生坐了坏的位置和是否有两个学生挨着坐。如果第 r o w row row 排的落座情况不可能为 s t a t u s status status ,返回一个极小的负值。接下来需要对前一排的落座情况进行遍历,即求出所有的 d p ( r o w ? 1 , u p p e r R o w S t a t u s ) dp(row?1,upperRowStatus) dp(row?1,upperRowStatus),并且在这相邻两排的落座情况不会产生作弊的情况下,求出最大的学生数后进行返回。

最后我们调用 d p dp dp ,求出最后一排所有状态下的最大学生数量。因为求解过程中会多次求解同一个状态,所以对动态规划进行记忆化的处理来降低时间复杂度。

实现代码(Python)
class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:

        def isSingleRowCompliant(status: int, row: int) -> bool:
            for j in range(n):
                if ((status >> j) & 1) == 1:
                    if seats[row][j] == '#':
                        return False
                    if j > 0 and ((status >> (j - 1)) & 1) == 1:
                        return False
            return True

        def isCrossRowsCompliant(status: int, upperRowStatus: int) -> bool:
            for j in range(n):
                if ((status >> j) & 1) == 1:
                    if j > 0 and ((upperRowStatus >> (j - 1)) & 1) == 1:
                        return False
                    if j < n - 1 and ((upperRowStatus >> (j + 1)) & 1) == 1:
                        return False
            return True

        @cache
        def dp(row: int, status: int) -> int:
            if not isSingleRowCompliant(status, row):
                return -inf
            students = bin(status).count('1')
            if row == 0:
                return students
            mx = 0
            for upperRowStatus in range(2 ** n):
                if isCrossRowsCompliant(status, upperRowStatus):
                    mx = max(mx, dp(row - 1, upperRowStatus))
            return students + mx

        m, n = len(seats), len(seats[0])
        mx = 0
        for i in range(2 ** n):
            mx = max(mx, dp(m - 1, i))
        return mx
复杂度分析:
  • 时间复杂度: O ( m × n × 2 2 n ) O(m×n×2 ^{2n}) O(m×n×22n), 状态数量共有 m × 2 n m×2^n m×2n种,计算一个状态需要消耗 O ( n × 2 n ) O(n×2^n) O(n×2n)的时间。可以通过预计算所有 i s C r o s s R o w s C o m p l i a n t isCrossRowsCompliant isCrossRowsCompliant 的结果来降低时间复杂度到 O ( ( m + n ) × 2 2 n ) ) O((m+n)×2^{2n})) O((m+n)×22n))
  • 空间复杂度: O ( n × 2 n ) O(n×2^n) O(n×2n)

题记:


  • 研究生在读,我会尽量保持LeetCode每日一题的思路和代码输出。希望大家多多支持。
  • 水平有限,希望各位大佬能够批评指正。您的教诲是我进步的船帆。
  • 希望各位跟我一样的小白能跟我一起参与到做题和讨论中来。共同进步是我所能期盼的最高愿想。
  • 您的点赞和关注是我坚持分享的动力泉源,希望能将这件简单平凡的事一直做下去。感谢大家。

文章来源:https://blog.csdn.net/weixin_52242569/article/details/135216784
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。