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多种语言分析,解答。

全部评论

相关推荐

豆泥🍀:同26届,加油,我也还没找到查看图片
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客企业服务