第93天。

今天的题目是Construct the Rectangle:

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.

比较简单的题目，但是题目有点长，总结一下就是，你要求出L,W满足一下条件：

1. L, W is int
2. L*W=Area
3. L >= W > 0
4. min |L-W|

既然要使得|L-W|最小，那么显然，L=W=sqrt(Area)时，L-W是最小的，但是因为L和W限制成整数了,且sqrt(Area)不一定是整数，如果把它转换成int的话，L*W不一定等于Area了。所以我们必须调整L和W的值，简单的调整方法就是，如果L*W < Area,我们就加大L之所以是加大L而不是加大W的原因是需要满足L >= W，同理L*W > Area时，我们就减小W。这样子我们始终会找到一个L,W满足上面的条件：

1
vector<int> constructRectangle(int area) {
2
    int L, W;
3
    int sqrt_a = sqrt(area);
4
    W = L = sqrt_a;
5
    int a = W*L;
6
    while(a != area) {
7
        if (a < area) L++;
8
        else if (a > area) W--;
9
        a = W*L;
10
    }
11
    return {L, W};
12
}

然后dicuss中的解法更巧妙一点，我们只求W，然后L = Area/W：

1
public int[] constructRectangle(int area) {
2
    int w = (int)Math.sqrt(area);
3
    while (area%w!=0) w--;
4
    return new int[]{area/w, w};
5
}