LeetCode Array系列三

Array

LeetCode数组分组中56、57、59、62、63、64、66、73、74,75题汇总

56. Merge Intervals (Medium)

题意

Given a collection of intervals, merge all overlapping intervals.

For example,

Given [1,3],[2,6],[8,10],[15,18],

return [1,6],[8,10],[15,18].

区间合并,如果两个集合间有交集就合并

解题

方法很简单,就是遍历,然后前面和后面一项进行对比就可以了,只要满足前面的end在后面的区间内就合并,合并的规则是从两个集合第一个数中选一个最小的,然后再第二个数中选一个最大的,但是有一个陷阱,就是原List里面的第一个数是无序的,因此先要对它按照第一个数进行排序

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> ret = new ArrayList<>();
        if(intervals.size() == 0) return ret;
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval i1, Interval i2) {
                return i1.start - i2.start;
            }            
        });
        Interval pre = intervals.get(0);
        for(int i = 1; i < intervals.size(); i++){
            if(pre.end < intervals.get(i).start) {
                ret.add(pre);
                pre = intervals.get(i);
                continue;
            }
            if(pre.start > intervals.get(i).start){
                pre.start = intervals.get(i).start;
            }
            if(pre.end < intervals.get(i).end){
                pre.end = intervals.get(i).end;
            }
        }
        ret.add(pre);
        return ret;
    }
}

提交以后看到比较优的解法:

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        int n = intervals.size();
        int[] starts = new int[n];
        int[] ends = new int[n];
        for (int i = 0; i < n; i++) {
            starts[i] = intervals.get(i).start;
            ends[i] = intervals.get(i).end;
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        List<Interval> res = new ArrayList<Interval>();
        for (int i = 0, j = 0; i < n; i++) { 
            if (i == n - 1 || starts[i + 1] > ends[i]) {
                res.add(new Interval(starts[j], ends[i]));
                j = i + 1;
            }
        }
        return res;
    }
}

原理就是两个指针,一个在前面,一个在后面,如果遇到不存在交集的,那么指针的两项就可以合并了

57. Insert Interval (Hard)

题意

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:

Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

这个题和上面的题类似,上面是直接合并,这里是有一个待插入的集合,它也需要加入到这个集合集中。最初先将插入的数加到List合适位置,然后在按照方法一进行合并,但是超时了,所以时间复杂度不满足

解题

对于待插入的集合,在源集合集中,和它关系有两种情况,一是有交集,二是没交集,而这两种的到底在集合集的哪部分是不确定的,于是我们将源集合分成三部分,认为头尾没有交集,中间有交集,而实际情况中,我们认为的头尾中这三部分都可能不存在,详细代码:

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> ret = new ArrayList<>();
        int index = 0;
        while(index < intervals.size() && intervals.get(index).end < newInterval.start)
            ret.add(intervals.get(index++));
        while(index < intervals.size() && intervals.get(index).start <= newInterval.end){
            newInterval = new Interval(Math.min(intervals.get(index).start, newInterval.start), Math.max(intervals.get(index).end, newInterval.end));
            index++;
        }
        ret.add(newInterval);
        while(index < intervals.size())
            ret.add(intervals.get(index++));
        return ret;
    }
}

59. Spiral Matrix II (Medium)

题意

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,

Given n = 3,

You should return the following matrix:

[

[ 1, 2, 3 ],

[ 8, 9, 4 ],

[ 7, 6, 5 ]

]

这道题和LeetCode Array系列二中的54题差不多,那道题中是取值,这道题是赋值,因此方法是一样的

解题

一个重要的性质,数组用声明了大小的方式初始化以后,它的长度也就确定了,即便是我们没有给里面的每一项赋值,这就和Java中的List不一样了,List初始化后,即便是我们声明了大小,如果没有向里面添加值,它的大小还是为零。这题是赋值,用一个基数从1开始,每次加1

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ret = new int[n][n];
        int rowStart = 0;
        int rowEnd = n - 1;
        int cowStart = 0;
        int cowEnd = n - 1;
        int num = 1;
        while(rowStart <= rowEnd && cowStart <= cowEnd){
            for(int i = cowStart; i <= cowEnd; i++) ret[rowStart][i] =  num++;
            for(int i = rowStart + 1; i <= rowEnd; i++) ret[i][cowEnd] =  num++;
            for(int i = cowEnd - 1; cowStart <= i && rowStart != rowEnd; i--) ret[rowEnd][i] =  num++;
            for(int i = rowEnd - 1; rowStart < i && cowStart != cowEnd; i--) ret[i][cowStart] =  num++;
            rowStart++;
            rowEnd--;
            cowStart++;
            cowEnd--;
        }
        return ret;
    }
}

62. Unique Paths (Medium)

题意

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

图中的机器人要走到右下角星星那里,机器人每一步只能是向下或者向右,问有多少种路线

解题

这道题就是典型的动态规划题,我们按照每一格为单位,计算出到达这一格有多少种方式,因此对于第一行所有的格子都为1,第一列所有格子的都为1(开始的位置严格来说是0,但是计算中不会用到,因此也赋值为1了),然后根据头行和头列计算出下面格子的数,每一格格子的数等于它左边和上面格子里面数的和

public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] ret = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i == 0 || j ==0)
                    ret[i][j] = 1;
                else 
                    ret[i][j] = ret[i][j - 1] + ret[i - 1][j];
            }
        }
        return ret[m - 1][n - 1];
    }
}

63. Unique Paths II (Medium)

题意

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[

[0,0,0],

[0,1,0],

[0,0,0]

]

The total number of unique paths is 2.

Note: m and n will be at most 100.

