ADM-201 dump PMP dumps pdf SSCP exam materials CBAP exam sample questions

编程面试题3:多少台阶组合可以上到第x级台阶 – 译学馆
未登录,请登录后再发表信息
最新评论 (0)
播放视频

编程面试题3:多少台阶组合可以上到第x级台阶

IQ 3: How many step combinations to get up x number of steps?

[音乐]
[Music]
大家好 我又有个编程面试题要和你们分享
Hi, guys how are you? I have the another coding interview problem that I want to share with you guys.
题目在这里
Here is the problem.
有一个n级的台阶
You have a stair case with n steps.
就是说 一个台阶 它共有n级
Let’s just say you have a staircase and it has n number of steps here.
你上台阶时 可以一次登1级或2级
You may take 1 or 2steps at a time to climb the stairs.
比如 台阶有3级
So let’s just say you have three stairs.
为了登顶 每次只能登1至2级
In order to get up these staires you have to take either one or two steps to make your way to the top of staircase.
那么第一种登顶的方法是
So the first way to make your way up these stairs are
1次1级 就是第1级 第2级 第3级
to take one step at a time which you go one two three.
一级一级又一级 这是一种组合
One step one step one step, that’ll be one combination.
另一种方法是 先登2级再登1级
Another way of making your way up these stairs would be to take two steps first
也可以登顶
and then one step to make your way to the top of these stairs.
还有一种方法是 先登1级再登2级
And another way to your way up these stairs would be to take one step first and take two steps
最终会有3种方法或3种组合
In order to get to the top of these stairs which would ultimately result in three ways or three combinations
来登上这个台阶
to making your way up this staircase.
写一个函数来找出登顶台阶的组合数
Write a method to find the total number of combinations to climb the stair case.
当我看到题目时 我需要考虑两件事
So when I was looking at this I know I had to consider two things,
我需要考虑基础情况并创建一个公式
I had to take note of the base case and I had to create a formula that
来计算登顶台阶的所有组合数
that would calculate the total number of combinations to make my way up this staircase.
因此 首先考虑基础情况
So the first thing I consider was the base case,
如果台阶数n小于等于2 返回值是n
if n which is equivalent to the number of stairs is lesser than or equal to 2 then I want to return n
这意味着 如果台阶只有1级
so this basically means that if there’s only one stair
那登顶就只有一个方法 也就是登1级
there is only one way up that stair, which is one step.
你不能登2级 因为台阶只有1级
You couldn’t take two steps, because simply just one step
如果台阶有2级 那登顶就有2种方法
if there are two steps there are two ways to reach the top stair case
1次1级 或1次2级
1 step at a time or 2 steps at a time.
另一个需要考虑的是公式
Another thing I consider was the formula.
基本上 我创建公式时
So the formula would be equal to so so basically when I’m creating the formula
需要考虑台阶数n大于2时的情况
I wanted the formula that would account for if n is greater than 2 if there are more than two steps.
结果表明 为了计算登顶
And it turned out that in order to calculate the combination
n级台阶的组合数 我需要将之前登顶
of the total number of ways that you can get to the top of n steps.
n-1级和n-2级台阶的组合数相加
I had to take the sum of the previous two steps.
公式在这里
ln order to come up with the combination so this is the formula here
Steps(n-1)+Steps(n-2)
steps n minus 1 plus steps n minus 2
这里有一个例子 比如说 n等于3
I have an example down here let’s just say n is equal to 3.
将3代入这里的n
So what I want to do is just pass 3 until … into n here.
(3-1)+(3-2) 等于 2+1
So 3 minus 1 plus 3 minus 2 you get 2 plus 1
也就是说有3种登顶的方法
which will be equal to three ways up the stairs.
为了让它更清楚一点 我们来写代码
So to make this a little clearer let’s start coding.
第一步是创建一个函数
So the first thing I wanted to do was to create a function
这个函数返回一个值
I want this function to return a number.
现在我将函数命名为”calculatestepways”
Now I’m going to name this function
它指的是登顶台阶的组合数
calculatestepways. Basically, number of ways that you can reach the top of a staircase.
另一件事是在这里增加一个参数
Another thing I want to do is actually add a parameter value here.
它是传递进函数里的台阶数n
This parameter value is just going to take the number of steps that are passed in.
首先 我们来处理基础情况
The first thing I want to do is handle this base case.
那么 “if (n <= 2)"
So the first thing I want to write is if n is less than or equal to 2
然后 “return n”
then I want to return n.
基本上 这就是在前面介绍中讲过的
So basically what’s happening here is
如果n小于等于2 那么返回值就是n
if the number as I explained before in the presentation is less than or equal to 2 I want to return n
如果n=1 返回1 因为台阶只有1级
if n equal to 1 I want to return 1 because there is only one stair
如果n=2 返回值是2
if it is equal to 2 I want to return 2
因为登顶的方法就是 1次1级 或者1次2级
Because you can make your way up the steps one way with just one step at a time or two steps at a time
现在另一件事是在这下面增加一个else语句
now another thing I want to do is add this else clause down here
这个else语句仅仅只是返回一个函数
And this else clause is simply going to return the method
让我们回到这里
let’s go back here
它将会返回这个公式 就是这里的(n-1)+(n-2)
It is going to return this formula that I’ve created here n minus 1 plus n minus 2.
calculatestepways(n-1)+ calculatestepways(n-2)
So calculatestepways n minus 1 plus calculatestepways n minus 2
这就是到现在为止的函数的内容
and that’s pretty much it as far as the function goes.
现在我只需要回到主函数里 调用这个函数
The only thing I need to do now is go up to this main method and call this function
并且要将这个值打印到控制台 因此我将会输入 “System.out.println(calculatestepways())”
also want this value to be printed out to the console so I’m going to do a
然后代入3 就像之前说过的
And then I’m going to pass in 3 now as we know as I explained before
通过代入3 就能获得3级台阶的结果
by passing in 3 I’m supposed to get 3 steps.
这里我将把“3”打印到控制台上
So I should have 3 printed out to the console here.
保存并运行程序
Then you save and let’s run the application here.
我们得到了所期望的结果”3″
We get three exactly what we were expecting.
另外 关于这个函数 我要指出的是
Another thing I want to point out about this function is
它看起来像之前一集视频中的斐波那契公式
that it looks it looks similar to the Fibonacci formula that I created in one of my earlier tutorial.
还有一件需要考虑的事是时间复杂度
So another thing we need to consider is the time complexity.
这个函数的时间复杂度是呈指数增加的
The time complexity of this function is exponential
指数式的时间复杂度 就是2的n次方
exponential time complexity to raise to the end to raise to the end all right.
在面试期间 他们也让我创建一个更高性能的函数
So during this interview they also asked me to create a function for a better performance.
一个办法就是 像我以前说的 它很像斐波那契数列
So basically a way of doing that as I said before it’s pretty much similar to the Fibonacci sequence.
唯一不同的是这个基础条件
The only thing that really changes is this basically this this base case condition
不再像斐波那契公式中那样返回1
instead of returning one which I have done in the Fibonacci formula.
现在 这里是返回n
I’m just returning n now.
所以 我要创建一个新函数
So I’m going to create a new function
一个无递归的函数计算登顶台阶的组合数
a non recursive function that calculates the number of ways you can make your way up these steps
这里输入 “public static int calculatestepways”
So I’m going to start off with public static int calculatestepways
函数名末尾加上”nonrecursive”
And I’m going to name this non recursive.
这个函数同样接收一个参数n
And this function is also going to take in a number yes n.
对于基础情况 我们用和这里同样的方法来设置它
It’s pretty much and also the base case we are going to set it up the same way we set it up here.
如果n小于等于2 返回n
So if n is less than or equal to 2, then I want to return n.
现在 我要创建三个变量
What I want to do now is create three variables
“int first = 1” “int second = 2” “int nth = 3”
int first equals one, int second equals two, int nth equals three.
然后……这里不是3 实际上应该是2 我的错
After this well not three, actually this is actually going to be two, my bad.
然后我要创建一个循环
So I then want to create myself a for loop
“for (int i = 3)”
for int I equals three.
从3开始的理由我在上次教程中讲过
The reason we are starting at three I explained this in previous tutorial.
从3开始是因为我已经处理了前2个的情况
But the reason I started at 3 is because I’ve already handled the case for 2 here.
然后我要输入 “i<=n" "i++"
Then I want to go i is lesser than or equal to n i plus plus.
好 首先是输入 “nth = first + second”
Alright so first thing I want to do is write nth equals first plus second,
“first = second” “second = nth”
first equals second, second equals nth
到最后 我只要返回nth
simply at the end I just want to return nth.
这就完成了 就像你注意到的 下面这个for循环
And this this is it as you notice with this for loop down here.
时间复杂度是O(n) 它比我们上面的那个指数式时间复杂度要好
Time complexity is O of n, which is a better time complexity than the exponential one that we have up here.
现在我们要做的是调用这个函数
So what I’m going to do now is call this function.
这里我代入相同的值 保存 如果我再次运行它 我将得到同样的数字3
And I’m passing in the same value here save it if I run it again I should get the same number three.
看 正是我们所期望的
See exactly what we’re looking for.
所以 这就是解决问题的办法了
So that’s pretty much it for solving this problem.
如果你有任何问题 请在下面的评论中留言
If you have any questions please leave them in the comments below.
如果你觉得能从中学到东西
Make sure to also subscribe and like the video
记得订阅和点赞 下次再见
if you felt like you’ve learned something from this and until next time.

发表评论

译制信息
视频概述

编程面试题3,算法求解及优化,上到n级台阶顶端总共有多少的步数组合?

听录译者

[B]倔强

翻译译者

B11101001

审核员

审核团O

视频来源

https://www.youtube.com/watch?v=lQjoQ_VZWIs

相关推荐