2024-11-29
1k 字
4 分钟
一维与二维前缀和与差分
什么是前缀和？
一维数组前缀和
例如数组nums = [1,2,3,4,5]
则其前缀和数组为qian = [1,3,6,10,15]，即qian数组的i索引位置处的值为nums数组索引0-i值的和
则有如下关系：nums[i] = qian[i] - qian[i-1]
注：使用该方法有一最大优势便是可以以(O1)的时间复杂度得到某块区间的总和，是典型的牺牲空间换取时间
二维数组前缀和
二维数组的应用和计算
二维数组前缀和是一种在二维矩阵上进行快速区域求和的技术，它是一维前缀和概念的扩展。在二维数组中，前缀和可以帮助我们快速计算任意子矩阵的元素和，这在处理图像处理或者某些区域查询
2024-11-29
438 字
1 分钟
跳跃游戏
题目
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
示例1
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例2
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
示例3
输入: [0]
输出: true
解释: 跳入的第一步就到终点了
《代码随想录》算法公开课
2024-11-29
577 字
2 分钟
买卖股票的最佳时机II
题目
给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例1
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第2天（股票价格 = 1）的时候买入，在第3天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第4天（股票价格 = 3）的时候买入，在第5天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例2
输入: [1,2,3,4,5]
输
