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

2023-02-17  本文已影响0人  韩其凯
  1. 题意
  2. 思路:由于f是单调递增函数,我们可以从x = 1, y = 1000开始,表示在横坐标为[x, 1000]以及纵坐标为[1, y]的举行范围内搜索答案。分类讨论:
  1. 代码:
    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
  1. 分析
上一篇 下一篇

猜你喜欢

热点阅读