「数组」专题 1：简单问题汇总

「数组」专题 1：简单问题汇总

「力扣」第 215 题：数组中的第 K 个最大元素

1、使用优先队列完成；

2、使用快速排序完成。

Java 代码：

public class Solution {

    /**
     * 给定任意一个数组，返回第 k 大的元素，并非索引
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int p = 0;

        int left = 0;
        int right = len - 1;
        while (left <= right) {
            p = partition(nums, left, right);
            if (len - p == k) {
                break;
            } else if (len - p + 1 > k) {
                left = p + 1;
            } else {
                right = p - 1;
            }
        }
        return nums[p];
    }

    /**
     * 4,3,7,8
     *
     * @param nums
     * @param left
     * @param right
     * @return
     */
    private int partition(int[] nums, int left, int right) {
        // 就找第 1 个元素作为标定点
        int k = nums[left];

        int i = left + 1; // [left,i)小于 k
        int j = right; // (j,right]大于 k

        for (int l = left + 1; i <= j; l++) {
            if (nums[l] < k) {
                i++;
            } else {//nums[l]>=k
                swap(nums, l, j--);
                l--;
            }

        }
        i--;
        swap(nums, i, left);
        return i;
    }


    private void swap(int[] data, int index1, int index2) {
        if (index1 == index2) return;
        int temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }


    public static void main(String[] args) {
        int[] data = {3, 2, 1, 5, 6, 4};
        int k = 2;
        Solution solution = new Solution();

        solution.partition(data, 2, 4);
        int kthLargest = solution.findKthLargest(data, k);
        System.out.println("kthLargest = >" + kthLargest);
    }
}

「力扣」第 5 题：最长回文子串

解法1：中心扩散法；

解法2：动态规划；

解法3：著名的马拉车算法。

「力扣」第 209 题： 长度最小的子数组

「力扣」第167 题：两数之和 II - 输入有序数组

「力扣」第 438 题：找到字符串中所有字母异位词

使用滑动窗口解决的典型问题。

「力扣」第 76 题： 最小覆盖子串（困难）

「力扣」第 630 题：课程调度问题

「力扣」第 452 题：用最少数量的箭引爆气球。

关键：画图。理解按照右端点升序排序的好处。

「力扣」第 80 题：删除排序数组中的重复项 II

这个写的比较顺，一下就通过了，但是我的解法只是击败了 35.43% 的选手。

public class Solution {

