宁波网站建设i sp.net,做游戏 做网站,移动网站开发服务器,佛山市外贸企业高端网站设计原题链接
难度#xff1a;middle\color{orange}{middle}middle
2023/2/18 每日一题 题目描述
给你一个函数 f(x,y)f(x, y)f(x,y) 和一个目标结果 zzz#xff0c;函数公式未知#xff0c;请你计算方程 f(x,y)zf(x,y) zf(x,y)z 所有可能的正整数 数对 xxx 和 yyy。满足条件…原题链接
难度middle\color{orange}{middle}middle
2023/2/18 每日一题 题目描述
给你一个函数 f(x,y)f(x, y)f(x,y) 和一个目标结果 zzz函数公式未知请你计算方程 f(x,y)zf(x,y) zf(x,y)z 所有可能的正整数 数对 xxx 和 yyy。满足条件的结果数对可以按任意顺序返回。
尽管函数的具体式子未知但它是单调递增函数也就是说
f(x,y)f(x1,y)f(x, y) f(x 1, y)f(x,y)f(x1,y)f(x,y)f(x,y1)f(x, y) f(x, y 1)f(x,y)f(x,y1)
函数接口定义如下
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);
};你的解决方案将按如下规则进行评判
判题程序有一个由 CustomFunctionCustomFunctionCustomFunction 的 999 种实现组成的列表以及一种为特定的 zzz 生成所有有效数对的答案的方法。判题程序接受两个输入functionidfunction_idfunctionid决定使用哪种实现测试你的代码以及目标结果 zzz 。判题程序将会调用你实现的 findSolutionfindSolutionfindSolution 并将你的结果与答案进行比较。如果你的结果与答案相符那么解决方案将被视作正确答案即 AcceptedAcceptedAccepted 。
示例 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提示
1functionid91 function_id 91functionid91z1001 z 1001z100题目保证 f(x,y)zf(x, y) zf(x,y)z 的解处于 1x,y10001 x, y 10001x,y1000 的范围内。在 1x,y10001 x, y 10001x,y1000 的前提下题目保证 f(x,y)f(x, y)f(x,y) 是一个 32 位有符号整数。 算法
(暴力枚举) O(n2)O(n^2)O(n2) 枚举 x 和 y调用接口判断 f(x, y) 是否等于 z。 如果等于 z则加入答案中如果大于 z则终止掉内层循环。
复杂度分析 时间复杂度最坏情况下需要判断每一个数对故时间复杂度为 O(n2)O(n^2)O(n2)。 空间复杂度 : 需要存储答案故空间复杂度也为 O(n2)O(n^2)O(n2)。
C 代码
/** // This is the custom function interface.* // You should not implement it, or speculate about its implementation* class CustomFunction {* public:* // Returns f(x, y) for any given positive integers x and y.* // Note that f(x, y) is increasing with respect to both x and y.* // i.e. f(x, y) f(x 1, y), f(x, y) f(x, y 1)* int f(int x, int y);* };*/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;}
};双指针
/** // This is the custom function interface.* // You should not implement it, or speculate about its implementation* class CustomFunction {* public:* // Returns f(x, y) for any given positive integers x and y.* // Note that f(x, y) is increasing with respect to both x and y.* // i.e. f(x, y) f(x 1, y), f(x, y) f(x, y 1)* int f(int x, int y);* };*/class Solution {
public:vectorvectorint findSolution(CustomFunction customfunction, int z) {vectorvectorint res;int x 1, y 1000;while (x 1000 y 1) {int t customfunction.f(x, y);if (t z) y --;else if (t z) x ;else {res.push_back({x, y});x , y --;}}return res;}
};
