Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. Problem

Sie erhalten ein nicht leeres Array „nums“, das nur positive Ganzzahlen enthält. Bitte beurteilen Sie, ob dieses Array in zwei Teilmengen unterteilt werden kann, sodass die Summe der Elemente der beiden Teilmengen gleich ist.

2. Lösungsidee 1

Dynamische Programmierlösung

Dieses Problem kann mit dem Backtracking-Algorithmus nicht gelöst werden. Wenn die Datenmenge groß ist, kommt es zu einer Zeitüberschreitung. Wir können dynamische Programmierung verwenden.
Diese Frage bestimmt, ob die Summe der Elemente der beiden Teile gleich ist, wenn das Array in zwei Teile geteilt wird. Zuerst müssen wir die Summe aller Elemente im Array berechnen und dann feststellen, ob die Summe eine gerade Zahl ist: Wenn es keine gerade Zahl ist, bedeutet dies, dass sie nicht in zwei völlig gleiche Teile geteilt werden kann und zurückgegeben wird direkt falsch.
Wenn es sich um eine gerade Zahl handelt, müssen wir nur feststellen, ob es einige Elemente gibt, deren Summe gleich Summe/2 ist. Wenn sie gleich Summe/2 ist, muss der Rest auch gleich Summe/2 sein, was bedeutet Wir können das Array in zwei Teile mit gleichen Elementen teilen.
Dann ist das Problem zu diesem Zeitpunkt sehr klar. Unter der Annahme, dass sum/2 die Kapazität eines Rucksacks ist, müssen wir nur einige Elemente finden und in den Rucksack stecken, wenn die maximale Summe der Elemente im Rucksack gleich ist /2 bedeutet, dass wir das Array in zwei gleiche Teile teilen können. Ist das nicht das klassische 0:1-Rucksackproblem? Das grundlegende Rucksackproblem in der Reihe der Rucksackprobleme kann unten für Einzelheiten gelesen werden. Ich werde die Einführung hier nicht wiederholen. Wir suchen nach seiner Rekursionsformel und definieren dp[i][j] als Darstellung des Maximalwerts, den man erhält, wenn man den i-ten Gegenstand in einen Rucksack mit der Kapazität j steckt.
Der Wert des i-ten Elements ist nums [i -1]:
Wenn nums [i -1]>j, bedeutet dies, dass die Rucksackkapazität nicht ausreicht und der i-te Artikel nicht hineingelegt werden kann, sodass wir den i-ten Artikel nicht auswählen können
dp[i][j]=dp[i -1][j];
Wenn nums [i -1] <= j ist, bedeutet dies, dass der j-te Gegenstand in den Rucksack gelegt werden kann. Wir können wählen, ob wir ihn platzieren möchten oder nicht. Nehmen Sie einfach den maximalen Wert Rucksackkapazität. Der maximale Wert ja
dp[i][j]=dp[i-1][j-Zahlen[i-1]]+Zahlen[i-1]
Wenn du nicht loslässt
dp[i][j]=dp[i -1][j];
Nehmen Sie das Maximum von beiden

Die endgültige rekursive Formel und der Code lauten wie folgt:

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) {
        return false;
    }
    // sum除以2
    int target = sum >> 1;
    int length = nums.size();
    std::vector<std::vector<int>> dp(length + 1, std::vector<int>(target + 1, 0));
    for (int i = 1; i <= length; ++i) {
        for (int j = 1; j <= target; ++j) {
            // 下面是递推公式
            if (j >= nums[i - 1]) {
                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // 判断背包最大是否能存放和为target的元素
    return dp[length][target] == target;
}

Wir können auch so schreiben: Das zweidimensionale Array dp ist vom booleschen Typ dp[i][j] und gibt an, ob die Summe der ersten i Elemente im Array eine Summe von j bilden kann. 0]=true, was bedeutet, dass die ersten 0 Elemente (dh keine Elemente) eine Summe von 0 bilden können.Code wird wie folgt angezeigt

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) {
        return false;
    }
    // sum除以2得到target
    int target = sum >> 1;
    int length = nums.size();
    std::vector<std::vector<bool>> dp(length + 1, std::vector<bool>(target + 1, false));
    // base case
    dp[0][0] = true;
    for (int i = 1; i <= length; ++i) {
        for (int j = 0; j <= target; ++j) {
            // 递推公式
            if (j >= nums[i - 1]) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // 返回能否找到和为target的子集
    return dp[length][target];
}

Wir sehen, dass sich der aktuelle Wert bei der Berechnung des obigen zweidimensionalen Arrays nur auf die obige Zeile bezieht, sodass wir ihn in einen eindimensionalen ändern können. Beachten Sie, dass die zweite for-Schleife ein Flashback sein muss, da sonst der vorherige Wert überschrieben wird und das Ergebnis wird falsch sein, schauen Sie genauer hin
dp[j] = (dp[j] || dp[j - Nums [i - 1]]);
Sie können verstehen, dass der Wert am Ende derselben Zeile vom vorherigen abhängt. Wenn es sich nicht um einen Rückblick handelt, wird der vorherige Wert geändert, was zu einem Fehler bei der Berechnung des späteren führt.Werfen wir einen Blick auf den Code

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) {
        return false;
    }
    // sum除以2得到target
    int target = sum >> 1;
    int length = nums.size();
    std::vector<bool> dp(target + 1, false);
    // base case
    dp[0] = true;
    for (int i = 0; i < length; ++i) {
        // 注意这里j要倒序
        for (int j = target; j >= nums[i]; --j) {
            // 递推公式
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    // 返回能否找到和为target的子集
    return dp[target];
}

3. Lösungsidee 2

DFS-Algorithmuslösung

Jedes Element kann ausgewählt werden oder nicht. Sie müssen nur bestimmen, ob die Summe der Elemente in allen möglichen Kombinationen gleich sum/2 ist. Wir können es uns als einen binären Baum vorstellen aktuelles Element, und der rechte untergeordnete Knoten stellt die Auswahl des aktuellen Elements dar. Der untergeordnete Knoten zeigt an, dass das aktuelle Element nicht ausgewählt ist, wie in der Abbildung unten gezeigt. Der orangefarbene Knoten zeigt an, dass das aktuelle Element ausgewählt ist, und der blaue Knoten zeigt an, dass das aktuelle Element nicht ausgewählt ist.

Werfen wir zunächst einen Blick auf den vorläufigen Implementierungscode

#include <vector>
 
bool dfs(const std::vector<int>& nums, int target, int index) {
    // target等于0，说明存在一些元素的和等于sum/2，直接返回true
    if (target == 0) return true;
    // 如果数组元素都找完了，或者target小于0，直接返回false
    if (index == nums.size() || target < 0) return false;
    // 选择当前元素和不选择当前元素两种情况
    return dfs(nums, target - nums[index], index + 1) || dfs(nums, target, index + 1);
}
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) sum += num;
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) return false;
    // 调用dfs函数
    return dfs(nums, sum >> 1, 0);
}

