LeetCode Array系列一

Array

LeetCode数组分组中1、4、11、15、16、18、26、27、31、33题汇总

LeetCode

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

1. Two Sum (Easy)

题意

Given an array of integers, return indices of the two numbers such that they add up to a > specific target.

You may assume that each input would have exactly one solution, and you may not use the
same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

给一个数组和数字,找出数组中两个数的和为该数字,数组中的每一个数只能用一次,并且可以认为数组中有且仅有一个解,就是需要找出来的这两个数仅有一对。注意并没有说数组是有序的,所以我们不能认为数组是有序的

解题

首相很容易能想到的还是暴力解法,这种解法只能击败23%左右的人,现在来一个可以击败75%的算法:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ret = new int[2];
        if(nums.length < 2)
            return ret;
        int d = 0;
        Map<Integer, Integer> m = new HashMap();
        for(int i= 0; i < nums.length; i++){
            d = target - nums[i];
            if(m.get(d) != null){
                ret[0] = m.get(d);
                ret[1] = i;
                break;
            }else {
                m.put(nums[i], i);
            }
        }
        return ret;
    }
}

最初,我在for循环中加入了一个判断,如果数组中的数大于目标就continue,提交后果断没有通过,原因是因为数组中可能有负数。

4. Median of Two Sorted Arrays (Hard)

题意

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]

nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]

nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

如果知道中位数,这题就很好理解。什么是中位数呢,一组数据按从小到大(或从大到小)的顺序依次排列,处在中间位置的一个数(或最中间两个数据的平均数)。这道题的意思就是有两个有序的数列,找出这连个数列的中位数,如例子中的两个数组,合并后为[1,2,3,4],为偶数长度,则中位数为(2 + 3)/2 = 2.5。同样的,这是分析,如果解题,我们不可能将两个数组合并后再求值

解题

首相还是说说最容易想到的办法,就是分别从数组中不断的选择合适的数组成新的一个数组,但是不用遍历整个数组,因为只需要遍历到两个数组组成完整数组的一半,既(m+n)/2(m、n分别为两个数组的长度),但是这种做法不能满足题目要求,这种做法的时间复杂度为O(m+n),而题目要求的是O(log(m+n))。我们把问题简化一下,就是找两个数组中第K个最大的数,如果数组和长度为偶数,这个需要找两个,如果为奇数,则找出一个就行。那么怎么找两个数组中第K个最大的数呢。用一个例子来说明这个问题:A = {1,3,5,7};B = {2,4,6,8,9,10};如果要求第7个小的数,A数列的元素个数为4,B数列的元素个数为6;k/2 = 7/2 = 3,而A中的第3个数A[2]=5;B中的第3个数B[2]=6;而A[2]<B[2];则A[0],A[1],A[2]中必然不可能有第7个小的数。因为A[2]<B[2],所以我们就抛弃A[0],A[1],A[2],问题变成在A = {7};B = {2,4,6,8,9,10}中找第4大的那个数,这样递归下去。

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        if (len % 2 == 1) {
            return findKth(nums1, 0, nums2, 0, len / 2 + 1);
        }
        return (findKth(nums1, 0, nums2, 0, len / 2) + findKth(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;
    }

    private int findKth(int[] A, int A_start, int[] B, int B_start, int k) {
        if (A_start >= A.length) {
            return B[B_start + k - 1];
        }
        if (B_start >= B.length) {
            return A[A_start + k - 1];
        }
        if (k == 1) {
            return Math.min(A[A_start], B[B_start]);
        }
        int A_key = A_start + k / 2 - 1 < A.length ? A[A_start + k / 2 - 1] : Integer.MAX_VALUE;
        int B_key = B_start + k / 2 - 1 < B.length ? B[B_start + k / 2 - 1] : Integer.MAX_VALUE;

        if (A_key < B_key) {
            return findKth(A, A_start + k / 2, B, B_start, k - k / 2);
        } else {
            return findKth(A, A_start, B, B_start + k / 2, k - k / 2);
        }
    }
}

这个解法是直接copy的LeetCode上的最快解,唯一不好理解的点就是当不足要找的K位时,为什么选择一个最大的数呢?其实就是直接跳过这个不足的数组,缩减另一而数组。

11. Container With Most Water (Medium)

题意

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.


有一个数组,按照数组的排列,数组每个索引所对的值代表高度,求这个数组组成的图形能放最多的水是多少。如上图,3和6柱子之前可以放最多的水。

解题

同样,双重循环暴力可解。一般数组我们首相想到的应该是能不能用线性的时间复杂度O(n)去解决,就是一趟循环。这道题我们选择两个指针,分别从头尾开始,分别计算出各自之间的面积,然后每一次只需要移动较短的那条指针,保留较长的,指导指针相遇,再用一个变量记住面积,同时每一次更新它,下面是这种思路的解法一:

