forked from fishercoder1534/Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 1
/
_1237.java
89 lines (82 loc) · 2.67 KB
/
_1237.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package com.fishercoder.solutions;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class _1237 {
// This is the custom function interface.
// You should not implement it, or speculate about its implementation
abstract 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 abstract int f(int x, int y);
}
public static class Solution1 {
/**
* Time: O(x*y)
* Space: O(1)
*/
public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
List<List<Integer>> result = new ArrayList<>();
for (int x = 1; x <= 1000; x++) {
for (int y = 1; y <= 1000; y++) {
if (customfunction.f(x, y) == z) {
result.add(Arrays.asList(x, y));
}
}
}
return result;
}
}
public static class Solution2 {
/**
* linear search
* <p>
* Time: O(x + y)
* Space: O(1)
*/
public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
List<List<Integer>> result = new ArrayList<>();
int x = 1;
int y = 1000;
while (x < 1001 && y > 0) {
int functionResult = customfunction.f(x, y);
if (functionResult < z) {
x++;
} else if (functionResult > z) {
y--;
} else {
result.add(Arrays.asList(x++, y--));
}
}
return result;
}
}
public static class Solution3 {
/**
* binary search
* <p>
* Time: O(xlogy)
* Space: O(1)
*/
public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
List<List<Integer>> result = new ArrayList<>();
for (int x = 1; x <= 1000; x++) {
int left = 1;
int right = 1001;
while (left < right) {
int y = (left + right) / 2;
if (customfunction.f(x, y) < z) {
left = y + 1;
} else {
right = y;
}
}
if (customfunction.f(x, left) == z) {
result.add(Arrays.asList(x, left));
}
}
return result;
}
}
}