当前位置：首页 > news >正文

南通模板网建站app制作公司

news 2025/7/18 11:47:16

南通模板网建站,app制作公司,蚌埠大建设及棚户区改造官方网站,西安网站空间LeetCode/卡码网题目: 322. 零钱兑换279. 完全平方数139. 单词拆分1920. 基于排列构建数组(每日一题5-6)56. 携带矿石资源（第八期模拟笔试） 其他: 今日总结往期打卡 322. 零钱兑换跳转: 322. 零钱兑换学习: 代码随想录公开讲解问题: 给你一个整数…

LeetCode/卡码网题目:

322. 零钱兑换
279. 完全平方数
139. 单词拆分
1920. 基于排列构建数组(每日一题5-6)
56. 携带矿石资源（第八期模拟笔试）

其他:

今日总结
往期打卡

322. 零钱兑换

跳转: 322. 零钱兑换

学习: 代码随想录公开讲解

问题:

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

思路:

完全背包问题求最小个数,排列或组合都没关系,只需要初始化成大值,剩下的就是价值看成1取最小,和最多物品相反.

复杂度:

时间复杂度: $O (mn)$
空间复杂度: $O (n)$

代码:

class Solution {public int coinChange(int[] coins, int amount) {if(amount==0) return 0;int[] dp = new int[amount+1];Arrays.fill(dp,Integer.MAX_VALUE>>1);dp[0] = 0;for(int i=0;i<coins.length;i++)for(int j=coins[i];j<=amount;j++){dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);}return dp[amount]>10001?-1:dp[amount];}
}

279. 完全平方数

跳转: 279. 完全平方数

学习: 代码随想录公开讲解

问题:

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

思路:

完全背包问题求最小个数,和上题思路相同.初始化大值,价值看成1取最小.

复杂度:

时间复杂度: $O (mn)$
空间复杂度: $O (n)$

代码:

class Solution {public int numSquares(int n) {if (n == 0) return 0;int[] dp = new int[n + 1];Arrays.fill(dp, Integer.MAX_VALUE >> 1);dp[0] = 0;for (int i = 1; i <= Math.sqrt(n); i++) {int x = i * i;for (int j = x; j <= n; j++) {dp[j] = Math.min(dp[j], dp[j -x] + 1);}}return dp[n] > 10001 ? -1 : dp[n];}
}

139. 单词拆分

跳转: 139. 单词拆分

学习: 代码随想录公开讲解

问题:

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意： 不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

思路:

可以看作完全背包问题,只不过装入需要条件,必须单词符合且前面装过才能装入,而且与排列有关,需要内层循环遍历物品

复杂度:

时间复杂度: $O (mn)$
空间复杂度: $O (n)$

代码:

class Solution {public boolean wordBreak(String s, List<String> wordDict) {int n = s.length();boolean[] dp = new boolean[n+1];Arrays.fill(dp,false);dp[0] = true;for (int i = 1; i <= n; i++) {for (String str : wordDict) {int x = i-str.length();if(x>=0&&dp[x]&&s.substring(x,i).equals(str)){dp[i] = true;}}}return dp[n];}
}

1920. 基于排列构建数组(每日一题5-6)

跳转: 1920. 基于排列构建数组

学习: 灵茶山艾府题解

问题:

给你一个 从 0 开始的排列 nums（下标也从 0 开始）。请你构建一个 同样长度 的数组 ans ，其中，对于每个 i（0 <= i < nums.length），都满足 ans[i] = nums[nums[i]] 。返回构建好的数组 ans 。

从 0 开始的排列 nums 是一个由 0 到 nums.length - 1（0 和 nums.length - 1 也包含在内）的不同整数组成的数组。

思路:

数字搬家,因为每个数字都有位置,所以最后循环一圈肯定能从给当前数搬家到搬家到当前位置,这种循环可能有多组,需要防止重复操作,比如取反后为负数标识为已操作.

复杂度:

时间复杂度: $O (n)$
空间复杂度: $O (1)$

代码:

class Solution {public int[] buildArray(int[] nums) {for(int i=0;i<nums.length;i++){int x = nums[i];if(x<0) continue;int cur = i;while(nums[cur]!=i){int nxt = nums[cur];nums[cur] = ~nums[nxt];cur = nxt;}nums[cur] = ~x;}for(int i=0;i<nums.length;i++)nums[i] = ~nums[i];return nums;}
}

56. 携带矿石资源（第八期模拟笔试）

跳转: 56. 携带矿石资源（第八期模拟笔试）

学习: 代码随想录公开讲解

问题:

你是一名宇航员，即将前往一个遥远的行星。在这个行星上，有许多不同类型的矿石资源，每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球，但你的宇航舱有一定的容量限制。

给定一个宇航舱，最大容量为 C。现在有 N 种不同类型的矿石，每种矿石有一个重量 w[i]，一个价值 v[i]，以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下，最大化你所能获取的总价值。

思路:

展开看成01背包求最大价值

复杂度:

时间复杂度: $O (mnk)$
空间复杂度: $O (n)$

代码:

import java.util.Scanner;
class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);int C = sc.nextInt();int N = sc.nextInt();int[] w = new int[N];int[] v = new int[N];int[] nums = new int[N];for(int i=0;i<N;i++){w[i] = sc.nextInt();}for(int i=0;i<N;i++){v[i] = sc.nextInt();}for(int i=0;i<N;i++){nums[i] = sc.nextInt();}int[] dp = new int[C+1];for(int i=0;i<N;i++){for(int k = 0;k<nums[i];k++){for(int j=C;j>=w[i];j--){dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i]); }}}System.out.println(dp[C]);}
}