找出给定方程的正整数解【LC1237】
给你一个函数
f(x, y)和一个目标结果z，函数公式未知，请你计算方程f(x,y) == z所有可能的正整数 数对x和y。满足条件的结果数对可以按任意顺序返回。尽管函数的具体式子未知，但它是单调递增函数，也就是说：
f(x, y) < f(x + 1, y)f(x, y) < f(x, y + 1)函数接口定义如下：
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); };
你的解决方案将按如下规则进行评判：
- 判题程序有一个由
CustomFunction的9种实现组成的列表，以及一种为特定的z生成所有有效数对的答案的方法。 - 判题程序接受两个输入：
function_id（决定使用哪种实现测试你的代码）以及目标结果z。 - 判题程序将会调用你实现的
findSolution并将你的结果与答案进行比较。
- 如果你的结果与答案相符，那么解决方案将被视作正确答案，即
Accepted。
说真的 我看了评论区才看懂题目的
暴力
思路：双重循环枚举每个可能的x 和y ，通过customfunction.f(x, y)求出运算结果，如果结果等于z zz，那么加入结果集中；由于函数是单调递增函数，因此如果结果大于z 时，退出循环。
实现
class Solution { public List<List<Integer>> findSolution(CustomFunction customfunction, int z) { List<List<Integer>> res = new ArrayList<>(); for (int i = 1; i <= 1000; i++){ for (int j = 1; j <= 1000; j++){ int num = customfunction.f(i, j); if (num == z){ res.add(Arrays.asList(i, j)); }else if (num > z){ break; } } } return res; } }
/* * // 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) * public int f(int x, int y); * }; */ class Solution { public List<List<Integer>> findSolution(CustomFunction customfunction, int z) { List<List<Integer>> res = new ArrayList<>(); for (int i = 1; i <= 1000; i++){ int jL = 1, jR = 1000; while (jL <= jR){ int mid = (jL + jR) / 2; int num = customfunction.f(i, mid); if (num == z){ res.add(Arrays.asList(i, mid)); break; }else if (num > z){ jR = mid - 1; }else{ jL = mid + 1; } } } return res; } }
class Solution { public List<List<Integer>> findSolution(CustomFunction customfunction, int z) { List<List<Integer>> res = new ArrayList<>(); int j = 1000; for (int i = 1; i <= 1000; i++){ while (j >= 1 && customfunction.f(i, j) > z){ j--; } if (j >= 1 && customfunction.f(i, j) == z){ res.add(Arrays.asList(i, j)); } } return res; } }
复杂度
- 时间复杂度：O ( C ，C 为x和y的取值范围，本题中为1000
空间复杂度：$O(1) $
