Hi, guys how are you? I have the another coding interview problem that I want to share with you guys.
Here is the problem.
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.
You may take 1 or 2steps at a time to climb the stairs.
So let’s just say you have three stairs.
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.
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.
And another way to your way up these stairs would be to take one step first and take two steps
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,
if n which is equivalent to the number of stairs is lesser than or equal to 2 then I want to return n
so this basically means that if there’s only one stair
there is only one way up that stair, which is one step.
You couldn’t take two steps, because simply just one step
if there are two steps there are two ways to reach the top stair case
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
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
of the total number of ways that you can get to the top of n steps.
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 minus 1 plus steps n minus 2
这里有一个例子 比如说 n等于3
I have an example down here let’s just say n is equal to 3.
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
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.
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.
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
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
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
now another thing I want to do is add this else clause down here
And this else clause is simply going to return the method
let’s go back here
It is going to return this formula that I’ve created here n minus 1 plus n minus 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
And then I’m going to pass in 3 now as we know as I explained before
by passing in 3 I’m supposed to get 3 steps.
So I should have 3 printed out to the console here.
Then you save and let’s run the application here.
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
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
instead of returning one which I have done in the Fibonacci formula.
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
And I’m going to name this non recursive.
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.
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.
The reason we are starting at three I explained this in previous tutorial.
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
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.
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.