代码随想录算法训练营第四十三天| 377. 组合总和 Ⅳ、57. 爬楼梯（第八期模拟笔试）、322. 零钱兑换、279. 完全平方数

2024-06-18 19:36
文章标签 算法 随想录 代码 组合 笔试 模拟 训练营 完全 平方 279 总和 377 爬楼梯 兑换 零钱 57 322 第八期 四十三天

本文主要是介绍代码随想录算法训练营第四十三天| 377. 组合总和 Ⅳ、57. 爬楼梯（第八期模拟笔试）、322. 零钱兑换、279. 完全平方数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[LeetCode] 377. 组合总和 Ⅳ
[LeetCode] 377. 组合总和 Ⅳ 文章解释

[LeetCode] 377. 组合总和 Ⅳ 视频解释​​​​​​​

题目：

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3
输出：0

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • nums 中的所有元素 互不相同
  • 1 <= target <= 1000

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

[LeetCode] 377. 组合总和 Ⅳ

自己看到题目的第一想法

    从一堆数中，找出总和等于或者最接近于总和的数，可以考虑用01背包或者完全背包等背包算法。

    这里求的是等于总和的组合个数，因此是背包问题应用到组合或者排列上。对于组合和排列的区别，在于当先便利容量时，dp[j] 是否和低位的 dp[j - weights[i]] 叠加， 有叠加的话就是排列问题，没有的话就是组合问题。（一开始想不明白其中的逻辑，后来画了好几次 dp 的模拟数据，才意识到 dp[i] = dp[i] + dp[i - weights[j]], 比如当前处理的背包容量为3，物品分别取 weights[j] = 1 以及 weights[j] = 2， 那么 dp[3] = dp[3] + dp[3 - 1](这里表示 1 + dp[2] 的组合)， dp[3] = dp[3] + dp[3 - 2](这里表示2+dp[1]的组合)。

看完代码随想录之后的想法

    因为之前有零钱组合的问题中踩过坑，所以这里一下子就想起那时候的问题。只要调换一下遍历顺序就行。

class Solution {public int combinationSum4(int[] nums, int target) {// dp[j] 表示使用 0～i 个元素，元素和为 j 的组合的个数int[] dp = new int[target + 1];dp[0] = 1;for (int i = 0; i <= target; i++) {for (int j = 0; j < nums.length; j++) {if (i < nums[j]) {continue;}dp[i] = dp[i] + dp[i - nums[j]];}}return dp[target];}
}
// 二维数组版本 
class Solution {public int combinationSum4(int[] nums, int target) {// dp[j] 表示使用 0～i 个元素，元素和为 j 的组合的个数int[][] dp = new int[nums.length][target + 1];dp[0][0] = 1;for (int i = nums[0]; i <= target; i++) {dp[0][i] = dp[0][i - nums[0]];}for (int j = 0; j <= target; j++) {for (int i = 1; i < nums.length; i++) {if (nums[i] > j) {// 当前物品无法放入当前的背包dp[i][j] = dp[i - 1][j];continue;}// 当前物品可以放入当前的背包// 这里 j 表示当前的背包的重量，i 表示当前物品最大的索引// 由于要求排列， 因此需要遍历一下所有的物品，// 以遍历到的物品为开头，看看以 i 为最大物品索引，j - nums[k] 为背包容量时，一共有多少组合// (我也是似懂非懂)for (int k = 0; k <= i; k++) {if (nums[k] > j) {continue;}dp[i][j] += dp[i][j - nums[k]];}}}return dp[nums.length - 1][target];}
}

自己实现过程中遇到哪些困难

    初始化问题还是比较棘手，需要多次尝试才能找到正确的方式。 

    二维数组版本给我整懵了！ 完全是模拟了一下 dp 后强行写出来的结果。。。

[KamaCoder] 57. 爬楼梯（第八期模拟笔试）

[KamaCoder] 57. 爬楼梯（第八期模拟笔试） 文章解释

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？ 

注意：给定 n 是一个正整数。

输入描述

输入共一行，包含两个正整数，分别表示n, m 

输出描述

输出一个整数，表示爬到楼顶的方法数。 

输入示例
3 2
输出示例
3
提示信息

数据范围： 
1 <= m < n <= 32;

当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。

此时你有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶段
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

[KamaCoder] 57. 爬楼梯（第八期模拟笔试） 

自己看到题目的第一想法

    如果一次可以跨越 m 个楼梯， 对于跨越到楼梯 i 的方式，一共有 dp[i - m] + dp[i - m + 1] ... + dp[i - 1]

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int maxStep = 0;int maxStairs = 0;while (scanner.hasNext()) {String stepAndStairsStr = scanner.nextLine();String[] stepAndStairs = stepAndStairsStr.split(" ");maxStairs = Integer.parseInt(stepAndStairs[0]);maxStep = Integer.parseInt(stepAndStairs[1]);}int[] dp = new int[maxStairs + 1];dp[0] = 1;for (int i = 1; i <= maxStairs; i++) {int lowestStair = i - maxStep;if (lowestStair < 0) {lowestStair = 0;}for (int j = lowestStair; j < i; j++) {dp[i] += dp[j];}}System.out.println(dp[maxStairs]);}
}

