You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Given a function f(x, y) and a value z, return all positive integer pairs x and y where f(x,y) == z.
The function is constantly increasing, i.e.:
f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)
The function interface is defined like this:
interfaceCustomFunction {
public:
// Returns positive integer f(x, y) for any given positive integer x and y.intf(intx, inty);
};
For custom testing purposes you're given an integer function_id and a target z as input, where function_id represent one function from an secret internal list, on the examples you'll know only two functions from the list.
You may return the solutions in any order.
Example 1:
Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]
Explanation: function_id = 1 means that f(x, y) = x + y
Example 2:
Input: function_id = 2, z = 5
Output: [[1,5],[5,1]]
Explanation: function_id = 2 means that f(x, y) = x * y
Constraints:
1 <= function_id <= 9
1 <= z <= 100
It's guaranteed that the solutions of f(x, y) == z will be on the range 1 <= x, y <= 1000
It's also guaranteed that f(x, y) will fit in 32 bit signed integer if 1 <= x, y <= 1000
题意:找出所有符合f(x, y) = z的[x, y]
算法思路:
设置左指针left和右指针right,左指针指向1,右指针指向1000;
循环判断f(left, right)是否等于z;
如果等于,则将[left, right]push进最终的结果中;
否则如果f(left, right) > z则right--;
如果f(left, right) < z则left++;
利用双指针遍历一遍即可找出所有符合条件的[x, y],时间复杂度为O(n)。
/* * // This is the custom function interface. * // You should not implement it, or speculate about its implementation * class CustomFunction { * public: * // 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) * int f(int x, int y); * }; */classSolution {
public:
vector<vector<int>> findSolution(CustomFunction&customfunction, intz) {
std::vector<std::vector<int>> result;
intleft=1, right=1000;
while(left <= 1000&&right >= 1){
intans=customfunction.f(left, right);
if(ans==z){
std::vector<int>temp;
temp.push_back(left);
temp.push_back(right);
result.push_back(temp);
left++;
}
elseif(ans>z){
right--;
}
else{
left++;
}
}
returnresult;
}
};
The text was updated successfully, but these errors were encountered:
lihe
changed the title
Find Positive Integer Solution for a Given Equation
Leetcode_1237_Find Positive Integer Solution for a Given Equation
Oct 30, 2019
Find Positive Integer Solution for a Given Equation
Given a function
f(x, y)
and a valuez
, return all positive integer pairsx
andy
wheref(x,y) == z
.The function is constantly increasing, i.e.:
f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)
The function interface is defined like this:
For custom testing purposes you're given an integer
function_id
and a targetz
as input, wherefunction_id
represent one function from an secret internal list, on the examples you'll know only two functions from the list.You may return the solutions in any order.
Example 1:
Example 2:
Constraints:
1 <= function_id <= 9
1 <= z <= 100
f(x, y) == z
will be on the range1 <= x, y <= 1000
f(x, y)
will fit in 32 bit signed integer if1 <= x, y <= 1000
题意:找出所有符合
f(x, y) = z
的[x, y]
算法思路:
left
和右指针right
,左指针指向1
,右指针指向1000
;f(left, right)
是否等于z
;[left, right]
push进最终的结果中;f(left, right) > z
则right--
;f(left, right) < z
则left++
;利用双指针遍历一遍即可找出所有符合条件的
[x, y]
,时间复杂度为O(n)
。The text was updated successfully, but these errors were encountered: