精华内容
下载资源
问答
  • 主要介绍了Java代码实现矩形覆盖实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,,需要的朋友可以参考下
  • js代码-200608-矩形覆盖

    2021-07-16 15:34:29
    js代码-200608-矩形覆盖
  • 矩形覆盖

    2021-02-19 19:10:37
    我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。 请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形, 总共有多少种方法? 解题思路 n=1 - 只有横放一个矩形一种解决办法 n=2 - 有横放一个矩形,竖放两个矩形两...

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

    解题思路
    n=1 - 只有横放一个矩形一种解决办法
    n=2 - 有横放一个矩形,竖放两个矩形两种解决办法
    n=3 - n=2的基础上加1个横向,n=1的基础上加2个竖向
    n=4 - n=3的基础上加1个横向,n=2的基础上加2个竖向
    ·
    ·
    ·
    n=n - n = f(n-1) + f(n-2)

    斐波那契数列变种。。。。。

    代码实现

    class Solution {
    public:
        int rectCover(int number) {
            if (number == 0)
                return 0;
            else if(number == 1){
                return 1;
            }
            else if (number == 2){
                return 2;
            }
    
            return rectCover(number - 1) + rectCover(number - 2);
        }
    };
    
    展开全文
  • 矩形覆盖 算法

    2019-09-27 08:15:48
    矩形覆盖 题目描述 我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法? import org.junit.Test; /** * 题目描述 我们可以用2*1的小矩形横着...

    矩形覆盖

    题目描述

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

    import org.junit.Test;
    
    /**
     * 题目描述
    我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
    
     * @author 10249
     *使用递归的方式一直到最后
     */
    public class Deal021 {
    	
    	@Test
    	public void Demo(){
    		System.out.println(RectCover(5));
    	}
    	
    	
        public int RectCover(int target) {
        	if(target<=3){return target;}//用2也可以
        	
        	return RectCover(target-1)+RectCover(target-2);
        }
    }
    
    展开全文
  • 矩形覆盖问题

    千次阅读 2019-04-15 21:34:08
    关于分治法  分治法,分而治之。就是将原问题划分为n个规模较小,结构与原问题类似的小问题进行处理,递归地解决这些问题,然后再合并求解的过程。  分治法在解决的流程上分为三个步骤: ...面试题:矩形覆盖...

    关于分治法

      分治法,分而治之。就是将原问题划分为n个规模较小,结构与原问题类似的小问题进行处理,递归地解决这些问题,然后再合并求解的过程。

      分治法在解决的流程上分为三个步骤:

      1.分解:将原问题划分为n个规模较小,结构与原问题类似的小问题。

      2.解决:若子问题规模小,足以处理,则求解,否则继续递归处理。

      3.合并:将子问题的解,合并成为原问题的解。

    面试题:矩形覆盖

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

      分析:我们化繁为简,从下面的示例说起(设该问题的处理函数为rectCover)。

      由于小矩形的尺寸是2×1,所以有大矩形为2×number的存在,那么我们第一步就可以有两种处理方式:

      第一步如果选择竖方向填充,那么该问题的规模就缩减为对于剩余的2×(number-1)的大矩形的填充。

      如果,第一步如果选择横方向的填充,则第二排的前面两个小矩形也只能如此填充,那么该问题的规模就缩减为对于剩余的2×(number-2)的大矩形的填充.

      结合上述分析,很容易得到递推的关系: rectCover(number)=rectCover(number-1)+rectCover(number-2)。当然此处也要注意递归跳出条件的判定。

     

    下面是带备忘录机制的自顶向下法:

    public class Solution {
        
        private int Count(int target, int[] result1) {
    		if(target<=0)
    		{
    			return 0;
    		}
    		if(target==1 || target==2)
    		{
    			return target;
    		}
    		if(result1[target]!=0)
    		{
    			return result1[target];
    		}
    		
    		result1[target]=Count(target-1,result1)+Count(target-2,result1);
    		return result1[target];
    	}
        
        public int RectCover(int target) {
            int[] result1=new int[target+1];
    		return Count(target,result1);
        }
        
        
    }

     

    展开全文
  • 矩形覆盖(C++)

    2020-07-17 00:46:20
    我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法? 比如n=3时,2*3的矩形块有3种覆盖方法: 2.具体算法 class Solution { public: int ...

    1.题目描述

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

    比如n=3时,2*3的矩形块有3种覆盖方法:
    在这里插入图片描述

    2.具体算法

    class Solution {
    public:
        int rectCover(int number) {
            if(number<1)//
                return 0;
            else if(number==1||number==2)
                return number;
            else if(number>2)
                return rectCover(number-1)+rectCover(number-2);
        }
    };
    

    3.算法总结

    • 该算法的难点就在于找到小矩形个数为k和k+1时,覆盖方法个数之间的递归关系,进而找到小矩形个数为n时覆盖方法的个数,简而言之,就是找到规律。
    • 算法规律的总结:
      我们对算法模型做些简化,我们知道,只可以放置两种类型的小矩形,一种是竖着放的2*1矩形,另一种是两块横着放的2 * 1矩形上下放置形成的2 * 2正方形,而题目要放置的是2 * n的大矩形。我们将上面模型映射到一维,即是我们有一条长度为n的线段,现在要么放置长度为1,要么放置长度为2的线段,请将该线段填满。这让我想起了走阶梯的题目,一个n级阶梯,每次要么走一级要么两级,请问有多少种方法。综上分析,可知n = 1时, f(n) = 1; n = 2时,f(n) = 2; n > 2时,f(n) = f(n - 1) + f(n - 2); 标准的斐波那契数列
    • 算法的改进:用递归来解决这个算法虽然思路和形式很简单,但是时间复杂度很高,因为每次输入一个number,就需要把所有比number小的正整数的rectCover函数全部调用一遍,对于一个对时间和空间复杂度都极其严格的算法来说,递归并不优越。那么下面还介绍一个不用递归来解决这个方法的算法:
    class Solution {
    public:
        int rectCover(int number) {
            if(number<1)
                return 0;
            else if(number==1||number==2)
                return number;
            else if(number>2)
            {
                int num,num1,num2;
                num1 = rectCover(1);
                num2 = rectCover(2);
                for(int i=3;i<=number;i++)
                {               
                    num = num1+num2;
                    num1 = num2;
                    num2 = num;
                }
                return num;
            }
            
                
        }
    };
    

    这样用迭代之后,复杂度小了很多很多,如果大家还是不太懂这个题目,可以去参考一下斐波那契数列,它和斐波那契数列的含义是一样的,只是描述形式不同。

    展开全文
  • 【模板】最小矩形覆盖

    千次阅读 2019-05-31 15:33:33
    给出平面上的一堆点,找出一个能够覆盖所有点的面积最小的矩形,输出面积及四个顶点的坐标。 分析 一眼计算几何好毒瘤题。(废话) 经过一番涂涂画画之后,我们可以非常感性地得出一个结论:最后这个矩形一定有一边...
  • c++ 刷题 矩形覆盖

    2020-05-26 10:41:34
    我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法? 比如n=3时,2*3的矩形块有3种覆盖方法: 思路: 根据观察: n = 1:f(n) = 1 n = 2:f(n...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 59,581
精华内容 23,832
关键字:

矩形覆盖