看完代码随想录之后的想法

    hhh， 自己的实现是很不动态规划的动态规划～

    这一题如果转换一下逻辑，对于第 i 层楼梯，要登上该楼梯，我们每次可以走 1 步、可以走 2 步、可以走 3 步，最多可以走 m 步，请问到达第 i 层楼梯一共有多少种走法。

    也就是说， 我们从 1 ～ m 中不断的选出数字， 最终加起来等于 i 的排列有几种。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int maxStep = 0;int maxStairs = 0;while (scanner.hasNext()) {String stepAndStairsStr = scanner.nextLine();String[] stepAndStairs = stepAndStairsStr.split(" ");maxStairs = Integer.parseInt(stepAndStairs[0]);maxStep = Integer.parseInt(stepAndStairs[1]);}int[] dp = new int[maxStairs + 1];dp[0] = 1;for (int i = 1; i <= maxStairs; i++) {for (int j = 1; j <= maxStep; j++) {if (i < j) {continue;}dp[i] += dp[i - j];}}System.out.println(dp[maxStairs]);}
}

自己实现过程中遇到哪些困难

   对于需要转化为完全背包的问题，由于当前问题可能并没有 weight 和 value（weight 和 value 的值都是相等的），因此在逻辑上会有点绕不过来。 

[LeetCode] 322. 零钱兑换
[LeetCode] 322. 零钱兑换 文章解释

[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

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

[LeetCode] 322. 零钱兑换 

自己看到题目的第一想法

    从多个数字中选取几个数字， 使这几个数字相加和为 target，数字可以重复选择， 因此是完全背包问题。

看完代码随想录之后的想法

    基本上差不多的想法， 初始化的逻辑不太一样。

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

自己实现过程中遇到哪些困难

    因为要求的是最小值， 因此就需要知道当前的 dp[j] 是否有效，在自己写算法代码的时候， 尝试了非常多的方式，最终才尝试出将 dp 数组赋值为 -1 的方式： dp[i] = -1.

[LeetCode] 279. 完全平方数
[LeetCode] 279. 完全平方数 文章解释

[LeetCode] 279. 完全平方数 视频解释

题目：

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

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

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

  • 1 <= n <= 10^4

[LeetCode] 279. 完全平方数

自己看到题目的第一想法

    先找到平方后依旧小于 n 的最大整数。从 1 到找到的这个整数，同时求平方，得到可以挑选的数字列表。再从这几个数字中不停的挑选数字，求和为 n 的最小数字个数。因此可以转换为完全背包问题。

看完代码随想录之后的想法

    思路一样，代码实现细节不同。 特别在于对 dp[j] 是否有效上， 将 dp[j] 初始化为 Integer.MAX_VALUE 确实很有效。 

// 先遍历容量是排列，比组合更低效一些
class Solution {public int numSquares(int n) {int[] dp = new int[n + 1];for (int i = 0; i < dp.length; i++) {dp[i] = Integer.MAX_VALUE;}dp[0] = 0;for (int j = 1; j <= n; j++) {for (int i = 1; i * i <= j; i++) {dp[j] = Math.min(dp[j], dp[j - i * i] + 1);}}return dp[n];}
}
// 先遍历元素的话是组合，比先遍历容量的排列更高效一些
class Solution {public int numSquares(int n) {int[] dp = new int[n + 1];for (int i = 0; i < dp.length; i++) {dp[i] = Integer.MAX_VALUE;}dp[0] = 0;// 先遍历元素, 元素的值为 i*i for (int i = 1; i * i <= n; i++) {// 后遍历容量for (int j = i * i; j <= n; j++) {dp[j] = Math.min(dp[j], dp[j - i * i] + 1);}}return dp[n];}
}

 

// 不初始化的方式，我也不知道这样的实现有没有意义。。。似乎挺蠢的？
class Solution {public int numSquares(int n) {int[] dp = new int[n + 1];// 先遍历元素, 元素的值为 i*i for (int i = 1; i * i <= n; i++) {// 后遍历容量for (int j = i * i; j <= n; j++) {if (j - i * i == 0) {dp[j] = 1;} else if (dp[j - i * i] > 0) {if (dp[j] == 0) {dp[j] = dp[j - i * i] + 1;} else {dp[j] = Math.min(dp[j], dp[j - i * i] + 1);}}}}return dp[n];}
}

自己实现过程中遇到哪些困难

    没想到把 dp 数组初始化为 Integer.MAX_VALUE 的方式，绕了不少弯路。 

这篇关于代码随想录算法训练营第四十三天| 377. 组合总和 Ⅳ、57. 爬楼梯（第八期模拟笔试）、322. 零钱兑换、279. 完全平方数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1072918。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
hdu4869（逆元+求组合数）

hdu4869（逆元+求组合数）

//输入n，m，n表示翻牌的次数，m表示牌的数目，求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
活用c4d官方开发文档查询代码

活用c4d官方开发文档查询代码

当你问AI助手比如豆包，如何用python禁止掉xpresso标签时候，它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来
阅读更多...
usaco 1.2 Transformations（模拟）

usaco 1.2 Transformations（模拟）

我的做法就是一个一个情况枚举出来 注意计算公式： （ 变换后的矩阵记为C） 顺时针旋转90°：C[i] [j]=A[n-j-1] [i] （旋转180°和270° 可以多转几个九十度来推） 对称：C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2