【LeetCode】每日一题 -- 1240. 铺瓷砖 -- Java Version

这篇具有很好参考价值的文章主要介绍了【LeetCode】每日一题 -- 1240. 铺瓷砖 -- Java Version。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目链接:https://leetcode.cn/problems/tiling-a-rectangle-with-the-fewest-squares/

1. 题解(1240. 铺瓷砖)

23.05.31 华为机试第二题

1.1 暴力深搜 – DFS

NP-Complete 问题

  • 题解参考:Java DFS暴力递归(详细注释)


题解思路

  1. 检查当前答案是否大于等于当前最佳答案,若是,则进行剪枝,回溯
  2. 检查正方形中是否有空位,若无空位,更新答案并回溯;
  3. 在查找到的第一个空位,进行填充,填充的规则是由大瓷砖到小瓷砖进行尝试(从小到大会导致运行时间大大增加);
    • 若尝试失败(部分位置可能已经被其它瓷砖占据),则更换成小瓷砖继续进行尝试。
    • 若尝试成功,则首先更新状态,并进行递归,同时在回溯时需要注意恢复状态。


下列代码还可参考官方题解进一步简化,如:

  • setStatus无需列出 x2,y2 的坐标,直接根据增量 k 进行循环遍历即可;
  • checkEmpty可省略,但省略后要确保在 dfs 的过程中是从左到右,从上到下顺序移动的;
class Solution {
    private int res; // 记录答案, 会在DFS过程中被更新
    private int row, col;
    public int tilingRectangle(int n, int m) {
        boolean[][] tiled = new boolean[n][m];
        res = Math.max(n, m);  // 初始赋值为最大值:即全为1的情况
        dfs(tiled, 0);
        return res;
    }
    
    // DFS:当前地上瓷砖状态为tiled,已经铺了count个瓷砖,继续铺下去把地面铺满
    private void dfs(boolean[][] tiled, int count) {
        if (count >= res) { // 剪枝
            return;
        }
        int[] emptyPos = checkEmpty(tiled); // 地上没瓷砖的第一个位置
        if (emptyPos[0] == -1 && emptyPos[1] == -1) { // 已经铺完了所有地方,收集答案
            res = Math.min(res, count);
            return;
        } 
        // 从大到小,开始尝试铺瓷砖
        int maxLen = Math.min(tiled.length - emptyPos[0], tiled[0].length - emptyPos[1]); 
        for (int len = maxLen; len >= 1; len--) {
            // 尝试用len*len的瓷砖的左上角去对齐地上没瓷砖的这个位置
            if (setStatus(tiled, emptyPos[0], emptyPos[1], emptyPos[0] + len - 1, emptyPos[1] + len - 1, false)) {
                dfs(tiled, count + 1);
                setStatus(tiled, emptyPos[0], emptyPos[1], emptyPos[0] + len - 1, emptyPos[1] + len - 1, true);
            } 
        }
    }

    // 尝试反转 (row1, col1) 和 (row2, col2) 之间的铺瓷砖状态
    // 必须确保这个区域内初始都是hasTiled状态,否则不会反转
    private boolean setStatus(boolean[][] tiled, int row1, int col1, int row2, int col2, boolean hasTiled) {
        for (int i = row1; i <= row2; i++) {
            for (int j = col1; j <= col2; j++) {
                if (tiled[i][j] != hasTiled) {
                    return false;
                }
            }
        }
        // 为什么不能将上下两个循环合在一起? 这是因为只要有一个瓷砖块的状态不满足就不能反转
        for (int i = row1; i <= row2; i++) {
            for (int j = col1; j <= col2; j++) {
                tiled[i][j] = !tiled[i][j];
            }
        }
        return true;
    }

