矩形覆盖
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?。
n<=39(点我直接练习)
分析
本题是剑指offer中的最后一道以循环和递归来解决的问题,其实做了这几道题,他们的共同点并不是使用何种数据结构,而是找规律。此题的规律看起来是需要一点平面的组合技巧,实际上,对于规律来说,递推出前面几项,就可以基本上得到大致的规律。输入为1,就1中;输入为2,那么就是一个田字形,我们可以有两种填法;输入为3,则代表又加入一列,经过枚举,发现是3种,此时猜测规律可能是前两项之和为本题的规律。再尝试输入为4时,枚举的结果是5,正是2+3。故确定规律,盘它!
使用到的知识点
C++
循环
Python
同上
题解
C++(Clang++ 3.9) : 运行时间:4ms 占用内存:620k
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;
}
}
};
Python 2.7-运行时间:34ms ,占用内存:5732k
# -*- 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风格,几乎相同的代码下,依然差了这么多的性能,不禁引发了我的思考,究竟差在哪里呢?