前往
大廳
主題

LeetCode - 492. Construct the Rectangle 解題心得

Not In My Back Yard | 2020-11-02 00:00:02 | 巴幣 0 | 人氣 144

題目連結:


題目意譯:
一個網頁開發者想要知道怎麼設計出網頁的大小。因此,給定一個特定的矩形網頁所佔之面積 area,你現在的工作設計一個矩形網頁,其長度 L 、寬度 W 滿足下列要求:
1. 你設計的矩形網頁之面積必須等於給定的目標面積。
2. 寬度 W 不應大於長度 L,即 L ≧ W。
3. 長度 L 與寬度 W 之差值應越小越好。

回傳一個陣列 [L, W],其中 L 和 W 分別為你設計的網頁之長度與寬度。

限制:
1 ≦ area ≦ 10 ^ 7



範例測資:
範例 1:
輸入: area = 4
輸出: [2,2]
解釋: 目標面積為 4 ,而所有的可能建立方式為 [1,4] 、 [2,2] 、 [4,1]。但根據第 2 點要求,[1,4] 不合法、根據第 3 點要求,[4,1] 比不上 [2,2] 來得好。因此所求長度 L = 2 且寬度 W = 2。

範例 2:
輸入: area = 37
輸出: [37,1]

範例 3:
輸入: area = 122122
輸出: [427,286]


解題思維:
因為第 3 點要求—— L 與 W 應越接近越好。因此可以看到 L 和 W 應當越接近給定的 area 值之平方根。

因此我們可以宣告一變數 X 為 sqrt(area) 取整數部分,其中 sqrt() 代表取平方根。然後從 X 之值開始,一直將 X 遞減 1。對於每次的 X ,判斷 X 可否整除 area 之值。如果可以即結束整個過程;反之繼續。

當離開上面的過程之後,此時的 X 值即是所求的 W 值,而 L 就等於 area ÷ X。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作