我的博客

Leetcode 5335. 参加考试的最大学生数 maximum students taking exam

目录
  1. 状态压缩 dp
    1. 解题思路
    2. 代码
  2. 超时代码

https://leetcode-cn.com/contest/weekly-contest-175/problems/maximum-students-taking-exam/

直接搜索会超时(附超时代码)

可以使用状态压缩 dp

状态压缩 dp

解题思路

seat_map 用一个整数表示一行的状态

line_state 标识任意一行所有可行的座位安排(其实就是没有相邻的)因为单就一行来看,只要没人相邻就 ok

line_state 中任意一个和 seat_map 的任意一行做按位与,看是否变化,就可以知道这一行是否可以这么座(是否会坐到坏座位)

两行之间的是否合法,就是一行右移、左移再和另一行按位与。

本思路参考了排行榜上 leoGW 的代码,思路一致,但是重写了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
def maxStudents(self, seats: List[List[str]]) -> int:
n = len(seats)
m = len(seats[0])
dp = [[-1] *(1<<m) for i in range(n)]
seat_map = [0] * n # 每个整数代表一行的座位,整数每个二进制位为 0 代表座位不能用, 1 代表能用
for i, l in enumerate(seats):
for ch in l:
if ch == ".":
seat_map[i] = (seat_map[i] << 1) + 1 # 1 代表当前座位可用
else:
seat_map[i] = (seat_map[i] << 1) + 0 # 0 代表当前座位不可用

line_state = []
num = []
for i in range(1<<m):
x = 3 # 3 的二进制是 011,表示有两个座位挨着的情况
f = True
for j in range(m):
if i & x == x: # 有相邻座位
f = False
break
x <<= 1
if not f: continue
line_state.append(i)
num.append(str(bin(i)).count('1'))
if i & seat_map[0] == i:
dp[0][i] = num[-1]
print(line_state)
print(num)
for i in range(1, n):
for j, jn in zip(line_state, num):
if j & seat_map[i] == j:
for k in line_state:
if ((j << 1) & k ==0 ) and ((j >> 1) & k == 0): # 两行没有斜对角的人
dp[i][j] = max(dp[i-1][k] + jn, dp[i][j])
return max(dp[n-1])

超时代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
cnt = 0
class Solution:
def maxStudents(self, seats: List[List[str]]) -> int:
global cnt, mcnt
n = len(seats)
m = len(seats[0])
mp = [[0] * m for i in range(n)]
# for i in range(n):
# for j in range(m):
# if seats[i][j] == '#':
# mp[i]
cnt = 0
mcnt = 0
#print(n, m)
def dfs(i, j):
global cnt, mcnt
#print(i, j)
if i == n:
mcnt = max(mcnt, cnt)
return
ni, nj = i, j + 1
if nj == m: ni, nj = i+1, 0
if seats[i][j] == '.':
if mp[i][j] == 0:
cnt += 1
mp[i][j] += 100
if j - 1 >= 0:
if i - 1 >= 0:
mp[i-1][j-1] += 1
if i + 1 < n:
mp[i+1][j-1] += 1
mp[i][j-1] += 1
if j + 1 < m:
if i - 1 >= 0:
mp[i-1][j+1] += 1
if i + 1 < n:
mp[i+1][j+1] += 1
mp[i][j+1] += 1

dfs(ni, nj)
cnt -= 1
mp[i][j] -= 100
if j - 1 >= 0:
if i - 1 >= 0:
mp[i-1][j-1] -= 1
if i + 1 < n:
mp[i+1][j-1] -= 1
mp[i][j-1] -= 1
if j + 1 < m:
if i - 1 >= 0:
mp[i-1][j+1] -= 1
if i + 1 < n:
mp[i+1][j+1] -= 1
mp[i][j+1] -= 1
dfs(ni, nj)
dfs(0, 0)
return mcnt

评论无需登录,可以匿名,欢迎评论!