[LeetCode 1237]找出给定方程的正整数解
题目描述
题目链接:[LeetCode 1237]找出给定方程的正整数解
给你一个函数 f(x, y) 和一个目标结果 z,函数公式未知,请你计算方程 f(x,y) == z 所有可能的正整数 数对 x 和 y。满足条件的结果数对可以按任意顺序返回。
尽管函数的具体式子未知,但它是单调递增函数,也就是说:
- f(x, y) < f(x + 1, y)
- f(x, y) < f(x, y + 1)
函数接口定义如下:
interface CustomFunction {
public:// Returns some positive integer f(x, y) for two positive integers x and y based on a formula.int f(int x, int y);
};
你的解决方案将按如下规则进行评判:
- 判题程序有一个由 CustomFunction 的 9 种实现组成的列表,以及一种为特定的 z 生成所有有效数对的答案的方法。
- 判题程序接受两个输入:function_id(决定使用哪种实现测试你的代码)以及目标结果 z 。
- 判题程序将会调用你实现的 findSolution 并将你的结果与答案进行比较。
- 如果你的结果与答案相符,那么解决方案将被视作正确答案,即 Accepted 。
示例1
输入:function_id = 1, z = 5
输出:[[1,4],[2,3],[3,2],[4,1]]
解释:function_id = 1 暗含的函数式子为 f(x, y) = x + y
以下 x 和 y 满足 f(x, y) 等于 5:
x=1, y=4 -> f(1, 4) = 1 + 4 = 5
x=2, y=3 -> f(2, 3) = 2 + 3 = 5
x=3, y=2 -> f(3, 2) = 3 + 2 = 5
x=4, y=1 -> f(4, 1) = 4 + 1 = 5
示例2
输入:function_id = 2, z = 5
输出:[[1,5],[5,1]]
解释:function_id = 2 暗含的函数式子为 f(x, y) = x * y
以下 x 和 y 满足 f(x, y) 等于 5:
x=1, y=5 -> f(1, 5) = 1 * 5 = 5
x=5, y=1 -> f(5, 1) = 5 * 1 = 5
提示
- 1 <= function_id <= 9
- 1 <= z <= 100
- 题目保证 f(x, y) == z 的解处于 1 <= x, y <= 1000 的范围内。
- 在 1 <= x, y <= 1000 的前提下,题目保证 f(x, y) 是一个 32 位有符号整数。
思路分析
1.题目描述很不清晰,尤其是引入这个function_id
完全可以不用管这个function_id,其实就是告诉你我有九个这样的函数,函数都具有单调递增的性质,那我管你几个函数,只需要知道函数的性质就好了!
2.x,y都为1000,问题规模卡在n^2级别,看到单调,第一反应想到的就是二分
3.但是对于两个维度x和y来说很麻烦,所以我们可以固定一个维度,从这个维度上看,就是一个一维的单调递增函数,如图所示:固定住x,比如x=0,那么这个维度上,y就是单调递增的,所以可以通过枚举x,然后在每个维度上二分y来做,复杂度是O(nlogn) < O(n2n^2n2)

