首页 > 编程语言 >算法练习小技巧之有序集合--套路详细解析带例题(leetcode)

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

时间:2024-09-06 15:51:02浏览次数:14  
标签:nums -- pos int window 集合 例题 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 SortedList

def 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 4

if __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 SortedList

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        if k <= 0 or t < 0:
            return False

        window = 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 True

            window.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 SortedList

class Solution:
    def reversePairs(self, record: List[int]) -> int:
        sorted_list = SortedList()
        count = 0
        for 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)

标签:nums,--,pos,int,window,集合,例题,leetcode
From: https://blog.csdn.net/2401_83669813/article/details/141946351

相关文章

  • 像花儿一样绽放
    Music:悲伤的秋千之前写了这么多鸡汤,其实我的本意并不如此不是刻意想把这里打造成一个心灵blog,可成长也是生命中最重要的环节今天没有鸡汤,发一些我的摄影作品吧~^_^(我可是多才多艺的哦,O(∩_∩)O哈哈~)像花儿一样绽放吧^_^......
  • 电话机器人外呼系统效果好吗
    嘉单科技yyzkd8电话机器人外呼系统是现在市面上的一款帮你代替真人自动拨打电话,自动筛选客户的一个软件。简单来说就是帮你把打出来的意向客户自动推送到你的微信上面,你人工重点跟进有意向的客户就可以了。嘉单科技电话机器人外呼系统好用吗?效果怎么样?①高效率低成本:电话......
  • 测试驱动开发(TDD)学习分享-上篇
    1.概述1.1什么是TDD测试驱动开发(TDD)是一种增量式软件开发技术。简单地说,就是在没有失败的单元测试的前提下不可以写产品代码。这些测试要很小,而且要自动化。用测试来驱动其实很合理。相对于直接写产品代码,TDD的实践者们会先用测试来表达他们希望产品代码会有什么样的行......
  • 简单实现限流中间件
    本文由ChatMoney团队出品引言在现代Web应用开发中,限流是一个重要的概念,它能够保护服务器免受流量攻击,确保服务的稳定性和可用性。Go语言以其高性能和并发处理能力在后端服务开发中广受欢迎。Gin是一个使用Go语言编写的Web框架,以其简洁和高效著称。在Gin框架中,通过中间件实现......
  • cron 表达式与crontab表达式详解
    转:https://zhuanlan.zhihu.com/p/614584979引言CRON表达式详解(阿里巴巴)我们在定时任务中经常能接触到cron表达式,但是在写cron表达式的时候我们会遇到各种各样版本的cron表达式,比如我遇到过5位、6位甚至7位的cron表达式,导致我一度搞混这些表达式。更严重的是,当我们没有准确写出......
  • 【2024年】6款搭建AI知识库的最佳SaaS软件
    现如今,越来越多的企业开始意识到搭建高效、智能的AI知识库是非常重要的,并在不断了解和搭建AI知识库。如何高效搭建出有效的AI知识库是很多企业存在的问题。在2024年,有哪些SaaS软件是搭建AI知识库的最佳软件呢?本文将推荐6个用于搭建AI知识库的最佳SaaS软件。1.HelpLookAI......
  • 9月12日云技术研讨会 | ECU电控软件开发及测试全流程解决方案
        “软件定义汽车”时代洪流下,电子电气架构往集中式发展已是大势所趋,控制器功能呈现出集中化、复杂化的特点,基于AutoSar架构开发复杂软件已成为行业共识。再加上ASPICE、ISO26262等过程体系和法规标准的要求,如何开发符合AutoSar架构的应用软件、评估软件质量和性能、优化......
  • 车载以太网交换机入门基本功(4)—优先级设计与VLAN测试
        在《车载以太网交换机入门基本功(3)》介绍了交换机端口属性和实际的VLAN转发过程。但是,当存在多个待转发的报文时,既要考虑到报文的及时性,又要考虑到转发效率,因此,如何进行有效调度就成了重要问题。一个解决办法是进行优先级设计。优先级设计    优先级设计包括报......
  • 实现中间件限流的简单方法
    本文由ChatMoney团队出品引言在现代Web应用开发中,限流是一个重要的概念,它能够保护服务器免受流量攻击,确保服务的稳定性和可用性。Go语言以其高性能和并发处理能力在后端服务开发中广受欢迎。Gin是一个使用Go语言编写的Web框架,以其简洁和高效著称。在Gin框架中,通过中间件实现......
  • 大模型微调使GPT3成为了可以聊天发布指令的ChatGPT
    你好,开始一种新的尝试,准备聊聊“大语言模型入门”。字少总结版本聊天大模型在通用大模型的基础上加一层微调就实现人人能用的大模型。使得通用大模型的能力被更多人使用和了解。大模型微调(Fine-tuning)是指在已经训练好的大模型基础上,进一步在特定任务或数据集上进行训练,以便让......