LeetCode - 1

LeetCode - 1

文章目录

一. 贪心算法

1. 区间问题 二. 双指针

1. 典型 Two Sum2. 归并数组3. 快慢指针4. 滑动窗口 三. 二分查找

1. 求开方2. 查找区间3. 翻转数组查找数字 四. 排序算法

1. 常用排序算法2. 快速选择3. 桶排序4. 三指针排序

一. 贪心算法 1. 区间问题

例题452. 用最少数量的箭引爆气球。

按照数组元素后一位进行排序，第一个区间的end大于等于后面区间的start时，这几个区间可用一支箭；区间问题，首先想想应该按照哪个元素进行排序。经常需要对第二个元素进行排序。从小到大排序写法：Arrays.sort(points, (a, b) -> a[1] < b[1] ? -1 : 1);
Arrays.sort(points, (a, b) -> a[1] - b[1] ); 可能会出现溢出 二. 双指针 1. 典型 Two Sum

例题167。采用相反的两个指针遍历数组。一个初始指向最小的元素，即数组最左边，向右遍历；一个初始指向最大的元素，即数组最右边，向左遍历。

2. 归并数组

例题88。归并两个有序数组使之成为一个有序数组。如果不重新开辟空间，直接将数组b中的元素插入到数组a中，会出现数组a后续的元素被覆盖的情况（元素需要不断后移）。
所以，如果数组的数据有被覆盖的风险，可以记得用倒序！！！

3. 快慢指针

例题142。判断一个链表有没有环，并且找出入口地址。

快慢指针先判断有没有环；快慢指针相遇后，慢指针继续走，另外再让一个指针从头开始走，两者相遇的地方就是环的入口；可以画图计算证明。 4. 滑动窗口

例题 76 给你一个字符串 s 、一个字符串 t ，返回 s 中涵盖 t 所有字符的最小子串。

用一个滑动窗口在字符串 s 中滑行，判断是否包含t中所有字符；先移动右窗口 j，将 t 中所有字符包含进来，再移动 i，使窗口恰好包含所有 t 中字符；记录下满足条件的子串后，继续移动一格 i，此时窗口内则不包含所有字符，重新移动 j 直至再次满足条件，再移动 i 缩小至恰好满足条件。循环直至找到最小的子串。如何判断窗口内是否包含所有 t 中字符？维护一个 need 数组，存储包含 t 还需每个字符的数量，再维护一个元素 needNum，存储包含 t 总的尚需元素数量。当 needNum 中对应的元素数量减少为 0 时，表示该元素已全部包含；当 needNum = 0 时，表示窗口内包含所有字符。

PS：对字母进行数量存储无需使用 hashmap，可以使用 int 数组，用 asci 值代表数组下标，存储对应字母的个数。

//如下式可存储 A至z的 字母个数
int[] need = new int[128];
need[c - 'A'] += 1; // c代表某一字符

三. 二分查找 1. 求开方

例题69。求一个数的开方，忽略小数部分。

二分查找，最后返回的是右区间;避免溢出可以将乘法改成除法。 2. 查找区间

例题34. 在排序数组中查找元素的第一个和最后一个位置

方法一：递归二分查找目标元素，用一个数组存储位置信息，并不断更新最大最小位置信息。方法二：二分法分别查找第一个和最后一个位置。

// 查找左边界
int lower_bound(vector &nums, int target) {
	int l = 0, r = nums.size(), mid;
	while (l < r) {
		mid = (l + r) / 2;
		if (nums[mid] >= target) { //这里等于和大于走一条路
			r = mid;
		} else {
			l = mid + 1;
		}
	}
}

3. 翻转数组查找数字

例题33。按升序排列的整数数组 nums 在 k 处进行了旋转，从中找出目标值所在的位置。数组中的值互不相同 。

旋转排序数组问题，数值全不相同，有个规律，比较中间数与第一个数的值，如果nums[0] < nums[mid]，左边有序，否则右边有序；如果左边有序且目标值在左边，则二分查找；左边有序目标值在右边，则比较中间值与右边第一个数的值进行重复判断；如果右边有序且目标值在右边，则二分查找；右边有序且目标值在左边，则重复判断。对于数组中的值会重复的情况，如果 nums[0] == nums[mid] 则无法判断哪边有序，可判断 nums[1] 与 nums[mid] 的大小关系，以此类推。此外，无论数组中的值是否会重复，只要其有序二分查找的方法都一样。 四. 排序算法 1. 常用排序算法

