厦门外贸网站建设公司,金华网站推广,积极参与网站信息建设工作,体育新闻来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
给你一个函数 f(x, y) 和一个目标结果 z#xff0c;函数公式未知#xff0c;请你计算方程 f(x,y) z 所有可能的正整数 数对 x 和 y。满足条件的结果数对可以按任意顺序返回。
尽管函数的具体式子…来源力扣LeetCode
描述
给你一个函数 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
x1, y4 - f(1, 4) 1 4 5
x2, y3 - f(2, 3) 2 3 5
x3, y2 - f(3, 2) 3 2 5
x4, y1 - 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
x1, y5 - f(1, 5) 1 * 5 5
x5, y1 - f(5, 1) 5 * 1 5提示
1 function_id 91 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:vectorvectorint findSolution(CustomFunction customfunction, int z) {vectorvectorint 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:vectorvectorint findSolution(CustomFunction customfunction, int z) {vectorvectorint 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:vectorvectorint findSolution(CustomFunction customfunction, int z) {vectorvectorint 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(mn)其中 m 是 x 的取值数目n 是 y 的取值数目。 空间复杂度O(1)。返回值不计入空间复杂度。 authorLeetCode-Solution
