• 欢迎访问小澍的博客,编程记录,技术贴以及折腾的日常,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏我的博客吧

剑指offer刷题记——矩形覆盖

C++ root 2年前 (2019-03-20) 379次浏览 已收录 0个评论

矩形覆盖

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

分析

本题是剑指offer中的最后一道以循环和递归来解决的问题,其实做了这几道题,他们的共同点并不是使用何种数据结构,而是找规律。此题的规律看起来是需要一点平面的组合技巧,实际上,对于规律来说,递推出前面几项,就可以基本上得到大致的规律。输入为1,就1中;输入为2,那么就是一个田字形,我们可以有两种填法;输入为3,则代表又加入一列,经过枚举,发现是3种,此时猜测规律可能是前两项之和为本题的规律。再尝试输入为4时,枚举的结果是5,正是2+3。故确定规律,盘它!

使用到的知识点

C++

循环

Python

同上

题解

class Solution {
public:
    int rectCover(int number) {
        if(number == 1)
            return 1;
        if(number == 2)
            return 2;
        else{
            int n1 = 1, n2 = 2;
            int anwser = 0;
            while((number-2)>0){
                anwser = n1+n2;
                n1 = n2;
                n2 = anwser;
                number--;
            }
            return anwser;
        }
    }
};
# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        if number == 1:
            return 1
        if number == 2:
            return 2
        else:
            n1 = 1
            n2 = 2
            anwser = 0
            number = number-2
            while(number>0):
                anwser = n1+n2
                n1 = n2
                n2 = anwser
                number = number-1
            return anwser

偷了个懒,直接把C++的写成python风格,几乎相同的代码下,依然差了这么多的性能,不禁引发了我的思考,究竟差在哪里呢?


XiaoShuBlog , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:剑指offer刷题记——矩形覆盖
喜欢 (0)
[gaosirgoo@foxmail.com]
分享 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址