网站后台怎么做水印图片,做招牌的网站有哪些,抖音代运营怎么收费,vip影视网站怎么做的文章目录 1. 山脉数组的峰顶索引题干#xff1a;算法原理#xff1a;代码#xff1a; 2. 寻找峰值题干#xff1a;算法原理#xff1a;1. 暴力解法2. 二分查找 代码#xff1a; 3. 下降路径最小和题干#xff1a;算法原理#xff1a;1. 状态表示2.状态转移方程3. 初始化… 文章目录 1. 山脉数组的峰顶索引题干算法原理代码 2. 寻找峰值题干算法原理1. 暴力解法2. 二分查找 代码 3. 下降路径最小和题干算法原理1. 状态表示2.状态转移方程3. 初始化4. 填表顺序5. 返回值 代码 1. 山脉数组的峰顶索引 原题链接 题干
山脉数组 找峰顶 返回索引
算法原理 由于这个数组具有“二段性”使用二分查找 目标是左边的左边小于右边 目标值右边的左边大于右边
峰顶数据特点 arr[i] arr[i - 1] arr[i] arr[i 1]峰顶左边的数据特点 arr[i] arr[i - 1] arr[i] arr[i 1] 也就是呈现上升趋势峰顶右边数据的特点 arr[i] arr[i - 1] arr[i] arr[i 1] 也就是呈现下降趋势 如果 mid 置呈现上升趋势说明我们接下来要在 [mid 1, right] 区间继续搜索如果 mid 位置呈现下降趋势说明我们接下来要在 [left, mid - 1] 区间搜索如果 mid 位置就是⼭峰直接返回结果
代码
class Solution {public int peakIndexInMountainArray(int[] arr) {int left 1;int right arr.length - 2;while(left right) {int mid left (right - left 1) / 2;if(arr[mid] arr[mid - 1]) {left mid;}else {right mid - 1;}}return left;}
}2. 寻找峰值 原题链接 题干
峰值元素严格大于左右相邻的元素
算法原理
首先这道题有三种情况
1. 暴力解法
从第一个位置开始一直向后走 分情况讨论
2. 二分查找 任取⼀个点 i 与下⼀个点 i 1 会有如下两种情况
arr[i] arr[i 1] 此时「左侧区域」⼀定会存在⼭峰因为最左侧是负无穷那么我们可以去左侧去寻找结果arr[i] arr[i 1] 此时「右侧区域」⼀定会存在⼭峰因为最右侧是负无穷那么我们可以去右侧去寻找结果 接下来按照模版写就可以
代码
class Solution {public int findPeakElement(int[] nums) {int left 0;int right nums.length - 1;while(left right) {int mid left (right - left) / 2;if(nums[mid] nums[mid 1]) {left mid 1;}else {right mid;}}return left;}
}3. 下降路径最小和 原题链接 题干
有一个 n * n 的整形数组 找到下降路径的最小和 比如示例一就有两种情况 1 可以向下、向左下、向右下
算法原理
1. 状态表示
dp[i][j] 表示到达 [i, j] 位置时所有下降路径中的最小和
2.状态转移方程 对于普遍位置 [i, j] 根据题意得到达 [i, j] 位置可能有三种情况
从正上方 [i - 1, j] 位置转移到 [i, j] 位置从左上方 [i - 1, j - 1] 位置转移到 [i, j] 位置从右上方 [i - 1, j 1] 位置转移到 [i, j] 位置
我们要的是三种情况下的「最小值」然后再加上矩阵在 [i, j] 位置的值 dp[i][j] min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j 1])) matrix[i][j]
3. 初始化
可以在最前⾯加上⼀个「辅助结点」帮助我们初始化
辅助结点里面的值要「保证后续填表是正确的」「下标的映射关系」
在本题中需要「加上⼀行」并且「加上两列」 所有的位置都初始化为无穷大然后将第⼀行初始化为 0 即可
4. 填表顺序
从上往下
5. 返回值
返回「dp表中最后⼀行的最小值」 代码
class Solution {public int minFallingPathSum(int[][] matrix) {int n matrix.length;int[][] dp new int[n 1][n 2];for(int i 1; i n; i) {dp[i][0] dp[i][n 1] Integer.MAX_VALUE;}for(int i 1; i n; i) {for(int j 1; j n; j) {dp[i][j] Math.min(dp[i-1][j], Math.min(dp[i-1][j-1],dp[i-1][j1])) matrix[i-1][j-1];}}int ret Integer.MAX_VALUE;;for(int j 1; j n; j) {ret Math.min(ret, dp[n][j]);}return ret;}
}
