LeetCode問題:長方形を構築する

2012 ワード
python challenge tutorial algorithms テキストリンク
この記事では、私はLeetcode問題492: Construct the Rectangleへの解決策を検討するつもりです.
つの解決策が開発され、私はそれらを通してあなたを歩いている

溶解性1


この関数はパラメータ領域を受け入れます.この例では16となりますarea = 16次に、ターゲット領域の要素を保持するために、回答辞書変数を作成しますad = {}また、無限大の最大値と最小値を持つtempリストを設定しますtemp = [ float('inf'), float('-inf')]まず、ターゲット領域+ 1の平方根まで1を繰り返して重複を避けるfor 1,2...sqrt(16)+1 --> 5すべての繰り返しについては、その数の要素を見つける場合は、答えの辞書に保存したい
 # 16/1
 # 16/2
 # 16/3
 # 16/4
 ad = {'1':'16', '2':'8', '4':'4'}
今、我々は答えの辞書を介して最高の長さと幅の組み合わせを選択するには
 for k,v in ad:
    if abs(k-v) < abs(temp[0]-temp[1])
    temp[0], temp[1] = min(k, v), max(k,v)
    return temp
このプロセスの終わりには、tempリストの答えがある
下記のコード
import math
class Solution:
    def constructRectangle(self, area: int) -> List[int]:
        answer_dict = {}
        temp = [float('inf'),  float('-inf')]
        for n in range(1, int(math.sqrt(area))+1):
            if area%n == 0:
                answer_dict[n] = area // n
        for k, v in answer_dict.items():
            if abs(temp[0] - temp[1]) > abs(k-v):
                temp[0], temp[1] = max(k, v), min(k, v)
        return temp
最初の解決策は長く、より簡単になりました
この2番目のソリューションは、1つのリストを使用して、将来の長さと幅を維持する
分かりやすい
class Solution:
    def constructRectangle(self, area: int) -> List[int]:
        ans = []
        for i in range(1, int(sqrt(area))+1):
            j = area // i
            if i * j == area:
                if i <= j:
                    ans.append([max(i,j), min(i,j)])
        return ans[-1]
読者のための小さな仕事は、両方のソリューションの時間と空間の複雑さは何ですか
また、より良い解決策、または改善する必要がある場合は私に知らせてください
ハッピーコディング
複数のバージョンの自動管理
学習の道のFragmentとFragmentの間の伝値