foolish fly fox's blog
--Stay hungry, stay foolish.
--Forever young, forever weeping.
https://leetcode.com/problems/construct-the-rectangle/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:
W
should not be larger than the length L
, which means L >= W
.L
and width W
should be as small as possible.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 lengthL
is 2, and the widthW
is 2.
Note:
版本1:
class Solution: def constructRectangle(self, area): """ :type area: int :rtype: List[int] """ import math L = math.ceil(area**.5) while area%L: L += 1 return L,area//L
该算法在 LeetCode 上测试的结果为 1596 ms。
非常耗时,因为在以 为分界点,前后能够整除 的因子个数是相同的,设为 个,而前面的因子的密度为 ,而后面的因子的密度约为 ,而 ,当 较大时,搜寻 之前的部分效率远比搜寻 之后的部分要高。
版本2:
class Solution: def constructRectangle(self, area): """ :type area: int :rtype: List[int] """ W = int(area**.5) while area%W: W -= 1 return [area//W,W]
该算法在 LeetCode 上测试的结果为 60 ms,与上一版本相比快了很多。
版本3:
class Solution: def constructRectangle(self, area): """ :type area: int :rtype: List[int] """ import math W = math.floor(area**.5) while area%W: W -= 1 return [area//W,W]
该算法在 LeetCode 上测试的结果为 40 ms,可见使用 math 的 floor()
运算比 int()
要高效很多。