分治與回溯

分治和回溯算法，包括其概念、特性、代碼模板，并結合具體題目進行講解，旨在幫助學員理解和掌握這兩種算法的應用。

1. 分治與回溯的概念
   • 分治（Divide & Conquer）：本質上基于遞歸，先將問題分解為多個子問題（Divide），分別求解子問題（Conquer），再將子問題的解合并（Merge）得到原問題的解 。以拋硬幣問題為例幫助理解，通過不斷將問題細分來簡化求解過程。
   • 回溯（Backtracking）：采用試錯思想，嘗試分步解決問題。在分步過程中，若當前分步答案無法得到正確解答，則取消上一步或上幾步計算，通過其他可能的分步解答繼續嘗試。它通常用簡單遞歸實現，可能找到正確答案，也可能在嘗試所有分步方法后宣告問題無解，最壞情況下時間復雜度為指數時間。
2. 分治算法
   • 代碼模板：包含遞歸終止條件判斷、數據準備、問題分解、子問題求解和結果合并等步驟。通過divide_conquer函數模板展示，在遞歸終止條件中判斷問題是否為空，若為空則打印結果并返回；準備數據后將問題拆分為子問題，遞歸調用函數求解子問題，最后處理并生成最終結果 。
   • 理解要點：代碼結構與遞歸相似，可看作在遞歸基礎上增加了問題分解和結果合并步驟，有助于將復雜問題逐步簡化解決。
3. 回溯算法
   • 代碼示例 - 括號生成：在力扣22題括號生成中，通過_generate遞歸函數實現回溯。利用left和right分別記錄左括號和右括號的使用數量，在遞歸過程中根據條件添加括號，當left和right都等于給定對數n時，將生成的括號組合加入結果列表 。
   • 算法理解：在解決問題時，通過不斷嘗試不同的分步選擇，當發現當前選擇無法得到有效答案時，回退到上一步重新選擇，直至找到正確答案或確定問題無解。

練習題

括號生成

題目復述

題目要求是，給定一個整數 n ，n 代表著括號的對數。任務是編寫一個函數，這個函數要能夠生成所有可能的、并且是有效的括號組合。這里的有效是指在任意前綴中左括號的數量都不少于右括號的數量，且最終左、右括號的數量都等于 n 。舉例來說，當 n = 3 時，生成的結果應該是像 ["((()))", "(()())", "(())()", "()(())", "()()()"] 這樣的一系列有效的括號組合。

Python代碼

from typing import Listclass Solution:def generateParenthesis(self, n: int) -> List[str]:result = []def _generate(left, right, s):# terminatorif left == n and right == n:result.append(s)return# drill downif left < n:_generate(left + 1, right, s + "(")if left > right:_generate(left, right + 1, s + ")")_generate(0, 0, "")return result

代碼解析

1. 整體結構：定義了 Solution 類，其中 generateParenthesis 方法是對外提供功能的接口，接收整數 n 作為參數，返回值類型是字符串列表，即所有有效的括號組合。在 generateParenthesis 方法內部，又定義了一個局部函數 _generate ，它采用遞歸的方式來逐步生成括號組合。同時初始化了一個空列表 result ，用于存儲最終有效的括號組合。
2. 遞歸終止條件（terminator）：在 _generate 函數中，通過判斷 if left == n and right == n: 來確定是否達到遞歸終止條件。當左括號的數量 left 和右括號的數量 right 都等于給定的 n 時，說明已經成功構建出了一個完整且有效的括號組合，此時將這個組合字符串 s 添加到結果列表 result 中，然后通過 return 語句結束當前這一支遞歸調用。
3. 處理當前邏輯并遞歸深入（drill down）
   • 添加左括號：使用條件 if left < n: 進行判斷，只要左括號的數量 left 還小于給定的 n ，就表示還可以繼續添加左括號。此時通過遞歸調用 _generate(left + 1, right, s + "(") ，將左括號數量增加1 ，并把左括號字符 ( 添加到當前正在構建的括號組合字符串 s 后面，繼續深入遞歸以進一步構建括號組合。
   • 添加右括號：利用條件 if left > right: 進行判斷，當左括號的數量 left 大于右括號的數量 right 時，意味著可以添加右括號（這是為了保證在構建括號組合的任意時刻，左括號的數量都不少于右括號的數量，從而保證組合的有效性 ）。通過遞歸調用 _generate(left, right + 1, s + ")") ，將右括號數量增加1 ，并把右括號字符 ) 添加到當前的括號組合字符串 s 后面，繼續遞歸構建括號組合。
