LeetCode Array系列二

Array

LeetCode数组分组中34、35、39、40、41、42、45、48、53、54、55题汇总。由于45和55两题是孪生题,因此系列二一共有11个题

LeetCode

后续博客中只会出现比较特殊的算法题,将不再出现其他的题,更多LeetCode Java解法请到我的GitHub,里面会有翻译和Solution

34. Search for a Range (Medium)

题意

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,

Given [5, 7, 7, 8, 8, 10] and target value 8,

return [3, 4].

在一个有序数组中,找到目标数开始的索引和结束的索引,如果没有则返回[-1, -1],如果只有一个,开始索引和结束索引就相同了。

解题

如果题目没有明确要求,用一趟循环这个题是可以求解的,但是题目要求时间复杂度为O(logn),所以不能用单循环的方式,思路很简单,先用二分查找找到目标数,然后再想两边找。

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[]{-1, -1};
        int l = 0;
        int r = nums.length - 1;
        int mid;
        while (l <= r && l < nums.length && r >= 0) {
            if (nums[l] == nums[r] && nums[l] == target) {
                ret[0] = l;
                ret[1] = r;
                return ret;
            }
            mid = l + (r - l) / 2;
            if (nums[mid] < target) l = mid + 1;
            else if (target < nums[mid]) r = mid - 1;
            else {
                int n = mid + 1;
                while (n < nums.length && nums[n] == nums[mid]) n++;
                ret[1] = n - 1;
                n = mid - 1;
                while (n >= 0 && nums[n] == nums[mid]) n--;
                ret[0] = n + 1;
                return ret;
            }
        }
        return ret;
    }
}

35. Search Insert Position (Easy)

题意

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

这道题很简单,找出目标数插入数组的合适位置,如果数组中存在,当然就是那个位置,如果不存在,就插入比它小的最大数前面

解题

用二分查找找到和它相差最小的数,然后判断,如果等于直接返回,如果小于目标数,就在当前数后一个,如果大于目标数,就在当前数前一个

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        int mid;
        while(l < r){
            mid = l + (r - l) / 2;
            if(nums[mid] == target)
                return mid;
            else if(nums[mid] < target){
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        if(nums[l] < target) return l + 1;
        else return l;
    }
}

39. Combination Sum (Medium)

题意

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[

[7],

[2, 2, 3]

]

有一个非负的整数集合,数字不重复,还要一个目标数,从这个集合选出任意数量的数,这些数满足和等于目标数,同一个数可以用多次

解题

这个主要的思想是回溯法,首先需要将数组排序,然后通过不断的循环递归所有可能的组合,判断是否有满足条件的组合,如果有,增新增到结果中,如果当前的数大于剩余目标数,就要将List中最后一个元素移除,如果小继续从当前位置继续递归:

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(candidates);
        List<Integer> list = new ArrayList<>();
        combinationSum(candidates, target, 0, list, ret);
        return ret;
    }

    private void combinationSum(int[] candidates, int target, int l, List<Integer> list, List<List<Integer>> ret){
        if(target == 0){
            List<Integer> tmp = new ArrayList<>(list);
            ret.add(tmp);
            return;
        }
        for(int i = l; i < candidates.length; i++){
            if(candidates[i] > target)
                return;
            list.add(candidates[i]);
            combinationSum(candidates, target - candidates[i], i, list, ret);
            list.remove(list.size() - 1);
        }
    }
}

40. Combination Sum II (Medium)

题意

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

[

[1, 7],

[1, 2, 5],

[2, 6],

[1, 1, 6]

]

和39类似,加了一个限制,同一个数只能用一次,而且数组中会有相同的数,另外还有一个注意的就是,比如[10, 1, 2, 7, 6, 1, 5]和目标8,两个1可以组成两个1、2、5,虽然是不同的1,但是结构中不能重复相同的序列

解题

