设计通网站建设,网站备案不能访问,常德做网站专业公司,现在推广平台哪家最好题目描述
题目链接#xff1a;[LeetCode 1237]找出给定方程的正整数解
给你一个函数 f(x, y) 和一个目标结果 z#xff0c;函数公式未知#xff0c;请你计算方程 f(x,y) z 所有可能的正整数 数对 x 和 y。满足条件的结果数对可以按任意顺序返回。
尽管函数的具体式子未知…题目描述
题目链接[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 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 位有符号整数。
思路分析
1.题目描述很不清晰尤其是引入这个function_id 完全可以不用管这个function_id其实就是告诉你我有九个这样的函数函数都具有单调递增的性质那我管你几个函数只需要知道函数的性质就好了
2.x,y都为1000问题规模卡在n^2级别看到单调第一反应想到的就是二分
3.但是对于两个维度x和y来说很麻烦所以我们可以固定一个维度从这个维度上看就是一个一维的单调递增函数如图所示固定住x比如x0那么这个维度上y就是单调递增的所以可以通过枚举x然后在每个维度上二分y来做复杂度是O(nlogn) O(n2n^2n2)
代码
class Solution {
public:vectorvectorint findSolution(CustomFunction c, int z) {vectorvectorint 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;}
};
