Řešení:Krásné aranžmá II

Toto je součástí řady vysvětlení řešení Leetcode (index). Pokud se vám toto řešení líbilo nebo bylo užitečné, dejte like tento příspěvek a/nebo hlasovat pro můj příspěvek řešení na fórech Leetcode.

Problém Leetcode #667 (Střední ):Krásné aranžmá II

Popis:

(Přejít na :Nápad na řešení || Kód :JavaScript | Python | Java | C++ )

Příklady:

Omezení:

Nápad:

(Přejít na :Popis problému || Kód :JavaScript | Python | Java | C++ )

U tohoto problému se musíme zamyslet nad povahou rozsahu možných hodnot pro k a jejich odpovídající pole. Nejmenší hodnota k možné je samozřejmě 1 , čehož lze dosáhnout striktně rostoucím (nebo klesajícím) polem. Přemýšlejte o největší možné hodnotě pro k , je však o něco náročnější.

Za prvé, můžeme zvážit rozsah hodnot v našem poli, což je [1, n] . Největší možný absolutní rozdíl jakýchkoli dvou čísel v tomto rozsahu by samozřejmě byl rozdíl mezi dvěma extrémy, 1 a n , což je n – 1 . Protože nejmenší možný absolutní rozdíl je samozřejmě 1 , pak by se zdálo, že je možné dosáhnout každého rozdílu v rozsahu [1, n - 1] nebo k hodnotu n – 1 .

Je to ale skutečně možné?

Vezměme n =5 a k =4 například. Jediný možný způsob, jak získat absolutní rozdíl 4 by bylo pro 1 a 5 být po sobě jdoucí. Poté existují dvě možnosti pro další nejmenší absolutní rozdíl 3 , což je 1 &4 nebo 2 &5 . Od 1 a 5 jsou již vedle sebe, to znamená, že tohoto druhého kroku můžeme dosáhnout buď pomocí [1,5,2] nebo [4,1,5] (nebo jejich ruby).

Pokračujeme-li v tomto trendu, postupně můžeme vidět, že skutečně můžeme dosáhnout maximálního k hodnotu n – 1 kličkováním tam a zpět mezi zbývajícími extrémy, když je přidáváme do našeho pole. V předchozím příkladu by jeden takový příklad byl [1,5,2,4,3] .

Otázkou pak zůstává, jak půjdeme k dosažení nějaké střední hodnoty k větší než 1 ale menší než n – 1 . Odpověď na to spočívá v tom, že se pole bude skládat ze dvou částí. V první části [1, k+1] , můžeme dosáhnout svého k počet absolutních rozdílů, pak můžeme jednoduše vyplnit zbývající rozsah, [k+2, n] , s ideálními přírůstkovými hodnotami bez zvýšení hodnoty k .

Pokud máme například n =8 a k =4 , vytvořili bychom první část stejně jako poslední příklad, [1,5,2,4,3] , pak přidáme zbývající hodnoty v rostoucím pořadí, [6,7,8] , chcete-li vytvořit pole wole, [1,5,2,4,3,6,7,8] .

Příklady každé varianty k když n =8 :

K dosažení klikaté výplně můžeme použít proměnné pro horní a dolní hodnoty naší první části (a, z ), pak použijte modulo operace (i % 2 ) pro přepínání mezi těmito dvěma možnostmi, přičemž nezapomeňte zvýšit/snížit příslušné proměnné pokaždé, když jsou použity.

O něco snadněji vizualizovatelná (ale hůře kódovatelná) verze řešení podobně zahrnuje použití stejného klikatého bodu pro první k prvky, ale s celým rozsahem n čísla a poté se pohybujte ideálním způsobem (buď zvýšení nebo snížení o 1 , podle toho, zda k je sudé nebo liché) k vyplnění zbývajících prvků pole.

Příklady každé alternativní varianty k když n =8 :

Realizace:

Mezi každým ze čtyř jazyků jsou pouze drobné rozdíly.

Kód JavaScript:

(Přejít na :Popis problému || Nápad na řešení )

var constructArray = function(n, k) {
    let ans = new Array(n)
    for (let i = 0, a = 1, z = k + 1; i <= k; i++)
        ans[i] = i % 2 ? z-- : a++
    for (let i = k + 1; i < n;)
        ans[i] = ++i
    return ans
};

Kód Pythonu:

(Přejít na :Popis problému || Nápad na řešení )

class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        ans, a, z = [0] * n, 1, k + 1
        for i in range(k+1):
            if i % 2:
                ans[i] = z
                z -= 1
            else:
                ans[i] = a
                a += 1
        for i in range(k+1,n):
            ans[i] = i + 1
        return ans

Kód Java:

(Přejít na :Popis problému || Nápad na řešení )

class Solution {
    public int[] constructArray(int n, int k) {
        int[] ans = new int[n];
        for (int i = 0, a = 1, z = k + 1; i <= k; i++)
            ans[i] = i % 2 == 1 ? z-- : a++;
        for (int i = k+1; i < n;)
            ans[i] = ++i;
        return ans;
    }
}

Kód C++:

(Přejít na :Popis problému || Nápad na řešení )

class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int> ans(n);
        for (int i = 0, a = 1, z = k + 1; i <= k; i++)
            ans[i] = i % 2 ? z-- : a++;
        for (int i = k+1; i < n; i++)
            ans[i] = i + 1;
        return ans;
    }
};