    /**
     * 如果我们允许重复的元素最多出现两次呢？
     *
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {

        int k = 0;// 从[0,k) 这个区间里的所有元素是一个有序数组，并且重复元素最多出现两次
        int duplicate_time = 0;

        // 首先考虑极端的情况
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        nums[k++] = nums[0];

        if (len == 1) {
            return 1;
        }

        for (int i = 1; i < len; i++) {
            if (nums[i] - nums[i - 1] == 0) {
                duplicate_time++;
                if (duplicate_time < 2) {
                    // 重复次数大于等于 2 次，什么都不做
                    nums[k++] = nums[i];
                }
            } else { // nums[i] - nums[i - 1] > 0
                duplicate_time = 0;
                nums[k++] = nums[i];
            }
        }
        // 把数组的剩余元素赋值为 -1
        for (int i = k; i < len; i++) {
            nums[i] = -1;
        }
        return k;
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4};
        Solution solution = new Solution();
        int removeDuplicates = solution.removeDuplicates(arr);
        System.out.println("剩余的数组元素的个数 => " + removeDuplicates);
        System.out.println(Arrays.toString(arr));
    }

}

「力扣」第 75 题：颜色分类

分析：三路快排，不借助额外空间就排好序，背模板。。

「力扣」第 88 题：合并两个有序数组

关键：从后向前归并排序，背模板。其实就是归并排序，从后面向前面归并排序，扩展：字符串替换空格。

Java 代码：

public class Solution {

    /**
     * @param nums1 一个排好序的数组1
     * @param m
     * @param nums2 一个排好序的数组2
     * @param n     结果放在 nums1 中
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] temp = new int[m + n];
        for (int i = 0; i < m; i++) {
            temp[i] = nums1[i];
        }
        for (int i = 0; i < n; i++) {
            temp[m + i] = nums2[i];
        }


        int left = 0; // 数组1的第1个元素
        int right = m; // 数组2的第1个元素

        // 这种特殊情况要考虑进去
        if (m > 0 && n > 0 && temp[m - 1] <= temp[m]) {
            for (int i = 0; i < m + n; i++) {
                nums1[i] = temp[i];
            }
            return;
        }

        // 要赋值完 m+n 个元素，就要遍历 m+n 个元素
        for (int i = 0; i < m + n; i++) {
            if (left >= m) { // 如果左边用完了，就一直拿右边的元素
                nums1[i] = temp[right];
                right++;
            } else if (right >= m + n) {
                nums1[i] = temp[left];
                left++;
            } else if (temp[left] < temp[right]) {
                nums1[i] = temp[left];
                left++;
            } else { // temp[left] >= temp[right]
                nums1[i] = temp[right];
                right++;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {0, 0, 0, 0, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1};
        int[] nums2 = {5, 6, 7, 8, 9};

        Solution solution = new Solution();
        solution.merge(nums1, 5, nums2, 5);
        System.out.println(Arrays.toString(nums1));

    }

} 

「力扣」第 56 题：压缩区间（区间个数变少）

链接：56. 合并区间。

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

注意：对于 list 对象而言，if l 等价于 if len(l) > 0 而不是 l is not Node。

Python 代码：

# Definition for an interval.
class Interval(object):
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e

    def __str__(self):
        return '[' + str(self.start) + ',' + str(self.end) + ']'


class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        result = []
        # 按照开始端点升序排序
        sorted_intervals = sorted(intervals, key=lambda x: x.start)

        for intv in sorted_intervals:
            if len(result) != 0 and result[-1].end >= intv.start:
                # 说明当前遍历到的区间和结果集中有交集
                result[-1].end = max(result[-1].end, intv.end)
            else:
                result.append(intv)
        return result


if __name__ == '__main__':
    # [[1, 3], [2, 6], [8, 10], [15, 18]]
    i1 = Interval(1, 3)
    i2 = Interval(2, 6)
    i3 = Interval(8, 10)
    i4 = Interval(15, 18)
    intervals = [i1, i2, i3, i4]
    solution = Solution()
    result = solution.merge(intervals)
    for item in result:
        print(item)

「力扣」第 57 题：插入一个区间（区间个数不变）

链接：57. 插入区间。

给出一个无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1:

输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
输出: [[1,5],[6,9]]

示例 2:

输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出: [[1,2],[3,10],[12,16]]
解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

Java 代码：

import java.util.*;

class Interval {
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) {
        start = s;
        end = e;
    }
}


// http://zxi.mytechroad.com/blog/geometry/leetcode-57-insert-interval/

public class Solution {

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        int len = intervals.size();
        if (len == 0) {
            intervals.add(newInterval);
            return intervals;
        }
        intervals.add(newInterval);

        // intervals.sort((Interval a, Interval b) -> a.start - b.start);
        intervals.sort(Comparator.comparingInt((Interval i) -> i.start));
        Stack<Interval> stack = new Stack<>();
        stack.add(intervals.get(0));

        for (int i = 1; i <= len; i++) {
            Interval peekInterval = stack.peek();
            Interval curInterval = intervals.get(i);
            if (peekInterval.end < curInterval.start) {
                // [1,3] [4,6] 这种情况，无论如何也合并不了的
                stack.add(curInterval);
            } else {
                // [1,3][3,5]
                // [1,3][2,6]
                // 这两种情况就需要合并
                peekInterval.end = Math.max(curInterval.end, peekInterval.end);
            }
        }
        return stack;
    }

    public static void main(String[] args) {
        // intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
        Interval interval1 = new Interval(1, 2);
        Interval interval2 = new Interval(3, 5);
        Interval interval3 = new Interval(6, 7);
        Interval interval4 = new Interval(8, 10);
        Interval interval5 = new Interval(12, 16);
        List<Interval> intervals = new ArrayList<>();
        intervals.add(interval1);
        intervals.add(interval2);
        intervals.add(interval3);
        intervals.add(interval4);
        intervals.add(interval5);

        Solution solution = new Solution();
        Interval newInterval = new Interval(4, 8);
        List<Interval> list = solution.insert(intervals, newInterval);
        for (Interval interval : list) {
            System.out.println("[" + interval.start + ", " + interval.end + "]");
        }
    }
}

Java 代码：

import java.util.ArrayList;
import java.util.List;

public class Solution2 {

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if (newInterval == null) {
            return intervals;
        }
        List<Interval> res = new ArrayList<>();
        int len = intervals.size();

        // 之前的加起来
        int i = 0;
        while (i < len && intervals.get(i).end < newInterval.start) {
            res.add(intervals.get(i));
            i++;
        }

        //
        // intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
        // 此时 intervals.get(i).end >= newInterval.start
        while (i < len && intervals.get(i).start <= newInterval.end) {
            newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
            newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
            i++;
        }

        res.add(newInterval);

        // 把剩下的加掉
        while (i < intervals.size()) {
            res.add(intervals.get(i));
            i++;
        }
        return res;
    }

    public static void main(String[] args) {
        // intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
        Interval interval1 = new Interval(1, 2);
        Interval interval2 = new Interval(3, 5);
        Interval interval3 = new Interval(6, 7);
        Interval interval4 = new Interval(8, 10);
        Interval interval5 = new Interval(12, 16);
        List<Interval> intervals = new ArrayList<>();
        intervals.add(interval1);
        intervals.add(interval2);
        intervals.add(interval3);
        intervals.add(interval4);
        intervals.add(interval5);

        Solution2 solution2 = new Solution2();
        Interval newInterval = new Interval(4, 8);
        List<Interval> list = solution2.insert(intervals, newInterval);
        for (Interval interval : list) {
            System.out.println("[" + interval.start + ", " + interval.end + "]");
        }
    }
}

「力扣」第 836 题：矩形重叠

要求：矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。

如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。

给出两个矩形，判断它们是否重叠并返回结果。

分析：

不是这种坐标系：

（0,0）（0,1）（0,2）（0,3）

（1,0）（1,1）（1,2）（1,3）

（2,0）（2,1）（2,2）（2,3）

（3,0）（3,1）（3,2）（3,3）

而是直角坐标系

（3,0）（3,1）（3,2）（3,3）

（2,0）（2,1）（2,2）（2,3）

（1,0）（1,1）（1,2）（1,3）

（0,0）（0,1）（0,2）（0,3）

（本节完）