https://leetcode.com/problems/construct-the-rectangle/
这道题让我们根据面积来求出矩形的长和宽,要求长和宽的差距尽量的小,那么就是说越接近正方形越好。那么我们肯定是先来判断一下是不是正方行,对面积开方,如果得到的不是整数,说明不是正方形。那么我们取最近的一个整数,看此时能不能整除,如果不行,就自减1,再看能否整除。最坏的情况就是面积是质数,最后减到了1,那么返回结果即可
https://leetcode.com/problems/construct-the-rectangle/discuss/97210/3-line-Clean-and-easy-understand-solution
比较简单的题目,容易想到应该让长和宽尽量接近即可
所以可以枚举宽,从1到取最接近的宽,那么长就可以直接算出来了
For a web developer, it is very important to know how to design a web page's size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements:
1. The area of the rectangular web page you designed must equal to the given target area. 2. The width W should not be larger than the length L, which means L >= W. 3. The difference between length L and width W should be as small as possible.You need to output the length L and the width W of the web page you designed in sequence.
Example:
Input: 4 Output: [2, 2] Explanation: The target area is 4, and all the possible ways to construct it are [1,4], [2,2], [4,1]. But according to requirement 2, [1,4] is illegal; according to requirement 3, [4,1] is not optimal compared to [2,2]. So the length L is 2, and the width W is 2.
Note:
- The given area won't exceed 10,000,000 and is a positive integer
- The web page's width and length you designed must be positive integers.
这道题让我们根据面积来求出矩形的长和宽,要求长和宽的差距尽量的小,那么就是说越接近正方形越好。那么我们肯定是先来判断一下是不是正方行,对面积开方,如果得到的不是整数,说明不是正方形。那么我们取最近的一个整数,看此时能不能整除,如果不行,就自减1,再看能否整除。最坏的情况就是面积是质数,最后减到了1,那么返回结果即可
vector<int> constructRectangle(int area) { int r = sqrt(area); while (area % r != 0) --r; return {area / r, r}; }
如果我们不想用开方运算sqrt的话,那就从1开始,看能不能整除,循环的终止条件是看平方值是否小于等于面积
vector<int> constructRectangle(int area) { int r = 1; for (int i = 1; i * i <= area; ++i) { if (area % i == 0) r = i; } return {area / r, r}; }
The W is always less than or equal to the square root of area
so we start searching at sqrt(area) till we find the result
so we start searching at sqrt(area) till we find the result
public int[] constructRectangle(int area) {
int w = (int)Math.sqrt(area);
while (area%w!=0) w--;
return new int[]{area/w, w};
}
http://www.wonter.net/archives/1102.html比较简单的题目,容易想到应该让长和宽尽量接近即可
所以可以枚举宽,从1到取最接近的宽,那么长就可以直接算出来了
vector<int> constructRectangle(int area)
{
int l, w;
int t = sqrt(area);
for(int i = t; i >= 1; --i)
{
if(area % i == 0)
{
w = i;
break;
}
}
l = area / w;
return vector<int>{l, w};
}