    // 顺序遍历寻找第一个没铺瓷砖的位置(从上到下,从左到右)
    private int[] checkEmpty(boolean[][] tiled) {
        for (int i = 0; i < tiled.length; i++) {
            for (int j = 0; j < tiled[0].length; j++) {
                if (!tiled[i][j]) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }
}

【LeetCode】每日一题 -- 1240. 铺瓷砖 -- Java Version

2. 参考资料

[1] 铺瓷砖 – 官方题解
[2] Java DFS 暴力递归(详细注释)
[3] NP complete概念浅析文章来源地址https://www.toymoban.com/news/detail-476359.html

到了这里,关于【LeetCode】每日一题 -- 1240. 铺瓷砖 -- Java Version的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode每日一题44

    图论 dfs/bfs dfs代码框架 思路:本题要求找到被x围绕的陆地,所以边界的陆地O肯定不符合条件。那么我们只要从周边找到陆地O然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地O都变成A,然后再去重新遍历地图的时候,把剩下的O变成X,再把所有的A变成O。 确认递归函数,参数

    2024年01月19日
    浏览(45)
  • Leetcode每日一题——“移除元素”

    各位CSDN的uu们你们好呀,小雅兰又来啦,今天,小雅兰的内容是移除元素,下面,让我们进入Leetcode的世界吧   说明: 为什么返回数值是整数,但输出的答案是数组呢? 请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。 你可以

    2023年04月23日
    浏览(54)
  • 每日一题(LeetCode)----二分查找(一)

    给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 104 -104 = nums[i] = 104 nums 为 无重复元素 的 升序 排列数

    2024年02月08日
    浏览(50)
  • 每日一题:LeetCode-75. 颜色分类

    前言: 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈    🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉 算法 👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长

    2024年02月04日
    浏览(40)
  • 【每日一题】Leetcode - 283. 移动零

    Leetcode - 283. 移动零 从右向左遍历,遇到0,就将后面所有元素前移,同时更新长度,使其减1,因为移动n次,倒数n位就被0占据,后续操作可忽略 前面的操作,从右向左,每次遇到0移动都要跑半个数组,慢在整体前移; 换个思路,从左向右,记录首个0的位置,将后面的第一

    2024年02月11日
    浏览(44)
  • 【LeetCode每日一题】——566.重塑矩阵

    矩阵 简单 566.重塑矩阵 在 MATLAB 中,有一个非常有用的函数 reshape ,它可以将一个 m x n 矩阵重塑为另一个大小不同(r x c)的新矩阵,但保留其原始数据。 给你一个由二维数组 mat 表示的 m x n 矩阵,以及两个正整数 r 和 c ,分别表示想要的重构的矩阵的行数和列数。 重构后

    2024年02月14日
    浏览(46)
  • 每日一题:leetcode 57 插入区间

    给你一个  无重叠的  , 按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 示例 2: 示例 3: 示例 4: 示例 5: 提示: 0 = intervals.length = 104 intervals[i].length == 2 0 = int

    2024年02月11日
    浏览(45)
  • 【LeetCode每日一题】——575.分糖果

    哈希表 简单 575.分糖果 Alice 有 n 枚糖,其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长,所以前去拜访了一位医生。 医生建议 Alice 要少摄入糖分,只吃掉她所有糖的 n / 2 即可(n 是一个偶数)。Alice 非常喜欢这些糖,她想要在遵循医生建议的情况下,尽可

    2024年02月13日
    浏览(75)
  • 【LeetCode每日一题】——85.最大矩形

    矩阵 困难 85.最大矩形 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例 1: 输入:matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“

    2024年02月13日
    浏览(41)
  • 【LeetCode】每日一题:移除元素

    目录  题目: 思想1:暴力解法 思想2:创建一个temp数组  思想3:双指针 👻内容专栏:《LeetCode刷题专栏》 🐨本文概括: 27.移除元素 🐼本文作者:花 碟 🐸发布时间:2023.4.15 https://leetcode.cn/problems/remove-element/   点击跳转到LeetCode平台OJ页面(27.移除元素)  👉 示例1: 解

    2023年04月19日
    浏览(73)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包