3.数组（三）
https://leetcode-cn.com/tag/array/
题目汇总
55. 跳跃游戏中等※
56. 合并区间中等※
57. 插入区间困难※※
59. 螺旋矩阵 II中等
62. 不同路径中等
63. 不同路径 II中等
64. 最小路径和中等
66. 加一简单※
73. 矩阵置零中等
74. 搜索二维矩阵中等
55. 跳跃游戏中等※
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
输入: [2,3,1,1,4]，输出: true
解释: 我们可以先跳 1 步，从位置 0 到达位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
输入: [3,2,1,0,4]，输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置
思路：
出处：这么简洁的算法，膜拜大佬！
如果某一个作为起跳点的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为起跳点。
可以对每一个能作为起跳点的格子都尝试跳一次，把能跳到最远的距离不断更新。
如果可以一直跳到最后，就成功了。
class Solution {
public boolean canJump(int[] nums) {
int k = 0; //k是当前能跳到的最远距离，每个位置都更新k，
for (int i = 0; i < nums.length; i++)
{
//如果到一个位置发现 i > k
//也就是说现在这个位置 i 已经超过了之前能跳到的最远距离，就返回false，否则返回true
if (i > k)
return false;
//i + nums[i]代表站在索引i的格子上，并且可以从这个格子能跳到最远的距离（nums[i]）
//这两个数值相比，较大的就可以继续保存成 k ，代表可以跳到最远的地方
k = Math.max(k, i + nums[i]);
}
return true;
}
}
56. 合并区间中等※
给出一个区间的集合，请合并所有重叠的区间。
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]
思路：排序，时间复杂度O(nlogn)
官方题解第二种
首先，将输入的区间集合排好序
然后，我们将第一个区间插入 merged 数组中，然后按顺序考虑之后的每个区间：如果当前区间的左端点在前一个区间的右端点之后，那么他们不会重合，我们可以直接将这个区间插入 merged 中；否则，他们重合，我们用当前区间的右端点更新前一个区间的右端点 end，如果前者数值比后者大的话
class Solution {
private static class Interval {
int start;
int end;
Interval(int[] interval) {
this.start = interval[0];
this.end = interval[1];
}
int[] toArray() {
return new int[]{this.start, this.end};
}
}
private class IntervalComparator implements Comparator<Interval>{
@Override
public int compare(Interval a, Interval b){
//return a.start < b.start ? -1 : a.start == b.start ? 0 : 1;
return a.start - b.start;
}
}
public int[][] merge(int[][] intervals) {
List<Interval> intervalsList = new LinkedList<>();
for (int[] interval : intervals) {
intervalsList.add(new Interval(interval));
}
//先将输入的区间集合排好序
intervalsList.sort(new IntervalComparator());
LinkedList<Interval> merged = new LinkedList<>();
for (Interval interval : intervalsList) {
if (merged.isEmpty() || merged.getLast().end < interval.start) {
merged.add(interval);//区间不用合并
}
else {//区间合并
merged.getLast().end = Math.max(merged.getLast().end, interval.end);
}
}
int i = 0;
int[][] result = new int[merged.size()][2];
for (Interval mergedInterval : merged) {
result[i] = mergedInterval.toArray();
i++;
}
return result;
}
}
57. 插入区间困难※※
给出一个无重叠的，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
输出: [[1,5],[6,9]]
思路：贪心算法
59. 螺旋矩阵 II中等
给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
与54. 螺旋矩阵类似
思路：定义边界
定义上下左右四个边界值，始终按照从左到右、从上到下、从右到左、从下到上的填入顺序循环
class Solution {
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
int left = 0;
int right = n - 1;
int up = 0;
int down = n - 1;
int num = 1, end = n * n;
while(num <= end){
//从左到右,最上边一行，向右走存入整行的值
for(int col=left;col<=right;col++)
matrix[up][col]=num++;
up++;//向下逼近
//从上到下，最右边一列，向下走存入整列的值
for(int row=up;row<=down;row++)
matrix[row][right]=num++;
right--;//向左逼近
//从右到左，最下边一行，向左走存入整行的值
for(int col=right;col>=left;col--)
matrix[down][col]=num++;
down--;//向上逼近
//从下到上，最左边一列，向上走存入整列的值
for(int row=down;row>=up;row--)
matrix[row][left]=num++;
left++;//向右逼近
}
return matrix;
}
}
62. 不同路径中等
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？
输入: m = 7, n = 3，输出: 28
思路：动态规划
dp[i][j]的值是从起始点走到(i, j)的路径数。由于机器人每次只能向下或者向右移动一步，dp[i][j]的值就是第 i 行第 j 列这个格子的上面格子的值加上左边格子的值，也就是dp[i][j] = dp[i-1][j] + dp[i][j-1]，其中第一行 dp[0][j]=0，第一列 dp[i][0]=0
class Solution {
public int uniquePaths(int m, int n) {
if(m < 0 || n < 0)
return 0;
if(m == 0 || n == 0)
return 1;
int[][] dp = new int[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if (i == 0 || j == 0) { //最上一行或者最左一列
dp[i][j] = 1;
}
else{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
}
63. 不同路径 II中等
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用1和0来表示。
说明：m 和 n 的值均不超过 100。
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
思路：动态规划
与62. 不同路径相比只是增加了障碍物
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid[0].length == 0) {
return 0;
}
int row = obstacleGrid.length;//行数
int col = obstacleGrid[0].length;//列数
int[][] dp = new int[row][col];
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(obstacleGrid[i][j]==1){
dp[i][j] = 0;
}else{
if(i==0 && j==0) dp[i][j]=1;
else if(i==0) dp[i][j]=dp[i][j-1];//第一行
else if(j==0) dp[i][j]=dp[i-1][j];//第一列
else dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
}
return dp[row-1][col-1];
}
}
64. 最小路径和中等
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
思路：动态规划
分为四种情况
(1)当i = 0, j = 0时，其实就是起点
(2)当j=0时，grid[i][j] = grid[i-1][j] + grid[i][j]
(3)当i=0时，grid[i][j] = grid[i][j-1]+ grid[i][j]
(4)当i，j均不为0时，grid[i][j] = Math.min(grid[i-1][j], grid[i][j-1])+ grid[i][j]
class Solution {
public int minPathSum(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(i==0&&j==0)
continue;
else if(i==0){
grid[i][j] += grid[i][j-1];
}
else if(j==0){
grid[i][j] += grid[i-1][j];
}
else{
grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
}
}
}
return grid[row-1][col-1];
}
}
66. 加一简单※
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
思路：
只要+1求余数，余数不等于0，说明没有进位，直接返回。如果余数等于0，说明有进位，遍历前一个数字，加1再求余数，以此循环。如果for循环都遍历完了，说明最高位也有进位，则重新建立一个数组，初始化为0，将第一位设置为1就可以了，因为，99、999之类的数字加一为100、1000。
这个精选题解很巧妙，太强了，代码简洁易懂
class Solution {
public int[] plusOne(int[] digits) {
int len = digits.length;
for(int i=len-1;i>=0;i--){
digits[i]++;
digits[i]%=10;
if(digits[i]!=0)
return digits;
}
digits = new int[len + 1];
digits[0] = 1;
return digits;
}
}
73. 矩阵置零中等
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
思路：
遍历数组，找到矩阵中元素为0时它的行号和列号，定义boolean变量，这些行和列的所有元素在下一次遍历时全部赋为零。
class Solution {
public void setZeroes(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
boolean[] judgeRow=new boolean[rows];
boolean[] judgeCol=new boolean[cols];
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(matrix[i][j]==0){
judgeRow[i]=true;
judgeCol[j]=true;
}
}
}
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if (judgeRow[i]||judgeCol[j]) {
matrix[i][j]=0;
}
}
}
}
}
74. 搜索二维矩阵中等
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true
思路一：从右上角开始找
首先选取数组中右上角的数字。如果该数字等于要查找的数字，则查找过程结束；如果该数字大于要查找的数字，则剔除这个数字所在的列；如果该数字小于要查找的数字，则剔除这个数字所在的行。如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，逐步缩小范围
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int rows = matrix.length;
if(rows == 0)
return false;
int cols = matrix[0].length;
if(cols == 0)
return false;
//从右上角开始找
int row = 0;
int col = cols - 1;
while(row<rows&&col>=0){
if(matrix[row][col]>target){
col--;
}else if(matrix[row][col]<target){
row++;
}else{
return true;
}
}
return false;
}
}
思路二：二分查找
该矩阵可以看成一个有序数组，数组中含有行数×列数个元素，虚数组的序号可以转化为原矩阵中的行和列，这样自然而然想到二分查找
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int rows = matrix.length;
if(rows == 0)
return false;
int cols = matrix[0].length;
if(cols == 0)
return false;
int nums = rows * cols;
int left = 0;
int right = nums - 1;
while(left <= right){
int mid = (right - left)/2 + left;
if(matrix[mid/cols][mid%cols] > target){
right = mid - 1;
}else if(matrix[mid/cols][mid%cols] < target){
left = mid + 1;
}else{
return true;
}
}
return false;
}
}
