2023 shein笔试题 0727
笔试时间:2023年7月27日 秋招提前批
第一题
题目:零钱兑换
给定数组arr,arr中所有的值都为正整数且不重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个aim,代表要找的钱数,求组成aim的最少货币数。
如果无解,请返回-1.
输入描述
第一行给定两个正整数分别是 n 和 aim 分别表示数组 arr 的长度和要找的钱数。
第二行给定 n 个正整数表示 arr 数组中的所有元素
输出描述
输出组成 aim 的最少货币数
样例输入
示例1:
3 20
5 2 3
示例2:
3 0
5 2 3
样例输出
示例1:
4
说明:最少用四个 5 元凑成 20 元
示例2:
0
参考题解
此题是典型的完全背包问题。
状态转移方程式:dp[i][j]考虑前i个硬币,凑出 j 元最少需要的硬币数。dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i])
容器规模:i 的范围是[0, coins.length] j 的范围是 [0, amount]
base case:dp[0][j]表示考虑前0个硬币凑出j的最少硬币数,除了dp[0][0] = 0以外,其余的均凑不了,也就是没有硬币的情况下,只能凑出0,其他的金额都凑不了,因此这里用一个比较大的数字表示(因为amount最大是10^4,因此我们用10001表示最大值)
顺序:i = 1 开始填表
可以利用滚动数组进行优化
C++:
#include <vector> #include <algorithm> #include <climits> class Solution { public: int coinChange(std::vector<int>& coins, int amount) { std::vector<int> dp(amount + 1, 10001); dp[0] = 0; for (int i = 1; i <= coins.size(); i++) { for (int j = coins[i - 1]; j <= amount; j++) { dp[j] = std::min(dp[j], dp[j - coins[i - 1]] + 1); } } return (dp[amount] == 10001) ? -1 : dp[amount]; } };
Java:
class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, 10001); dp[0] = 0; for (int i = 1 ; i <= coins.length ; i++) { for (int j = coins[i - 1] ; j <= amount ; j++) { d
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2023 秋招笔试题汇总解析 文章被收录于专栏
2023秋招各大笔试题汇总,c++,java,python多种语言分析,解答。