【Leetcode 每日一题】3266. K 次乘运算后的最终数组 II
问题背景
给你一个整数数组 n u m s nums nums,一个整数 k k k 和一个整数 m u l t i p l i e r multiplier multiplier。
你需要对 n u m s nums nums 执行 k k k 次操作,每次操作中:
- 找到 n u m s nums nums 中的 最小 值 x x x,如果存在多个最小值,选择最 前面 的一个。
- 将 x x x 替换为 x × m u l t i p l i e r x \times multiplier x×multiplier。
请你返回执行完 k k k 次乘运算之后,最终的 n u m s nums nums 数组。
数据约束
- 1 ≤ n u m s . l e n g t h ≤ 1 0 4 1 \le nums.length \le 10 ^ 4 1≤nums.length≤104
- 1 ≤ n u m s [ i ] ≤ 1 0 9 1 \le nums[i] \le 10 ^ 9 1≤nums[i]≤109
- 1 ≤ k ≤ 1 0 9 1 \le k \le 10 ^ 9 1≤k≤109
- 1 ≤ m u l t i p l i e r ≤ 1 0 6 1 \le multiplier \le 10 ^ 6 1≤multiplier≤106
解题过程
题干和昨天一样,但是数据规模大了很多,暴力解一定会超时。
一般的做法 已经分析过了,算法上的重点还是堆模拟和 快速幂。
具体实现
class Solution {private static final int MOD = 1000000007;public int[] getFinalState(int[] nums, int k, int multiplier) {// 特判乘子为 1 的情形,避免多余的计算if(multiplier == 1) {return nums;}int n = nums.length;int max = 0;// 用最小堆来模拟操作,其中存储数组中每个元素和它的下标Queue<long[]> heap = new PriorityQueue<>((o1, o2) -> o1[0] != o2[0] ? Long.compare(o1[0], o2[0]) : Long.compare(o1[1], o2[1]));for(int i = 0; i < n; i++) {max = Math.max(max, nums[i]);heap.offer(new long[] {nums[i], i});}// 达到统一处理的条件之前,先进行若干次操作,更新堆for(; k > 0 && heap.peek()[0] < max; k--) {long[] cur = heap.poll();cur[0] *= multiplier;heap.offer(cur);}// 用快速幂计算结果,根据堆中的元素更新数组for(int i = 0; i < n; i++) {long[] cur = heap.poll();nums[(int) cur[1]] = (int) (cur[0] % MOD * pow(multiplier, k / n + (i < k % n ? 1 : 0)) % MOD);}return nums;}// 快速幂private long pow(long x, int n) {long res = 1;while(n != 0) {if((n & 1) == 1) {res = res * x % MOD;}x = x * x % MOD;n >>>= 1;}return res;}
}
相关文章:
【Leetcode 每日一题】3266. K 次乘运算后的最终数组 II
问题背景 给你一个整数数组 n u m s nums nums,一个整数 k k k 和一个整数 m u l t i p l i e r multiplier multiplier。 你需要对 n u m s nums nums 执行 k k k 次操作,每次操作中: 找到 n u m s nums nums 中的 最小 值 x x x&a…...
etcd集群常见日志
1、节点失去领导者 {"level":"info","ts":"2024-05-07T01:54:04.948Z","logger":"raft","caller":"etcdserver/zap_raft.go:77","msg":"raft.node: 9afce9447872453 lost le…...
【漫话机器学习系列】005.神经网络的结构(architecture on the neural network)
神经网络(Neural Network)是一种模拟人脑神经系统的计算模型,由大量相互连接的神经元(节点)组成,广泛应用于深度学习和机器学习领域。以下是神经网络的基本结构及关键组成部分。 1. 神经网络的基本组成 一…...
基于 Couchbase 数据仓库元数据管理的可行性方案
在大数据体系中,元数据管理是数据治理的关键一环。以下是一套元数据管理的可行性方案,适合你的当前架构设计(基于 Couchbase 数据仓库)并支持高效管理数据的分层与结构。 1. 元数据管理的目标 统一数据管理:清晰描述 …...
SpringBoot:快速构建微服务应用
一、SpringBoot简介 什么是SpringBoot 是由Pivotal团队提供的快速开发框架。它基于Spring框架,可以用于快速构建微服务应用程序。SpringBoot提供了一种快速、便捷的方式来启动和配置一个基于Spring的应用程序,它封装了很多常用的配置,简化了开…...
汽车嵌入式软件构建高效技术团队的全面思考
在汽车嵌入式软件开发领域,构建一支高效的通用技术团队至关重要。这类团队负责为各种项目提供可复用、标准化的技术基石,从而提高开发效率、降低成本并确保产品质量。构建这样的团队需要从技术能力、角色分工、标准化与复用、流程管理与质量保证、工具和…...
【跨库查询、多库查询】.NET开源 ORM 框架 SqlSugar 系列
文章目录 一、跨库方式1:跨库导航二、手动跨库查询三、同服务器:自动查询跨库查询3.1 Mysql和SqlServer自动3.2 自动: PgSql跨Scheme查询3.3 其他库同服务器 四、跨服务器:自动跨库查询4.1 配置SqlServer dblink4.2 配置 Oracle dblink4.3 配…...
智能人体安全防护:3D 视觉技术原理、系统架构与代码实现剖析
随着工业化程度的提高,生产安全已成为企业关注的重点。尤其是在一些存在禁区的工业厂区和车间,人员误入或违规进入将带来严重的安全隐患。为了解决这一问题,迈尔微视推出了智能人体安全检测解决方案,为企业提供全方位的人员安全监…...
第24周:文献阅读
目录 摘要 Abstract 一、现有问题 二、提出方法 三、创新点 模型结构创新 强化学习与GAN结合 属性特征与通顺性优化 四、方法论 生成对抗网络(GAN) 强化学习(RL) 模型组件 五、实验研究 数据集 数据预处理 评价指…...
yolov8 转华为昇腾om脚本
目录 yolov8 转华为昇腾 om脚本 测试ok 推理demo: yolov8 转华为昇腾 om脚本 测试ok import sys import osos.chdir(os.path.dirname(os.path.abspath(__file__)))import torchcurrent_dir = os.path.dirname(os.path.abspath(__file__))paths = [os.path.abspath(__file__)…...
分布式事物XA、BASE、TCC、SAGA、AT
分布式事务——Seata 一、Seata的架构: 1、什么是Seata: 它是一款分布式事务解决方案。官网查看:Seata 2.执行过程 在分布式事务中,会有一个入口方法去调用各个微服务,每一个微服务都有一个分支事务,因…...
域名信息收集(小迪网络安全笔记~
附:完整笔记目录~ ps:本人小白,笔记均在个人理解基础上整理,若有错误欢迎指正! 2.1 域名信息收集 引子:上一章介绍了服务器的信息收集。本篇则介绍在面对存在Web资产企业时,其域名信息该如何收…...
力扣-图论-13【算法学习day.63】
前言 ###我做这类文章一个重要的目的还是给正在学习的大家提供方向和记录学习过程(例如想要掌握基础用法,该刷哪些题?)我的解析也不会做的非常详细,只会提供思路和一些关键点,力扣上的大佬们的题解质量是非…...
【设计模式】如何用C++实现观察者模式【发布订阅机制】
【设计模式】如何用C实现观察者模式【发布订阅机制】 一、问题背景 代码质量影响生活质量。最近工作中频繁接触各种设计模式,深刻体会到优秀的设计模式不仅能显著降低后续维护的压力,还能提升开发效率。观察者模式作为一种降低耦合度、提高扩展性的利器…...
【LC】2717. 半有序排列
题目描述: 给你一个下标从 0 开始、长度为 n 的整数排列 nums 。 如果排列的第一个数字等于 1 且最后一个数字等于 n ,则称其为 半有序排列 。你可以执行多次下述操作,直到将 nums 变成一个 半有序排列 : 选择 nums 中相邻的两…...
AI智算-k8s部署大语言模型管理工具Ollama
文章目录 简介k8s部署OllamaOpen WebUI访问Open-WebUI 简介 Github:https://github.com/ollama/ollama 官网:https://ollama.com/ API:https://github.com/ollama/ollama/blob/main/docs/api.md Ollama 是一个基于 Go 语言开发的可以本地运…...
CloudberryDB(二) 演化路线图
CloudberryDB 制定了演化路线图(https://github.com/orgs/cloudberrydb/discussions/369)并在逐步改进,这是 Cloudberry Database 发挥独特价值之处。 计划、正在进行或已完成的一些工作。 支持轻松升级 PostgreSQL 内核版本。 原有 Greenp…...
《拉依达的嵌入式\驱动面试宝典》—C/CPP基础篇(二)
《拉依达的嵌入式\驱动面试宝典》—C/CPP基础篇(二) 你好,我是拉依达。 感谢所有阅读关注我的同学支持,目前博客累计阅读 27w,关注1.5w人。其中博客《最全Linux驱动开发全流程详细解析(持续更新)-CSDN博客》已经是 Linux驱动 相关内容搜索的推荐首位,感谢大家支持。 《拉…...
实现canal监控binlog日志再通过消息队列异步处理
一、简单步骤 实现Canal监控Binlog日志,并通过消息队列进行异步处理,步骤如下: 配置Canal:首先,需要配置Canal进行Binlog日志监控。可以通过Canal的官方文档了解如何配置Canal。 连接到Canal:使用Canal客户…...
Linux DNS 协议概述
1. DNS 概述 互联网中,一台计算机与其他计算机通信时,通过 IP 地址唯一的标志自己。此时的 IP 地址就类似于我们日常生活中的电话号码。但是,这种纯数字的标识是比较难记忆的,而且数量也比较庞大。例如,每个 IPv4 地址…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...
