文章目录
- 1. 不同路径 II
- 题干:
- 算法原理:
- 代码:
- 2. 在排序数组中查找元素的第一个和最后一个位置
- 题干:
- 算法原理:
- 解法一:暴力解法 O(n)
- 解法二:朴素二分
- 解法三:查找区间左右端点
- 代码:
- 二分模版:
- 查找左区间模版:
- 查找右区间模版:
1. 不同路径 II
原题链接
题干:
这道题和 第16天 的题非常相似
只是在机器人走的路径上加了一个障碍物
障碍物为 1 ,没有障碍物为 0
所以这里我们要看给的二维数组的映射关系
算法原理:
- 状态表示
经验 + 题目要求
以[ i,j ] 为结尾时…
dp[i][j] 表示:走到 [i, j] 位置处,⼀共有多少种方式 - 状态转移方程
从 [i, j] 位置的上方( [i - 1, j] 的位置)向下走一步,转移到 [i, j] 位置
从 [i, j] 位置的左方( [i, j - 1] 的位置)向右走⼀步,转移到 [i, j] 位置
但是如果有障碍物,那么就为 0 - 初始化
这里我们依然要使用虚拟节点来写
不过,这里我们要做到以下两点:
(1)虚拟节点里面的值,要保证后面填表的结果正确
(2)下标的映射
这里最重要的就是第二点
要注意给的二维数组和现在和映射
- 填表顺序
从上往下填写每一行
每一行从左往右填写 - 返回值
dp[m][n]
代码:
class Solution {
public int uniquePathsWithObstacles(int[][] ob) {
int m = ob.length;
int n = ob[0].length;
int[][] dp = new int[m + 1][n + 1];
dp[1][0] = 1;
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(ob[i - 1][j - 1] == 0) {
dp[i][j] = dp[i -1][j] + dp[i][j - 1];
}
}
}
return dp[m][n];
}
}
2. 在排序数组中查找元素的第一个和最后一个位置
原题链接
题干:
一个非递减顺序的数组
找目标值的 开始 和 结束位置
返回下标
算法原理:
解法一:暴力解法 O(n)
从前往后进行查找
遇到第一个目标值记录,遇到最后一个目标值记录
很简单,但是时间复杂度会比较高
解法二:朴素二分
这个是不可取的
因为朴素二分只能找到中间值是否是目标值
并不能确定范围
解法三:查找区间左右端点
根据数组的“二段性”
我们可以找到目标值的左端点和右端点
查找区间左端点
我们可以看到,如果找左端点
我们可以根据左端点划分为两个区间,小于目标值,大于等于目标值
这个时候
- x < t 的时候 left = mid + 1
- x >= t 的时候 right = mid
接下来在继续进行查找
为什么在第二步 要求 right = mid 呢?
因为这个时候的 mid 很有可能就是左端点
细节处理:
- 循环条件(left < right)
(1)left < right 的时候,就是最终结果,无需判断
(2)如果判断,就会导致死循环 - 求中点的方法
我们知道有两种求中点的方法,主要是因为如果长度是偶数
我们可以定位到中间靠左,或者中间靠右
(1)left + (right - left) / 2 左端点
(2)left + (right - left + 1) / 2 右端点 (错,会死循环)
定位右端点会导致死循环
查找区间右端点
这个跟查找左端点非常类似
如果找右端点
我们可以根据有端点划分为两个区间,小于等于目标值,大于目标值
这个时候
- x <= t 的时候 left = mid
- x > t 的时候 right = mid - 1
细节处理:
- 循环条件(left < right)
(1)left < right 的时候,就是最终结果,无需判断
(2)如果判断,就会导致死循环 - 求中点的方法
(1)left + (right - left) / 2 左端点 (错,会死循环)
(2)left + (right - left + 1) / 2 右端点
代码:
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ret = new int[2];
ret[0] = ret[1] = -1;
//处理边界情况
if(nums.length == 0) {
return ret;
}
//1.二分左端点
int left = 0;
int right = nums.length - 1;
while(left < right) {
int mid = left + (right - left) / 2;
if(nums[mid] < target) {
left = mid + 1;
}else {
right = mid;
}
}
//判断是否有结果
if(nums[left] != target) {
return ret;
}else {
ret[0] = right;
}
//2.二分右端点
left = 0;
right = nums.length - 1;
while(left < right) {
int mid = left + (right - left + 1) / 2;
if(nums[mid] <= target) {
left = mid;
}else {
right = mid - 1;
}
}
ret[1] = left;
return ret;
}
}
二分模版:
查找左区间模版:
while(left < right) {
int mid = left + (right - left) / 2;
if(......) {
left = mid + 1;
}else {
right = mid;
}
}
查找右区间模版:
while(left < right) {
int mid = left + (right - left + 1) / 2;
if(......) {
left = mid;
}else {
right = mid - 1;
}
}
下面出现 - 1,上面就 + 1