平台和自建网站服务提供者,网上购物哪个商城好,全国旅游卡app,企业文化学习心得其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 前缀和的解题模板
2.1.1 最长递增子序列长度
2.1.2 寻找数组中第 k 大的元素
2.1.3 最长公共子序列… 其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 前缀和的解题模板
2.1.1 最长递增子序列长度
2.1.2 寻找数组中第 k 大的元素
2.1.3 最长公共子序列长度
2.1.4 寻找数组中第 k 小的元素
2.2 方法一前缀和差分数组
三、代码
3.2 方法一前缀和差分数组
四、复杂度分析
4.2 方法一前缀和差分数组 前言
这是力扣的 1732 题难度为简单解题方案有很多种本文讲解我认为最奇妙的一种。
这是一道非常经典的前缀和问题虽然看似简单但它却能让你深入理解前缀和的特点。 一、题目描述
有一个自行车手打算进行一场公路骑行这条路线总共由 n 1 个不同海拔的点组成。自行车手从海拔为 0 的点 0 开始骑行。
给你一个长度为 n 的整数数组 gain 其中 gain[i] 是点 i 和点 i 1 的 净海拔高度差0 i n。请你返回 最高点的海拔 。
示例 1 输入gain [-5,1,5,0,-7]
输出1
解释海拔高度依次为 [0,-5,-4,1,1,-6] 。最高海拔为 1 。示例 2 输入gain [-4,-3,-2,-1,4,3,2]
输出0
解释海拔高度依次为 [0,-4,-7,-9,-10,-6,-3,-1] 。最高海拔为 0 。提示
n gain.length1 n 100-100 gain[i] 100 二、题解 2.1 前缀和的解题模板
前缀和算法是一种在处理数组或链表问题时常用的技巧它可以有效地减少重复计算提高算法的效率。下面是一些常见的使用前缀和算法的题目以及解题思路
2.1.1 最长递增子序列长度 题目描述给定一个无序数组求最长递增子序列的长度。 解题思路可以使用前缀和和单调栈来解决这个问题。首先遍历数组计算出前缀和。然后使用单调栈记录当前递增子序列的起始位置。遍历数组时如果当前元素大于前缀和说明可以扩展当前递增子序列将当前位置入栈。如果当前元素小于等于前缀和说明当前递增子序列已经结束弹出栈顶元素。最后栈中剩余的元素即为最长递增子序列的起始位置计算长度即可。
2.1.2 寻找数组中第 k 大的元素 题目描述给定一个无序数组和一个整数k找到数组中第k大的元素。 解题思路可以使用前缀和和快速选择算法来解决这个问题。首先计算出数组的前缀和。然后使用快速选择算法在数组中找到第k小的元素。具体实现中每次选择一个枢轴元素将数组分成两部分小于枢轴的元素和大于枢轴的元素。如果枢轴左边的元素个数小于k则在左边的子数组中继续查找如果枢轴左边的元素个数大于等于k则在右边的子数组中继续查找。最后当找到第k小的元素时返回该元素即可。
2.1.3 最长公共子序列长度 题目描述给定两个字符串求最长公共子序列的长度。 解题思路可以使用动态规划算法来解决这个问题。如果字符串长度分别为m和n则可以定义一个二维数组dp[m1][n1]其中dp[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符的最长公共子序列长度。根据动态规划的思想状态转移方程为dp[i][j] max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])。如果s1[i-1]等于s2[j-1]则dp[i][j] dp[i-1][j-1] 1否则dp[i][j]取其他两种情况中的较大值。最终结果为dp[m][n]。
2.1.4 寻找数组中第 k 小的元素 题目描述给定一个无序数组和一个整数k找到数组中第k小的元素。 解题思路可以使用前缀和和快速选择算法来解决这个问题。具体实现与寻找第k大元素类似只不过最后返回的是第k小的元素而非第k大的元素。
2.2 方法一前缀和差分数组
解这个问题需要注意以下几点
理解题意首先要明确题目的要求理解自行车手的骑行路线和海拔变化的关系。根据题目描述自行车手从海拔为0的点开始骑行通过一系列的海拔变化最终要找到最高点的海拔。分析海拔变化根据给定的gain数组可以分析出自行车手的海拔变化。gain[i]表示点i和点i1之间的净海拔高度差。通过累加这些高度差可以计算出经过每个点后的总海拔变化。确定最高点的海拔在计算出总的海拔变化后需要找到最高点的海拔。这可以通过比较累加海拔和初始海拔的大小来实现。最高点的海拔即为累加海拔和初始海拔中的较大值。注意数组边界条件在处理gain数组时需要注意数组的边界条件。例如gain[0]表示起点和终点之间的海拔高度差而gain[n-1]表示倒数第二个点和终点之间的海拔高度差。代码实现最后根据上述分析可以使用Python等编程语言实现相应的算法。在实现过程中需要注意代码的简洁性和可读性同时也要注意处理可能的异常情况。
思路与算法
我们假设每个点的海拔为 hi 由于 gain[i] 表示第 i 个点和第 i1 个点的海拔差因此
gain[i] hi1) − hi那么 可以发现每个点的海拔都可以通过前缀和的方式计算出来。因此我们只需要遍历一遍数组求出前缀和的最大值即为最高点的海拔。 实际上题目中的 gain 数组是一个差分数组对差分数组求前缀和即可得到原海拔数组。然后求出原海拔数组的最大值即可。 三、代码
3.2 方法一前缀和差分数组
Java版本
class Solution {public int largestAltitude(int[] gain) {int high 0, max 0;for (int h : gain) {high h;max Math.max(max, high);}return max;}
}
C版本
class Solution {
public:int largestAltitude(std::vectorint gain) {int high 0, max 0;for (int h : gain) {high h;max std::max(max, high);}return max;}
};Python版本
class Solution:def largestAltitude(self, gain: List[int]) - int:high 0max_altitude 0for h in gain:high hmax_altitude max(max_altitude, high)return max_altitudeGo版本
func largestAltitude(gain []int) int {high, max : 0, 0for _, h : range gain {high hif high max {max high}}return max
}func main() {gain : []int{-5, 1, 5, 0, -7}result : largestAltitude(gain)fmt.Println(result)
}四、复杂度分析
4.2 方法一前缀和差分数组
时间复杂度 O(n)其中 n 为数组 gain 的长度。空间复杂度 O(1)。
