当前位置: 首页 > news >正文

[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]找出给定方程的正整数解

题目描述 题目链接&#xff1a;[LeetCode 1237]找出给定方程的正整数解 给你一个函数 f(x, y) 和一个目标结果 z&#xff0c;函数公式未知&#xff0c;请你计算方程 f(x,y) z 所有可能的正整数 数对 x 和 y。满足条件的结果数对可以按任意顺序返回。 尽管函数的具体式子未知…...

6.2 构建 RESTful 应用接口

第6章 构建 RESTful 服务 6.1 RESTful 简介 6.2 构建 RESTful 应用接口 6.3 使用 Swagger 生成 Web API 文档 6.4 实战&#xff1a;实现 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 温柔的“莫兰迪色”&#xff0c;如何引领设计时尚&#xff1f; 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命令来处理&#xff0c;所以全部的操作都需要使用systemctl systemctl管理单一服务 一般来说服务的启动有两个阶段&#xff0c;一个是开机是否启动&#xff0c;以及现在是否启动 systemctl【command】【unit】 command主要有&…...

【GStreamer 】 TX1中CPU和GPU解码显示海康相机RTSP流

大家好&#xff0c;我是虎哥&#xff0c;今天找了一套海康的相机&#xff0c;想后续测试一下DeepStream用网络相机RTSP流做输入看看后续目标识别和分类。但是还是想先实时看看视频&#xff0c;当然&#xff0c;可以选择VLC去查看&#xff0c;顺道我也用GStreamer 来测试了一下&…...

匿名内部类、Lambda表达式、方法引用对比分析

文章目录一、匿名内部类1. 语法格式2. 使用方法① 传统方式② 匿名内部类方式二、Lambda表达式1. 语法格式2. 使用方法① 匿名内部类方式② Lambda表达式方式三、方法引用1. 语法格式2. 使用方法① 类型的静态方法引用② 类型的构造方法引用③ 类型的实例方法引用④ 对象的实例…...

ESXi主机CVE-2021-21972漏洞复现安全处置建议

一、漏洞简介 vSphere 是 VMware 推出的虚拟化平台套件&#xff0c;包含 ESXi、vCenter Server 等一系列的软件。其中 vCenter Server 为 ESXi 的控制中心&#xff0c;可从单一控制点统一管理数据中心的所有 vSphere 主机和虚拟机。 vSphere Client&#xff08;HTML5&#xf…...

研报精选230217

目录 【行业230217毕马威】奢侈品行业新气象【行业230217国信证券】医药生物行业2023年2月投资策略&#xff1a;持续关注疫后复苏和创新两大主线【行业230217国金证券】航空锻造&#xff1a;稳定格局筑专业化壁垒&#xff0c;顺势而为拓产业链深度【个股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语言进阶】你听说过柔性数组吗?

&#x1f466;个人主页&#xff1a;Weraphael ✍&#x1f3fb;作者简介&#xff1a;目前是C语言学习者 ✈️专栏&#xff1a;C语言航路 &#x1f40b; 希望大家多多支持&#xff0c;咱一起进步&#xff01;&#x1f601; 如果文章对你有帮助的话 欢迎 评论&#x1f4ac; 点赞&a…...

[LeetCode]1237. 找出给定方程的正整数解

题目链接&#xff1a;https://leetcode.cn/problems/find-positive-integer-solution-for-a-given-equation/description/ 题目描述&#xff1a; 样例1&#xff1a; 输入&#xff1a;function_id 1, z 5 输出&#xff1a;[[1,4],[2,3],[3,2],[4,1]] 解释&#xff1a;functi…...

【路径规划】基于A*算法和Dijkstra算法的路径规划(Python代码实现)

&#x1f468;‍&#x1f393;个人主页&#xff1a;研学社的博客&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5;&#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密…...

蓝桥杯 stm32 PWM 设置占空比

本文代码使用 HAL 库。 文章目录 前言一、创建CubeMX 工程 ,占空比分析:二、相关函数:1. 获取 CNT函数2.设置CNT为 0 函数(计算器清零)3.开启TIM2_CH1的输入捕获中断函数4.TIM 回调函数三、设置上升沿,下降沿四、在lcd上显示 R40 占空比 详细代码五、设置占空比,输出 PW…...

React 合成事件理解

1 事件三个阶段 捕获、目标、处理 &#xff08;具体百度&#xff0c;后面有空补全&#xff09;2import React from "react";class Test extends React.Component {parentRef;childRef;constructor(props) {super(props);this.parentRef React.createRef();this.chil…...

202302|读书笔记——国图点滴

杂志剪影|看一本赚一本系列 anywhere 随心而行随心而动&#xff0c;极简相生复古文艺 热情洋溢 色彩斑斓 极致优雅 深邃魅力 新生绽放 灿若星空 异彩纷呈含苞待放 惊艳绽放 爱在云端 空中婚礼 暗夜浪漫 策马逐梦橘影相映 浆果红唇 梦幻无暇 永无止境浮光掠影 微酥清风低调奢华…...

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 你好&#xff0c;窗口LearnOpenGL 笔记 - 入门 04 你好&#xff0c;三角形 文章目录系列文章目录1. 前言2. 渲染管线的入口 - 顶点着色器2.1 顶点着色器处理过…...

Linux中sed的使用

语法&#xff1a; sed [选项] [sed内置命令字符] [输入文件]选项&#xff1a; 参数说明-n取消默认色的输出常与sed内置命令p一起使用-i直接将修改结果写入文件&#xff0c;不用-i&#xff0c;sed修改的是内存数据-e多次编译&#xff0c;不需要管道符了-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&#xff0c;网络提供商/运营商&#xff0c;如电信、联通、移动等。 1. 与ISP互联的出口带宽 IDC或云提供商会与各运营商互联&#xff0c;互联的具体带宽数值一旦泄露&#xff0c;就会被恶意的攻击者利用。例如&#xff0c;若DDos攻击者知道了被攻击…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...

【Linux】自动化构建-Make/Makefile

前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...