每日算法刷题Day31 6.14:leetcode二分答案2道题,结束二分答案,开始枚举技巧,用时1h10min

7. 1439.有序矩阵中的第K个最小数组和(困难,学习转化为373)

1439. 有序矩阵中的第 k 个最小数组和 - 力扣(LeetCode)

思想

1.给你一个 m * n 的矩阵 mat,以及一个整数 k ,矩阵中的每一行都以非递减的顺序排列。
你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。
2.转化为373.查找和最小的K对数字,利用最小堆,373是从两个数组找前K个,而此题是m*n矩阵,但是发现假设已经取完矩阵前两行的数组和,再考虑第3行时,只要考虑前两行数组前K个值即可(因为后面的不可能是最终的K个最小数组和),所以问题就转化为得到前面i-1行的最小K个数组和数组,然后第i行考虑进来,最终再得到一个最小K个数组和数组,实现行的压缩
3.初始数组为只有0元素的数组和第一行(表示取第一行前K个元素)

代码

c++:

class Solution {
public:vector<int> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {int n1 = nums1.size(), n2 = nums2.size();priority_queue<tuple<int, int, int>> pq;vector<int> res;for (int i = 0; i < min(n1, k); ++i) {pq.emplace(-nums1[i] - nums2[0], i,0); }while (!pq.empty() && res.size() < k) {auto t = pq.top();pq.pop();int i = get<1>(t), j = get<2>(t);res.push_back(nums1[i] + nums2[j]);if (j + 1 < n2)pq.emplace(-nums1[i] - nums2[j + 1], i,j + 1); }return res;}int kthSmallest(vector<vector<int>>& mat, int k) {int n = mat.size();vector<int> ini = {0};for (auto& row : mat) {ini = kSmallestPairs(row, ini, k);}return ini.back();}
};
8. 786. 第K个最小的质数分数(中等)
思想

1.给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 质数 组成,且其中所有整数互不相同。
对于每对满足 0 <= i < j < arr.length 的 i 和 j ,可以得到分数 arr[i] / arr[j] 。
那么第 k 个最小的分数是多少呢?  以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j] 。
2.依旧转化为373.查找和最小的K对数字,只不过nums2是倒序的arr,且多个条件i+j!=n-1

代码

c++:

class Solution {
public:vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {int n = arr.size();vector<int> arr2 = arr;vector<vector<int>> res;reverse(arr2.begin(), arr2.end());priority_queue<tuple<double, int, int>> pq;for (int i = 0; i < min(n - 1, k); ++i)pq.emplace(-1.0 * arr[i] / arr2[0], i, 0);while (res.size() < k && !pq.empty()) {auto t = pq.top();pq.pop();int i = get<1>(t), j = get<2>(t);if (i + j == n - 1)continue;res.push_back({arr[i], arr2[j]});if (j + 1 < n)pq.emplace(-1.0 * arr[i] / arr2[j + 1], i, j + 1);}return res.back();}
};

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

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

springMVC-13 文件下载及上传

文件下载-ResponseEntity<T> 说明 在SpringMVC中&#xff0c;通过返回ResponseEntity<T>的类型&#xff0c;可以实现文件下载的功能 核心代码&#xff1a;就是设置HttpHeader 文件下载响应头的设置 content-type 指示响应内容的格式 content…

数据库学习笔记(十六)--控住流程与游标

前言&#xff1a; 学习和使用数据库可以说是程序员必须具备能力&#xff0c;这里将更新关于MYSQL的使用讲解&#xff0c;大概应该会更新30篇&#xff0c;涵盖入门、进阶、高级(一些原理分析);这一篇和上一篇差不多&#xff0c;当做扩展&#xff0c;用到的时候再查即可(毕竟数据…

《Origin画百图》之核密度图

核密度图&#xff08;Kernel Density Plot&#xff09; 是一种用于展示数据分布形态的可视化工具&#xff0c;它通过平滑的曲线来估计数据的概率密度函数&#xff0c;相比直方图能更细腻地呈现数据的分布特征。 具体步骤&#xff1a; &#xff08;1&#xff09;选中数据&#…

使用Apache POI操作Word文档:从入门到实战

Apache POI是Java生态中最流行的Microsoft Office文档操作库之一&#xff0c;它为Word文档&#xff08;包括传统的.doc格式和现代的.docx格式&#xff09;提供了全面的API支持。本文将详细介绍如何使用Apache POI创建、读取和修改Word文档。 一、Apache POI简介与环境准备 1.…

CentOS 7.3环境中部署Kerberos集群

CentOS 7.3环境中部署Kerberos集群 文章目录 CentOS 7.3环境中部署Kerberos集群环境安装服务包 Kerberos MS 规划安装 KDC Master Server配置文件/etc/krb5.conf/var/kerberos/krb5kdc/kdc.conf/var/kerberos/krb5kdc/kadm5.acl 创建Kerberos数据库启动与停止服务创建管理员创建…

1 Studying《Arm A715 Software Optimization Guide》

目录 1 Introduction 1.1 Product revision status 1.2 Intended audience 1.3 Scope 1.4 Conventions 1.5 Useful resources 2 Overview 2.1 Pipeline overview 3 Instruction characteristics 3.1 Instruction tables 3.2 Legend for reading the utilized pipeli…

第二十四章 24.QoS(CCNA)

第二十四章 24.QoS(CCNA) 介绍了switch QoS的配置方法 注释&#xff1a; 学习资源是B站的CCNA by Sean_Ning CCNA 最新CCNA 200-301 视频教程(含免费实验环境&#xff09; PS&#xff1a;喜欢的可以去买下他的课程&#xff0c;不贵&#xff0c;讲的很细 To be continued……

