|
>
学习工控知识，就来工控小新
农历十一月初五
2023/12/ 17
往期推荐
2023年12月16日，这个C语言的编程题目，可能是你见过的最简单的矩阵运算！
2023年12月14日，每天花费一分钟练习C语言：用C语言判断自己体重标准，今天你瘦了吗？
每
日
一
练
/ Daily Exercises
题目：
给定一个非负整数数组nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
题目分析
这是一个经典的动态规划问题，它要求给定一个非负整数数组nums，判断从数组的第一个下标开始，是否能够通过跳跃到达最后一个下标。数组中的每个元素代表在该位置可以跳跃的最大长度。例如，给定数组[2, 3, 1, 1, 4]，从第一个下标开始，可以跳跃到第二个下标，然后跳跃到第四个下标，再跳跃到最后一个下标，所以返回true。但是，给定数组 [3,2, 1, 0, 4]，从第一个下标开始，无论如何都无法跳跃到最后一个下标，所以返回false。
要解决这个问题，我们可以使用一个一维数组dp，用来记录从第一个下标开始，能够跳跃到的最远的下标。初始时，dp[0]=nums[0]，表示从第一个下标开始，最多可以跳跃到第一个下标加上第一个元素的位置。然后，我们遍历数组中的每个元素，对于每个元素，我们判断它的下标是否小于等于当前的最远跳跃下标，如果是，说明它是可以到达的，那么我们就更新最远跳跃下标为它的下标加上它的元素值，和原来的最远跳跃下标的较大值。如果不是，说明它是无法到达的，那么我们就跳过它，继续遍历下一个元素。最后，我们判断最远跳跃下标是否大于等于数组的最后一个下标，如果是，说明可以跳跃到最后一个下标，返回true。如果不是，说明无法跳跃到最后一个下标，返回false。
为了实现这个算法，我们需要定义一个函数，用来判断一个数组是否能够跳跃到最后一个下标。函数的参数是一个非负整数数组和它的长度，函数的返回值是一个布尔值，表示是否能够跳跃到最后一个下标。
函数伪代码
// 定义跳跃函数bool canJump(int[] nums, int n) { // 如果数组为空或者长度为0，返回false if (nums == null || n == 0) { return false; } // 定义一个变量，用来记录从第一个下标开始，能够跳跃到的最远的下标，初始值为nums[0] int maxJump = nums[0]; // 遍历数组中的每个元素，从第二个元素开始 for (int i = 1; i < n; i++) { // 判断当前元素的下标是否小于等于最远跳跃下标，如果是，说明它是可以到达的 if (i <= maxJump) { // 更新最远跳跃下标为当前元素的下标加上当前元素的值，和原来的最远跳跃下标的较大值 maxJump = max(maxJump, i + nums); // 如果最远跳跃下标已经大于等于数组的最后一个下标，说明可以跳跃到最后一个下标，返回true if (maxJump >= n - 1) { return true; } } // 如果当前元素的下标大于最远跳跃下标，说明它是无法到达的，跳过它，继续遍历下一个元素 else { continue; } } // 遍历完所有的元素后，如果最远跳跃下标仍然小于数组的最后一个下标，说明无法跳跃到最后一个下标，返回false return false;}
完整程序展示
// 导入标准输入输出库#include <stdio.h>
// 定义一个辅助函数，用来求两个整数的较大值int max(int a, int b) { return a > b ? a : b;}
// 定义跳跃函数，参数和返回值与伪代码相同bool canJump(int nums[], int n) { if (nums == NULL || n == 0) { return false; } int maxJump = nums[0]; for (int i = 1; i < n; i++) { if (i <= maxJump) { maxJump = max(maxJump, i + nums); if (maxJump >= n - 1) { return true; } } else { continue; } } return false;}
// 定义主函数，用来测试跳跃函数int main() { // 定义两个测试用例的数组和它们的长度 int nums1[5] = {2, 3, 1, 1, 4}; int n1 = 5; int nums2[5] = {3, 2, 1, 0, 4}; int n2 = 5; // 调用跳跃函数，传入数组和长度，打印返回值 printf("The result for the first array is %d.\n", canJump(nums1, n1)); printf("The result for the second array is %d.\n", canJump(nums2, n2)); // 返回0，表示程序正常结束 return 0;}
程序测试
运行程序：
下期题目
给定一个二叉树，检查它是不是镜像对称的
有需要C语言书籍的朋友可以从下面的链接进行购买，或者跟着我一起学习也行
点赞加关注，学习不迷路
微信公众号｜工控小新
EPLAN电气绘图、TIA博图基础 、CAD、C语言教学、单片机基础、三菱PLC ... 每日持续更新中
发现“分享”和“赞”了吗，戳我看看吧
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
