力扣 第 122 场双周赛 解题报告 | 珂学家 | 脑筋急转弯 + 滑窗反悔堆


前言

image.png


整体评价

倒开差点崩盘,T4这个反悔堆写吐了,T3往众数上去猜了,幸好case良心。


T1. 将数组分成最小总代价的子数组 I

思路: 取 nums[1:] 的最小2个值

可以部分排序,这样更快捷

class Solution {
    public int minimumCost(int[] nums) {
        Arrays.sort(nums, 1, nums.length);
        return nums[0] + nums[1] + nums[2];
    }
}

T2. 判断一个数组是否可以变为有序

思路: 分组分段排序

把连续同构子数组排序(同构即1的个数相同)

最后验证一把即可

class Solution {
    public boolean canSortArray(int[] nums) {
        // 分组分段排序
        int n = nums.length;
        int i = 0;
        while (i < n) {
            int j = i + 1;
            while (j < n && Integer.bitCount(nums[j - 1]) == Integer.bitCount(nums[j])) {
                j++;
            }
            Arrays.sort(nums, i, j);
            i = j;
        }
        
        // 最后验证下
        for (i = 0; i < n - 1; i++) {
            if (nums[i] > nums[i + 1]) return false;
        }
        return true;
    }
}

T3. 通过操作使数组长度最小

思路: 找规律, 从最小数切入

可以发现:

小数可以剔除大数 小数可以剔除大数 小数可以剔除大数

比如 a , b 两数 ( a < b ) , 则 a   m o d   b = a , 相当于单独剔除 b , 保留小数 a a,b两数(a\lt b), 则 a\ mod\ b = a, 相当于单独剔除b, 保留小数a a,b两数(a<b),a mod b=a,相当于单独剔除b,保留小数a

那大数可以剔除小数呢? 那大数可以剔除小数呢? 那大数可以剔除小数呢?

  • a , b ( a < b ) , a   m o d   b ≠ 0 , 则构建了更小的数 c ( c < a ) a,b(a\lt b), a\ mod\ b \ne 0, 则构建了更小的数c(c\lt a) a,b(a<b),a mod b=0,则构建了更小的数c(c<a)
  • a , b ( a < b ) , a   m o d   b = 0 , 则不行 a,b(a\lt b), a\ mod\ b = 0, 则不行 a,b(a<b),a mod b=0,则不行

令最小值为v,个数为m

如果存在一个数,其余最小数不为0,则结果为1

如果不存在这样的数,则结果为 ( m + 1 ) / 2 (m+1)/2 (m+1)/2

class Solution {
    public int minimumArrayLength(int[] nums) {
        if (nums.length <= 2) return 1;
        
        int minV = Arrays.stream(nums).min().getAsInt();
        
        int minNum = 0;
        for (int v: nums) {
            // 存在一个数可以构造更小的数
            if (v % minV != 0) return 1;
            else if (v == minV) minNum++;
        }
        
        return (minNum + 1) / 2;
    }
}

T4. 将数组分成最小总代价的子数组 II

思路: 反悔堆

划分型DP只是幌子,核心是

滑窗区间 ( d i s t ) 内的最小 k − 1 个数之和 滑窗区间(dist)内的最小k-1个数之和 滑窗区间(dist)内的最小k1个数之和

这个过程中,有旧数据的滑出,有新数据的滑入,还有实时更新k-1个最小和。

除了滑窗的框架,还需要额外引入

对顶堆 对顶堆 对顶堆

即原先k-1最小的集合元素,因窗口挪动,被更小的新值替换(非窗口有效范围原因)

class Solution {

