学习工控知识，就来工控小新
农历十一月初五
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[i]);
// 如果最远跳跃下标已经大于等于数组的最后一个下标，说明可以跳跃到最后一个下标，返回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[i]);
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;
}
程序测试
运行程序：
给定一个二叉树，检查它是不是镜像对称的
点赞加关注，学习不迷路
微信公众号｜工控小新
EPLAN电气绘图、TIA博图基础 、CAD、C语言教学、单片机基础、三菱PLC ... 每日持续更新中
