[LeetCode] 1237. Find Positive Integer Solution for a Given Equation 找出给定方程的正整数解


Given a callable function f(x, y) with a hidden formula and a value z, reverse engineer the formula and return *all positive integer pairs x and y where *f(x,y) == z. You may return the pairs in any order.

While the exact formula is hidden, the function is monotonically increasing, i.e.:

  • f(x, y) < f(x + 1, y)
  • f(x, y) < f(x, y + 1)

The function interface is defined like this:

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);
};

We will judge your solution as follows:

  • The judge has a list of 9 hidden implementations of CustomFunction, along with a way to generate an answer key of all valid pairs for a specific z.
  • The judge will receive two inputs: a function_id (to determine which implementation to test your code with), and the target z.
  • The judge will call your findSolution and compare your results with the answer key.
  • If your results match the answer key, your solution will be Accepted.

Example 1:

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]
Explanation: The hidden formula for function_id = 1 is f(x, y) = x + y.
The following positive integer values of x and y make f(x, y) equal to 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.

Example 2:

Input: function_id = 2, z = 5
Output: [[1,5],[5,1]]
Explanation: The hidden formula for function_id = 2 is f(x, y) = x * y.
The following positive integer values of x and y make f(x, y) equal to 5:
x=1, y=5 -> f(1, 5) = 1 * 5 = 5.
x=5, y=1 -> f(5, 1) = 5 * 1 = 5.

Constraints:

  • 1 <= function_id <= 9
  • 1 <= z <= 100
  • It is guaranteed that the solutions of f(x, y) == z will be in the range 1 <= x, y <= 1000.
  • It is also guaranteed that f(x, y) will fit in 32 bit signed integer if 1 <= x, y <= 1000.

这道题说是给了一个隐藏的函数,并且给了一个函数调用的接口,可以传参数x和y进去并得到一个返回值,现在题目给定了一个返回值z,让反向找出所有的x和y的参数组合。博主刚看到这题的时候是一脸懵逼的,这尼玛还逆向工程呢,咋可能就凭一个返回值就能推导出函数表达式,瞬间尼克杨问号脸。看了看这道题的赞踩比,估计有不少人跟博主抱有同样的想法吧~ 没办法,只好逛论坛求解法,果然排在第一的仍然是 lee215 大神,他将问题做了个神转化,瞬间变的清晰无比。其实这道题并不需要知道具体的函数表达式,题目中有个关键的信息千万不能忽略,函数在x和y参数上都是单调递增的,就是说x参数不变的话,y越大,返回值越大,同理,y不变的话,x越大,返回值也越大,当然,若x和y同时大,则返回值更大。为啥说这个条件重要呢?题目中给了x和y的取值范围 [1, 1000],则x和y可以看作一个二维数组的行列坐标,并且这个数组的值是按行和列分别递增,题目就变成了找出所有值为z的位置坐标,这样一转换,是不是豁然开朗了。

当然,暴力的方法是尝试x和y的所有的组合,一个一个的调用 API 比较返回值,但这种方法想必不能通过 OJ,毕竟完全没有考察到什么知识点。我们希望尽可能的减少调用 API 的次数,那么选择检测的起点最好是一个中间的值,数组左上角的起点是最小的数字,右下角是最大数字,那么选中间的数字就可以选左下角或右上角的数字,这里李哥选了右上角的数字当作起点,即 (1, 1000) 这个位置,然后往左下角开始遍历。对每个x和y值调用 API,若结果大于给定z值,说明需要减小参数,则y值自减1;若返回结果小于z值,说明需要增大参数,则x值自增1;若返回结果正好等于z值,完美,则将x和y值组成对儿加入结果 res 中,并且同时让x自增1,y自减1,这样最终就可以将所有和z相等的位置坐标找出来了。题目中有个标签是二分搜索法,其实就像李哥说的,如果选对了双指针的遍历逻辑,速度并不比二分搜索慢,参见代码如下:


解法一:

class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> res;
        int x = 1, y = 1000;
        while (x <= 1000 && y > 0) {
            int val = customfunction.f(x, y);
            if (val > z) --y;
            else if (val < z) ++x;
            else res.push_back({x++, y--});
        }
        return res;
    }
};

还可以换一种写法,写得更简洁一些,但是貌似上面的解法更快一些,参见代码如下:


解法二:

class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> res;
        int y = 1000;
        for (int x = 1; x <= 1000; ++x) {
            while (y > 1 && customfunction.f(x, y) > z) --y;
            if (customfunction.f(x, y) == z) res.push_back({x, y});
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1237


参考资料:

https://leetcode.com/problems/find-positive-integer-solution-for-a-given-equation/

https://leetcode.com/problems/find-positive-integer-solution-for-a-given-equation/discuss/414249/JavaC%2B%2BPython-O(X%2BY)

https://leetcode.com/problems/find-positive-integer-solution-for-a-given-equation/discuss/414158/JavaPython-3-3-methods%3A-time-O(x-%2B-y)-O(xlogy)-and-O(x-%2B-logy)-w-analysis.


LeetCode All in One 题目讲解汇总(持续更新中...)

上一篇:01:判断数正负


下一篇:欧几里得的游戏