漳州正规网站建设哪家便宜,wordpress+重复插件,做旅游网站的开题报告,番禺核酸检测点免费LeetCode-1237. 找出给定方程的正整数解【双指针#xff0c;二分查找】题目描述#xff1a;解题思路一#xff1a;双指针。首先我们不管f是什么#xff0c;即function_id等于什么不管。但是我们可以调用customfunction中的f函数#xff0c;然后我们遍历x,y(1 x, y 二分查找】题目描述解题思路一双指针。首先我们不管f是什么即function_id等于什么不管。但是我们可以调用customfunction中的f函数然后我们遍历x,y(1 x, y 1000)只要f(x,y)z的(x,y)即是我们需要的答案。然后我们从x1与y1000开始遍历。此时有三种情况解题思路二二分查找。枚举x二分查找y。找到之后x增大因为f对x,y递增故之后的y必小于middle。即f(x,middle)z若要f(x1,y)z那么y必小于middle;对右边界的优化。解题思路三0题目描述
给你一个函数 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 9 1 z 100 题目保证 f(x, y) z 的解处于 1 x, y 1000 的范围内。 在 1 x, y 1000 的前提下题目保证 f(x, y) 是一个 32 位有符号整数。
解题思路一双指针。首先我们不管f是什么即function_id等于什么不管。但是我们可以调用customfunction中的f函数然后我们遍历x,y(1 x, y 1000)只要f(x,y)z的(x,y)即是我们需要的答案。然后我们从x1与y1000开始遍历。此时有三种情况 情况一:f(x,y)z那么固定y继续增大x函数值也会继续增大。显然不符合题意。故将y减1缩小答案。 情况二:f(x,y)z那么固定y继续增大x函数值也会继续增大。显然是符合题意的。故将x加1增大答案。 情况三:f(x,y)z先将x,y加入答案然后固定y继续增大x函数值也会继续增大。显然是不符合题意的。故将y减1缩小答案。类似情况一 /** // 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 ans;int x1,y1000;while(x1000y1){int tcustomfunction.f(x,y);if(tz) --y;else if(tz) x;else ans.push_back({x,y--});}return ans; }
};时间复杂度O(2C)//C1000 空间复杂度O(1)
解题思路二二分查找。枚举x二分查找y。找到之后x增大因为f对x,y递增故之后的y必小于middle。即f(x,middle)z若要f(x1,y)z那么y必小于middle;对右边界的优化。
/** // 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 left 1, right 1000;//右边界right会不断缩小for(int x1;x1000;x) {//枚举x二分查找yleft 1;//每次左边界left从1开始while(leftright) {int middle(leftright)/2;int tcustomfunction.f(x, middle);if(tz){res.push_back({x, middle});rightmiddle-1;//缩小右边界break;//break之后x增大因为f对x,y递增故之后的y必小于middle。即f(x,middle)z若要f(x1,y)z那么y必小于middle;}else if(tz) leftmiddle 1;else rightmiddle-1;//缩小右边界}//其实发现 right 0 了可以直接返回}return res;}
};时间复杂度O(ClogC)//C1000 空间复杂度O(1)
解题思路三0
