算法题练习——JS Node+python题解NC76 用两个栈实现队列、NC68 跳台阶

灰太狼 2024-04-07 11:20 17阅读 0赞

**目录**

NC76 用两个栈实现队列

NC68 跳台阶

--------------------

### NC76 用两个栈实现队列 ###

**描述**

> 用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

> 数据范围： n≤1000
> 
> 要求：存储n个元素的空间复杂度为 O(n) ，插入与删除的时间复杂度都是 O(1)

**示例1**

> 输入：\["PSH1","PSH2","POP","POP"\]
> 
> 返回值：1,2
> 
> 说明：
> 
>  *  "PSH1":代表将1插入队列尾部
>  *  "PSH2":代表将2插入队列尾部
>  *  "POP“:代表删除一个元素，先进先出=>返回1
>  *  "POP“:代表删除一个元素，先进先出=>返回2

**示例2**

> 输入：\["PSH2","POP","PSH1","POP"\]
> 
> 返回值：2,1

JavaScript题解：

let queue = []
    function push(node)
    {
        // write code here
        return queue.push(node)
    }
    function pop()
    {
        // write code here
        return queue.shift()
    }
    module.exports = {
        push : push,
        pop : pop
    };

**python代码解：**

# -*- coding:utf-8 -*-
    class Solution:
        def __init__(self):
            self.stack1 = []
            self.stack2 = []
        def push(self, node):
            # write code here
            self.stack1.append(node)
        def pop(self):
            # return xx
            if self.stack2:
                return self.stack2.pop()
            else:
                for i in range(len(self.stack1)):
                    self.stack2.append(self.stack1.pop())
                return self.stack2.pop()

--------------------

### NC68 跳台阶 ###

**描述**

> 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

> 数据范围：1≤n≤40
> 
> 要求：时间复杂度：O(n) ，空间复杂度： O(1)

**示例1**

> 输入：2
> 
> 返回值：2
> 
> 说明：青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2

**示例2**

> 输入：7
> 
> 返回值：21

**JavaScript题解：**

**python代码解：**

#
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param number int整型 
    # @return int整型
    #
    class Solution:
        def jumpFloor(self , number: int) -> int:
            # write code here
            if number <= 1:
                return 1
            res = 0
            a = 1
            b = 1
            for i in range(2,number+1):
                res = (a+b)
                a = b
                b = res
            return res