本文主要是介绍力扣热门算法题 322. 零钱兑换，344. 反转字符串，347. 前 K 个高频元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
322. 零钱兑换，344. 反转字符串，347. 前 K 个高频元素，每题做详细思路梳理，配套Python&Java双语代码， 2024.04.02 可通过leetcode所有测试用例。
目录
322. 零钱兑换
解题思路
完整代码
Python
Java
编辑
344. 反转字符串
解题思路
完整代码
Python
Java
编辑
347. 前 K 个高频元素
解题思路
完整代码
Python
Java
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) - 1while 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;}
}这篇关于力扣热门算法题 322. 零钱兑换，344. 反转字符串，347. 前 K 个高频元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
