文章目录
1. 寻找旋转排序数组中的最小值
题干：
对升序数组进行旋转（数字互不相同）
要求返回数组的最小元素
时间复杂度为 O(log n)
算法原理：
1. 暴力查找最小值
这个虽然可以但是时间复杂度为 O(n)
2. 二分查找
我们观察一下给了数组翻转过后的数据
可以发现，这段数据分成了两端
有了“二段性”，因此可以使用二分查找
由于数组是升序，那么翻转之后的左边数据一定大于右边的数据
所以我们就可以 以 D 点为参照物
初始化左右两个指针 left ， right ：
然后根据 mid 的落点，我们可以这样划分下⼀次查询的区间：
- 当 mid 在 [A，B] 区间的时候，也就是 mid 位置的值严格大于 D 点的值，下⼀次查询区间在 [mid + 1，right] 上
- 当 mid 在 [C，D] 区间的时候，也就是 mid 位置的值严格小于等于 D 点的值，下次查询区间在 [left，mid] 上
当区间⻓度变成 1 的时候，就是我们要找的结果
代码：
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
int x = nums[right];//最后一个位置的值
while(left < right) {
int mid = left + (right - left) / 2;
if(nums[mid] > x) {
left = mid + 1;
}else {
right = mid;
}
}
return nums[right];
}
}
2. 点名
题干：
0 ~ n-1 的升序数组
仅有一位同学缺席，返回学号
算法原理：
1. 哈希表
2. 直接遍历找到结果
3. 位运算
4. 数学方法（高斯求和公式）
5. 二分查找
根据例子我们可以看出来，数字和下标是一一对应的，这样我们就可以找开始不对应的那个数字
这个时候 找到右边区间，最左边下标的值
细节问题：
当数组为升序数组，该返回 4 的时候，我们需要怎么做？
在最后用三目运算符进行返回判断
代码：
class Solution {
public int takeAttendance(int[] nums) {
int left = 0;
int right = nums.length - 1;
while(left < right) {
int mid = left + (right - left) / 2;
if(nums[mid] == mid) {
left = mid + 1;
}else {
right = mid;
}
}
return nums[left] == left ? left + 1 : left;
}
}
3. 最小路径和
题干：
非负整数 m * n 的网格
找从左上到右下的路径，使路径之和最小
只能向下或向右
算法原理：
1. 状态表示：
dp[i][j] 表示：到达 [i, j] 位置处，最小路径和是多少
2. 状态转移方程
根据最近的一步划分问题
如果 dp[i][j] 表示到达 [i, j] 位置处的最小路径和
那么到达[i, j] 位置之前的⼀小步，有两种情况：
- 从 [i - 1, j] 向下⾛⼀步，转移到 [i, j] 位置
- 从 [i, j - 1] 向右⾛⼀步，转移到 [i, j] 位置
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
3. 初始化
可以在最前⾯加上⼀个「辅助结点」，帮助我们初始化
- 辅助结点里面的值要「保证后续填表是正确的」
- 「下标的映射关系」
「添加⼀行」，并且「添加⼀列」后，所有位置的值可以初始化为无穷大，然后让 dp[0][1] = dp[1][0] = 1
4. 填表顺序
从上往下
从左往右
5. 返回值
dp[m][n]
代码：
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m+1][n+1];
for(int i = 0; i <= n; i++) {
dp[0][i]= Integer.MAX_VALUE;
}
for(int i = 0; i <= m; i++) {
dp[i][0]= Integer.MAX_VALUE;
}
dp[0][1] = dp[1][0] = 0;
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
dp[i][j] = Math.min(dp[i - 1][j],dp[i][j - 1]) + grid[i-1][j-1];
}
}
return dp[m][n];
}
}
4. 最大子数组和
题干：
整数数组
找到最大和的连续子数组
题目解析：
1. 状态表示：
dp[i] 表示：以 i 位置元素为结尾的所有子数组的最大和
2. 状态转移方程
dp[i] 的所有可能可以分为以下两种：
- 子数组的长度为 1 ：此时 dp[i] = nums[i]
- 子数组的长度大于 1 ：此时 dp[i] 应该等于以 i - 1 做结尾的「所有子数组」中和的最⼤值再加上 nums[i]
也就是 dp[i - 1] + nums[i]
由于我们要的是「最大值」，因此应该是两种情况下的最大值，因此可得转移方程：
dp[i] = max(nums[i], dp[i - 1] + nums[i])
3. 初始化
可以在最前⾯加上⼀个「辅助结点」，帮助我们初始化
- 辅助结点里面的值要「保证后续填表是正确的」
- 「下标的映射关系」
「最前⾯加上⼀个格子，并且让 dp[0] = 0
4. 填表顺序
从左往右
5. 返回值
返回整个 dp 表中的最大值
代码：
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n+1];
dp[0] = 0;
int ret = Integer.MIN_VALUE;
for(int i = 1; i <= n; i++) {
dp[i] = Math.max(nums[i-1], dp[i-1] + nums[i-1]);
ret = Math.max(ret,dp[i]);
}
return ret;
}
}
