javascript 解法, 执行用时: 72 ms, 内存消耗: 43.4 MB, 提交时间: 2023-12-26 09:22:41

/**
 * @param {character[][]} seats
 * @return {number}
 */
var maxStudents = function(seats) {
    const m = seats.length, n = seats[0].length;
    const memo = new Map();

    const isSingleRowCompliant = function(status, row) {
        for (let j = 0; j < n; j++) {
            if ((status >> j) & 1) {
                if (seats[row][j] == '#') {
                    return false;
                }
                if (j > 0 && ((status >> (j - 1)) & 1)) {
                    return false;
                }
            }
        }
        return true;
    };
    
    const isCrossRowsCompliant = function(status, upperRowStatus) {
        for (let j = 0; j < n; j++) {
            if ((status >> j) & 1) {
                if (j > 0 && ((upperRowStatus >> (j - 1)) & 1)) {
                    return false;
                }
                if (j < n - 1 && ((upperRowStatus >> (j + 1)) & 1)) {
                    return false;
                }
            }
        }
        return true;
    };

    // 当第row排学生状态为status时，第row排及之前排最多能坐的学生数量
    const dp = function(row, status) {
        const key = (row << n) + status;
        if (!memo.has(key)) {
            if (!isSingleRowCompliant(status, row)) {
                memo.set(key, -Infinity);
                return -Infinity;
            }
            let students = bitCount(status);
            if (row == 0) {
                memo.set(key, students);
                return students;
            }
            let mx = 0;
            for (let upperRowStatus = 0; upperRowStatus < 1 << n; upperRowStatus++) {
                if (isCrossRowsCompliant(status, upperRowStatus)) {
                    mx = Math.max(mx, dp(row - 1, upperRowStatus));
                }
            }
            memo.set(key, students + mx);
        }
        return memo.get(key);
    };
    
    let mx = 0;
    for (let i = 0; i < (1 << n); i++) {
        mx = Math.max(mx, dp(m - 1, i));
    }
    return mx;
};

var bitCount = function(num) {
    let bits = num;
    bits = bits - ((bits >> 1) & 0x55555555);
    bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
    bits = (bits + (bits >> 4)) & 0x0f0f0f0f;
    bits = (bits + (bits >> 8)) & 0x00ff00ff;
    bits = (bits + (bits >> 16)) & 0x0000ffff;
    return bits;
}

java 解法, 执行用时: 1 ms, 内存消耗: 39.1 MB, 提交时间: 2023-10-12 09:56:56

class Solution {
    public int maxStudents(char[][] seats) {
        int n = seats.length;
        int[] arr = new int[n];
        //组成二进制数组
        for(int i = 0; i < n; i++){
            char[] seat = seats[i]; // 遍历行
            int v = 0;
            for(char c:seat){  // 遍历列
                int curr = c == '.' ? 1: 0;
                v = v*2 + curr;
            }
            arr[i] = v;
        }

        //记忆化数组，index+前一元素状态
        for(int i = 0; i < 8; i++) Arrays.fill(dp[i],-1);

        return dfs(arr,0,0);
    }
    
    int[][] dp = new int[8][256];

    private int dfs(int[]list,int index,int preVal){
        if(index==list.length) return 0;

        if(dp[index][preVal]!=-1) return dp[index][preVal];
        int ans = 0;
        int v = list[index];
        //枚举子集
        for(int i=v;i>0;i=v&(i-1)){
            //和本行两侧不连着，和上一行两侧不连着
            if((i&(i>>1))==0 && (preVal&(i<<1))==0 && (preVal&(i>>1))==0){
                ans = Math.max(dfs(list,index+1,i)+Integer.bitCount(i),ans);
            }
        }
        ans = Math.max(ans,dfs(list,index+1,0));
        dp[index][preVal] = ans;
        return ans;
    }
}

java 解法, 执行用时: 1 ms, 内存消耗: 38.8 MB, 提交时间: 2023-10-12 09:52:55

class Solution {
    private int M;//座位行数
    private int N;//每行座位数
    private int[] initStatusOfRows;//初始时，各行座位的状态

