LeetCode492-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.

Exmaple:

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:

  1. The given area won’t exceed 10,000,000 and is a positive integer
  2. The web page’s width and length you designed must be positive integers.

分析

解法一:平方遍历

首先想到的是暴力地穷举,即让长和宽都分别从1 – area/2进行平方遍历,每找出一对长和宽,就计算他们是否符合题目条件。但这种方法很自然低效。

解法二:线性遍历

更好的方式是以宽w(短的边l)为基准考察。我们来看看area = 24和area = 36的情况:

1 * 24 –> 23                   1 * 36 –> 35

2 * 12 –> 10                   2 * 18 –>  16

3 * 8  –> 5                      3 * 12 –>   9

4 * 6  –> 2                      4 * 9  –>   5

6 * 4  –> 2                      6 * 6  –>   0

……                                  ……

从上面的组合结果中我们不难得到以下结论:

  • 随着宽边w长度逐1增大,长边l长度逐渐减小
  • 长边具体减小到多少由l = area / w相除决定
  • 宽边w增大到\(\sqrt {area} \)时(即此时w = l),之后将出现w > l(不满足条件)

根据上面的发现我们不难总结出思路:只要以1增量的速度考察1<= w <= \(\sqrt {area} \),由此算得长边l,再计算l * w看是否等于area(为证明l与w两者为正整数),若是,则进一步用gap = min {l – w, gap}决定是否更新当前的最优长宽组合。

代码

解法一

public class Solution {
    public int[] constructRectangle(int area) {
        int length = area;
        int width = 1;
        int gap = area - 1;

        for (int w = 2; w <= area / 2; w++) {
            for (int l = w; l <= area / 2; l++) {
                if (l * w == area) {
                    int newGap = l - w;
                    if(newGap < gap) { 
                        length = l;
                        width = w;
                        gap = newGap;              
                    }
                }
            }
        }
        
        return new int[] {length, width};
    }
}

解法二

public class Solution {
    public int[] constructRectangle(int area) {
        int length = area;
        int width = 1;
        int gap = area - 1;
        int sqrt = (int) Math.sqrt(area);
        
        for (int w = 2; w <= sqrt; w++) {
            int l = area / w;
            if (l * w == area) {
                int newGap = l - w;
                if(newGap < gap) { 
                    length = l;
                    width = w;
                    gap = newGap;
                }
            }
        }
    
        return new int[] {length, width};
    }
}

Leave a Comment.