    public long minimumCost(int[] nums, int k, int dist) {
        long inf = Long.MAX_VALUE;
        long ans = inf;

        long res = nums[0];
        int n = nums.length;
        int cnt = 1;

        // 两者构建对顶堆
        // 候选堆(最小堆)
        PriorityQueue<int[]> minPq = new PriorityQueue<>(Comparator.comparing(x -> x[0]));
        // k-1集合堆(最大堆)
        PriorityQueue<int[]> maxPq = new PriorityQueue<>(Comparator.comparing(x -> -x[0]));

        for (int i = 1; i <= dist + 1; i++) {
            minPq.offer(new int[] {nums[i], i});
        }

        boolean[] vis = new boolean[n];
        while (cnt < k) {
            int[] cur = minPq.poll();
            res += cur[0];
            vis[cur[1]] = true;
            maxPq.offer(new int[] {cur[0], cur[1]});
            cnt++;
        }
        ans = Math.min(ans, res);

        for (int i = 1; i + 1 + dist < n; i++) {
            // 滑窗
            if (vis[i] == true) {
                cnt--;
                res -= nums[i];
            }

            minPq.offer(new int[] {nums[i + 1 + dist], i + 1 + dist});
            // 保证k-1大小
            while (cnt < k && !minPq.isEmpty()) {
                int[] cur = minPq.poll();
                // 惰性删除
                if (cur[1] <= i) continue;
                vis[cur[1]] = true;
                res += cur[0];
                cnt++;
                maxPq.offer(cur);
            }

            while (!maxPq.isEmpty() && !minPq.isEmpty()) {
                // 惰性删除
                int[] cur2 = maxPq.peek();
                if (cur2[1] <= i) {
                    maxPq.poll();
                    continue;
                }
                // 惰性删除
                int[] cur1 = minPq.peek();
                if (cur1[1] <= i) {
                    minPq.poll();
                    continue;
                }

                if (cur1[0] >= cur2[0]) break;

                // 反悔核心逻辑
                res = res + cur1[0] - cur2[0];
                vis[cur1[1]] = true;
                vis[cur2[1]] = false;
                minPq.poll();
                maxPq.poll();
                maxPq.offer(cur1);
                minPq.offer(cur2);
            }

            ans = Math.min(ans, res);
        }

        return ans;
    }
}

写在最后

image.png

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/337748.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

WorkPlus:构建高效协作的企业即时通讯解决方案

在现代企业中&#xff0c;高效沟通是实现协作和改善工作效率的关键。而企业即时通讯工具成为了推进沟通的利器。作为一款高质量的企业即时通讯解决方案&#xff0c;WorkPlus以其卓越的性能和独特的功能&#xff0c;助力企业构建高效协作的新格局。 为什么选择WorkPlus作为企业即…

一文读懂「RAG,Retrieval-Augmented Generation」检索增强生成

Retrieval-Augmented Generation&#xff08;RAG&#xff09;作为机器学习和自然语言处理领域的一大创新&#xff0c;不仅代表了技术的进步&#xff0c;更在实际应用中展示了其惊人的潜力。 RAG结合了检索&#xff08;Retrieval&#xff09;和生成&#xff08;Generation&#…

windows Server 退域操作

要将运行Windows Server 2003的域控制器从Active Directory环境中退出&#xff08;降级&#xff09;&#xff0c;您需要按照以下步骤操作&#xff1a; ### 步骤1&#xff1a;转移角色与功能 - 如果这台服务器拥有任何活动目录角色&#xff0c;如FSMO&#xff08; Flexible Sin…

AI教我学编程之C#类的实例化与访问修饰符

前言 在这篇文章中&#xff0c;我将带大家深入了解C#编程语言的核心概念&#xff0c;包括类的实例化、访问修饰符的应用&#xff0c;以及C#中不同数据类型的默认值。我会通过逐步分析和具体实例&#xff0c;详细解释如何在C#中正确创建和操作对象&#xff0c;并探讨如何通过访…

设计模式——装饰者模式

更多内容&#xff0c;前往 IT-BLOG 现实生活中常常需要给某类产品动态增加新的功能&#xff0c;如&#xff1a;给面条各种调味品。在软件开发过程中&#xff0c;有时想用一些现存的组件。这些组件可能只是完成一些核心功能。但在不改变其架构的情况下&#xff0c;可以动态地扩展…

Java毕业设计-基于jsp+servlet的大学生学业规划咨询服务平台管理系统-第84期

获取源码资料&#xff0c;请移步从戎源码网&#xff1a;从戎源码网_专业的计算机毕业设计网站 项目介绍 基于jspservlet的大学生学业规划咨询服务平台管理系统&#xff1a;前端 jsp、jquery、ajax&#xff0c;后端 servlet、jdbc&#xff0c;角色分为管理员、学生&#xff1b…

C++ :命名空间域

目录 冲突与命名&#xff1a; 举个例子&#xff1a; 全局与局部&#xff1a; 域作用限定符&#xff1a; 命名空间域&#xff1a; 冲突与命名&#xff1a; 在C语言中&#xff0c;我们通常会使用stdlib.h 而stdlib.h 本质上是一个函数的库&#xff0c;在程序中使用的大多数…

C++(14)——string的模拟实现

前几篇文章中介绍了关于以及其相关函数的使用&#xff0c;为了更清楚的了解这些函数的作用&#xff0c;本篇文章通过模拟实现的方式来加深对于函数作用原理的理解。 目录 1. String的整体框架&#xff1a; 1.1 成员变量&#xff1a; 1.2 构造函数&#xff1a; 1.3 析构函数…

第十一站:多态练习ODU

