专栏首页小浩算法《剑指offer》第11天:矩形覆盖

《剑指offer》第11天:矩形覆盖

矩形覆盖

题目描述

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

解法

覆盖 2*n 的矩形:

  • 可以先覆盖 2*n-1 的矩形,再覆盖一个 2*1 的矩形;
  • 也可以先覆盖 2*(n-2) 的矩形,再覆盖两个 1*2 的矩形。

解法一:利用数组存放结果

public class Solution {
    /**
     * 矩形覆盖
     * @param target 2*target大小的矩形
     * @return 多少种覆盖方法
     */
    public int RectCover(int target) {
        if (target < 3) {
            return target;
        }
        int[] res = new int[target + 1];
        res[1] = 1;
        res[2] = 2;
        for (int i = 3; i <= target; ++i) {
            res[i] = res[i - 1] + res[i - 2];
        }
        return res[target];
    }
}

解法二:直接用变量存储结果

public class Solution {
    /**
     * 矩形覆盖
     * @param target 2*target大小的矩形
     * @return 多少种覆盖方法
     */
    public int RectCover(int target) {
        if (target < 3) {
            return target;
        }
        int res1 = 1;
        int res2 = 2;
        int res = 0;
        for (int i = 3; i <= target; ++i) {
            res = res1 + res2;
            res1 = res2;
            res2 = res;
        }
        return res;
    }
}

测试用例

  1. 功能测试(如输入 3、5、10 等);
  2. 边界值测试(如输入 0、1、2);
  3. 性能测试(输入较大的数字,如 40、50、100 等)。

内容展示:

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员小浩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:滑动窗口入门题目,没有之一

    今天是小浩算法“365刷题计划”第83天 。昨天写了一篇感悟,没想到那么受欢迎。几百人转发,好几千人阅读,虚荣心得到了极大的满足。今天继续为大家分享一道经典面试...

    程序员小浩
  • 漫画:二叉树系列 第二讲(层次遍历与BFS)

    在上一节中,我们通过例题学习了二叉树的DFS(深度优先搜索),其实就是沿着一个方向一直向下遍历。那我们可不可以按照高度一层一层的访问树中的数据呢?当然可以,就是...

    程序员小浩
  • 第36期:二叉树的遍历(小白必看)

    BFS,广度/宽度优先。其实就是从上到下,先把每一层遍历完之后再遍历一下一层。假如我们的树如下:

    程序员小浩
  • Thinkphp5.0 框架使用模型Model添加、更新、删除数据操作详解

    本文实例讲述了Thinkphp5.0 框架使用模型Model添加、更新、删除数据操作。分享给大家供大家参考,具体如下:

    砸漏
  • Arcgis for Android 开发环境搭建(Android Studio篇)

    开发工具:Android Studio 2.1.2(mac版本) 开发环境:OS X EI Capitan 版本 10.11.5 Android系统要求:A...

    专注APP开发
  • Junit5系列-Junit5中Assumptions假设类

    在Junit5中的JUnit Jupiter模块附带了JUnit 4提供的假设方法的一个子集,并添加了一些非常适合与Java 8 lambdas一起使用的方法。...

    洋仔聊编程
  • C语言标准工具库函数库:stdlib.h

      对于一些特殊的操作,C语言提供了标准工具库函数库,其中包括可以实现数值转换,内存分配,随机数操作以及字符串转换等函数。本篇博文一一来讲述这个函数库中的那些函...

    深度学习思考者
  • 数学题:查找,快速幂,二进制,剪绳子

    各位小伙伴,又到周末啦~本周小白已经开始二刷《剑指offer》了,这次在LeetCode上面刷题,发现LeetCode上面的《剑指offer》和牛客上面的题目好...

    鹏-程-万-里
  • [WCF REST] 提高性能的一个有效的手段:条件资源获取(Conditional Retrieval)

    条件获取(Conditional Retrieval)旨在解决这样的问题:客户端获取某个资源并对其进行缓存,当再次获取相同资源时,如果资源数据与之前获取的一致,...

    蒋金楠
  • 43页PPT | 数据思维全解析

    来源公众号:母婴零售探索(FoxHo1108) 当年我们说,“学好数理化,走遍天下都不怕”。 大数据时代,我们的口号是“有了数据思维,真理就在你手中”。 ? 什...

    小莹莹

扫码关注云+社区

领取腾讯云代金券