4. 返回結果：在 generateParenthesis 方法中，調用 _generate(0, 0, "") 開始遞歸構建括號組合的過程，當遞歸結束后，直接返回存儲著所有有效括號組合的 result 列表。

復雜度分析

• 時間復雜度：該算法的時間復雜度大致為 $O(4^n/\sqrt{n})$ 。從解空間角度來看，對于 n 對括號，其所有可能的組合數量規模大致符合這樣的數量級。雖然在遞歸過程中通過條件判斷（左括號數量和右括號數量的約束 ）減少了一些無效分支的計算，但整體數量級仍然是這個范圍。
• 空間復雜度：遞歸調用棧的深度最大為 2n （因為最多會有 n 個左括號和 n 個右括號依次入棧 ），所以僅考慮遞歸棧的空間占用時，空間復雜度為 $O(n)$ 。再考慮到結果列表 result ，在最壞情況下它存儲的有效括號組合數量為卡特蘭數 $O(C_{2n}^n)$ ，每個組合的長度為 2n ，綜合起來整個算法的空間復雜度為 $O(4^n/\sqrt{n})$ 。

題目描述

實現 pow(x, n) ，也就是計算 x 的 n 次冪函數（即 $x^n$ ）。題目給定了相關約束條件：-100.0 < x < 100.0 ，n 是 32 位有符號整數，數值范圍在 [?2^31, 2^31 ? 1] 。同時給出了示例：

• 示例 1 中，輸入 x = 2.00000, n = 10 ，輸出 1024.00000 。
• 示例 2 里，輸入 x = 2.10000, n = 3 ，輸出 9.26100 。
• 示例 3 時，輸入 x = 2.00000, n = -2 ，輸出 0.25000 ，因為 2^(-2) = 1/2^2 = 1/4 = 0.25 。

Python代碼和解析

暴力解法

class Solution:def myPow(self, x: float, n: int) -> float:if n == 0:return 1elif n < 0:x = 1 / xn = -nresult = 1for _ in range(n):result *= xreturn result

解析：先處理特殊情況，當 n 為 0 ，任何數的 0 次冪是 1 ，直接返回 1 。若 n 為負，將 x 取倒數，n 變為正。然后通過 for 循環，讓 result 連乘 n 次 x 得到結果。時間復雜度為 $O(n)$ ，因為要進行 n 次乘法；空間復雜度 $O(1)$ ，只用到幾個固定變量。

分治算法

class Solution:def myPow(self, x: float, n: int) -> float:if n == 0:return 1elif n < 0:x = 1 / xn = -nreturn self.helper(x, n)def helper(self, x, n):if n == 0:return 1half = self.helper(x, n // 2)if n % 2 == 0:return half * halfelse:return half * half * x

解析：同樣先處理 n 為 0 和負數情況。helper 遞歸函數用分治思想，把求 x 的 n 次冪問題分解成求 x 的 n//2 次冪問題。若 n 是偶數，x^n = (x^(n//2)) * (x^(n//2)) ；若 n 是奇數，x^n = (x^(n//2)) * (x^(n//2)) * x 。時間復雜度 $O(logn)$ ，每次遞歸問題規模減半；空間復雜度 $O(logn)$ ，遞歸調用棧深度最大為 $O(logn)$ 。

分治 + 迭代

class Solution:def myPow(self, x: float, n: int) -> float:if n < 0:x = 1 / xn = -nresult = 1current_product = xwhile n > 0:if n % 2 == 1:result *= current_productcurrent_product *= current_productn = n // 2return result

解析：先處理 n 為負的情況。初始化 result 為 1 ，current_product 為 x 。循環中，通過 n % 2 檢查 n 的二進制位，為 1 就把 current_product 乘到 result 中，接著 current_product 平方，n 右移一位（除以 2 ），直到 n 為 0 。時間復雜度 $O(logn)$ ，循環次數是 n 二進制表示的位數；空間復雜度 $O(1)$ ，只用了幾個固定變量。
在二進制冪次計算里，一個整數的冪次計算可以轉化為對其二進制表示的處理。以計算$x^n$為例，將$n$用二進制表示后，每一位都對應著不同的$x$的冪次。

• 例如計算$x^{13}$，$13$的二進制是$1101$ ，$x^{13}=x^{8+4+1}=x^8\times x^4\times x^1$ 。從右往左看二進制位，第一位是$1$，代表$x^1$；第二位是$0$，代表沒有$x^2$ ；第三位是$1$，代表$x^4$ ；第四位是$1$，代表$x^8$ 。
• 回到代碼中，while n > 0:循環每次處理$n$的一個二進制位。if n % 2 == 1:判斷當前處理的二進制位是否為$1$，如果是，說明這個二進制位對應的$x$的冪次需要乘到結果里。比如在計算$x^{13}$時，當處理到第一位（從右往左）和第三位、第四位時，由于這些位是$1$，所以要把對應的$x$的冪次（即當前的current_product）乘到result中。而current_product在每次循環中會不斷平方，依次對應$x^1$ 、$x^2$ 、$x^4$ 、$x^8$等冪次。在計算$x^{13}$時，第一次循環current_product是$x$ ，對應$x^1$ ，因為第一位是$1$，所以result乘上$x$ ；第二次循環current_product變為$x^2$ ，但第二位是$0$，不乘；第三次循環current_product變為$x^4$ ，第三位是$1$，result乘上$x^4$ ；第四次循環current_product變為$x^8$ ，第四位是$1$，result乘上$x^8$ 。最終result的值就是$x^{13}$ 。 所以在二進制冪次計算中，奇數冪次（對應二進制位為$1$的情況）需要額外乘上當前的底數，以此完成冪次的計算。

題目描述

給定一個整數數組 nums ，數組中的元素互不相同。返回該數組所有可能的子集（冪集）。解集不能包含重復的子集，輸出順序可以任意。

最優解思路（位運算解法）

1. 對于一個含有 n 個元素的集合，它的子集個數為 $2^n$ 個 。可以用二進制數來表示每個子集，從 0 到 $2^n?1$ 這 $2^n$ 個二進制數，每一位對應集合中的一個元素，若該位為 1 ，表示對應元素在子集中；若為 0 ，表示對應元素不在子集中。
2. 遍歷從 0 到 $2^n?1$ 的所有整數，對于每個整數，將其轉換為二進制形式，根據二進制位的情況構建對應的子集。

代碼實現（Python）

class Solution:def subsets(self, nums):n = len(nums)result = []for i in range(2 ** n):subset = []for j in range(n):if (i >> j) & 1:subset.append(nums[j])result.append(subset)return result

代碼解析

1. 確定子集數量范圍：
   • n = len(nums) 獲取數組 nums 的長度。總共有 $2^n$ 個子集，所以通過 for i in range(2 ** n) 遍歷從 0 到 $2^n?1$ 的所有整數。
2. 構建每個子集：
   • 對于每個整數 i ，內部通過 for j in range(n) 遍歷 nums 數組的每個元素位置。(i >> j) & 1 用于判斷 i 的二進制表示中第 j 位是否為 1 。i >> j 是將 i 的二進制表示右移 j 位，然后 & 1 是取最低位，如果結果為 1 ，說明第 j 位是 1 ，此時將 nums[j] 添加到當前子集 subset 中。
3. 收集結果：
   • 構建好一個子集 subset 后，將其添加到結果列表 result 中，最后返回 result 。

復雜度分析

• 時間復雜度：外層循環執行 $2^n$ 次，內層循環對于每個外層循環執行 n 次，整體時間復雜度為 $O(n\times 2^n)$ ，這是生成所有子集問題的理論最小時間復雜度。
• 空間復雜度：除輸入數組外，額外空間主要用于存儲結果集。最壞情況下有 $2^n$ 個子集，假設每個子集平均長度為 n ，空間復雜度為 $O(n\times 2^n)$ 。

前面我們提到一個含有(n)個元素的集合，其子集個數為(2^n)個，這可以通過二項式展開來理解，下面結合代碼詳細闡述。

二項式定理回顧

二項式定理的表達式為((a + b)^n=\sum_{k = 0}^{n}C_{n}k a^{n - k}b^{{k})，其中(C_{n}}k=\frac{n!}{k!(n - k)!})，它表示從(n)個不同元素中取出(k)個元素的組合數 。當(a = b = 1)時，((1 + 1)^n=\sum_{k = 0}^{n}C_{n}k\times1^{n - k}\times1^{k}=\sum_{k = 0}^{n}C_{n}k)，也就是(2^n = C_{n}^0 + C_{n}^1+C_{n}2+\cdots + C_{n}^n)。

代碼邏輯與二項式展開的關聯

以下是之前的代碼：

class Solution:def subsets(self, nums):n = len(nums)result = []for i in range(2 ** n):subset = []for j in range(n):if (i >> j) & 1:subset.append(nums[j])result.append(subset)return result

1. 二項式展開各項含義

• (C_{n}^k)表示從(n)個元素中選取(k)個元素的組合方式的數量。在集合的子集中，這就對應著含有(k)個元素的子集的個數。
• 比如，對于一個有(n = 3)個元素的集合({a,b,c})：
  • (C_{3}^0)表示從(3)個元素中選(0)個元素的組合數，其值為(1)，對應的子集就是空集(\varnothing)。
  • (C_{3}^{1)表示從(3)個元素中選(1)個元素的組合數，(C_{3}}1=\frac{3!}{1!(3 - 1)!}=\frac{3!}{1!2!}=3)，對應的子集為({a})、({b})、({c})。
  • (C_{3}^{2)表示從(3)個元素中選(2)個元素的組合數，(C_{3}}2=\frac{3!}{2!(3 - 2)!}=\frac{3!}{2!1!}=3)，對應的子集為({a,b})、({a,c})、({b,c})。
  • (C_{3}^3)表示從(3)個元素中選(3)個元素的組合數，其值為(1)，對應的子集就是原集合({a,b,c})。

2. 代碼中循環與二項式展開的對應關系

• 外層循環：for i in range(2 ** n)，這里(2^n)就是二項式展開((1 + 1)^{n)的結果。從(0)到(2}n-1)的每一個整數(i)都對應著集合的一個子集。這是因為每一個整數(i)的二進制表示可以用來確定集合中的哪些元素被選入子集中。
• 內層循環：for j in range(n)用于檢查整數(i)的二進制表示的每一位。(i >> j) & 1 這個表達式用于判斷(i)的第(j)位是否為(1)，如果為(1)，則將nums[j]添加到子集中。從二項式展開的角度看，當我們遍歷所有的(i)時，實際上是在遍歷所有可能的元素選取組合，也就是在遍歷二項式展開中的每一項。

舉例說明

假設nums = ['a', 'b', 'c']，(n = 3)，(2^n=8)。

• 當(i = 0)（二進制(000)）時，內層循環中(i >> j) & 1對于所有(j)都為(0)，得到子集(\varnothing)，對應二項式展開中的(C_{3}^0)這一項。
• 當(i = 1)（二進制(001)）時，(i >> 0) & 1 = 1，將nums[0]（即a）加入子集，得到子集({a})；當(i = 2)（二進制(010)）時，得到子集({b})；當(i = 4)（二進制(100)）時，得到子集({c})，這三個子集對應二項式展開中的(C_{3}^1)這一項。
• 當(i = 3)（二進制(011)）時，得到子集({a,b})；當(i = 5)（二進制(101)）時，得到子集({a,c})；當(i = 6)（二進制(110)）時，得到子集({b,c})，這三個子集對應二項式展開中的(C_{3}^2)這一項。
• 當(i = 7)（二進制(111)）時，得到子集({a,b,c})，對應二項式展開中的(C_{3}^3)這一項。

綜上所述，代碼通過遍歷(0)到(2^n - 1)的所有整數，利用二進制位運算來確定元素的選取，從而得到集合的所有子集，這與二項式展開所表示的從(n)個元素中選取不同個數元素的組合情況是一一對應的，體現了集合子集個數與二項式展開結果(2^n)之間的緊密聯系。

題目：多數元素（Majority Element）

鏈接：https://leetcode-cn.com/problems/majority-element/description/

題目描述

給定一個大小為n的數組nums，返回其中的多數元素。多數元素是指在數組中出現次數 大于 ?n / 2?的元素。

你可以假設數組是非空的，并且給定的數組總是存在多數元素。

解法一：哈希表法

1. 思路
   使用哈希表來記錄每個元素出現的次數。遍歷數組，對于每個元素，如果它已經在哈希表中，就將其對應的值（出現次數）加1；如果不在，就將其加入哈希表，出現次數初始化為1 。最后遍歷哈希表，找出出現次數大于?n / 2?的元素。
2. Python代碼實現

class Solution:def majorityElement(self, nums):num_count = {}n = len(nums)for num in nums:num_count[num] = num_count.get(num, 0) + 1if num_count[num] > n // 2:return num

3. 代碼解釋
   • 首先創建一個空的字典num_count用于存儲元素及其出現次數，獲取數組nums的長度n。
   • 然后遍歷數組nums，對于每個元素num，使用num_count.get(num, 0)獲取num在字典中的出現次數（如果不存在則默認為0），并將其加1。
   • 每次更新完出現次數后，檢查當前元素的出現次數是否大于n // 2，如果大于則直接返回該元素。
4. 時間復雜度：$O(n)$，其中n是數組nums的長度。遍歷數組一次，哈希表的操作平均時間復雜度為常數，所以整體時間復雜度為$O(n)$。
5. 空間復雜度：$O(n)$，在最壞情況下，數組中的所有元素都不同，此時哈希表需要存儲n個鍵值對，所以空間復雜度為$O(n)$。

解法二：排序法

1. 思路
   先對數組進行排序，由于多數元素出現的次數大于?n / 2?，那么排序后數組中間位置（索引為n // 2）的元素必然是多數元素。
2. Python代碼實現

class Solution:def majorityElement(self, nums):nums.sort()return nums[len(nums) // 2]

3. 代碼解釋
   • 使用nums.sort()對數組nums進行排序，Python的內置排序函數平均時間復雜度為$O(nlogn)$。
   • 排序后直接返回數組中間位置（索引為len(nums) // 2）的元素，該元素就是多數元素。
4. 時間復雜度：$O(nlogn)$，主要時間消耗在排序操作上，常見排序算法平均時間復雜度為$O(nlogn)$。
5. 空間復雜度：如果使用的是原地排序算法（如Python的list.sort ），空間復雜度為$O(1)$；如果使用的是需要額外空間的排序算法（如歸并排序），空間復雜度為$O(n)$ 。

解法三：摩爾投票法（最優解）

1. 思路
   摩爾投票法的核心思想是通過兩兩抵消不同的元素，最后剩下的就是多數元素。維護一個候選元素candidate和它的計數值count。遍歷數組，當count為0時，將當前元素設為candidate；如果當前元素與candidate相同，count加1，否則count減1 。遍歷結束后，candidate即為多數元素。
2. Python代碼實現

class Solution:def majorityElement(self, nums):candidate = Nonecount = 0for num in nums:if count == 0:candidate = numcount += (1 if num == candidate else -1)return candidate

3. 代碼解釋
   • 初始化候選元素candidate為None，計數值count為0。
   • 遍歷數組nums，當count為0時，將當前元素num設為candidate。然后根據當前元素num是否與candidate相同，對count進行加1或減1操作。
   • 遍歷結束后，candidate就是多數元素，直接返回。
4. 時間復雜度：$O(n)$，只需要遍歷數組一次，時間復雜度為$O(n)$。
5. 空間復雜度：$O(1)$，只使用了常數級別的額外空間。