网站建设后台管理便捷平板电视seo优化关键词
找出给定方程的正整数解【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
。
说真的 我看了评论区才看懂题目的
暴力
-
思路:双重循环枚举每个可能的xxx和yyy,通过
customfunction.f(x, y)
求出运算结果,如果结果等于zzz,那么加入结果集中;由于函数是单调递增函数,因此如果结果大于zzz时,退出循环。 -
实现
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;} }
-
复杂度
- 时间复杂度:O(C2)O(C^2)O(C2),CCC为x和y的取值范围,本题中为100010001000
- 空间复杂度:O(1)O(1)O(1)
-
二分查找
-
思路:由于函数为单调递增函数,因此可以固定xxx,二分查找yyy,二分查找的上限为1,下限为1000,假定运算结果为numnumnum
- 如果num==znum==znum==z,那么将结果添加至结果集
- 如果num>znum>znum>z,那么yyy向左边查询,right = mid - 1
- 如果num==znum==znum==z,那么yyy向右边查询,left = mid + 1
-
实现
/** // 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;} }
-
复杂度
- 时间复杂度:O(ClogC)O(ClogC)O(ClogC),CCC为x和y的取值范围,本题中为100010001000
- 空间复杂度:$O(1) $
-
双指针
-
思路:当x1<x2x_1<x_2x1<x2时,如果f(x1,y1)=f(x2,y2)=zf(x_1,y_1)=f(x_2,y_2)=zf(x1,y1)=f(x2,y2)=z,那么此时y1>y2y_1>y_2y1>y2,因此可以从小到大枚举xxx,从大到小枚举yyy,那么可以固定xxx,在上次循环的yyy值作为起始值,找到本次的yyy。
-
实现
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)O(C)O(C),CCC为x和y的取值范围,本题中为100010001000
- 空间复杂度:$O(1) $
-