    public int maxStudents(char[][] seats) {
        M = seats.length;
        N = seats[0].length;//每行座位数
        initStatusOfRows = compress(seats);//初始时，各行座位的状态
        int[][] cache = new int[M][(1 << N)];
        for (int[] row : cache) Arrays.fill(row, -1);
        return dfsProcess(0, initStatusOfRows[0], cache);//第0行座位状态总是等于初始状态
    }

    /**
     * 按行尝试在座位上填充学生，求当前行座位状态为statusOfCurRow的情况下，在第rowNum~M-1行上最多安排多少学生
     *
     * @param rowNum         当前考察到的座位行号
     * @param statusOfCurRow 当前行的座位状态，第0~N-1 bit位上如果是1，表示该位置可以坐人；当前行状态是由该行初始状态和上一行学生分布状态决定的
     * @param cache          记忆化搜索的缓存数组 rowNum:0~M-1  statusOfCurRow:0~((1<<N)-1)
     * @return
     */
    private int dfsProcess(int rowNum, int statusOfCurRow, int[][] cache) {
        if (cache[rowNum][statusOfCurRow] != -1) return cache[rowNum][statusOfCurRow];
        int res = 0;//返回值
        //穷举当前行学生所有可能的分布状态
        int limit = (1 << N);
        for (int studentOfCurRow = 0; studentOfCurRow < limit; ++studentOfCurRow) {//StudentOfCurRow表示当前行学生分布状态，某个bit为1表示该位置有学生坐
            //当前行学生分布首先不能与当前行座位分布冲突（不能坐到不可以坐的位置），
            //这意味着在0~N-1 bit范围上，如果statusOfCurRow在该bit为0，StudentOfCurRow在该bit只能为0
            if (((~statusOfCurRow) & studentOfCurRow) != 0) continue;
            //当前行学生分布，任意两学生之间不能相邻
            if ((studentOfCurRow & (studentOfCurRow >> 1)) != 0) continue;
            int count = 0;//统计人数
            for (int i = 0; i < N; i++) {
                count += (studentOfCurRow >> i) & 1;
            }
            if (rowNum < M - 1) {//如果当前行不是最后一行(这个代码块也是隐含的递归出口)
                //求下一行座位状态
                int statusOfNextRow = initStatusOfRows[rowNum + 1];
                //由于本行的学生分布studentOfCurRow会影响下一行，具体来说：(studentOfCurRow>>1)或者(studentOfCurRow<<1)哪个bit位为1，
                //那么statusOfNextRow的该bit位必须为0
                statusOfNextRow &= (~(studentOfCurRow >> 1));
                statusOfNextRow &= (~(studentOfCurRow << 1));
                count += dfsProcess(rowNum + 1, statusOfNextRow, cache);
            }
            res = Math.max(res, count);
        }
        cache[rowNum][statusOfCurRow] = res;
        return res;
    }

    //计算初始时，各行座位的状态
    private int[] compress(char[][] seats) {
        int[] res = new int[M];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                res[i] |= seats[i][j] == '.' ? (1 << j) : 0;
            }
        }
        return res;
    }
}

cpp 解法, 执行用时: 4 ms, 内存消耗: 7.5 MB, 提交时间: 2023-10-12 09:50:16

class Solution {
    int memory[8][1 << 8];
    vector<int> compressed_seats;
    int f(int X, int row_num, int width) {
        if (memory[row_num][X] != -1)
            return memory[row_num][X];
        int ans = 0;
        for (int scheme = 0; scheme != (1 << width); ++scheme) {
            if (scheme & ~X || scheme & (scheme << 1))
                continue;
            int curans = 0;
            for (int j = 0; j != width; ++j)
                if ((1 << j) & scheme)
                    ++curans;
            if (row_num == compressed_seats.size() - 1)
                ans = max(ans, curans);
            else {
                int next_seats = compressed_seats[row_num + 1];
                next_seats &= ~(scheme << 1);
                next_seats &= ~(scheme >> 1);
                ans = max(ans, curans + f(next_seats, row_num + 1, width));
            }
        }
        memory[row_num][X] = ans;
        return ans;
    }
    