实现动态切换 ODU.h #pragma once #include <iostream> using namespace std; #define ODU_TYPE_311_FLAG "311" #define ODU_TYPE_335_FLAG "335" enum class ODU_TYPE {ODU_TYPE_311,ODU_TYPE_335,ODU_TYPE_UNKNOW };class ODU{ public:ODU();//发…

Elasticsearch的映射操作

本文来记录下Elasticsearch的映射操作 文章目录 映射的概述 映射的概述 Elasticsearch与mysql数据库对比 映射的概述 有了索引库&#xff0c;等于有了数据库中的 database。索引库(index)中的映射&#xff0c;类似于数据库(database)中的表结构(table)。创建数据库表需要设置字…

SpringBoot实现文件上传和下载实现全过程(值得珍藏)

1. 引言 在Web应用中&#xff0c;文件上传和下载是常见的需求。Spring Boot框架提供了强大的支持和便利的API&#xff0c;使得开发者可以轻松地实现文件上传和下载功能。本文将详细介绍如何在Spring Boot应用中实现文件上传和下载&#xff0c;包括实现原理和完整的代码示例。 …

【js】js 异步机制详解 Generator / Async / Promise

三种语法功能放在一起&#xff0c;是因为他们都有相似特点&#xff1a; 维护某种状态在未来恢复状态并执行 本文重点回答以下几个问题&#xff1a; 为什么 Generator 和 Async 函数的 代码执行流 都可以简化成树形结构&#xff1f;async 函数为什么返回一个 promise&#xf…

list下

文章目录 注意&#xff1a;const迭代器怎么写&#xff1f;运用场合&#xff1f; inserterase析构函数赋值和拷贝构造区别&#xff1f;拷贝构造不能写那个swap,为什么&#xff1f;拷贝构造代码 面试问题什么是迭代器失效&#xff1f;vector、list的区别&#xff1f; 完整代码 注…

3、非数值型的分类变量

非数值型的分类变量 有很多非数字的数据,这里介绍如何使用它来进行机器学习。 在本教程中,您将了解什么是分类变量,以及处理此类数据的三种方法。 本课程所需数据集夸克网盘下载链接:https://pan.quark.cn/s/9b4e9a1246b2 提取码:uDzP 文章目录 1、简介2、三种方法的使用1…

idea运行卡顿优化方案

文章目录 前言一、调整配置1. idea.properties2. idea.vmoptions3.heap size4.Plugins5.Inspections 总结 前言 本人电脑16G内存&#xff0c;处理器i7 10代&#xff0c;磁盘空间也够用&#xff0c;整体配置够用&#xff0c;但运行idea会很卡&#xff0c;记录优化过程&#xff…

Linux中关于head命令详解

head的作用 head用于查看文件的开头部分的内容。 head的参数 -q隐藏文件名-v 显示文件名-c<数目>显示的字节数-n<数目>显示的行数 head的案例 # 查看yum.log前五行内容 head -5 yum.log

文件操作和IO(1)

认识文件 先来认识狭义上的文件(存储在硬盘(磁盘)上).针对硬盘这种持久化的I/O设备,当我们想要进行数据保存时,往往不是保存成一个整体,而是独立成一个个的单位进行保存,这个独立的单位就被抽象成文件的概念,就类似办公桌上的一份份真实的文件一般. 注意:硬盘 ! 磁盘 磁盘属于…

1885_Arduino 1306 OLED屏幕的使用

全部学习汇总&#xff1a; g_arduino: Arduino hack笔记 (gitee.com) 以前我基于Arduino做过一个环境信息采集的小工具&#xff0c;采集到的信息存储到SD卡中。当时的笔记&#xff1a; 341_Arduinopython分析天气变化导致颈椎病发的原因_颈椎病相关数据分析python-CSDN博客 以前…

Jan AI本地运行揭秘:首次体验,尝鲜科技前沿

&#x1f31f;&#x1f30c; 欢迎来到知识与创意的殿堂 — 远见阁小民的世界&#xff01;&#x1f680; &#x1f31f;&#x1f9ed; 在这里&#xff0c;我们一起探索技术的奥秘&#xff0c;一起在知识的海洋中遨游。 &#x1f31f;&#x1f9ed; 在这里&#xff0c;每个错误都…

关于Hive架构原理,尚硅谷

最近学习hive 时候&#xff0c;在做一个实操案例&#xff0c;具体大概是这样子的&#xff1a; 我在dataGip里建了一个表&#xff0c;然后在hadoop集群创建一个文本文件里面存储了数据库表的数据信息&#xff0c;然后把他上传到hdfs后&#xff0c;dataGrip那个表也同步了我上传到…