LEETCODE 1237. Find Positive Integer Solution for a Given Equation解题思路分析

题目大意:

找出给定方程的正整数解

给出一个函数  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解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。