Da der Rechenaufwand jedoch zu groß ist, kommt es leider zu einer Zeitüberschreitung des Vorgangs. Wir können ihn optimieren und einen Blick auf den Code werfen.

#include <vector>
 
bool dfs(const std::vector<int>& nums, int index, int target, std::vector<std::vector<int>>& map) {
    // target等于0，说明存在一些元素的和等于sum/2，直接返回true
    if (target == 0) return true;
    // 如果数组元素都找完了，或者target小于0，直接返回false
    if (index >= nums.size() || target < 0) return false;
    // 如果此子问题已经被计算过，直接返回结果
    if (map[index][target] != -1) return map[index][target] == 1;
    // 选择当前元素
    bool select = dfs(nums, index + 1, target - nums[index], map);
    // 不选择当前元素
    bool unSelect = dfs(nums, index + 1, target, map);
    // 存储结果，并返回
    map[index][target] = select || unSelect ? 1 : 0;
    return select || unSelect;
}
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) sum += num;
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if (sum % 2 != 0) return false;
    // sum除以2
    int target = sum / 2;
    std::vector<std::vector<int>> map(nums.size(), std::vector<int>(target + 1, -1));
    return dfs(nums, 0, target, map);
}

4. Lösungsidee 3

Bit-Operationslösung

Hier können Bitoperationen verwendet werden, aber der Schlüssel liegt in einigen Einschränkungen in der Frage, wie z. B. einem nicht leeren Array positiver Ganzzahlen, die Elemente in jedem Array werden 100 nicht überschreiten, die Größe des Arrays wird 200 nicht überschreiten usw .
Das Prinzip ist sehr einfach. Für ein Array müssen wir nur bits[sum+1] der Größe sum+1 anwenden. Die Zahlen im Array können nur 0 und 1 sein. Wir können es uns als ein sehr langes Binärbit vorstellen, weil int und der Typ long ist zu kurz, wir verwenden hier ein Array. Jedes Mal, wenn ein Element im Array durchlaufen wird, beispielsweise m, wird das Binärbit um m Bits nach links verschoben und dann mit dem ursprünglichen Binärbit ODER-verknüpft. Bestimmen Sie abschließend, ob bits[sum/2] 1 ist, und geben Sie true zurück, wenn es 1 ist.Die Textbeschreibung ist nicht ganz einfach. Nehmen wir Beispiel 1 als Beispiel, um ein Bild zu zeichnen.

Schließlich finden Sie eine Regel: Solange das Endergebnis der Operation 1 ist, kann es mit Elementen im Array kombiniert werden. Solange es 0 ist, kann es nicht mit Elementen im Array kombiniert werden Der obige Prozess ist einfach zu schreiben. Da wir nur bestimmen müssen, ob der mittlere Wert im Binärbit 1 ist, müssen wir nur das niedrige Bit berechnen, und das hohe Bit muss überhaupt nicht berechnet werden, da es nach links und nach oben verschoben wird Das Bit hat keinen Einfluss auf den Mittelwert, also können wir es hier tun. Eine kleine Optimierung, und schließlich schauen wir uns den Code an.

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有数字的和
    int sum = 0;
    for (int n : nums) {
        sum += n;
    }
    // 如果sum是奇数，直接返回false
    if ((sum & 1) == 1) {
        return false;
    }
    int len = sum / 2;
    // 这里bits的长度是len+1，因为我们只需要计算低位就行了，没必要计算所有的
    std::vector<char> bits(len + 1, 0);
    bits[0] = 1;
    for (int num : nums) {
        for (int j = len - num; j >= 0; j--) {
            bits[j + num] |= bits[j];
        }
        // 判断中位数如果是1，说明可以分成两种相等的子集，直接返回true，不需要再计算了
        if ((bits[len] & 1) != 0) {
            return true;
        }
    }
    return false;
}