[LeetCode] 1237. Find Positive Integer Solution for a Given Equation #1237

grandyang · 2019-05-30T16:33:32Z

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 同步地址:

#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 题目讲解汇总(持续更新中...)

喜欢请点赞，疼爱请打赏❤️~.~

微信打赏

|

Venmo 打赏

---|---