ConstructTheRectangle [source code]

public class ConstructTheRectangle {
    public int[] constructRectangle(int area) {
        int w = (int) Math.sqrt(area);
        double l = (double) area / w;        
        while (l * 10 % 10 != 0) {
            w--;
            l = (double) area / w;
        }
        int[] res = new int[2];
        res[0] = (int) l;
        res[1] = w;
        return res; 
    }

    public static void main(String[] args) {
        ConstructTheRectangle tester = new ConstructTheRectangle();
        int input1 = 5;
        for (int i : tester.constructRectangle(input1)) System.out.println(i);
    }
}

题目本身其实很简单, 就是一些 JAVA 本身的小细节上面不熟悉;

作为一个strong typed language, JAVA对于 operator 的定义跟 ocaml 有点像. 就是你要给出明确的提示之后系统才会认为, 比如你这里的/是一个 double 除.

        double l = area / w;

仅仅因为 l 是 double, 并不会导致最后右边的除法实际执行的就是 double 除.

        double l = (double) area / w;

只有这样明确的表示(让至少一个 operand 是double), 系统才会知道是一个 double 除;

5ms, 60%的速度, 不算太差;

这个是 submission 最优解(实际上是6ms):

public class Solution {  
    public int[] constructRectangle(int area) {  
        int[] result = new int[2];  
        if(area == 0){  
            return result;  
        }  
        int a = (int)Math.sqrt(area);  
        while(area%a != 0){  
            a--;  
        }  
        int b = area/a;  
        result[0] = b;  
        result[1] = a;  
        return result;  
    }  
}

总体是类似的一个算法, 因为这个问题本身的核心就是比较简单的, 你要做好的就是这个循环的 beginning 和termination 的处理就行了; 虽然看起来是一个 optimization 问题, 但是因为 opt 的条件很清晰, 所以只要自己写一个对应的循环就行了;

注意他这里判断的方法: area & a != 0, 这个其实比我的方法要聪明; discussion最优解也差不多;

Problem Description

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.
   Difficulty:Easy
   Category:Algorithms
   Acceptance:48.75%
   Contributors:
   love_Fawn