//冒泡排序，比较相邻元素间的大小，每循环一次确定最后一个值
for (int i = 0; i < nums.length; i++) {
    for(int j = 0; j < nums.length - i - 1; j++) {
        if(nums[j] > nums [j + 1]) {
            int tmp = nums[j+1];
            nums[j+1] = nums[j];
            nums[j] = tmp;
        }
    }
}
return nums;

//选择排序，将当前元素与后续每一个元素进行比较，每次循环确定第一个值
for (int i = 0; i < nums.length; i++) {
    for (int j = i+1; j < nums.length; j++) {
        if (nums[j] < nums[i]) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
}
return nums;

//插入排序，将当前元素之前的数组当成已排序数组，从后往前相邻比较并交换
for (int i = 1; i < nums.length; i++) {
    for (int j = i; j > 0; j--) {
        if (nums[j] < nums[j-1]) {
            int tmp = nums[j];
            nums[j] = nums[j-1];
            nums[j-1] = tmp;
        } else {
            break;
        }
    }
}
return nums;

//归并排序，不断拆分数组直至最小，归并两队已排序数组
int[] tmp = new int[nums.length];
mergeSort(nums, 0, nums.length-1, tmp);
return nums;

public void mergeSort(int[] nums, int l, int r, int[] tmp) {
    if (l >= r) {
        return;
    }
    int m = (l + r) / 2;
    mergeSort(nums, l, m, tmp); //递归不断拆分数组直至最小
    mergeSort(nums, m+1, r, tmp);

    int p = l;
    int q = m+1;
    int i = l;
    //拆分后开始合并有序数组至tmp
    while(p <= m || q <= r) {
        if (q > r || (p <= m && nums[p] <= nums[q])) {
            tmp[i++] = nums[p++];
        } else {
            tmp[i++] = nums[q++];
        }
    }
    i = l;
    while(i <= r) {
        nums[i] = tmp[i];
        i++;
    }
}

//快排，以数组中第一个数为基准，头尾两个指针，比较指针所指元素与基准元素的大小
quickSort(0, nums.length-1, nums);
return nums;

public void quickSort(int i, int j, int[] nums) {
    if (i >= j) {
        return;
    }
    int start = i;
    int end = j;
    int tmp = nums[i];
    while (i < j) {
        while (i < j && nums[j] >= tmp) {
            j --;
        }
        nums[i] = nums[j];
        while (i < j && nums[i] <= tmp) {
            i++;
        }
        nums[j] = nums[i];
    }
    nums[i] = tmp;
    quickSort(start, i-1, nums);
    quickSort(i+1, end, nums);
}

2. 快速选择

例题 215. 数组中的第K个最大元素

快速选择，与快排类似，但是无需对元素左右两边都排序。每排完一次可以确定第 i 个元素在数组中的排序；即可比较 i 与 k 的大小，若 i == k，则返回 nums[i]；若 i < k，对右边元素进行快排；若 i > k，对左边元素进行快排。此外，为避免极端情况时间复杂度为 O(n^2)，可以随机获取每轮进行比较的 key 值，不一定取第一个数。 3. 桶排序

例题347 找出数组中前 k 个出现频率最高的元素。

桶排序，桶排序的意思是为每个值设立一个桶，桶内记录这个值出现的次数，然后对桶进行排序。先遍历数组，用hashmap存储每个元素对应的个数，然后对hashmap的值排序。对 hashmap 的值排序可以维护一个元素数目为 k 的最小堆，当元素数量小于k时，直接插入，大于 k 时比较插入值与堆顶元素的大小，将小的d出。最小堆可用优先队列实现。 4. 三指针排序

例题75. 对三个重复且打乱顺序的数排序。

三指针，一个指针l指向头，一个指针r指向尾;第三个指针i遍历，遇到0与l交换，此时i 与 l 都可以后移一位，因为交换到头的一定是0;遇到2与r交换，此时r前移，但是 i 不一定能后移，因为交换后的 i 的值不确定。

public void sortColors(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        int i = 0;
        while (i <= r) {
            if(nums[i] == 0) {
                swap(nums, i++, l++);     
            } else if (nums[i] == 2) {
                swap(nums, i, r--);
            } else {
                i ++;
            }
        }
    }