Leetcode 2023-12-26 题目分享

参加考试的最大学生数

给你一个 m * n 的矩阵 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

思路

首先是图上的搜索问题，结合数据量，完全可以 DFS+记忆化搜索解决。
但这个问题本质上是“选和不选”：‘1’代表选择这个座位，‘0’代表不选。所以很自然想到状态压缩+DP。
对每一行数据进行处理，枚举所有可能的情况：
- 判断这一行是否有效：检查每个‘1’左右是否都为‘0‘
- 枚举前一行的所有情况，判断是否有效：检查当前行每个‘1’的前一行左右是否都为‘0’
  - 有效则可以更新 DP 数组

代码

class Solution {
public:
    int maxStudents(vector<vector<char>>& seats) {
        int n = seats.size(), m = seats[0].size(), INF = -1e9;
        // 判断当前行是否有效
        function<bool(int,vector<char>)> ckrow = [&](int st, vector<char> g){
            for (int j = 0;j < m;j++){
                // 选择第j个座位 但该座位是坏的 或 右边已经有人了
                if ((st>>j&1)==1 && (g[j]=='#' || (j>0&&st>>(j-1)&1)==1)){
                    return false;
                }
            }
            return true;
        };
        // 判断当前行和上一行合在一起是否有效
        function<bool(int,int)> ckpre = [&](int cur, int pre){
            for (int k = 0;k < m;k++){
                int x = cur>>k&1; // 当前行第k个座位状态
                int y = k==0?0:pre>>(k-1)&1; // 前一行第k-1座位状态
                int z = k==m-1?0:pre>>(k+1)&1; // 前一行第k+1座位状态
                // x有人坐 但y或z也已经有人坐了
                if (x==1 && (y==1 || z==1)){
                    return false;
                }
            }
            return true;
        };
        vector<int> pre(1 << m, 0);
        for (int i = 0;i < n;i++){
            vector<char> g = seats[i];
            vector<int> cur(1 << m, INF), cnt(1 << m);
            // 枚举当前行所有状态
            for (int st = 0;st < (1<<m);st++){
                if (!ckrow(st, g)) continue;
                for (int j = 0;j < m;j++) if (st>>j&1) cnt[st]++;
                // 枚举前一行所有状态
                for (int j = 0;j < (1<<m);j++){
                    if (pre[j] == INF || !ckpre(st, j)) continue;
                    cur[st] = max(cur[st], pre[j]+cnt[st]);
                }
            }
            pre = cur;
        }
        return *max_element(pre.begin(), pre.end());
    }
};

复杂度分析

时间：O( n * 2^m * (m + 2^m) = n * 4^m )。
空间：O( 2^m )。

类似记得蓝桥杯也很喜欢出这种题

贴一个以前的蓝桥杯真题，也是 DP+状态压缩：玉米田