深圳福田专业网站建设,企业网站备案好不好,app界面设计案例分析,黄页网站营销找出给定方程的正整数解
难度#xff1a;中等
给你一个函数 f(x, y) 和一个目标结果 z#xff0c;函数公式未知#xff0c;请你计算方程 f(x,y) z 所有可能的正整数 数对 x 和 y。满足条件的结果数对可以按任意顺序返回。
尽管函数的具体式子未知#xff0c;但它是单调…找出给定方程的正整数解
难度中等
给你一个函数 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 。
示例 1
输入function_id 1, z 5
输出[[1,4],[2,3],[3,2],[4,1]]
解释function_id 1 暗含的函数式子为 f(x, y) x y
以下 x 和 y 满足 f(x, y) 等于 5
x1, y4 - f(1, 4) 1 4 5
x2, y3 - f(2, 3) 2 3 5
x3, y2 - f(3, 2) 3 2 5
x4, y1 - f(4, 1) 4 1 5示例 2
输入function_id 2, z 5
输出[[1,5],[5,1]]
解释function_id 2 暗含的函数式子为 f(x, y) x * y
以下 x 和 y 满足 f(x, y) 等于 5
x1, y5 - f(1, 5) 1 * 5 5
x5, y1 - f(5, 1) 5 * 1 5二分查找
思路
先用二分查找x的最小值和最大值再在x的这个区间中二分查找y值
复杂度分析
时间复杂度 O(mlogn)O(m \log n)O(mlogn)其中 mmm 是 xxx 的取值数目nnn 是 yyy 的取值数目。空间复杂度 O(1)O(1)O(1)。返回值不计入空间复杂度。
This is the custom function interface.You should not implement it, or speculate about its implementationclass 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: CustomFunction, z: int) - List[List[int]]:# 求 x 可能的最大值l1, r1 1, 1000while l1 r1: mid (l1 r1) // 2 if customfunction.f(mid, 1) z:r1 mid - 1else:l1 mid 1# 求 x 可能的最小值 l2, r2 1, l1while l2 r2: mid (l2 r2) // 2 if customfunction.f(mid, 1000) z:l2 mid 1else:r2 mid - 1# 求 x 合理区间内和 y 可能的数组res []for i in range(l2, l1):l, r 1, 1000while l r:mid (l r) // 2if customfunction.f(i, mid) z:res.append([i, mid])breakelif customfunction.f(i, mid) z:r mid - 1else:l mid 1return res双指针
思路 假设 x1x2x_1 x_2x1x2且 f(x1,y1)f(x2,y2)zf(x_1, y_1) f(x_2, y_2) zf(x1,y1)f(x2,y2)z显然有 y1y2y_1 y_2y1y2。因此我们从小到大进行枚举 xxx并且从大到小枚举 yyy当固定 xxx 时不需要重头开始枚举所有的 yyy只需要从上次结束的值开始枚举即可。 有个思路是用二分查找缩小x的范围理论上应该更快。
复杂度分析
时间复杂度 O(mn)O(mn)O(mn)其中 mmm 是 xxx 的取值数目nnn 是 yyy 的取值数目。空间复杂度 O(1)O(1)O(1)。返回值不计入空间复杂度。
This is the custom function interface.You should not implement it, or speculate about its implementationclass 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: CustomFunction, z: int) - List[List[int]]:y 1000res []for x in range(1, 1001):while y and customfunction.f(x, y) z:y - 1if y 0:breakif customfunction.f(x, y) z:res.append([x, y])return res源力扣LeetCode 链接https://leetcode.cn/problems/find-positive-integer-solution-for-a-given-equation
