Code & Fun

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

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

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

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

本文首发于Code & Fun