public class Solution {
    public int maxArea(int[] height) {
        int l = 0;
        int r = height.length - 1;
        int max = 0;
        int c = 0;
        while(l < r){
            c = (r - l) * Math.min(height[l], height[r]);
            if(height[l] < height[r]) l++;
            else r--;
            max = Math.max(max, c);
        }
        return max;
    }
}

但是看见了LeetCode上还有更快的解法,其实思路是一样的,只是在做法上稍微优化了一下,就是减少了外层while循环的次数:

public class Solution {
    public int maxArea(int[] height) {
        int l = 0;
        int r = height.length - 1;
        int max = 0;
        while(l < r){
            int left = height[l];
            int right = height[r];
            max = Math.max(max, ((r - l) * Math.min(height[l], height[r])));
            if(left < right) while(height[l] <= left && l++ < height.length - 1);
            else while(height[r] <= right && r-- > 0);
        }
        return max;
    }
}

15. 3Sum (Medium)

题意

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

这道题的题意和简单,他也是我们第一题Two Sum的进阶,就是在一个数组中找出任意三个数,它们的和需要为0,有多少组这样的数,就找出多少组,同一个数可以用多次。如给出的示例

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:

[

[-1, 0, 1],

[-1, -1, 2]

]

解题

三重循环暴力可解。想一想一趟循环可解吗?这种数组题,有一个经验,如果和索引没有关系,我们就可以思考一下是否对它进行排序可以帮助我们解决问题,是的,这题就可以,我们可以根据排序后的数组做到一些更容易的事。首先对数组排序,然后从首位循环,以每次循环到的这个数为基准,用两个指针,一个指向它前面的一个数,一个指向数组最后一个数,基准加两个指针指向的数组成三个数,根据这三个数的和来移动两个指针,如果和刚好为零,就找出来了一组,如果和太大,就将后面的指针向前移,反之。

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        if(nums.length < 3)
            return ret;
        Arrays.sort(nums);
        int l;
        int r;
        for(int i = 0; i < nums.length; i++){
            if(i >0 && nums[i] == nums[i - 1]) continue;
            l = i + 1;
            r = nums.length - 1;
            while(l < r){
                int t = nums[i] + nums[l] + nums[r];
                if(t == 0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[l]);
                    list.add(nums[r]);
                    ret.add(list);
                    while(l < r && nums[l] == nums[l + 1])
                        l++;
                    while(l < r && nums[r] == nums[r - 1])
                        r--;
                    l++;
                    r--;
                }else if (t > 0) {
                    while(l < r && nums[r] == nums[r - 1])
                        r--;
                    r--;
                }else {
                    while(l < r && nums[l] == nums[l + 1])
                        l++;
                    l++;
                }
            }
        }
        return ret;
    }
}

题中有一些细节的优化,可以留意一下。

16. 3Sum Closest (Medium)

题意

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

这题就不用翻译了,和上面的差不多,只是要找三个数和最接近target的。

解题

同样是选一个基准和两个指针,两个指针的移动规则是,三个数的和小于目标,就增大,也就是左指针前进,反之。

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if (nums == null)
            return 0;
        int result = 0;
        int i = 0;
        if (nums.length < 4) {
            while (i < nums.length) {
                result += nums[i];
                i++;
            }
            return result;
        }
        Arrays.sort(nums);
        int minClose = Integer.MAX_VALUE;
        int s, e;
        for (; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            s = i + 1;
            e = nums.length - 1;
            while (s < e) {
                int total = nums[i] + nums[s] + nums[e];
                int close = Math.abs(total - target);
                if (close < minClose) {
                    minClose = close;
                    result = total;
                }
                if (total < target) {
                    s++;
                } else {
                    e--;
                }
            }
        }
        return result;
    }
}

18. 4Sum (Medium)

题意

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:

[

[-1, 0, 0, 1],

[-2, -1, 1, 2],

[-2, 0, 0, 2]

]

在数组中选四个数,四个数的和等于目标数

解题

这次就选两个基准数,一个从数组开始选择,一个从数组末选择,然后两个指针分别指向开始位置的下一个和数组末的上一个。

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 4)
            return result;
        Arrays.sort(nums);
        int s, e;
        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            for (int j = nums.length - 1; j > i + 2; j--) {
                if (j < nums.length - 1 && nums[j] == nums[j + 1])
                    continue;
                s = i + 1;
                e = j - 1;
                while (s < e) {
                    int sum = nums[i] + nums[j] + nums[s] + nums[e];
                    if (sum == target) {
                        List<Integer> list = new ArrayList<>(4);
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[s]);
                        list.add(nums[e]);
                        result.add(list);
                        while (s < e && nums[s] == nums[s + 1])
                            s++;
                        while (s < e && nums[e] == nums[e - 1])
                            e--;
                        s++;
                        e--;
                    } else if (sum < target)
                        s++;
                    else
                        e--;
                }
            }
        }
        return result;
    }
}

