Leetcode 1349. 参加考试的最大学生数(Java + 按行状压暴力 + DP)

2023-12-26 06:45

本文主要是介绍Leetcode 1349. 参加考试的最大学生数(Java + 按行状压暴力 + DP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 题目
  • 思路
    • Java + 按行状压暴力 + DP:
    • 第 1 步:
    • 第 2 步:
    • 第 3 步:
    • 第 4 步:
  • 复杂度
  • Code

题目

  • Problem: 1349. 参加考试的最大学生数
  • 给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的(不可用),就用 ‘#’ 表示;否则,用 ‘.’ 表示。
  • 学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷,但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的同时参加考试且无法作弊的 最大 学生人数。
  • 学生必须坐在状况良好的座位上。
  • seats 只包含字符 ‘.’ 和’#’
  • m == seats.length
  • n == seats[i].length
  • 1 <= m <= 8
  • 1 <= n <= 8

思路

Java + 按行状压暴力 + DP:

第 1 步:

  • 首先思考每个好座位选或不选的 DFS 暴力求解,会超时
  • 其次分析题意可知,仅有相邻两行之间有限制,
  • 因此可以想到将行拆开,仅每一行去暴力所有可能,使用 DP 判断相邻两行的限制即可

第 2 步:

  • 每行暴力:
  • 每行遍历从 0 到 (2 ^ n) - 1 的数字 seat,seat 转化为二进制、1 代表有人,
  • isRowUsableSeat 行内满足要求:遍历每个 1 相邻左侧没有 1 且 每个 1 均是好座位,
  • 此 seat 代表该行内部满足条件,

第 3 步:

  • DP 判断两行的限制:
  • 定义状态:dp[i][seat] 代表前 i 行中,第 i 行座位为 seat 时的最大学生数
  • 初始化:dp[0][isRowUsableSeat(seat)] = countOne(seat)(seat 中 1 个个数),代表第一行没有限制
  • 状态转移方程:
    • dp[i][isRowUsableSeat(seat)] = countOne(seat) + max(isCrossUsableSeat(0, seat)?dp[i-1][0]):0 , … , isCrossUsableSeat((2 ^ n) - 1, seat)?dp[i-1][(2 ^ n) - 1]:0)
  • 其中 isCrossUsableSeat(seat1, seat2) 代表两行(seat1-上一行、seat2-下一行)是否满足要求,即 seat2 每个 1 的下标 col、在 seat1 中 col-1 与 col+1 都不存在 1

第 4 步:

  • 预处理所有 isCrossUsableSeat,
  • 由于 i 仅与 i-1 相关,因此使用滚动数组即可

复杂度

时间复杂度:

时间复杂度: O ( ( m + n ) ∗ 2 2 n ) O((m + n) * 2 ^ {2n}) O((m+n)22n)

空间复杂度:

空间复杂度: O ( n ∗ 2 2 n ) O(n * 2 ^ {2n}) O(n22n)

Code

