1237. 找出给定方程的正整数解

Posted on | In
Words count in article: 629 | Reading time ≈ 3

题目

给出一个函数 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：

1
2
3
输入：function_id = 1, z = 5
输出：[[1,4],[2,3],[3,2],[4,1]]
解释：function_id = 1 表示 f(x, y) = x + y

示例2：

1
2
3
4
输入：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 位有符号整数。

解法

解法一：

暴力

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> result = new ArrayList<>();
            for (int i = 1;i <= z;i++) {
                for (int j = 1;j <= z;j++) {
                    if (customfunction.f(i, j) == z) {
                        List<Integer> temp = new ArrayList<>();
                        temp.add(i);
                        temp.add(j);
                        result.add(temp);
                    }
                }
            }
            return result;
    }

解法二：

二分查找因为函数是严格单调递增的，所以，可以使用二分查找

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> resultList = new ArrayList<>();
        for (int j = 1000, tmp = 1; j > 0; j--) {
            int left = tmp, right = 1000, mid;
            while (left <= right) {
                mid = left + (right - left >> 1);
                int myZ = customfunction.f(mid, j);
                if (myZ > z)
                    right = mid - 1;
                else if (myZ < z)
                    left = mid + 1;
                else {
                    List<Integer> paramList = new ArrayList<>();
                    paramList.add(mid);
                    paramList.add(j);
                    resultList.add(paramList);
                    tmp = mid + 1;
                    break;
                }
            }
        }
        return resultList;
    }

解法三：

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        
        List<List<Integer>> res = new LinkedList<>();
        int start = 1, end = 1000;
        while (start <= 1000 && end >= 1) {
            
            int r = customfunction.f(start, end);
            if (r == z) {
                
                List<Integer> tmp = new LinkedList<>();
                tmp.add(start);
                tmp.add(end);
                res.add(tmp);
                start++;
                end--;
                
            } else if (r > z)
                end--;
            else
                start++;   
        }
        
        return res;
    }
0%