Leetcode_1237_Find Positive Integer Solution for a Given Equation

[lihe]

Find Positive Integer Solution for a Given Equation

Given a function f(x, y) and a value z, return all positive integer pairs x and y where f(x,y) == z.

The function is constantly 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 positive integer f(x, y) for any given positive integer x and y.
  int f(int x, int y);
};

For custom testing purposes you're given an integer function_id and a target z as input, where function_id represent one function from an secret internal list, on the examples you'll know only two functions from the list.

You may return the solutions in any order.

Example 1：

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]
Explanation: function_id = 1 means that f(x, y) = x + y

Example 2：

Input: function_id = 2, z = 5
Output: [[1,5],[5,1]]
Explanation: function_id = 2 means that f(x, y) = x * y

Constraints:

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

题意：找出所有符合f(x, y) = z的[x, y]

算法思路：

1. 设置左指针left和右指针right，左指针指向1，右指针指向1000；
2. 循环判断f(left, right)是否等于z；
   • 如果等于，则将[left, right]push进最终的结果中；
   • 否则如果f(left, right) > z则right--；
     • 如果f(left, right) < z则left++；

利用双指针遍历一遍即可找出所有符合条件的[x, y],时间复杂度为O(n)。

/*
 * // 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:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        std::vector<std::vector<int>> result;
        int left = 1, right = 1000;
        while(left <= 1000 && right >= 1){
            int ans = customfunction.f(left, right);
            if(ans == z){
                std::vector<int> temp;
                temp.push_back(left);
                temp.push_back(right);
                result.push_back(temp);
                left++;
            }
            else if(ans > z){
                right--;
            }
            else{
                left++;
            }
        }
        return result;
    }
};