和62题一样,也是找到右下角的线路,但是现在使用二维数组来表示的,如果原始二维数组中的值为1的话,那么这一格是不能够走的

解题

还是用62的解法,先对头行和头列赋值,如果当前位置为1,则新的值为0,表示这里没有路,有一个技巧,就是如果头行和头列里面有一个是1了,后面的就不用遍历了,直接为0;然后还有就是如果开始的位置为1,就没有路了,同理右下角为1也没有路,直接返回0;后面的计算的计算和62一样了,有一点不一样的就是当前位置为1的话,我们需要将它变为0

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid.length == 0) return 0;
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        if(obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;
        int k = 0;
        while(k < n && obstacleGrid[0][k] == 0) {
            obstacleGrid[0][k] = 1;
            k++;
        }
        while(k < n){
            obstacleGrid[0][k] = 0;
            k++;
        }
        k = 1;
        while(k < m && obstacleGrid[k][0] == 0) {
            obstacleGrid[k][0] = 1;
            k++;
        }
        while(k < m){
            obstacleGrid[k][0] = 0;
            k++;
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(obstacleGrid[i][j] == 1) obstacleGrid[i][j] = 0;
                else obstacleGrid[i][j] = obstacleGrid[i][j - 1] + obstacleGrid[i - 1][j];
            }
        }
        return obstacleGrid[m - 1][n -1];
    }
}

64. Minimum Path Sum (Medium)

题意

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

这个和62题的差别是,现在格子里有数,找一条路线,它满足所经过格子的数总和是最小的

解题

和第一题的解法一样,只是现在格子里最新放入的数,是它左边或者上边最小的那个数和它自己本身的和,最后那个格子的数就是最终解

public class Solution {
    public int minPathSum(int[][] grid) {
        if(grid.length == 0) return 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(i == 0 && j == 0) continue;
                else if(i == 0 && j > 0) grid[i][j] = grid[i][j - 1] + grid[i][j];
                else if (i > 0 && j == 0) grid[i][j] = grid[i - 1][j] + grid[i][j];
                else grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}

66. Plus One (Easy)

题意

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

这个题挺有意思的,有一个数组,用这个数组加1,然后得出新的数组

解题

解法挺简单的,注意每一位只可能是0-9,因此只有9有进位,而小于9的直接就加1就行

public class Solution {
    public int[] plusOne(int[] digits) {
        int ret[] = new int[digits.length + 1];
        for(int i = digits.length - 1; i >= 0; i--){
            if(digits[i] < 9){
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        ret[0] = 1;
        return ret;
    }
}

73. Set Matrix Zeroes (Medium)

题意

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

有一个二维数组,将数组中0所在的行和列都变成0,其他的不变

解题

先遍历一遍,然后将为0的所在行的第一个和所在列的第一个数置为0,然后在遍历每一行,如果第该行第一个为0,则该行都为0,然后遍历列,如果该列第一个为0,则该列全部为0。但是特别注意的第0行0列那个数,它如果为零,有三张情况,在第0行原始有0,或者在第0列原始有0,或者0行0列原始都为0,所以我们要标识这三种情况

public class Solution {
    public void setZeroes(int[][] matrix) {
        if(matrix.length == 0) return;
        boolean rowZero = false;
        boolean colZero = false;
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[0].length; j++){
                if(matrix[i][j] == 0){
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                    if(i == 0) rowZero = true;
                    if(j == 0) colZero = true;
                }
            }
        }
        int j = 1;
        for(int i = 1; i < matrix.length; i++){
            if(matrix[i][0] == 0){
                j = 1;
                while(j < matrix[0].length){
                    matrix[i][j] = 0;
                    j++;
                }
            }
            if(matrix[0][0] == 0 && colZero) matrix[i][0] = 0;
        }
        for(int i = 1; i < matrix[0].length; i++){
            if(matrix[0][i] == 0){
                j = 1;
                while(j < matrix.length){
                    matrix[j][i] = 0;
                    j++;
                }
            }
            if(matrix[0][0] == 0 && rowZero) matrix[0][i] = 0;
        }
    }
}

74. Search a 2D Matrix (Medium)

题意

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.

The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[

[1, 3, 5, 7],

[10, 11, 16, 20],

[23, 30, 34, 50]

]

Given target = 3, return true.

在一个行和列都递增的二维数组中查找是否存在目的数

解题

典型的二分查找,二分时,将它考虑成一维的数组

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return false;
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m * n - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            int midX = mid / n;
            int midY = mid % n;
            if(matrix[midX][midY] == target) 
                return true;
            if(matrix[midX][midY] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return false;
    }
}

75. Sort Colors (Medium)

题意

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:

You are not suppose to use the library’s sort function for this problem.

在一个数组中,用0表示红色,1表示白色,2表示蓝色,将红色放在最前面,白色放中间,蓝色放最后,简单说就是对数组排序,只是数组中只有0、1、2这三类数而已

解题

用两个指针分别指向数组头和尾,然后遍历数组,遇到红色就放在头那个指针上,然后头指针向右一步,同理,遇到蓝色就将它放到尾指针上,然后尾指针前左移

public class Solution {
    public void sortColors(int[] nums) {
        int red = 0;
        int blue = nums.length - 1;
        for(int i = 0; i < nums.length && i <= blue;){
            if(nums[i] == 0 && i > red){
                swap(nums, i, red++);
            }else if(nums[i] == 2 && i < blue){
                swap(nums, i, blue--);
            }else i++;
        }
    }
    private void swap(int[] n, int a, int b) {
        int temp = n[a];
        n[a] = n[b];
        n[b] = temp;
    }
}
坚持原创分享,您的支持将鼓励我不断前行!