    int compress(vector<char>& row) {
        int ans = 0;
        for (char c : row) {
            ans <<= 1;
            if (c == '.')
                ++ans;
        }
        return ans;
    }

public:
    int maxStudents(vector<vector<char>>& seats) {
        for (int i = 0; i != seats.size(); ++i)
            for (int j = 0; j != (1 << seats[0].size()); ++j)
                memory[i][j] = -1;
        for (auto row: seats)
            compressed_seats.push_back(compress(row));
        return f(compressed_seats[0], 0, seats[0].size());
    }
};

python3 解法, 执行用时: 88 ms, 内存消耗: 16.1 MB, 提交时间: 2023-10-12 09:49:58

'''
记忆化搜索 + 状态压缩dp
'''

import functools

class Solution:
    @functools.lru_cache(8 * 2 ** 8)
    def f(self, X: List[str], row_num: int, width: int) -> int:
        ans = 0
        for scheme in range(1 << width):
            if scheme & ~X or scheme & (scheme << 1):
                continue
            curans = 0
            for j in range(8):
                if (1 << j) & scheme:
                    curans += 1
            if row_num == len(self.seats) - 1:
                ans = max(ans, curans)
            else:
                next_seats = self.seats[row_num + 1]
                next_seats &= ~(scheme << 1)
                next_seats &= ~(scheme >> 1)
                ans = max(ans, curans + self.f(next_seats, row_num + 1, width))
        return ans

    def compress(self, row: List[str]) -> int:
        ans = 0
        for c in row:
            ans <<= 1
            if c == '.':
                ans += 1
        return ans

    def maxStudents(self, seats: List[List[str]]) -> int:
        self.seats = [self.compress(row) for row in seats]
        return self.f(self.seats[0], 0, len(seats[0]))

cpp 解法, 执行用时: 12 ms, 内存消耗: 8 MB, 提交时间: 2023-10-12 09:46:49

class Solution {
public:
    int maxStudents(vector<vector<char>>& seats) {
        int m=seats.size();
    int n=seats[0].size();
    vector<vector<int>> dp(m+1,vector<int>(1<<n));  //初始化

    for(int row=1;row<=m;row++){
        for(int s=0;s<(1<<n);s++){//遍历 2^n 个状态
            bitset<8> bs(s);//记录对应状态的bit位
            bool ok=true;
            for(int j=0;j<n;j++){
                if((bs[j] && seats[row-1][j]=='#') || (j<n-1 && bs[j] && bs[j+1])){//不能坐在坏椅子上也不能在同一行相邻坐
                    ok=false;
                    break;
                }
            }
            if(!ok){
                dp[row][s]=-1;//说明坐在坏椅子上或相邻坐了，该状态舍弃
                continue;
            }
            for(int last=0;last<(1<<n);last++){//找到一种当前行的可行状态后，遍历上一行的所有状态
                if(dp[row-1][last]==-1)//上一行的状态被舍弃了，那就直接下一个状态
                    continue;
                bitset<8> lbs(last);
                bool flag=true;
                for(int j=0;j<n;j++){
                    if(lbs[j] && ((j>0 && bs[j-1]) || (j<n-1 && bs[j+1]))){//如果找到的这个上一行状态的j位置坐了人，
                        flag=false;                                    //下一行的j+1位置或j-1位置也坐了人，那么该状态不合法，舍弃
                        break;
                    }
                }
                if(flag){//flag为真说明这个last状态的每个位置都合法
                    dp[row][s]=max(dp[row][s],dp[row-1][last]+(int)bs.count());//转移方程
                }
            }

        }
    }
    int res=0;
    for(int i=0;i<(1<<n);i++){//在最后一行的所有状态中找出最大的
        if(dp[m][i]>res){
            res=dp[m][i];
        }
    }
    return res;
    }
};

python3 解法, 执行用时: 120 ms, 内存消耗: 15.8 MB, 提交时间: 2023-10-12 09:46:11