什么是稳定币?

稳定币&#xff08;Stablecoin&#xff09;是一种特殊的加密货币&#xff0c;其核心目标是维持价格稳定&#xff0c;通常与某种稳定资产&#xff08;如美元、黄金等&#xff09;挂钩。 一、为什么需要稳定币&#xff1f; 普通加密货币&#xff08;如比特币、以太坊&#xff09…

伺服学习(IS620N)

DI 端子的基本概念 DI 端子是伺服驱动器上的数字输入接口&#xff0c;用于接收外部开关、按钮或PLC的24V/0V信号。每个端子的功能可通过参数灵活配置&#xff08;如启停、限位等&#xff09;。 核心要点 功能设置&#xff1a;通过驱动器参数组&#xff08;如H03&#xff09;…

基于Python的气象数据分析及可视化研究

目录 一.&#x1f981;前言二.&#x1f981;开源代码与组件使用情况说明三.&#x1f981;核心功能1. ✅算法设计2. ✅PyEcharts库3. ✅Flask框架4. ✅爬虫5. ✅部署项目 四.&#x1f981;演示效果1. 管理员模块1.1 用户管理 2. 用户模块2.1 登录系统2.2 查看实时数据2.3 查看天…

Excel处理控件Aspose.Cells教程:使用 C# 在 Excel 中应用数据验证

Excel 中的数据验证可确保用户在工作表中仅输入有效数据。在设计表单、收集数据或构建财务模型时&#xff0c;数据验证有助于维护结构并最大限度地减少用户错误。在本文中&#xff0c;我们将向您展示如何使用 C# 以编程方式在 Excel 中应用数据验证。 Aspose.Cells 最新版下载…

AI应用:计算机视觉相关技术总结

计算机视觉概述 计算机视觉&#xff08;Computer Vision, CV&#xff09;是一门让计算机从图像或视频中 “理解” 和 “解释” 视觉信息的技术&#xff0c;涉及多学科交叉&#xff08;如数学、统计学、机器学习、信号处理等&#xff09;。以下从技术体系、核心任务、关键技术、…

人口贩卖暑期威胁消解:算法协同提升安全预警

随着暑期的到来&#xff0c;人员流动加剧&#xff0c;人口贩卖等恶性犯罪活动进入高发阶段&#xff0c;景区、车站、商场等公共场所成为潜在风险区域。传统安防手段在应对此类隐蔽性强、危害性大的犯罪时显得力不从心。为此&#xff0c;引入基于视觉分析的多维度算法技术&#…

【DSP笔记 · 第3章】数字世界的“棱镜”:离散傅里叶变换(DFT)完全解析

数字世界的“棱镜”&#xff1a;离散傅里叶变换&#xff08;DFT&#xff09;完全解析 在上一章&#xff0c;我们探索了Z变换和离散时间傅里叶变换&#xff08;DTFT&#xff09;。我们知道&#xff0c;DTFT是一个无比强大的理论工具&#xff0c;它能将一个时域离散序列的“基因…

卷积神经网络的参数量及尺度变化计算

文章目录 前言1.卷积2.参数量的计算2.1案例一2.2案例二 3.奇怪的优化思想3.1使用小核卷积替换大核卷积3.2卷积核11的应用 4.输出图像尺寸的计算4.1Same convolution4.2具体计算规则4.3转置卷积 小结 前言 本篇博客主要介绍卷积基本概念&#xff0c;卷积神经网络的参数量计算、…

OpenCV——图像平滑

图像平滑 一、图像的噪声1.1、噪声来源1.2、噪声类型1.3、噪声模拟 二、滤波器三、线性滤波3.1、均值滤波3.2、方框滤波3.3、高斯滤波 四、非线性滤波4.1、中值滤波4.2、双边滤波 图像在采集和传输过程中容易受到各种因素的影响而产生噪声&#xff0c;而噪声会对图像的正确解读…

鸿蒙系统备份恢复

鸿蒙系统尝试者&#xff0c;在纯血鸿蒙与鸿蒙4.2/4.3之前反复横跳&#xff0c;中间折腾… 目录 鸿蒙4.2/4.3升级鸿蒙5.0系统备份 鸿蒙5.0回退鸿蒙4.2/4.3系统备份备份恢复 华为手机助手注意 鸿蒙4.2/4.3升级鸿蒙5.0 系统备份 云空间备份手机本地备份华为手机助手备份 鸿蒙5.…

JS进阶 Day03

1.两种面向编程思想 2.构造函数实现封装以及存在的问题 下面就引出了原型对象 3.原型对象prototype 共享原理图&#xff1a; 4.数组扩展案例-求最大值和数组求和 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><…

visual studio小番茄插件某些快捷键失效

问题 AltO 切换头文件和源文件失效。 背景 最近升级了 visual studio&#xff0c;多了一些插件 原因 Alt O 快捷键被其他插件占用了 解决方案 工具 → 选项 → 环境 → 键盘 搜索这个 VAssistX.OpenCorrespondingFile&#xff08;切换头/源文件&#xff09; 发现命令的快…

基于单片机的PT100温度变送器设计

基于单片机的PT100温度变送器设计 文章目录 基于单片机的PT100温度变送器设计前言一、资源分享二、系统框架三、硬件准备1.主控制器2、PT100温度传感器3、显示屏4、WIFI模块5、USB转RS485模块6、SP3485EN7、K11-11D3 四、设计PCB1、安装下载立创EDA专业版2、画原理图3、摆放元器…