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

【1237. 找出给定方程的正整数解】

来源:力扣(LeetCode)

描述:

给你一个函数 f(x, y) 和一个目标结果 z,函数公式未知,请你计算方程 f(x,y) == z 所有可能的正整数 数对 xy。满足条件的结果数对可以按任意顺序返回。

尽管函数的具体式子未知,但它是单调递增函数,也就是说:

  • 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);
};

你的解决方案将按如下规则进行评判:

  • 判题程序有一个由 CustomFunction9 种实现组成的列表,以及一种为特定的 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 位有符号整数。

方法一:枚举

根据题目给出的 x 和 y 的取值范围,枚举所有的 x, y 数对,保存满足 f(x, y) = z 的数对,最后返回结果。

代码:

class Solution {
public:vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {vector<vector<int>> res;for (int x = 1; x <= 1000; x++) {for (int y = 1; y <= 1000; y++) {if (customfunction.f(x, y) == z) {res.push_back({x, y});}}}return res;}
};

执行用时:124 ms, 在所有 C++ 提交中击败了13.98%的用户
内存消耗:6.2 MB, 在所有 C++ 提交中击败了80.64%的用户
复杂度分析
时间复杂度:O(mn),其中 m 是 x 的取值数目,n 是 y 的取值数目。
空间复杂度:O(1)。返回值不计入空间复杂度。

方法二:二分查找

我们固定 x = x0​ 时,函数 g(y) = f(x0, y) 是单调递增函数,可以通过二分查找来判断是否存在 y = y0 ,使 g(y0) = f(x0, y0) = z 成立。

代码:

class Solution {
public:vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {vector<vector<int>> res;for (int x = 1; x <= 1000; x++) {int yleft = 1, yright = 1000;while (yleft <= yright) {int ymiddle = (yleft + yright) / 2;if (customfunction.f(x, ymiddle) == z) {res.push_back({x, ymiddle});break;}if (customfunction.f(x, ymiddle) > z) {yright = ymiddle - 1;} else {yleft = ymiddle + 1;}}}return res;}
};

执行用时:4 ms, 在所有 C++ 提交中击败了51.61%的用户
内存消耗:6.1 MB, 在所有 C++ 提交中击败了96.77%的用户
复杂度分析
时间复杂度:O(mlogn),其中 m 是 x 的取值数目,n 是 y 的取值数目。
空间复杂度:O(1)。返回值不计入空间复杂度。

方法三:双指针

假设 x1 < x2,且 f(x1, y1) = f(x2, y2) = z,显然有 y1 > y2。因此我们从小到大进行枚举 x,并且从大到小枚举 y,当固定 x 时,不需要重头开始枚举所有的 y,只需要从上次结束的值开始枚举即可。

代码:

class Solution {
public:vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {vector<vector<int>> res;for (int x = 1, y = 1000; x <= 1000 && y >= 1; x++) {while (y >= 1 && customfunction.f(x, y) > z) {y--;}if (y >= 1 && customfunction.f(x, y) == z) {res.push_back({x, y});}}return res;}
};

执行用时:4 ms, 在所有 C++ 提交中击败了51.61%的用户
内存消耗:6.3 MB, 在所有 C++ 提交中击败了17.20%的用户
复杂度分析
时间复杂度:O(m+n),其中 m 是 x 的取值数目,n 是 y 的取值数目。
空间复杂度:O(1)。返回值不计入空间复杂度。
author:LeetCode-Solution

相关文章:

【1237. 找出给定方程的正整数解】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一个函数 f(x, y) 和一个目标结果 z&#xff0c;函数公式未知&#xff0c;请你计算方程 f(x,y) z 所有可能的正整数 数对 x 和 y。满足条件的结果数对可以按任意顺序返回。 尽管函数的具体式子…...

java基础学习 day41(继承中成员变量和成员方法的访问特点,方法的重写)

继承中&#xff0c;成员变量的访问特点 a. name前什么都不加&#xff0c;name变量的访问采用就近原则&#xff0c;先在局部变量中查找&#xff0c;若没找到&#xff0c;继续在本类的成员变量中查找&#xff0c;若没找到&#xff0c;继续在直接父类的成员变量中查找&#xff0c…...

【c语言进阶】深度剖析整形数据

&#x1f680;write in front&#x1f680; &#x1f4dc;所属专栏&#xff1a; &#x1f6f0;️博客主页&#xff1a;睿睿的博客主页 &#x1f6f0;️代码仓库&#xff1a;&#x1f389;VS2022_C语言仓库 &#x1f3a1;您的点赞、关注、收藏、评论&#xff0c;是对我最大的激励…...

【信息系统项目管理师】项目管理十大知识领域记忆敲出(采购风险沟通干系人)

【信息系统项目管理师】项目管理十大知识领域记忆敲出&#xff08;采购风险沟通干系人&#xff09; 这里写目录标题【信息系统项目管理师】项目管理十大知识领域记忆敲出&#xff08;采购风险沟通干系人&#xff09;一.项目采购管理记忆敲出1.合同管理&#xff1a;2.规划采购管…...

[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 架构中的性能优化:使用多核编程代替多线程…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...

恶补电源:1.电桥

一、元器件的选择 搜索并选择电桥&#xff0c;再multisim中选择FWB&#xff0c;就有各种型号的电桥: 电桥是用来干嘛的呢&#xff1f; 它是一个由四个二极管搭成的“桥梁”形状的电路&#xff0c;用来把交流电&#xff08;AC&#xff09;变成直流电&#xff08;DC&#xff09;。…...

Vue3 PC端 UI组件库我更推荐Naive UI

一、Vue3生态现状与UI库选择的重要性 随着Vue3的稳定发布和Composition API的广泛采用&#xff0c;前端开发者面临着UI组件库的重新选择。一个好的UI库不仅能提升开发效率&#xff0c;还能确保项目的长期可维护性。本文将对比三大主流Vue3 UI库&#xff08;Naive UI、Element …...