当前位置： 首页 > news >正文

算法练习（堆/栈/队列）

news 来源：原创 2024/5/7 6:12:07

BM42 用两个栈实现队列

描述 用两个栈来实现一个队列，使用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

# -*- 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
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        res = self.stack2.pop()
        while self.stack2:
            self.stack1.append(self.stack2.pop())
        return res

BM43 包含min函数的栈

描述 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min
函数操作时，栈中一定有元素。

此栈包含的方法有： push(value):将value压入栈中 pop():弹出栈顶元素 top():获取栈顶元素
min():获取栈中最小元素

数据范围：操作数量满足0≤n≤300 ，输入的元素满足∣val∣≤10000 进阶：栈的各个操作的时间复杂度是 O(1) ，空间复杂度是 O(n)

示例:
输入: [“PSH-1”,“PSH2”,“MIN”,“TOP”,“POP”,“PSH1”,“TOP”,“MIN”]
输出: -1,2,1,-1
解析:
"PSH-1"表示将-1压入栈中，栈中元素为-1
"PSH2"表示将2压入栈中，栈中元素为2，-1
“MIN”表示获取此时栈中最小元素==>返回-1
"TOP"表示获取栈顶元素==>返回2
"POP"表示弹出栈顶元素，弹出2，栈中元素为-1
"PSH1"表示将1压入栈中，栈中元素为1，-1
"TOP"表示获取栈顶元素==>返回1
“MIN”表示获取此时栈中最小元素==>返回-1

示例1
输入：["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
返回值：-1,2,1,-1

# -*- coding:utf-8 -*-
class Solution:
    stack1 = []
    stack2 = []

    def push(self, node):
        # write code here
        self.stack1.append(node)
        if not self.stack2:
            self.stack2.append(node)
        elif node < self.stack2[-1]:
            self.stack2.append(node)
        else:
            self.stack2.append(self.stack2[-1])

    def pop(self):
        # write code here
        self.stack1.pop()
        self.stack2.pop()

    def top(self):
        # write code here
        return self.stack1[-1]

    def min(self):
        # write code here
        return self.stack2[-1]

BM44 有效括号序列

描述
给出一个仅包含字符’(‘,’)‘,’{‘,’}‘,’[‘和’]',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()“和”()[]{}“都是合法的括号序列，但”(]“和”([)]"不合法。

数据范围：字符串长度 n≤10000
要求：空间复杂度 O(n)，时间复杂度 O(n)

示例1
输入："["
返回值：false

示例2
输入："[]"
返回值：true

class Solution:
    def isValid(self, s):
        stack1 = []
        check = {
            "(": ")",
            "{": "}",
            "[": "]",
        }

        for i in s:
            if len(stack1) >= 1:
                left = stack1[-1]
                if i in check.keys():
                    stack1.append(i)
                elif check.get(left) == i:
                    stack1.pop()
            else:
                stack1.append(i)

        if len(stack1) == 0:
            return True
        return False

BM45 滑动窗口的最大值

描述
给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。
例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
窗口大于数组长度或窗口长度为0的时候，返回空。
数据范围： 1≤n≤10000，0≤size≤10000，数组中每个元素的值满足∣val∣≤10000
要求：空间复杂度 O(n)，时间复杂度 O(n)

示例1
输入：[2,3,4,2,6,2,5,1],3
返回值：[4,4,6,6,6,5]

示例2
输入：[9,10,9,-7,-3,8,2,-6],5
返回值：[10,10,9,8]

示例3
输入：[1,2,3,4],5
返回值：[]

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @param size int整型 
# @return int整型一维数组
#
class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        # write code here
        if size == 0 :
            return
        max_wind = []
        for i in range(len(num)):
            if size > len(num):
                break
            new_num = num[:size]
            max_wind.append(max(new_num))
            num.pop(0)

        return max_wind

BM46 最小的K个数

描述
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围：0≤k,n≤10000，数组中每个数的大小0≤val≤1000
要求：空间复杂度 O(n) ，时间复杂度 O(nlogk)

示例1
输入：[4,5,1,6,2,7,3,8],4 
返回值：[1,2,3,4]
说明：返回最小的4个数即可，返回[1,3,2,4]也可以    
    
示例2
输入：[1],0
返回值：[]

示例3
输入：[0,1,2,1,2],3
返回值：[0,1,1]

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param input int整型一维数组
# @param k int整型
# @return int整型一维数组
#


class Solution:
    def GetLeastNumbers_Solution(self, input: List[int], k: int) -> List[int]:
        # write code here
        # 方式一
        # new_list = sorted(input)
        # return new_list[:k]

        #方式二
        for i in range(len(input)):
            for j in range(len(input) - i - 1):
                if input[j] > input[j + 1]:
                    input[j], input[j + 1] = input[j + 1], input[j]
        return input[:k]

BM47 寻找第K大

描述 有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。

给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。 要求：时间复杂度 O(nlogn)，空间复杂度 O(1)
数据范围：0≤n≤1000， 1≤K≤n，数组中每个元素满足 0≤val≤10000000

示例1
输入：[1,3,5,2,2],5,3
返回值：2

示例2
输入：[10,10,9,9,8,7,5,6,4,3,4,2],12,3
返回值：9
说明：去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9

BM48 数据流中的中位数

描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
数据范围：数据流中数个数满足1≤n≤1000 ，大小满足 1≤val≤1000
进阶： 空间复杂度 O(n)， 时间复杂度 O(nlogn)

示例1
输入：[5,2,3,4,1,6,7,0,8]
返回值："5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "
说明：数据流里面不断吐出的是5,2,3...,则得到的平均数分别为5,(5+2)/2,3...   

示例2
输入：[1,1,1]
返回值："1.00 1.00 1.00 "

# -*- coding:utf-8 -*-
class Solution:
    list_data = []
    def Insert(self, num):
        # write code here
        print(num)
        self.list_data.append(num)
        print(self.list_data)

    def GetMedian(self):
        # write code here
        if len(self.list_data) % 2 == 0:
            new_list = sorted(self.list_data)
            mid = len(new_list)//2
            median = (new_list[mid] + new_list[mid-1])/2
        else:
            new_list = sorted(self.list_data)
            mid = len(new_list)//2
            median = new_list[mid]
        return median

BM49 表达式求值

描述
请写一个整数计算器，支持加减乘三种运算和括号。
数据范围：0≤∣s∣≤100，保证计算结果始终在整型范围内
要求：空间复杂度： O(n)，时间复杂度 O(n)

示例1
输入："1+2"
返回值：3

示例2
输入："(2*(3-4))*5"
返回值：-10

示例3
输入："3+2*3*4-1"
返回值：26

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
#
class Solution:
    def solve(self , s: str) -> int:
        # write code here
        return eval(s)

相关文章：

  • 大数据-ClickHouse技术一（安装部署）
  • 【Android入门】4、数据持久化：文件、SharedPreferences 和 Sqlite
  • style样式优先级问题【display:block依旧无法显示DOM元素】
  • （编程语言界的丐帮 C#）.NET MD5 HASH 哈希 加密 与JAVA 互通
  • 面试宝典------经典
  • node.js环境搭建
  • 【5G核心网】手把手教你将Open5gs托管到k8s（KubeSphere）
  • 空城机在CSDN的四周年创作纪念日
  • C++ Reference: Standard C++ Library reference: C Library: clocale: struct lconv
  • JavaSE进阶--集合(2万字总结)
  • CKA考题 [k8s1.21]
  • AcWing第 70 场周赛题解
  • 读FFA-net: Feature Fusion Attention Network for Single Image Dehazing
  • 测试需求平台4-Flask实现API服务入门实战
  • js单行代码-----dom
  • (十五)java多线程之并发集合ArrayBlockingQueue
  • ➹使用webpack配置多页面应用(MPA)
  • Android 架构优化~MVP 架构改造
  • Android框架之Volley
  • ES6, React, Redux, Webpack写的一个爬 GitHub 的网页
  • HTTP请求重发
  • Java精华积累：初学者都应该搞懂的问题
  • JS基础之数据类型、对象、原型、原型链、继承
  • Solarized Scheme
  • Wamp集成环境 添加PHP的新版本
  • Webpack 4x 之路 （ 四 ）
  • web标准化（下）
  • 从@property说起（二）当我们写下@property (nonatomic, weak) id obj时，我们究竟写了什么...
  • 大数据与云计算学习：数据分析（二）
  • - 概述 - 《设计模式（极简c++版）》
  • 蓝海存储开关机注意事项总结
  • 力扣(LeetCode)21
  • 普通函数和构造函数的区别
  • 使用iElevator.js模拟segmentfault的文章标题导航
  • 使用SAX解析XML
  • 提升用户体验的利器——使用Vue-Occupy实现占位效果
  • 微信如何实现自动跳转到用其他浏览器打开指定页面下载APP
  • Android开发者必备：推荐一款助力开发的开源APP
  • 昨天1024程序员节，我故意写了个死循环~
  • ​油烟净化器电源安全，保障健康餐饮生活
  • ## 临床数据 两两比较 加显著性boxplot加显著性
  • #1014 : Trie树
  • #git 撤消对文件的更改
  • #NOIP 2014#Day.2 T3 解方程
  • ＃在线报价接单​再坚持一下 明天是真的周六.出现货 实单来谈
  • $emit传递多个参数_PPC和MIPS指令集下二进制代码中函数参数个数的识别方法
  • （10）STL算法之搜索（二） 二分查找
  • (webRTC、RecordRTC):navigator.mediaDevices undefined
  • （附源码）spring boot建达集团公司平台 毕业设计 141538
  • (附源码)springboot课程在线考试系统 毕业设计 655127
  • （每日持续更新）信息系统项目管理（第四版）（高级项目管理）考试重点整理 第13章 项目资源管理（七）
  • （转）http-server应用
  • （转载）虚幻引擎3--【UnrealScript教程】章节一：20.location和rotation
  • .NET Micro Framework 4.2 beta 源码探析
  • .NET Standard 支持的 .NET Framework 和 .NET Core