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

news/2024/11/27 0:12:39/

来源:力扣(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


http://www.ppmy.cn/news/26069.html

相关文章

Python学习笔记:条件、循环及其他语句

条件、循环及其他语句 赋值 赋值语句的右边可以是任何类型的序列&#xff0c;但带星号的变量最终包含的总是一个列表。 >>> a, *b, c "abc" >>> a, b, c (a, [b], c)这种收集方式也可用于函数参数列表中 条件语句 用作布尔表达式&#xff…

【Java基础】Java对象创建的几种方式

先上关键内容&#xff0c;所用到的代码请参考文末示例代码。一、使用new关键字创建对象这是一种最常用的创建对象的方式。Student student1 new Student();二、使用Class的newInstance()方法创建对象需要有一个无参构造方法&#xff0c;这个newInstance()方法调用无参的构造函…

Java反序列化漏洞——CommonsCollections4.0版本—CC2、CC4

一、概述4.0版本的CommonsCollections对之前的版本做了一定的更改&#xff0c;那么之前的CC链反序列化再4版本中是否可用呢。实际上是可用的&#xff0c;比如CC6的链&#xff0c;引入的时候因为⽼的Gadget中依赖的包名都是org.apache.commons.collections &#xff0c;⽽新的包…

【ArcGIS Pro二次开发】(5):UI管理_自定义控件的位置

新增的自定义控件一般放在默认的【加载项】选项卡下&#xff0c;但是根据需求&#xff0c;我们可能需要将控件放在新的自定义选项卡下&#xff0c;在自定义选项卡添加系统自带的控件&#xff0c;将自定义的按钮等控件放在右键菜单栏里以方便使用&#xff0c;等等。 下面就以一…

【MySQL进阶】视图 存储过程 触发器

&#x1f60a;&#x1f60a;作者简介&#x1f60a;&#x1f60a; &#xff1a; 大家好&#xff0c;我是南瓜籽&#xff0c;一个在校大二学生&#xff0c;我将会持续分享Java相关知识。 &#x1f389;&#x1f389;个人主页&#x1f389;&#x1f389; &#xff1a; 南瓜籽的主页…

Pytorch 基础之张量数据类型

学习之前&#xff1a;先了解 Tensor&#xff08;张量&#xff09; 官方文档的解释是&#xff1a; 张量如同数组和矩阵一样, 是一种特殊的数据结构。在PyTorch中, 神经网络的输入、输出以及网络的参数等数据, 都是使用张量来进行描述。 说白了就是一种数据结构 基本数据类型…

Redis学习【8】之Redis RDB持久化

文章目录Redis 持久化1 持久化基本原理2 RDB(Redis DataBase) 持久化2.1 持久化的执行2.2 手动 save 命令2.3 手动 bgsave 命令2.4 自动条件触发2.5 查看持久化时间3 RDB 优化配置3.1 save3.2 stop-write-on-bgsave-error3.3 rdbcompression3.4 rdbchecksum3.5 sanitize-dump-p…

「JVM 编译优化」Java 语法糖(泛型、自动装箱/拆箱、条件编译)

「JVM 编译优化」Java 语法糖&#xff08;泛型、自动装箱/拆箱、条件编译&#xff09; 语法糖可以看做事前端编译期的一些小把戏&#xff1b;虽不会提供实质性的功能改进&#xff0c;但它们或能提高效率&#xff0c;或能提升语法的严谨性&#xff0c;或能减少编码出错的机会&a…