322. 零钱兑换，344. 反转字符串，347. 前 K 个高频元素，每题做详细思路梳理，配套Python&Java双语代码， 2024.04.02 可通过leetcode所有测试用例。
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
解题思路
-
初始化动态规划表：创建一个长度为
amount + 1的数组dp，其中dp[i]表示组成金额i所需的最少硬币数量。由于金额 0 不需要任何硬币，所以dp[0] = 0。对于其他金额，可以初始化为一个大数，例如amount + 1，表示这个金额当前无法被组成。 -
填充动态规划表：遍历每一个金额
i从1到amount，对于每个i，再遍历每一个硬币面额coin，如果coin小于等于i，意味着这个硬币可以被用来组成金额i。此时，我们更新dp[i]为min(dp[i], dp[i - coin] + 1)，即比较当前dp[i]的值和使用这个硬币之后的硬币总数（dp[i - coin] + 1）哪个更小，取较小值更新dp[i]。 -
返回结果：计算完成后，检查
dp[amount]的值，如果它仍然是初始化的大数（表示无法组成），则返回-1；否则，返回dp[amount]，即组成金额amount所需的最少硬币数量。
完整代码
Python
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# 初始化动态规划数组，所有值设为一个大数
dp = [amount + 1] * (amount + 1)
dp[0] = 0 # 金额为0时不需要硬币
# 动态规划填表
for i in range(1, amount + 1):
for coin in coins:
if i - coin >= 0:
dp[i] = min(dp[i], dp[i - coin] + 1)
# 检查是否有解
return dp[amount] if dp[amount] != amount + 1 else -1Java
class Solution {
public int coinChange(int[] coins, int amount) {
// 初始化动态规划数组，所有值设为一个大数
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0; // 金额为0时不需要硬币
// 动态规划填表
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i - coin >= 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
// 检查是否有解
return dp[amount] != amount + 1 ? dp[amount] : -1;
}
}
344. 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组
s的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"] 输出：["o","l","l","e","h"]示例 2：
输入：s = ["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]
解题思路
-
初始化两个指针：
left指针指向数组的第一个元素，right指针指向数组的最后一个元素。 -
交换并移动：当
left指针小于right指针时，交换它们指向的元素，然后将left指针向右移动一位，right指针向左移动一位。 -
重复上述过程：继续进行交换和移动，直到
left指针不再小于right指针。 -
完成反转：当
left指针大于或等于right指针时，整个数组已经反转完成。
完整代码
Python
class Solution:
def reverseString(self, s: List[str]) -> None:
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left] # 交换两个指针指向的元素
left, right = left + 1, right - 1 # 移动指针Java
class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while (left < right) {
// 交换两个指针指向的元素
char temp = s[left];
s[left] = s[right];
s[right] = temp;
// 移动指针
left++;
right--;
}
}
}
347. 前 K 个高频元素
给你一个整数数组
nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]示例 2:
输入: nums = [1], k = 1 输出: [1]
解题思路
-
使用哈希表统计频率：遍历数组
nums，使用哈希表（或字典）记录每个元素出现的次数。 -
构建最小堆：由于需要找出前
k高的元素，我们可以构建一个最小堆，这个堆中存放的是元素及其频率的对，按照频率进行排序。堆的大小维持在k，这样堆顶就是当前第k高的频率。 -
遍历哈希表，填充堆：遍历步骤1中的哈希表，将元素及其频率的对加入到最小堆中。当堆的大小超过
k时，移除堆顶元素，这样可以保证堆中始终是当前频率最高的k个元素。 -
收集结果：最后，堆中的元素即为出现频率前
k高的元素，遍历堆并收集元素。
完整代码
Python
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# 统计元素出现频率
count = Counter(nums)
# 构建最小堆，只保留频率最高的k个元素
heap = []
for num, freq in count.items():
heapq.heappush(heap, (freq, num))
if len(heap) > k:
heapq.heappop(heap)
# 收集结果
return [num for freq, num in heap]Java
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 使用哈希表统计每个数字出现的次数
Map<Integer, Integer> frequencyMap = new HashMap<>();
for (int num : nums) {
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
// 构建一个最小堆，堆的大小为 k。使用 (频率, 数字) 的元组来比较元素
PriorityQueue<Integer> heap = new PriorityQueue<>(
(n1, n2) -> frequencyMap.get(n1) - frequencyMap.get(n2));
// 遍历频率哈希表，维护一个大小为 k 的最小堆
for (int num : frequencyMap.keySet()) {
heap.add(num);
if (heap.size() > k) {
heap.poll(); // 移除堆顶元素，即频率最小的元素
}
}
// 取出最小堆中的元素，这些就是频率最高的 k 个元素
int[] topK = new int[k];
for (int i = 0; i < k; i++) {
topK[i] = heap.poll(); // 依次从堆顶取出元素
}
return topK;
}
}
