(優先整理熱門100及面試150，不定期持續更新，歡迎關注)

---

322. 零錢兌換

給你一個整數數組 coins ，表示不同面額的硬幣；以及一個整數 amount ，表示總金額。
計算并返回可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。
你可以認為每種硬幣的數量是無限的。

示例 1：

輸入：coins = [1, 2, 5], amount = 11
輸出：3 

解釋：11 = 5 + 5 + 1

示例 2：

輸入：coins = [2], amount = 3
輸出：-1

示例 3：

輸入：coins = [1], amount = 0
輸出：0

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

方法一：動態規劃

使用動態規劃數組 dp，其中 dp[i] 表示湊成金額 i 所需的最少硬幣個數。通過逐步填充 dp 數組，最終得到 dp[amount] 的結果。

1. 初始化

   • dp[0] = 0：金額為0時不需要任何硬幣。
   • 其他金額初始化為 amount + 1，因為最多需要 amount 個硬幣（全用面額1的硬幣），初始值設為更大的數表示暫時不可達。

2. 狀態轉移

   • 對于每個金額 i，遍歷所有硬幣面額 coin。
   • 若 coin ≤ i，則可以通過 i - coin 的金額加上當前硬幣組成 i，即 dp[i] = min(dp[i], dp[i - coin] + 1)。

3. 結果判斷

   • 如果最終 dp[amount] 仍大于 amount，說明無法湊出目標金額，返回 -1。
   • 否則返回 dp[amount]，即最少硬幣數。

代碼實現(Java)：

import java.util.Arrays;class Solution {public int coinChange(int[] coins, int amount) {if (amount == 0) {return 0;}int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1); // 初始化為一個較大的值（超過最大可能硬幣數）dp[0] = 0; // 金額0需要0個硬幣// 遍歷所有金額，從1到amountfor (int i = 1; i <= amount; i++) {// 遍歷所有硬幣面額for (int coin : coins) {if (coin <= i) { // 硬幣面額不超過當前金額時，才可能使用dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}}// 判斷結果是否有效return dp[amount] > amount ? -1 : dp[amount];}
}

方法二：BFS解法

將問題轉化為圖的最短路徑問題，其中每個節點表示當前剩余金額，邊表示使用一枚硬幣。BFS按層遍歷，首次到達金額0時的層數即為最少硬幣數。

1. 初始化

   • 隊列存放待處理的金額，初始為 amount。
   • 已訪問集合 visited 防止重復處理相同金額。
   • steps 記錄當前層數（即已用硬幣數）。

2. 層序遍歷

   • 每層開始前記錄隊列大小，處理完該層所有節點后步數+1。
   • 對每個金額嘗試所有硬幣：
     • 若 current - coin == 0，直接返回當前步數。
     • 若新金額合法且未訪問過，加入隊列并標記，避免重復處理相同金額。

3. 終止條件

   • 隊列清空時仍未找到解，返回 -1。

代碼實現(Java)：

import java.util.*;class Solution {public int coinChange(int[] coins, int amount) {if (amount == 0) return 0;Queue<Integer> queue = new LinkedList<>();Set<Integer> visited = new HashSet<>();queue.offer(amount);visited.add(amount);int steps = 0;while (!queue.isEmpty()) {int size = queue.size();steps++;for (int i = 0; i < size; i++) {int current = queue.poll();for (int coin : coins) {int next = current - coin;if (next == 0) {return steps; // 找到解，直接返回}if (next > 0 && !visited.contains(next)) {visited.add(next);queue.offer(next);}}}}return -1; // 隊列清空仍未找到解}
}

復雜度分析

• 動態規劃時間復雜度：外層循環：O(amount)，內層循環：O(coins.length)，總復雜度：O(amount * coins.length)。
• BFS時間復雜度：最壞情況：O(amount * coins.length)，實際效率取決于硬幣面額分布，大額硬幣可能加速收斂。

對比總結

方法	優勢	劣勢
BFS	無需預計算所有狀態，快速收斂	空間復雜度高（隊列膨脹）
動態規劃	適合多次查詢，空間可控	需遍歷全部狀態

---

347. 前 K 個高頻元素

給你一個整數數組 nums 和一個整數 k ，請你返回其中出現頻率前 k 高的元素。你可以按任意順序返回答案。

示例 1:

輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]

示例 2:

輸入: nums = [1], k = 1
輸出: [1]

提示：

• 1 <= nums.length <= 105
• k 的取值范圍是 [1, 數組中不相同的元素的個數]
• 題目數據保證答案唯一，換句話說，數組中前 k 個高頻元素的集合是唯一的

進階： 你所設計算法的時間復雜度必須優于 O(n log n) ，其中 n 是數組大小。

方法一：最小堆（優先隊列）

使用最小堆維護當前頻率最高的k個元素，遍歷時保持堆的大小不超過k，時間復雜度為O(n log k)。

1. 統計頻率：使用哈希表記錄每個元素的出現次數。
2. 維護最小堆：將元素按頻率加入堆，堆大小超過k時移除堆頂（最小頻率元素）。
3. 提取結果：堆中剩余的元素即為前k高的頻率元素。

代碼實現(Java)：

class Solution {public int[] topKFrequent(int[] nums, int k) {// 統計頻率Map<Integer, Integer> freqMap = new HashMap<>();for (int num : nums) {freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);}// 創建最小堆，按頻率升序排序PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());// 維護堆的大小為kfor (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {heap.offer(entry);if (heap.size() > k) {heap.poll();}}// 提取結果int[] res = new int[k];int idx = 0;while (!heap.isEmpty()) {res[idx++] = heap.poll().getKey();}return res;}
}

方法二：桶排序

基于頻率的桶排序，時間復雜度為O(n)，適合處理大數據量。

1. 統計頻率：記錄每個元素出現的次數及最大頻率。
2. 構建頻率桶：將元素按頻率存入對應桶中。
3. 逆序收集結果：從高頻率到低頻率遍歷桶，收集前k個元素。

代碼實現(Java)：

class Solution {public int[] topKFrequent(int[] nums, int k) {// 統計頻率Map<Integer, Integer> freqMap = new HashMap<>();for (int num : nums) {freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);}// 創建桶數組List<Integer>[] bucket = new List[nums.length + 1];for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {int freq = entry.getValue();if (bucket[freq] == null) {bucket[freq] = new ArrayList<>();}bucket[freq].add(entry.getKey());}// 收集結果int[] res = new int[k];int idx = 0;for (int i = bucket.length - 1; i >= 0 && idx < k; i--) {if (bucket[i] != null) {for (int num : bucket[i]) {res[idx++] = num;if (idx == k) break;}}}return res;}
}

復雜度分析

1、最小堆

• 時間復雜度：O(n log k)，其中n為數組長度，k為結果數量。
  空間復雜度：O(n)，哈希表和堆的空間。
• 優點：空間占用相對較低，適合k較小的情況。
  缺點：當k接近n時，時間復雜度接近O(n log n)。

2、桶排序

• 時間復雜度：O(n)，所有操作均為線性時間。
  空間復雜度：O(n)，桶數組和哈希表的空間。
• 優點：時間復雜度嚴格為O(n)，適合大數據量。
  缺點：需要額外空間存儲桶，最大頻率較高時空間占用大。

---

394. 字符串解碼

給定一個經過編碼的字符串，返回它解碼后的字符串。
編碼規則為: k[encoded_string]，表示其中方括號內部的 encoded_string 正好重復 k 次。注意 k 保證為正整數。
你可以認為輸入字符串總是有效的；輸入字符串中沒有額外的空格，且輸入的方括號總是符合格式要求的。
此外，你可以認為原始數據不包含數字，所有的數字只表示重復的次數 k ，例如不會出現像 3a 或 2[4] 的輸入。

示例 1：

輸入：s = "3[a]2[bc]"
輸出："aaabcbc"

示例 2：

輸入：s = "3[a2[c]]"
輸出："accaccacc"

示例 3：

輸入：s = "2[abc]3[cd]ef"
輸出："abcabccdcdcdef"

示例 4：

輸入：s = "abc3[cd]xyz"
輸出："abccdcdcdxyz"

提示：

• 1 <= s.length <= 30
• s 由小寫英文字母、數字和方括號 '[]' 組成
• s 保證是一個有效的輸入
• s 中所有整數的取值范圍為 [1, 300]

方法：棧輔助法

利用棧來處理嵌套的括號結構，保存每層括號外的字符串和重復次數。遍歷字符串時解析數字，遇到左括號時將當前狀態壓棧，遇到右括號時彈出棧頂元素進行字符串拼接。

1. 初始化棧和變量：使用兩個棧分別保存當前層的字符串和重復次數，當前字符串和數字變量記錄正在處理的部分。
2. 遍歷字符：
   • 數字：累加計算多位數。
   • 左括號：壓棧當前字符串和數字，重置變量。
   • 右括號：彈出棧頂的字符串和數字，將當前字符串重復后拼接。
   • 字母：直接追加到當前字符串。
3. 返回結果：最終拼接完成的字符串即為答案。

代碼實現(Java)：

class Solution {public String decodeString(String s) {Stack<Integer> numStack = new Stack<>();Stack<StringBuilder> strStack = new Stack<>();StringBuilder currentStr = new StringBuilder();int num = 0;for (char c : s.toCharArray()) {if (Character.isDigit(c)) {num = num * 10 + (c - '0');} else if (c == '[') {strStack.push(currentStr);numStack.push(num);currentStr = new StringBuilder();num = 0;} else if (c == ']') {int k = numStack.pop();StringBuilder prevStr = strStack.pop();String temp = currentStr.toString();prevStr.append(temp.repeat(k));currentStr = prevStr;} else {currentStr.append(c);}}return currentStr.toString();}
}

復雜度分析

• 時間復雜度：O(n × m)，其中n是字符串長度，m是最大重復次數。每個字符處理一次，字符串拼接的時間取決于重復次數。
• 空間復雜度：O(n)，棧的深度最壞情況下與字符串長度成線性關系。

---

博客源文件Gitee倉庫:

gitee.com/richardmilos/allen-csdn-notes

(持續更新，未完待續)