leetcode每日一题（1237找出给定方程的正整数解）

1. 题意
2. 思路：由于是单调递增函数，我们可以从开始，表示在横坐标为以及纵坐标为的举行范围内搜索答案。分类讨论：

• 如果，那么对于任意的,都有，这说明固定，无论怎样枚举，都无法找到答案，那么将加一，缩小搜索范围；
• 如果，那对于任意，都有，这说明固定枚举其余无法找到答案，那么将减一，缩小搜索范围；
• 如果，那么记录答案，同情况1一样，将加一。由于，根据情况2，可以同时将减一。
• 不断循环直到或为止，此时搜索范围为空。

3. 代码：
   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:
    vector<vector<int>> findSolution(CustomFunction& f, int z) {
        vector<vector<int>> res;
        int i = 1, j = 1000;
        while(i <= 1000 && j >= 1) {
            if (f.f(i, j) == z) res.push_back({i ++, j --});
            if (f.f(i, j) > z) --j;
            if (f.f(i, j) < z) ++i;
        }
        return res;

        
    }
};

Python代码

"""
   This is the custom function interface.
   You should not implement it, or speculate about its implementation
   class CustomFunction:
       # 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)
       def f(self, x, y):
  
"""
class Solution:
    def findSolution(self, customfunction: 'f', z: int) -> List[List[int]]:
        res = []
        i, j = 1, 1000
        while(i <=1000 and j >= 1):
            if customfunction.f(i, j) == z:
                res.append([i, j])
                i += 1
                j += 1
            if customfunction.f(i, j) < z:   i += 1
            if customfunction.f(i, j) > z:   j -= 1
        return res

4. 分析

• 时间复杂度：；
• 空间复杂第：。