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

相关文章

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Springboot @Autowired和@Resource的区别解析

《Springboot@Autowired和@Resource的区别解析》@Resource是JDK提供的注解,只是Spring在实现上提供了这个注解的功能支持,本文给大家介绍Springboot@... 目录【一】定义【1】@Autowired【2】@Resource【二】区别【1】包含的属性不同【2】@

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

Elasticsearch 在 Java 中的使用教程

《Elasticsearch在Java中的使用教程》Elasticsearch是一个分布式搜索和分析引擎,基于ApacheLucene构建,能够实现实时数据的存储、搜索、和分析,它广泛应用于全文... 目录1. Elasticsearch 简介2. 环境准备2.1 安装 Elasticsearch2.2 J

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis