算法练习小技巧之有序集合--套路详细解析带例题(leetcode)

本文主要是介绍算法练习小技巧之有序集合--套路详细解析带例题(leetcode),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言:

        本文详细讲解Python中的有序集合SortedList和C++中的有序集合multiset的用法,配合leetcode的例题来展示实际的用处。(本人水平不够,还无法讲解有序集合的实现方法,只会用)

        觉得有帮助或者写的不错可以点个赞,后面也有几道我找出来的题目可以用这个方法快速解决的

        (感觉有点水)

目录

有序集合用法讲解:

C++:

Python:

例题一:

题目描述和解题思路:

代码(C++):

代码(Python):

例题二:

题目描述和解题思路:

代码(Python):

一些可以用有序集合解的题目:


有序集合用法讲解:

(有序集合提供了有序性,但不够高效,可以简化代码,但慎用,比如例题二C++用就会超时)

C++:

        std::multiset 是来自 #include <set> 头文件

        可以高效的插入,删除,查找元素,插入进入的元素可以自动排序(升序排列),允许重复的元素

#include <iostream>
#include <set>int main() {std::multiset<int> A;A.insert(4);A.insert(1);A.insert(3);A.insert(2);for (auto& a : A) {std::cout << a << " "; //输出1 2 3 4}
}

Python:

        SortedList 类是由 sortedcontainers 库提供的     

        注意这里的sortedcontainers 库是第三方库,使用的时候需要下载,在codeforces,atcoder等平台无法使用,但在leetcode里面可以使用

下载方法,在命令行输入: pip install sortedcontainers

 如图:

        

from sortedcontainers import SortedListdef main():A = SortedList()A.add(4)A.add(1)A.add(3)A.add(2)for a in A:print(a, end=' ')  # 输出1 2 3 4if __name__ == "__main__":main()

例题一:

LCR 057. 存在重复元素 III - 力扣(LeetCode)

题目描述和解题思路:

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j,使得 abs(nums[i] - nums[j]) <= t ,同时又满足 abs(i - j) <= k 

如果存在则返回 true,不存在返回 false

在一个长度为k的滑动窗口中,通过 lower_bound 查找当前元素减去 (t) 的位置,并判断此位置的元素是否满足条件即可

if (pos != window.end() && *pos <= (long long)(nums[i]) + t) 

位置在集合中,并且元素满足条件

代码(C++):

class Solution {
public:bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {if (k <= 0 || t < 0) return false;multiset<long long> window;for (int i = 0; i < nums.size(); ++i) {if (i > k) {window.erase(window.find(nums[i - k - 1]));}auto pos = window.lower_bound((long long)(nums[i]) - t);if (pos != window.end() && *pos <= (long long)(nums[i]) + t) {return true;}window.insert(nums[i]);}return false;}
};

代码(Python):

from sortedcontainers import SortedListclass Solution:def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:if k <= 0 or t < 0:return Falsewindow = SortedList()for i in range(len(nums)):if i > k:window.remove(nums[i - k - 1])pos = window.bisect_left(nums[i] - t)if pos < len(window) and window[pos] <= nums[i] + t:return Truewindow.add(nums[i])return False

例题二:

LCR 170. 交易逆序对的总数 - 力扣(LeetCode)


题目描述和解题思路:

在股票交易中,如果前一天的股价高于后一天的股价,则可以认为存在一个「交易逆序对」。请设计一个程序,输入一段时间内的股票交易记录 record,返回其中存在的「交易逆序对」总数。

示例 1:

输入:record = [9, 7, 5, 4, 6]
输出:8
解释:交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

很难想象这是一个困难题,不过官方的题解确实有点难度:

官方题解:

LCR 170. 交易逆序对的总数 - 力扣(LeetCode)

我的做法:

创建一个有序集合,从后往前遍历,将此时的元素插入有序集合

继续遍历,由于是有序的,可以用二分查找,查找元素在集合中的位置,也就是对于当前这个元素,集合中有多少元素比它小即可

(好像说的有点抽象了)

代码(Python):

from sortedcontainers import SortedListclass Solution:def reversePairs(self, record: List[int]) -> int:sorted_list = SortedList()count = 0for price in reversed(record):count += sorted_list.bisect_left(price)sorted_list.add(price)return count

一些可以用有序集合解的题目:

Problem - C - Codeforces 

Problem - 1249B2 - Codeforces
Problem - 1454C - Codeforces

456. 132 模式 - 力扣(LeetCode)

1818. 绝对差值和 - 力扣(LeetCode)

2653. 滑动子数组的美丽值 - 力扣(LeetCode)

这篇关于算法练习小技巧之有序集合--套路详细解析带例题(leetcode)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1146459

相关文章

深度解析Java DTO(最新推荐)

《深度解析JavaDTO(最新推荐)》DTO(DataTransferObject)是一种用于在不同层(如Controller层、Service层)之间传输数据的对象设计模式,其核心目的是封装数据,... 目录一、什么是DTO?DTO的核心特点:二、为什么需要DTO?(对比Entity)三、实际应用场景解析

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

SpringBoot整合liteflow的详细过程

《SpringBoot整合liteflow的详细过程》:本文主要介绍SpringBoot整合liteflow的详细过程,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋...  liteflow 是什么? 能做什么?总之一句话:能帮你规范写代码逻辑 ,编排并解耦业务逻辑,代码

浏览器插件cursor实现自动注册、续杯的详细过程

《浏览器插件cursor实现自动注册、续杯的详细过程》Cursor简易注册助手脚本通过自动化邮箱填写和验证码获取流程,大大简化了Cursor的注册过程,它不仅提高了注册效率,还通过友好的用户界面和详细... 目录前言功能概述使用方法安装脚本使用流程邮箱输入页面验证码页面实战演示技术实现核心功能实现1. 随机

使用Python绘制3D堆叠条形图全解析

《使用Python绘制3D堆叠条形图全解析》在数据可视化的工具箱里,3D图表总能带来眼前一亮的效果,本文就来和大家聊聊如何使用Python实现绘制3D堆叠条形图,感兴趣的小伙伴可以了解下... 目录为什么选择 3D 堆叠条形图代码实现:从数据到 3D 世界的搭建核心代码逐行解析细节优化应用场景:3D 堆叠图

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器(Decorator)是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决