前面的问题的很好解决,我们每一次更深度搜索时,不再搜索它本身,而是从下一个开始,而不能存在重复的序列只需要判断一下最后移除那个数和下一个要加进去的数是否相等,如果是则跳过

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(candidates);
        List<Integer> list = new ArrayList<>();
        combinationSum2(candidates, target, 0, ret, list);
        return ret;
    }

    private void combinationSum2(int[] candidates, int target, int l, List<List<Integer>> ret, List<Integer> list){
        if(target == 0){
            List<Integer> tmp = new ArrayList<>(list);
            ret.add(tmp);
            return;
        }
        int last = -1;
        for(int i = l; i < candidates.length; i++){
            if(last > 0 && candidates[i] == last)
                continue;
            if(candidates[i] > target)
                return;
            list.add(candidates[i]);
            combinationSum2(candidates, target - candidates[i], i + 1, ret, list);
            last = list.remove(list.size() - 1);
        }
    }
}

41. First Missing Positive (Hard)

题意

Given an unsorted integer array, find the first missing positive integer.

For example,

Given [1,2,0] return 3,

and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

在一个数组中,寻找第一个丢失的整数

解题

这个题网上最多解法就是把每个正数放到它数值少1的索引上,比如1,放在数组0上,5放在数组4上,然后在遍历数组,如果当前位置的数和它的索引大小+1不相等,则缺少的就是这个位置上的数,即为索引+1。注意有一点,交换时,如果当前位置的数不满足条件,思路是把这数放到正确的位置,而当前位置的数不一定对,然后循环的进行交换

public class Solution {
    public int firstMissingPositive(int[] nums) {
        int i = 0;
        for(; i < nums.length; i++){
            while(nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]){
                int tmp = nums[i];
                nums[i] = nums[tmp - 1];
                nums[tmp - 1] = tmp;
            }
        }
        i = 0;
        for(; i < nums.length; i++){
            if(nums[i] != i + 1)
                break;
        }
        return i + 1;
    }
}

42. Trapping Rain Water (Hard)

题意

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

根据图就可以知道题意了,有一个数组,求以这个数组值为高度的柱状图最大的盛水量,题意没什么说的,主要是怎么解

解题

从里面任意选一个,我们选从0开始的第4个,它的高度为1,它上面要盛水,它的两边必须要有比它高的,或者相邻,或者不相邻,如果没有,它的上面是不能盛水的,比如倒数第二块,两边只有它的左边有一块比它高,而右边没有。那么问题就简单了,我们可以求数组每一项两边比它高的,然后它能盛水的多少就取决于两边比它高的、较短的那块。怎么确定呢,我们用一个数组从左到右依次扫描,每一项存它所在位置左边最高的(包括它自己),然后用一个从右向左扫描,每一项存它所在位置右边最高的(包括它自己),最后再循环一次,用当前位置左右两边的最高的较短的那个减去当前位置的高度就是当前位置上面能装的水了,可能最高的就是它自己的高度,也就不能装水了,详细代码:

public class Solution {
    public int trap(int[] height) {
        if(height.length == 0)
            return 0;
        int[] left = new int[height.length];
        left[0] = height[0];
        for(int i = 1; i < height.length; i++){
            left[i] = Math.max(height[i], left[i - 1]);
        }

        int[] right = new int[height.length];
        right[height.length - 1] = height[height.length - 1];
        for(int i = height.length - 2; i >= 0; i--){
            right[i] = Math.max(height[i], right[i + 1]);
        }

        int sum = 0;
        for(int i = 0; i < height.length; i++){
            sum += Math.min(left[i], right[i]) - height[i];
        }
        return sum;
    }
}

45. Jump Game II (Hard)

在55. Jump Game后面,文末

48. Rotate Image (Medium)

题意

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

将一个二维数组顺时针旋转90度,不能使用额外的空间,就是必须在原数组上进行操作

解题

先从右上到左下画一条对角线,交换对角线两边对称的数,然后再从水平方向画一条线,交换上下的数

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for(int i = 0; i < n - 1; i++){
            for(int j = 0; j < n - i - 1; j++){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][n - i - 1];
                 matrix[n - j - 1][n - i - 1] = tmp;
            }
        }
        for(int i = 0; i <= (n - 1) / 2; i++){
            for(int j = 0; j < n; j++){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = tmp;
            }
        }
    }
}

53. Maximum Subarray (Easy)

题意

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],

the contiguous subarray [4,-1,2,1] has the largest sum = 6.

经典问题,最大子列和,暴力的方式比较容易想到,不过还有一种方式叫着在线处理

解题