'''
状态压缩dp
dp[i][j] 表示第i行的座位分布为j时，前i行可容纳最多学生人数
'''
from functools import reduce
class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        m, n = len(seats), len(seats[0]),
        dp = [[0]*(1 << n) for _ in range(m+1)]  # 状态数组 dp
        # 将 # 设为 1，当遇到 . 时与运算结果为 0，表示可以坐人
        a = [reduce(lambda x,y:x|1<<y,[0]+[j for j in range(n) if seats[i][j]=='#'])  for i in range(m)] 
        # print(a)
        for row in range(m)[::-1]: # 倒着遍历
            for j in range(1 << n):
                # j & a[row]代表该位置可以坐人，j & j<<1 and not j&j>>1 表示该位置左右没人可以坐的
                if not j & j<<1 and not j&j>>1 and not j & a[row]:
                    for k in range(1 << n):
                        if not j&k<<1 and not j&k>>1: # j状态的左上和右上没有人
                            dp[row][j] = max(dp[row][j], dp[row+1][k] + bin(j).count('1'))
        # print(dp)
        return max(dp[0])

golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-10-12 09:36:27

func maxStudents(seats [][]byte) (ans int) {
	m, n := len(seats), len(seats[0])
	mm := 1 << uint(n)
	ss, f := make([]int, m+1), make([]int, mm)
	ss[0] = 0
	for i := range seats {
		for j := range seats[i] {
			if seats[i][j] == '.' {
				ss[i+1] |= 1 << uint(j)
			}
		}
	}
	preMax := 0
	for i := 1; i <= m; i++ {
		ff := make([]int, mm)
		for mask := 0; mask < mm; mask++ {
			ff[mask] = preMax
			curMax := 0
			if mask&ss[i] == mask && mask<<1&mask == 0 {
				preMask := (mask<<1 ^ ss[i-1]) & (ss[i-1] ^ mask>>1)
				curCnt := bits.OnesCount(uint(mask))
				curMax = max(curMax, f[preMask])
				for sub := preMask; sub > 0; sub = (sub - 1) & preMask {
					curMax = max(curMax, f[sub])
				}
				ff[mask] = max(ff[mask], curMax+curCnt)
			}
			ans = max(ans, ff[mask])
		}
		preMax = ans
		f = ff
	}

	return
}

func max(a, b int) int { if a > b { return a }; return b }

golang 解法, 执行用时: 0 ms, 内存消耗: 2.6 MB, 提交时间: 2023-10-12 09:35:32

func maxStudents(seats [][]byte) int {
	var (
		// 某一行中处于 state i 时，可以坐 stateCount[i] 个学生
		stateCount = make([]int, 256)
		//  前 i 排在第 i 排处于 state j 时可以坐 lineStateCount[i][j] 个学生
		lineStateCount = make([][]int, 9)
		badSeats       = make([]int, 9)
		lenX           = len(seats)
		lenY           = len(seats[0])
		i, j, k        int
		ans            = 0
	)
	for i = 1; i < 256; i++ {
		stateCount[i] = stateCount[i>>1] + (i & 1)
	}
	for i = 0; i <= lenX; i++ {
		lineStateCount[i] = make([]int, 256)
	}
	for i = 0; i < lenX; i++ {
		badSeats[i] = 0
		for j = 0; j < lenY; j++ {
			if seats[i][j] == '#' {
				badSeats[i] |= 1 << j
			}
		}
	}
	lineStateCount[0][0] = 0
	for i = 0; i < lenX; i++ {
		// 对于第 i 排的 state j 作判断
		for j = 0; j < 1<<lenY; j++ {
			// 没有坏座位： j&badSeats[i] == 0
			// 对于每个坐了人的座位，左右都没有人：j&j>>1 == 0 && j&j<<1 == 0
			if j&badSeats[i] == 0 && j&(j>>1) == 0 && j&(j<<1) == 0 {
				for k = 0; k < 1<<lenY; k++ {
					// 对于每个坐了人的座位，左前和右前都没有人
					if j&(k>>1) == 0 && j&(k<<1) == 0 {
						// stateCount[j]：状态 j 下可以这一排可以坐多少人
						lineStateCount[i+1][j] = max(lineStateCount[i+1][j], lineStateCount[i][k]+stateCount[j])
					}
				}
			}
		}
	}
	for i = 0; i < 1<<lenY; i++ {
		ans = max(ans, lineStateCount[lenX][i])
	}
	return ans
}

func max(a, b int) int { if a > b { return a }; return b }