26. Remove Duplicates from Sorted Array (Easy)

题意

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,

Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

这道题有两个要求,第一是返回数组不重复的数组长度,另外,根据这个长度,该数组还必须是从零开始到指定长度都以此是不重复的数,也就是要修改原有数组。

解题

不要想得过去复杂,我们只需要一个长度变量,记录已有不同的长度,同时这个长度也代表了已经排列好的数组前一个索引。

public class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length < 2)
            return nums.length;
        int c = 1;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] == nums[i - 1]) continue;
            else {
                nums[c] = nums[i];
                c++;
            }
        }
        return c;
    }
}

27. Remove Element (Easy)

题意

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:

Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

也是两个要求,找出数组中和目标数相同的数的数量,同时需要将相同的移除。

解题

两个指针,一个在数组首,另一个在数组末。前一个指针遇到相同的,移动到后面,并把后面的向前移。如果不同,移动前面的指针。

public class Solution {
    public int removeElement(int[] nums, int val) {
        if(nums == null)
            return 0;
        int i = 0;
        int j = nums.length - 1;
        while(i <= j){
            if(nums[i] == val){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                j--;
            }else{
                i++;
            }
        }
        return j + 1;
    }
}

31. Next Permutation (Medium)

题意

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

全排列中当前排列的下一个排列,什么是全排列呢?就是一个序列的所有排列形式,如123,它所有的排列为123、132、213、231、312、321,那么下一个排列的要求是什么呢?可以直接理解按字典的顺序,下一个要比上一个序列大,就如上面举例的123

解题

怎么求一个序列的下一个排列呢?具体步骤如下:

  1. 从右向左扫描先找到第一个逆序对,记住逆序对的开始索引
  2. 从开始索引后面找,找到比该索引位置大的最小的数,然后交换它们
  3. 将开始索引位置前一个到数组末旋转

再用1 2 3 5 7 4 6 10 9 8为实例应用上面的步骤,求它的下一个排列。

  1. 从右到左找到第一个逆序对,这里是6 10,6的索引为6
  2. 从索引7开始找,找到比它大的最小的数,这里为8,交换它们:1 2 3 5 7 4 8 10 9 6
  3. 旋转索引7开始到数组末,数组变为:1 2 3 5 7 4 8 6 9 10,这个就是它的下一个排列

具体算法:

public class Solution {
    public void nextPermutation(int[] nums) {
        int j = -1;
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i - 1] < nums[i]) {
                j = i - 1;
                break;
            }
        }
        int k = j + 1;
        if (j != -1) {
            for (int i = j + 2; i < nums.length; i++) {
                if (nums[i] > nums[j] && nums[i] <= nums[k])
                    k = i;
            }
            swap(nums, j, k);
        }
        j++;
        k = nums.length - 1;
        while (j < k) {
            swap(nums, j, k);
            j++;
            k--;
        }
    }

    private void swap(int[] nums, int i, int j) {
        nums[i] = nums[i] + nums[j];
        nums[j] = nums[i] - nums[j];
        nums[i] = nums[i] - nums[j];
    }
}

33. Search in Rotated Sorted Array (Medium)

题意

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

有一个有序的数组,但是可能在某一点经过了一个180度的旋转,在这样一个数组中找到目标数,并返回索引。

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

如例子中,原数组经旋转后变成了后者数组,需要在后者数组中找到目标数,并返回索引,如果没有,返回-1,可以认为数组中不包含重复的数字

解题

有一种思路,是找到分界的那个数,如上面的0,然后在左或右进行查找。另外,在一个有序的数组中,可以使用二分查找,但是在在这样一个数组中是否可以呢?分析一下,常规的二分查找,我们只需要确定了二分的位置上的和目标的大小,就可以把左或者右指针移到二分位置右边或者左边。但是这个题中,我们要明确一点,找到二分位置后,要先确定二分位置左边的数比二分位上的数大还是小,如果小,我们就认为左边到二分位是有序的,然后确定我们要找的数是不是在之间,是就将右边指针移动到二分位左边。反之。如果左边比二分位大,我们就要确认要找的数比二分位大,比右边小,就移动左指针到二分位右边,反之。

public class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0)
            return -1;
        int l = 0;
        int r = nums.length - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(nums[mid] == target)
                return mid;
            if(nums[l] <= nums[mid]){
                if(target >= nums[l] && target < nums[mid])
                    r = mid - 1;
                else
                    l = mid + 1;
            }else{
                if(target > nums[mid] && target <= nums[r])
                    l = mid + 1;
                else
                    r = mid - 1;
            }
        }
        return -1;
    }
}
坚持原创分享,您的支持将鼓励我不断前行!