一个2*N的表格,砖块是1*2的尺寸,可以横着放或竖着放,请问2*N列表格有多少种放法
一个2N的表格,砖块是12的尺寸,可以横着放或竖着放,请问2*N列表格有多少种放法?
本题是2022届毕业生秋招一个银行大招聘笔试题
有了斐波那契数列,其实经常又大厂会改编一些类似斐波那契数列的题目来考,因此,这类题目咱们要总结和梳理一下,以防万一
提示:矩阵A的p次幂的快速乘法,是重要的优化算法基础知识
之前的基础:咱们求过数字最快速乘幂的方法(数字a的p次幂),
(1)最快乘法:普通数字a的p次幂怎么求速度最快,不用Math.pow(a,p)哦
(2)咱们求过矩阵最快速乘幂的方法(矩阵A的p次幂),
最快矩阵乘法:矩阵A的p次幂怎么求速度最快,Math根本没有求矩阵的幂次函数
这俩知识点,你必须看懂,否则这个文章你看不懂!
这俩知识点,你必须看懂,否则这个文章你看不懂!
这俩知识点,你必须看懂,否则这个文章你看不懂!
在笔试中,建议还是用暴力递归改记忆化搜索算法,或者改动态规划填表的做法!
笔试的话,不建议用快速矩阵乘法来求斐波那契数列类似的问题!
但是在,面试的过程中,先可以用暴力递归解决类似的问题,改动态规划
然后,咱们可以秀一下自己的优化实力与技能!即完全可以用矩阵的乘幂来求类似的斐波那契数列f(n)题
下列文章是重要的关于斐波那契数列的题目:
(3)斐波那契数列:暴力递归改动态规划
(4)用矩阵乘幂的方法,求斐波那契数列f(n)=f(n-1)+f(n-2),不用递归求,速度非常非常快
(5)类似斐波那契数列:奶牛生牛问题:奶牛生下来3年可以成熟生小牛,请问第N年一共多少牛
(6)人或者青蛙走台阶,每次它可以一步走1阶,或2阶,请问总共n层能有多少种走法
(7)一个N位字符串s,只包含0和1的,要求每个0左边都是1才达标,请问01组合出s有多少种组合方法
题目
一个2N的表格,砖块是12的尺寸,可以横着放或竖着放,请问2*N列表格有多少种放法?
一、审题
示例:
绿色那是横着放
粉色那是竖着放
请问2*N列表格,有多少种放法?
……
二、解题
!!!这个题目,完全和走阶梯那题目一模一样!!!
(6)人或者青蛙走台阶,每次它可以一步走1阶,或2阶,请问总共n层能有多少种走法
!!!这个题目,完全和01组合字符串达标那题目一模一样!!!
(7)一个N位字符串s,只包含0和1的,要求每个0左边都是1才达标,请问01组合出s有多少种组合方法
你完全可以根据案例去画,然后得出递推公式:
(1)n=1:就粉色这一种情况:1
(2)n=2:
第一块取(1)的话,第2块只能竖着放,1种
第一块横着放,(绿色那),那下面也只能横着放,1种
共2种
(3)n=3:
实际上,把3位置当(1)搞定【21】,那就是f(n-1)种方法;
如果把23位置横着放,就当(2)来看【22】,那就是f(n-2)种方法;
也就是说,f(3)=f(1)+f(2)=1+2=3
(4)n=4:
跟(3)类似,咱把4位置当(1)来看,实际上就是f(n-1)种方法
如果34位置横着放,那就是(2)来看,实际上就是f(n-2)种方法
也就是说f(4)=f(3)+f(2)=3+2=5
……
观察可以知道,实际上,f(n)=f(n-1)+f(n-2)
初始化条件f(1)=1,f(2)=2;
这跟斐波那契数列很相似,只不过斐波那契数列的始化条件f(1)=1,f(2)=1;
咱们还可以这么推,不单单是观察
事情是这样的:
如果看看n位怎么放砖的话?
(1)直接让n位置,一块砖竖着放,那只看f(n-1)种方法即可
(2)如果n-1和n位置联合放2块横着的砖,那只需要看f(n-2)
所以求和就是我们要的方案数,因为就上面2种摆法!
f(n)=f(n-1)+f(n-2)
初始化条件f(1)=1,f(2)=2;
是不是超级easy?
剩下的撸代码的事情,完全和青蛙走台阶、和01组合字符串那俩题目一模一样,没有任何区别!——所以上面的基础知识一定要看。
三、暴力递归,关键是上面的公式,撸代码不是问题
对于本题,你还要注意,其实
f(n)=f(n-1)+f(n-2),初始化条件f(1)=1,f(2)=2;
f即:1 2 3 5 8……
这跟斐波那契数列很相似,feiBo(n)=feiBo(n-1)+feiBo(n-2),只不过斐波那契数列的始化条件f(1)=1,f(2)=1;
feiBo即:1 1 2 3 5 8……
当年咱们求过斐波那契数列的代码,你完全可以用!
public static int feiBo(int n){
if (n == 1 || n == 2) return 1;
return feiBo(n - 1) + feiBo(n - 2);
}
只不过是当n=2开始,f(n)=feiBo(n+1);
n=2时,而feiBo(2)=1,但是f(2)=2了,实际就是f(n)=feiBo(n+1)=feiBo(3)=2
这非常简单吧……
public static int qingWa(int n){
if (n == 1) return 1;
return feiBo(n + 1);
}
当然,每次遇到不同的递归,你完全可以重头再写暴力递归代码,非常非常简单的
咱们手撕一下:
//复习青蛙台阶f
public static int f(int n){
if (n == 1) return 1;
if (n == 2) return 2;
return f(n - 1) + f(n - 2);
}
public static void test2(){
System.out.println(qingWa(4));
System.out.println(f(4));
}
public static void main(String[] args){
test2();
}
问题不大:
5
5
四、笔试AC解:改记忆化搜索方案,让dp表跟随暴力递归
既然一个变量n,那就是一维表格dp,长n+1,i从0–n取值
咱们可以搞一个dp表伴随f
dp就是傻缓存,在笔试时就这能AC,速度很快的。
手撕代码问题不大:
//复习青蛙台阶fDP
public static int fDP(int n, int[] dp){
if (dp[n] != -1) return dp[n];
if (n == 1) {
dp[n] = 1;
return dp[n];
}
if (n == 2) {
dp[n] = 2;
return dp[n];
}
dp[n] = fDP(n - 1, dp) + fDP(n - 2, dp);
return dp[n];
}
public static int jumpSteps(int n){
int[] dp = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
dp[i] = -1;//初始化
}
return fDP(n, dp);
}
public static void test2(){
System.out.println(qingWa(4));
System.out.println(f(4));
System.out.println(jumpSteps(4));
}
public static void main(String[] args){
test2();
}
5
5
5
五、面试精华解:改精细化动态规划填写dp表,整转移方程
笔试可以了,但是我们面试还需要直接从暴力递归的代码,推导转移方程,直接填表dp,返回dp[n]【下面那个五角星位置】
填表初始化,左边1 2两个格子
然后从左往右填写即可
超级简单
public static int jumpStepsDP(int n){
if (n < 1) return 0;
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;//暴力递归怎么写,咱就怎么改
for (int i = 3; i < n + 1; i++) {
dp[i] = dp[i - 1] + dp[i - 2];//暴力递归直接改f为dp来的
}
return dp[n];
}
public static void test2(){
System.out.println(qingWa(4));
System.out.println(f(4));
System.out.println(jumpSteps(4));
System.out.println(jumpStepsDP(4));
}
public static void main(String[] args){
test2();
}
5
5
5
5
面试高超优化技能:矩阵A的p次幂求斐波那契数列
之前,咱们学过,斐波那契数列的快速矩阵幂次求法
(4)用矩阵乘幂的方法,求斐波那契数列f(n)=f(n-1)+f(n-2),不用递归求,速度非常非常快
咱必须要记住的d矩阵是:【可别记错了!】
类似斐波那契数列的通用矩阵乘积形式:
故当d的n-2次幂求出来之后,完全可以这么做
那么关键就在矩阵的乘积AB的代码和A的p次幂的代码,你要记住,数量掌握
//C=A×B咋求--Math中没有的,需要自己整
public static int[][] matrixMul(int[][] A, int[][] B){
int m = A.length;
int b = B[0].length;
int[][] C = new int[m][b];//A的一行,×B的一列,求和,放在C的m行,b列
for (int i = 0; i < m; i++) {
for (int j = 0; j < b; j++) {
//A的一行,×B的一列,求和,放在C的m行,b列
int ans = 0;
for (int k = 0; k < A[0].length; k++) {//是A的列哦
ans += A[i][k] * B[k][j];
}
C[i][j] = ans;
}
}
return C;
}
//矩阵A的p次幂--这个要熟练掌握,二进制幂次求法
public static int[][] powMatrixAitsPCiMi(int[][] A, int p){
int m = A.length;
int n = A[0].length;
//初始化,a=I,t=A的1次方
int[][] a = new int[m][n];
for (int i = 0; i < m; i++) {
a[i][i] = 1;//单位阵
}
int[][] tmp = A;//基数矩阵
//(1)p的0位x=1:a=a×t=1×A的1次方=A的1次方,t=t×t=A的2次方
//(2)p的1位x=1:a=a×t=A的1次方=A的1次方×A的2次方,t=t×t=A的4次方
//(3)p的2位x=0:~~a=a×t=A的1次方=A的1次方×A的2次方~~ ,t=t×t=A的8次方
//(4)p的3位x=1:a=a×t=A的1次方=A的1次方×A的2次方×A的8次方,t=t×t=A的16次方
//(5)p的4位x=0:~~a=a×t=A的1次方=A的1次方×A的2次方×A的8次方~~ ,t=t×t=A的32次方
//(6)p的5位x=0:~~a=a×t=A的1次方=A的1次方×A的2次方×A的8次方~~ ,t=t×t=A的64次方
//(7)p的6位x=1:a=a×t=A的1次方=A的1次方×A的2次方×A的8次方×A的64次方 ,t=t×t=A的128次方
//此时a已经是A的p=75次方了
//看p的x位是否为1
for(; p != 0; p >>= 1){//每次结束p往右移动1位,p=0结束
if ((p & 1) != 0){
//p最右那个x位=1,需要雷×结果
a = matrixMul(a, tmp);//a=a*t
}
//每次t都需要倍次幂
tmp = matrixMul(tmp, tmp);//t=t*t
}
return a;//返回a
}
好,现在就可以求阶梯有多少走法了?
//阶梯与斐波那契数列的关系
public static int fMatrixMiCi(int n){
if (n == 1) return 1;
if (n == 2) return 2;
int[][] d = {
{1,1},
{1,0}
};//1110的d,千万别记错了
d = matrixPower(d, n - 2);//d的n-2次幂
//fn fn-1 = f2 f1 * d的n-2次幂
//fn = 2 1 8 d的n-2次幂
return 2 * d[0][0] + d[1][0];//画个图看矩阵就知道了,很简单。
}
public static void test2(){
System.out.println(qingWa(4));
System.out.println(f(4));
System.out.println(jumpSteps(4));
System.out.println(jumpStepsDP(4));
System.out.println(fMatrixMiCi(4));
}
public static void main(String[] args){
test2();
}
5
5
5
5
5
总结
提示:重要经验:
1)类似斐波那契数列的递推公式,可以通过观察得到,也可以通过推理得到,反正不会太难的,要找到这个规律。
2)矩阵幂次的求法,可以在笔试秀技,但是笔试就踏实写傻缓存dp跟随暴力递归的代码就行。
3)笔试求AC,可以不考虑空间复杂度,但是面试既要考虑时间复杂度最优,也要考虑空间复杂度最优。
相关文章
- HT for Web列表和3D拓扑组件的拖拽应用
- iOS开发UI篇—使用UItableview完成一个简单的QQ好友列表(一)
- 数据存储之属性列表Plist
- 第七十五节,CSS表格与列表
- QMUI UI库 控件 弹窗 列表 [MD]
- 论字母导航的重要性,我们来实现一个联系人字母导航列表吧!
- glob模块--查询一个文件名列表
- 15拓展控件X-01高级列表面板-xlistwidget
- Linux 列出文件列表命令ls
- 《ASP.NET Core 6框架揭秘》实例演示列表
- 168. 用 SAP UI5 Select 控件(下拉列表),来驱动表格控件(Table)刷新的一个实战例子
- 用 SAP UI5 Select 控件(下拉列表),来驱动表格控件(Table)刷新的一个实战例子试读版
- SAP UI5 应用开发教程之九十一 - 如何使用客户端 JSON 模型构建一个 Master-Detail-Detail 布局中的列表页面试读版
- 如何给SAP Cloud ConnectorRegion列表中添加新的Region
- Atitit.列表页面and条件查询的实现最佳实践(2)------翻页 分页 控件的实现java .net php
- SAP UI5 应用开发教程之九十一 - 如何使用客户端 JSON 模型构建一个 Master-Detail-Detail 布局中的列表页面试读版
- flutter 在一个动态列表里面怎么插入一个广告图片
- flutter 把一个列表传进一个界面,对新列表进行操作,实际上是对旧列表进行操作
- Python:利用collections库实现统计单个字或单个字母的频率统计并进行降序输出、统计一个列表内重复元素并以字典形式输出
- Excel:利用Excel内置功能实现对某列表格按照条件进行升降序排列
- Python:利用collections库实现统计单个字或单个字母的频率统计并进行降序输出、统计一个列表内重复元素并以字典形式输出
- Python编程语言学习:列表与字典互转的几大方法集锦、从列表中按顺序循环抽走一个元素输出剩余元素之详细攻略
- Qt制作一个ListView列表
- 【Linux 内核 内存管理】分区伙伴分配器 ③ ( 备用内存区域列表 | ZONELIST_FALLBACK 枚举 | zoneref 结构体 | 备用内存区域借用物理页规则 )
- react文档demo实现输入展示搜索结果列表
- CCScrollView/CCTableView(CCTableViewDelegate CCTableViewDataSource CCTableView-滑动列表-游戏中大量使用 非常重要的一个类)
- Swift基础--使用TableViewController自己定义列表
- 将合并的数据结构来实现一个单一的列表
- F4nniu 的读书列表
- python里给出一个列表,怎么样从列表里取出最小两项的索引值
- 查看svchost的服务列表
- Spring MVC列表多选框
- 数据结构与算法_19 _ 散列表(中):如何打造一个工业级水平的散列表?
- 如何将 kitten编程猫里的以分号分隔的长字符串转换成列表结构