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

本文主要是介绍代码随想录算法训练营第四十三天| 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 的完全平方数的最少数量 。

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,149 和 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

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码,该代码实现了图片的旋转(90度和180度)以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中,

Python如何去除图片干扰代码示例

《Python如何去除图片干扰代码示例》图片降噪是一个广泛应用于图像处理的技术,可以提高图像质量和相关应用的效果,:本文主要介绍Python如何去除图片干扰的相关资料,文中通过代码介绍的非常详细,... 目录一、噪声去除1. 高斯噪声(像素值正态分布扰动)2. 椒盐噪声(随机黑白像素点)3. 复杂噪声(如伪

Java Spring ApplicationEvent 代码示例解析

《JavaSpringApplicationEvent代码示例解析》本文解析了Spring事件机制,涵盖核心概念(发布-订阅/观察者模式)、代码实现(事件定义、发布、监听)及高级应用(异步处理、... 目录一、Spring 事件机制核心概念1. 事件驱动架构模型2. 核心组件二、代码示例解析1. 事件定义