代码
class Solution {
public:vector<vector<int>> findSolution(CustomFunction& c, int z) {vector<vector<int>> res;//遍历xfor (int x = 1; x <= 1000; x++) {//二分yint l = 1, r = 1000;while(l < r) {int mid = (l + r) >> 1;if(c.f(x, mid) >= z) r = mid;else l = mid + 1;}//如果二分出来的点是零点,那么保存答案if(c.f(x, l) == z) res.push_back({x, l});}return res;}
};
相关文章:
[LeetCode 1237]找出给定方程的正整数解
题目描述 题目链接:[LeetCode 1237]找出给定方程的正整数解 给你一个函数 f(x, y) 和一个目标结果 z,函数公式未知,请你计算方程 f(x,y) z 所有可能的正整数 数对 x 和 y。满足条件的结果数对可以按任意顺序返回。 尽管函数的具体式子未知…...
6.2 构建 RESTful 应用接口
第6章 构建 RESTful 服务 6.1 RESTful 简介 6.2 构建 RESTful 应用接口 6.3 使用 Swagger 生成 Web API 文档 6.4 实战:实现 Web API 版本控制 6.2 构建 RESTful 应用接口 6.2.1 Spring Boot 对 RESTful 的支持 Spring Boot 提供的spring-boot-starter-web组件完全…...
20230218英语学习
How Italian Artist’s Mild Colors Dominate World of Design 温柔的“莫兰迪色”,如何引领设计时尚? The Morandi color scheme has become an across-the-board fashion that now prevails in the world of design.Soft and sophisticated Morandi c…...
Linux单一服务管理systemctl
基本上systemd这个启动服务机制只有systemctl命令来处理,所以全部的操作都需要使用systemctl systemctl管理单一服务 一般来说服务的启动有两个阶段,一个是开机是否启动,以及现在是否启动 systemctl【command】【unit】 command主要有&…...
【GStreamer 】 TX1中CPU和GPU解码显示海康相机RTSP流
大家好,我是虎哥,今天找了一套海康的相机,想后续测试一下DeepStream用网络相机RTSP流做输入看看后续目标识别和分类。但是还是想先实时看看视频,当然,可以选择VLC去查看,顺道我也用GStreamer 来测试了一下&…...
匿名内部类、Lambda表达式、方法引用对比分析
文章目录一、匿名内部类1. 语法格式2. 使用方法① 传统方式② 匿名内部类方式二、Lambda表达式1. 语法格式2. 使用方法① 匿名内部类方式② Lambda表达式方式三、方法引用1. 语法格式2. 使用方法① 类型的静态方法引用② 类型的构造方法引用③ 类型的实例方法引用④ 对象的实例…...
ESXi主机CVE-2021-21972漏洞复现安全处置建议
一、漏洞简介 vSphere 是 VMware 推出的虚拟化平台套件,包含 ESXi、vCenter Server 等一系列的软件。其中 vCenter Server 为 ESXi 的控制中心,可从单一控制点统一管理数据中心的所有 vSphere 主机和虚拟机。 vSphere Client(HTML5…...
研报精选230217
目录 【行业230217毕马威】奢侈品行业新气象【行业230217国信证券】医药生物行业2023年2月投资策略:持续关注疫后复苏和创新两大主线【行业230217国金证券】航空锻造:稳定格局筑专业化壁垒,顺势而为拓产业链深度【个股230217西南证券_招商轮船…...
c++11 标准模板(STL)(std::unordered_set)(一)
定义于头文件 <unordered_set> template< class Key, class Hash std::hash<Key>, class KeyEqual std::equal_to<Key>, class Allocator std::allocator<Key> > class unordered_set;(1)(C11 起)namespace pmr { templ…...
【C语言进阶】你听说过柔性数组吗?
👦个人主页:Weraphael ✍🏻作者简介:目前是C语言学习者 ✈️专栏:C语言航路 🐋 希望大家多多支持,咱一起进步!😁 如果文章对你有帮助的话 欢迎 评论💬 点赞&a…...
[LeetCode]1237. 找出给定方程的正整数解
题目链接:https://leetcode.cn/problems/find-positive-integer-solution-for-a-given-equation/description/ 题目描述: 样例1: 输入:function_id 1, z 5 输出:[[1,4],[2,3],[3,2],[4,1]] 解释:functi…...
【路径规划】基于A*算法和Dijkstra算法的路径规划(Python代码实现)
👨🎓个人主页:研学社的博客💥💥💞💞欢迎来到本博客❤️❤️💥💥🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密…...
蓝桥杯 stm32 PWM 设置占空比
本文代码使用 HAL 库。 文章目录 前言一、创建CubeMX 工程 ,占空比分析:二、相关函数:1. 获取 CNT函数2.设置CNT为 0 函数(计算器清零)3.开启TIM2_CH1的输入捕获中断函数4.TIM 回调函数三、设置上升沿,下降沿四、在lcd上显示 R40 占空比 详细代码五、设置占空比,输出 PW…...
React 合成事件理解
1 事件三个阶段 捕获、目标、处理 (具体百度,后面有空补全)2import React from "react";class Test extends React.Component {parentRef;childRef;constructor(props) {super(props);this.parentRef React.createRef();this.chil…...
202302|读书笔记——国图点滴
杂志剪影|看一本赚一本系列 anywhere 随心而行随心而动,极简相生复古文艺 热情洋溢 色彩斑斓 极致优雅 深邃魅力 新生绽放 灿若星空 异彩纷呈含苞待放 惊艳绽放 爱在云端 空中婚礼 暗夜浪漫 策马逐梦橘影相映 浆果红唇 梦幻无暇 永无止境浮光掠影 微酥清风低调奢华…...
Linux 操作系统原理 — NUMA 架构中的多线程调度开销与性能优化
目录 文章目录 目录前言NUMA 架构中的多线程性能开销1、跨 Node 的 Memory 访问开销2、跨 Core 的多线程 Cache 同步开销3、多线程上下文切换开销4、多线程模式切换开销5、中断处理的开销6、TLB 缓存失效的开销7、内存拷贝的开销NUMA 架构中的性能优化:使用多核编程代替多线程…...
OpenGL - 如何理解 VAO 与 VBO 之间的关系
系列文章目录 LearnOpenGL 笔记 - 入门 01 OpenGLLearnOpenGL 笔记 - 入门 02 创建窗口LearnOpenGL 笔记 - 入门 03 你好,窗口LearnOpenGL 笔记 - 入门 04 你好,三角形 文章目录系列文章目录1. 前言2. 渲染管线的入口 - 顶点着色器2.1 顶点着色器处理过…...
Linux中sed的使用
语法: sed [选项] [sed内置命令字符] [输入文件]选项: 参数说明-n取消默认色的输出常与sed内置命令p一起使用-i直接将修改结果写入文件,不用-i,sed修改的是内存数据-e多次编译,不需要管道符了-r支持正则扩展 sed的内…...
[软件工程导论(第六版)]第1章 软件工程学概述(复习笔记)
文章目录1.1 软件危机1.1.1 软件危机的介绍1.1.2 产生软件危机的原因1.1.3 消除软件危机的途径1.2 软件工程1.2.1 软件工程的介绍1.2.2 软件工程的基本原理1.2.3 软件工程方法学1.3 软件生命周期组成1.4 软件过程概念1.4.1 瀑布模型1.4.2 快速原型模型1.4.3 增量模型1.4.4 螺旋…...
ISP相关
Internet Service Provider,网络提供商/运营商,如电信、联通、移动等。 1. 与ISP互联的出口带宽 IDC或云提供商会与各运营商互联,互联的具体带宽数值一旦泄露,就会被恶意的攻击者利用。例如,若DDos攻击者知道了被攻击…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
django blank 与 null的区别
1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是,要注意以下几点: Django的表单验证与null无关:null参数控制的是数据库层面字段是否可以为NULL,而blank参数控制的是Django表单验证时字…...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...
CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!
本文介绍了一种名为AnomalyAny的创新框架,该方法利用Stable Diffusion的强大生成能力,仅需单个正常样本和文本描述,即可生成逼真且多样化的异常样本,有效解决了视觉异常检测中异常样本稀缺的难题,为工业质检、医疗影像…...
