第7章10アレイ(アレイパーティション1)

1700 ワード
パイ アルゴリズム#アルゴリズム# テキストリンク
配列に2つのmin(a,b)、出力、最大数を作成します.

問題は,1,4,3,2の配列があり,2つずつ2つ抽出し,min(a 1,b 1)min(a 2,b 2)の2つの数の和を生成し,最大の数を出力する.

1.昇順解除


初めて問題を見た時、複雑な問題だと思ったが、理解してみると、簡単すぎると思った.
最後に2つの値を抽出し、2対のminを生成することは、2つの値のうちの小さな値の加算であるため、min()値はできるだけ大きくしなければならない点が重要である.
これは,降順に並べて入れると,常に最大min()値を保つことができることを意味する.
from typing import List


class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        sum = 0
        pair = []
        nums.sort()

        for n in nums:
            # 앞에서 부터 오름차순으로 페어를 만들어 합 계산
            pair.append(n)
            if len(pair) == 2:
                sum += min(pair)
                pair = []

        return sum

2.偶数の2番目の値を計算する


公平に1 min()値を求めず,偶数値を加算しても上記の結果が得られる.
偶数の理由は0からですから.
from typing import List


class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        sum = 0
        nums.sort()

        for i, n in enumerate(nums):
            # 짝수 번째 값의 합 계산
            if i % 2 == 0:
                sum += n

        return sum

3.ダウンジャケット


PythonのSleeringを利用すれば、1本の線がより簡単な問題になります.
from typing import List


class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        return sum(sorted(nums)[::2])
レーン2マスをスキップするのは、偶数回を計算するのと同じです.
標準9251 LCS
FE<->BEデータが転送できない場合.