题目大意：
找出给定方程的正整数解
给出一个函数 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 positive integer f(x, y) for any given positive integer x and y.
int f(int x, int y);
}; 如果你想自定义测试，你可以输入整数 function_id 和一个目标结果 z 作为输入，其中 function_id 表示一个隐藏函数列表中的一个函数编号，题目只会告诉你列表中的 2 个函数。
你可以将满足条件的 结果数对 按任意顺序返回。
示例 1：
输入：function_id = 1, z = 5 输出：[[1,4],[2,3],[3,2],[4,1]] 解释：function_id = 1 表示 f(x, y) = x + y
示例 2：
输入：function_id = 2, z = 5 输出：[[1,5],[5,1]] 解释：function_id = 2 表示 f(x, y) = x * y
提示：
- 1 <= function_id <= 9
- 1 <= z <= 100
- 题目保证 f(x, y) == z 的解处于 1 <= x, y <= 1000 的范围内。
- 在 1 <= x, y <= 1000 的前提下，题目保证 f(x, y) 是一个 32 位有符号整数。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1237
解题思路分析：
简单总结一下题目，大意是说有一个f方法，参数是两个整数x和y，只要你传给它两个整数它就能返回一个结果。本题是已知结果的前提下，反推x和y可能有哪些组合？
因为我们不清楚f方法内的实现逻辑，所以通过结果反算出x和y是不可能的，进而我们只有一种方法，用不同的x和y代入f方法，看得出的结果是否与题目给出的结果相同，如果相同，当前x和y即是一个答案。（这种思想很像哈希碰撞，类似比特币的挖矿原理。虽然和刷题无关，但有兴趣的可以看下我之前的文章： 程序猿白话分析比特币原理 ）
解题思路很简单，题目给出x和y的大小在1到1000之内，我们使用2层循环，分别遍历x和y的所有组合即可。另外题目给出一个可以剪枝的条件，f函数的结果是伴随s或者y递增而递增的，所以，当f的返回结果大于等于给定结果时，该层循环可以结束。
实现代码：
public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
List<List<Integer>> res = new ArrayList<>(); // 返回结果
for(int i=1;i<=1000;i++){ // 循环i
if(i>z){ // 如果i大于z，说明之后所有i乘j均大于z
break; // 结束循环
}
for(int j=1;j<=1000;j++){ // 循环j
int result = customfunction.f(i,j); // 计算结果
if(result==z){ // 如果计算结果等于z
List<Integer> list = new ArrayList<>();
list.add(i);
list.add(j);
res.add(list); // 将当前i和j添加到返回结果
}
if(result>=z){ // 如果计算结果大于等于z
break; // 结束当前循环
}
}
}
return res;
} 本题解法执行时间为1ms。
Runtime: 1 ms, faster than 99.95% of Java online submissions for Find Positive Integer Solution for a Given Equation.
Memory Usage: 33.9 MB, less than 100.00% of Java online submissions for Find Positive Integer Solution for a Given Equation.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1237-find-positive-integer-solution-for-a-given-equation解题思路分析/