在线处理的思想就是,我们一个一个的把数组中的数拿出来,比如对于[-2,1,-3,4,-1,2,1,-5,4],第一个为-2,此时的最大子列和就为-2,然后再取下一个数,-2我们可以抛弃了,因为它一个负数,他不能使我们的和增加,读到1时,更新最大和为1,同时1我们需要记录下来,因为它可以使我们的和增加,读下一个数-3,用它加上我们的1,并不能大于我们的最大和1,最大和还是1,但此时我们的记录应该变成0了,然后继续下去……

public class Solution {
    public int maxSubArray(int[] nums) {
        int thisSum = Math.max(0, nums[0]);
        int max = nums[0];
        for(int i = 1; i < nums.length; i++){
           thisSum += nums[i];
           max = Math.max(thisSum, max);
           thisSum = Math.max(thisSum, 0);
        }
        return max;
    }
}

可能解释不太清楚,大家按照代码走一趟就明白了

54. Spiral Matrix (Medium)

题意

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,

Given the following matrix:

[

[ 1, 2, 3 ],

[ 4, 5, 6 ],

[ 7, 8, 9 ]

]

You should return [1,2,3,6,9,8,7,4,5].

顺时针遍历二维数组,其实这个题没什么技巧性,主要考察逻辑,因此算法也是模拟整个遍历的过程

解题

我们一圈一圈的遍历,然后下一次再进去一圈再遍历,只需要用4个变量记住我们遍历的范围就可以了,比较简单:

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        if(matrix.length == 0) return list;
        int rowStart = 0;
        int rowEnd = matrix.length - 1;
        int colStart = 0;
        int colEnd = matrix[0].length - 1;
        while(rowStart <= rowEnd && colStart <= colEnd){
            for(int j = colStart; j <= colEnd; j++) list.add(matrix[rowStart][j]);
            for(int i = rowStart + 1; i <= rowEnd; i++) list.add(matrix[i][colEnd]);
            for(int j = colEnd - 1; j >= colStart && rowEnd > rowStart; j--) list.add(matrix[rowEnd][j]);
            for(int i = rowEnd - 1; i > rowStart && colStart < colEnd; i--) list.add(matrix[i][colStart]);
            rowStart++;
            rowEnd--;
            colStart++;
            colEnd--;
        }
        return list;
    }
}

特别注意while里面的后两个for循环,有两个限制条件,也就是下面和左边那一趟不能再重复之前的上面和右边的了

55. Jump Game (Medium)

题意

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:

A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

跳格子游戏,格子里面的数是你可以从这个位置跳的最多步数(可以使用少于步数的步数),这道题主要解答能不能根据格子里面的步数跳到最后一格

解题

我们看一个短的[2,3,1],用一个数记录这个位置可以用的最大步数,每一个位置看能不能根据前面的到达,首先,最大步数为零,我们在2的头上,我们可以用的步数是2,我们可以到3,于是我们到3的头上,到3以后,我们现在能用的步数是多少呢?答案是4,为3加上它的索引1,为什么为4,因为我们在3头上时,使用了一步,再加上它本身的,所以在3头上时其实是有4步的能力的,因此,我们有能力到达1头上

public class Solution {
    public boolean canJump(int[] nums) {
        int max = 0;
        for(int i = 0; i < nums.length && i <= max; i++)
            max = Math.max(nums[i] + i, max);
        return (max >= nums.length - 1 ? true : false);
    }
}

45. Jump Game II

题意

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:

Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

55题的升级版,要到达,还要选择的次数越少

解题

基于上面的方法,我们增加一个变量,记录上一次可以使用的步数,对于当前位置,如果上一次就能到达该位置,我们就不用增加一次选择,如果到达不到,我们就必须选择一次,就是浪费一次机会,遍历到最后一个时,就知道能不能到达

public class Solution {
    public int jump(int[] nums) {
        int max = 0;
        int last = 0;
        int ret = 0;
        for(int i = 0; i < nums.length && i <= max; i++){
            if(i > last){
                ret++;
                last = max;
            }
            max = Math.max(nums[i] + i, max);
        }
        return (max >= nums.length - 1 ? ret : 0);
    }
}
坚持原创分享,您的支持将鼓励我不断前行!