class Solution {/*** Java + 按行状压暴力 + DP:** 第 1 步:* 首先思考每个好座位选或不选的 DFS 暴力求解,会超时* 其次分析题意可知,仅有相邻两行之间有限制,* 因此可以想到将行拆开,仅每一行去暴力所有可能,使用 DP 判断相邻两行的限制即可** 第 2 步:* 每行暴力:* 每行遍历从 0 到 (2 ^ n) - 1 的数字 seat,seat 转化为二进制、1 代表有人,* isRowUsableSeat 行内满足要求:遍历每个 1 相邻左侧没有 1 且 每个 1 均是好座位,* 此 seat 代表该行内部满足条件,** 第 3 步:* DP 判断两行的限制:* 定义状态:dp[i][seat] 代表前 i 行中,第 i 行座位为 seat 时的最大学生数* 初始化:dp[0][isRowUsableSeat(seat)] = countOne(seat)(seat 中 1 个个数),代表第一行没有限制* 状态转移方程:dp[i][isRowUsableSeat(seat)] = countOne(seat) * + max(isCrossUsableSeat(0, seat)?dp[i-1][0]):0 , ... , isCrossUsableSeat((2 ^ n) - 1, seat)?dp[i-1][(2 ^ n) - 1]:0)* 其中 isCrossUsableSeat(seat1, seat2) 代表两行(seat1-上一行、seat2-下一行)是否满足要求,即 seat2 每个 1 的下标 col、在 seat1 中 col-1 与 col+1 都不存在 1** 第 4 步:* 预处理所有 isCrossUsableSeat,* 由于 i 仅与 i-1 相关,因此使用滚动数组即可* 时间复杂度:O((m + n) * 2 ^ 2n),空间复杂度:O(n * 2 ^ 2n)**/public int maxStudents(char[][] seats) {int m = seats.length;int n = seats[0].length;int seatTotal = 1 << n;// 预处理所有 isCrossUsableSeatboolean[][] crossUsableSeat = preCrossUsableSeat(seatTotal);int[][] dp = new int[2][seatTotal];// 初始化for (int j = 0; j < seatTotal; j++) {// 第 0 行满足 isRowUsableSeatif (isRowUsableSeat(seats[0], j)) {dp[0][j] = countOne(j);}}// 状态转移方程:dp[i][isRowUsableSeat(seat)] = countOne(seat) // + max(isCrossUsableSeat(0, seat)?dp[i-1][0]):0 , ... , isCrossUsableSeat((2 ^ n) - 1, seat)?dp[i-1][(2 ^ n) - 1]:0)for (int i = 1; i < m; i++) {for (int j = 0; j < seatTotal; j++) {// 第 i 行内满足条件if (isRowUsableSeat(seats[i], j)) {int countOneJ = countOne(j);for (int k = 0; k < seatTotal; k++) {// 第 i 行与 i-1 行满足条件if (crossUsableSeat[j][k]) {dp[i & 1][j] = Math.max(dp[i & 1][j], dp[(i - 1) & 1][k] + countOneJ);}}}}}int res = 0;for (int j = 0; j < seatTotal; j++) {res = Math.max(res, dp[(m - 1) & 1][j]);}return res;}/*** 遍历每个 1:相邻左侧没有 1 且 每个 1 均是好座位*/private boolean isRowUsableSeat(char[] seats, int seat) {for (int i = 0; (1 << i) <= seat; i++) {if (((1 << i) & seat) > 0) {if (seats[i] == '#' || ((1 << i + 1) & seat) > 0) {return false;}}}return true;}/*** 预处理所有 isCrossUsableSeat,*/private boolean[][] preCrossUsableSeat(int seatTotal) {boolean[][] crossUsableSeat = new boolean[seatTotal][seatTotal];// seat2 每个 1 的下标 col、在 seat1 中 col-1 与 col+1 都不存在 1for (int seat1 = 0; seat1 < seatTotal; seat1++) {for (int seat2 = 0; seat2 < seatTotal; seat2++) {if (isCrossUsableSeat(seat1, seat2)) {crossUsableSeat[seat1][seat2] = true;}}}return crossUsableSeat;}private boolean isCrossUsableSeat(int seat1, int seat2) {for (int bitNum = (seat2 & -seat2); bitNum > 0; bitNum = (seat2 & -seat2)) {if ((bitNum != 1 && (seat1 & (bitNum >> 1)) > 0) || ((seat1 & (bitNum << 1)) > 0)) {return false;}seat2 -= bitNum;}return true;}/*** 二进制 1 的个数*/private int countOne(int seat) {int res = 0;while (seat > 0) {seat &= seat - 1;res++;}return res;}
}

这篇关于Leetcode 1349. 参加考试的最大学生数(Java + 按行状压暴力 + DP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/538444

相关文章

idea maven编译报错Java heap space的解决方法

《ideamaven编译报错Javaheapspace的解决方法》这篇文章主要为大家详细介绍了ideamaven编译报错Javaheapspace的相关解决方法,文中的示例代码讲解详细,感兴趣的... 目录1.增加 Maven 编译的堆内存2. 增加 IntelliJ IDEA 的堆内存3. 优化 Mave

Java String字符串的常用使用方法

《JavaString字符串的常用使用方法》String是JDK提供的一个类,是引用类型,并不是基本的数据类型,String用于字符串操作,在之前学习c语言的时候,对于一些字符串,会初始化字符数组表... 目录一、什么是String二、如何定义一个String1. 用双引号定义2. 通过构造函数定义三、St

springboot filter实现请求响应全链路拦截

《springbootfilter实现请求响应全链路拦截》这篇文章主要为大家详细介绍了SpringBoot如何结合Filter同时拦截请求和响应,从而实现​​日志采集自动化,感兴趣的小伙伴可以跟随小... 目录一、为什么你需要这个过滤器?​​​二、核心实现:一个Filter搞定双向数据流​​​​三、完整代码

SpringBoot利用@Validated注解优雅实现参数校验

《SpringBoot利用@Validated注解优雅实现参数校验》在开发Web应用时,用户输入的合法性校验是保障系统稳定性的基础,​SpringBoot的@Validated注解提供了一种更优雅的解... 目录​一、为什么需要参数校验二、Validated 的核心用法​1. 基础校验2. php分组校验3

Java Predicate接口定义详解

《JavaPredicate接口定义详解》Predicate是Java中的一个函数式接口,它代表一个判断逻辑,接收一个输入参数,返回一个布尔值,:本文主要介绍JavaPredicate接口的定义... 目录Java Predicate接口Java lamda表达式 Predicate<T>、BiFuncti

Spring Security基于数据库的ABAC属性权限模型实战开发教程

《SpringSecurity基于数据库的ABAC属性权限模型实战开发教程》:本文主要介绍SpringSecurity基于数据库的ABAC属性权限模型实战开发教程,本文给大家介绍的非常详细,对大... 目录1. 前言2. 权限决策依据RBACABAC综合对比3. 数据库表结构说明4. 实战开始5. MyBA

Spring Security方法级安全控制@PreAuthorize注解的灵活运用小结

《SpringSecurity方法级安全控制@PreAuthorize注解的灵活运用小结》本文将带着大家讲解@PreAuthorize注解的核心原理、SpEL表达式机制,并通过的示例代码演示如... 目录1. 前言2. @PreAuthorize 注解简介3. @PreAuthorize 核心原理解析拦截与

一文详解JavaScript中的fetch方法

《一文详解JavaScript中的fetch方法》fetch函数是一个用于在JavaScript中执行HTTP请求的现代API,它提供了一种更简洁、更强大的方式来处理网络请求,:本文主要介绍Jav... 目录前言什么是 fetch 方法基本语法简单的 GET 请求示例代码解释发送 POST 请求示例代码解释

Java图片压缩三种高效压缩方案详细解析

《Java图片压缩三种高效压缩方案详细解析》图片压缩通常涉及减少图片的尺寸缩放、调整图片的质量(针对JPEG、PNG等)、使用特定的算法来减少图片的数据量等,:本文主要介绍Java图片压缩三种高效... 目录一、基于OpenCV的智能尺寸压缩技术亮点:适用场景:二、JPEG质量参数压缩关键技术:压缩效果对比

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++