LeetCode 665: Nicht abnehmendes Array

Question

Ich veröffentliche eine Lösung für LeetCodes "Nicht abnehmendes Array". Wenn Sie eine Bewertung abgeben möchten, tun Sie dies bitte. Dankeschön!

Problem

Bei einem Array numsmit nganzen Zahlen müssen Sie überprüfen, ob es nicht abnehmen kann, indem Sie höchstens 1 Element ändern.

Wir definieren, dass ein Array nicht abnimmt, wenn es nums[i] <= nums[i + 1]für jedes i (0-basiert) gilt, so dass ( 0 <= i <= n - 2).

Beispiel 1:

• Eingabe: nums = [4,2,3]
• Ausgabe: wahr
• Erläuterung: Sie können die ersten 4 zu 1 ändern, um ein nicht abnehmendes Array zu erhalten.

Beispiel 2:

• Eingabe: nums = [4,2,1]
• Ausgabe: false
• Erläuterung: Sie können ein nicht abnehmendes Array nicht erhalten, indem Sie höchstens ein Element ändern.

Einschränkungen:

• 1 <= n <= 10 ^ 4
• -10 ^ 5 <= nums[i] <= 10 ^ 5

Code

// Most of headers are already included;
// Can be removed;
#include <iostream>
#include <cstdint>
#include <vector>

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

struct Solution {
    using ValueType = std::int_fast32_t;
    static const bool checkPossibility(
        std::vector<int>& nums
    ) {

        if (std::size(nums) < 3) {
            return true;
        }

        ValueType max_changes = 0;

        for (ValueType index = 1; max_changes < 2 && index < std::size(nums); ++index) {
            if (nums[index - 1] > nums[index]) {
                ++max_changes;

                if (index - 2 < 0 || nums[index - 2] <= nums[index]) {
                    nums[index - 1] = nums[index];

                } else {
                    nums[index] = nums[index - 1];
                }
            }
        }

        return max_changes < 2;
    }
};


int main() {
    std::vector<int> nums = {3, 4, 2, 3};
    std::cout << std::to_string(Solution().checkPossibility(nums) == false) << "\n";
    return 0;
}

Answer 1

Vermeiden Sie unnötige Sonderfälle

Sie beenden das Array vorzeitig, wenn die Größe des Arrays weniger als 3 beträgt. Dies ist jedoch nicht erforderlich: Der Rest des Codes behandelt Arrays der Größen 0, 1 und 2 bereits korrekt. Sie können einen Zyklus speichern, wenn Sie ihm ein kleines Array zuführen, aber Sie bezahlen diesen Scheck mit ein oder zwei Zyklen für jedes Mal, wenn die Funktion mit std::size(nums)> 2 aufgerufen wird .

Verwendung std::size_tfür Indizes

Sie haben indexein gemacht std::int_fast32_t, aber dies hat eine andere Größe (wahrscheinlich) und eine andere Signatur als das Ergebnis von std::size(nums). Dies bedeutet, dass der Compiler Sie vor einem Vergleich zwischen vorzeichenbehafteten und vorzeichenlosen Ganzzahlen gewarnt haben sollte. Da hier die Dinge gut laufen, ist es am besten, std::size_thier zu verwenden, um die Compiler-Warnung zu vermeiden , da Sie wissen, dass die Größe des Eingabearrays eingeschränkt ist . Die Leistung wird sich wahrscheinlich nicht um ein Bit unterscheiden, da indexsie jederzeit in einem CPU-Register gespeichert werden kann.

std::to_string()Bei Verwendung <<auf a ist keine Verwendung erforderlichstd::ostream

Wenn Sie in a schreiben std::ostream, operator<<wird das Argument bereits formatiert, sodass kein Aufruf erforderlich ist std::to_string(). Tatsächlich können Sie den Stream anweisen, einen boolals Text zu formatieren :

int main() {
    std::vector<int> nums = {3, 4, 2, 3};
    std::cout << std::boolalpha << Solution().checkPossibility(nums) << "\n";
}