转码野生老农刷题打卡

2022-11-02打卡

658        找到 K 个最接近的元素
Link：https://leetcode.cn/problems/find-k-closest-elements/
题解：https://gitee.com/vincentmliu/Al ... losestElements.java
耗时： 1h



笔记：
1. 先通过二分找到是否有存在x，如果没有，left在右边第一个，right在左边第一个。
2. 确定搜索范围，防止越界
    startIndex = Math.max(right - k + 1, 0); //right落在小于x的第一个
    endIndex = Math.min(left + k - 1, len-1);//left落在大于x的第一个
3. 从左到右遍历（可以确保 |a - x| == |b - x| 且 a < b ）
    如果堆顶元素 top - x > now -x ，就把top弹出，now入堆
    最后sort以下返回的数组


时间复杂度 O(logN + k*logN + nlogN) 二分 + 堆排序 + 排序， 取最大，nLogn
空间复杂度 O(N) 需要一个堆来保存最接近k的数

2022-11-03打卡

875         爱吃香蕉的珂珂
Link：https://leetcode.cn/problems/koko-eating-bananas/
题解：https://gitee.com/vincentmliu/Al ... oEatingBananas.java
耗时： 1h



笔记：
1. 速度为线性递增，所以可以通过二分法来求满足条件得最佳速度
2. 确定搜索范围，因为 piles.length <= h , 所以最大速度就为 数组中的最大值，最小速度就是1（必须得吃）
3. 因为要求最接近条件得最小速度，所以 time == h 也不能停，得继续求再小的速度，知道 low == high就是最小速度
4. 最小速度是high的时候无法参与循环，所以结果初始化为high


时间复杂度 O(NlogM) 每次求吃的时间和 N * 二分次数 logM, pile中的最大值
空间复杂度 O(1) 只需要指针

2022-11-04打卡

81        搜索旋转排序数组 II
Link：https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/
题解：https://gitee.com/vincentmliu/Al ... dSortedArrayIi.java
耗时： 1d



笔记：
1. 重复数字可能会导致 nums[l] == nums[mid] == nums[r] 无法判断继续往左区间还是右区间。所以需要通过l++ 和 r--来排除while(nums[l] == nums[r] )
2. 排出后判断哪个区间是有序区间，左边还是右边。如果左边是有序区间，且nums[mid] > target （表示target落在左区间内）。 继续往左边找。反之亦然



时间复杂度 O(logN) 最差的情况可能导致算法退化为O(n),如果数组内大部分数字都是相等的话
空间复杂度 O(1) 只需要指针

2022-11-07打卡

154        寻找旋转排序数组中的最小值 II
Link：https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/
题解：https://gitee.com/vincentmliu/Al ... dSortedArrayIi.java
耗时： 1d



笔记：
1. 以nums[right]为坐标判断，
如果nums[mid] < nums[right] 说明最小值坐标i在nums[mid]的左边（i< mid < right）， right = mid;
如果nums[mid] > nums[right] 说明最小值坐标i在nums[mid]的右边(mid < i < right), left = mid + 1;
2. 对比153题，难度增加在 nums[mid] == nums[right]
无法判断mid在左区间还是右区间。所以要right--
为啥是right--不是left++?
假设 nums[right]是唯一最小值，那就不满足nums[mid] == nums[right]
假设 nums[right] 不是唯一最小值， 由于 mid < right且nums[mid] == nums[right]。 所以还存在最小值在[left, right-1]的区间内。所以不会丢失最小值。
如果是left++，可能left为最小值，而left++就会导致left丢失。




时间复杂度 O(logN) 最差的情况可能导致算法退化为O(n),如果数组内大部分数字都是相等的话
空间复杂度 O(1) 只需要指针

2022-11-09打卡

Interview 16.02        单词频率
Link：https://leetcode.cn/problems/words-frequency-lcci/
题解：https://gitee.com/vincentmliu/Al ... sFrequencyLcci.java
耗时： 20min



笔记：
1. 就把单词放到hashMap里。
2. 或者用字典树，每个char是一个array，最后叶子节点的Trie[] son = new Trir[26]频率就是该单词的频率

2022-11-10打卡

Interview 01.02        判定是否互为字符重排
Link：https://leetcode.cn/problems/check-permutation-lcci/
题解：https://gitee.com/vincentmliu/Al ... ermutationLcci.java
耗时： 5min



笔记：
1. 就把s1每个char放到hashMap里。
2. 遍历s2,遇到不包含的在s1的词就直接返回false，如果包含在s1内就 count--,直到count为0就remove掉该char的key。
3. 遍历完后，如果s1不为空，返回false;为空则为true




时间复杂度 O(n1+n2) 需要遍历s1和s2
空间复杂度 O(n1) 需要保存s1的所有char和其对应频率，最差为n1

2022-11-11打卡

4         寻找两个正序数组的中位数
Link：https://leetcode.cn/problems/median-of-two-sorted-arrays/
题解：https://gitee.com/vincentmliu/Al ... woSortedArrays.java
耗时： 5h



笔记：
1. 首先最容易想到的就是类似归并排序，排除掉 len = (nums1.len + nums2.len) /2 个值，就是中位数median。只是归并排序的时间复杂度时O(m+n) 不满足题目需求
2. 二分法的精髓主要是通过逐步排除不可能成为 len/2的数来确定 len/2 的位置。
3. 假设 k = len/2，要获取前k小的数。
分别用index1和index2在两个数组中进行标记
那么二分法就是分别获取nums1和nums2中前 k/2 个数中最大的那个，下标就是 index1 = index2 = k/2 - 1;
比较 nums1[index1] 和 nums2[index2] 有三种情况：
nums1[index1] < nums2[index2] ： 那说明 [nums1[0], nums1[index1]] 都不可能成为 前k个最小的数。排除了nums1中的 index1个数字
nums1[index1] > nums2[index2] ： 那说明 [nums2[0], nums2[index2]] 都不可能成为 前k个最小的数。排除了nums2中的 index2个数字
nums1[index1] = nums2[index2] ： 可等价于情况1或情况2，统一等价于情况1。
排除了 index1 或 index2 个数字后，大数组（nums1 + nums2）就需要获取前 k - index1或 k - index2 个数字。
最后，当k==1时，比较nums[index1] 和 nums[index2]。取小的那个就是前k个的值
执行的时候注意边界条件，如果index1或者index2到达边界了，只需返回另一个数组的前k个数字即可。

4. 要注意大数组的长度分两种情况，奇数和偶数。根据题意
奇数的时候直接寻找前 k = len/2 + 1 个值，也就是返回 下标 len/2 的值即可
偶数的时候，要找到两个值，可以分别找到 下标 len/2 - 1 和 len/2 的值，然后除以2

时间复杂度 O(log(m+n)) 每次排除 (m+n)/2个值，首次排除的是 len/2后面的数字
空间复杂度 O(1) 二分，只需要下标

2022-11-12打卡

49        字母异位词分组
Link：https://leetcode.cn/problems/group-anagrams/
题解：https://gitee.com/vincentmliu/Al ... 9GroupAnagrams.java
耗时： 20min


笔记：
1.其实就相当于给每个异位词找一个同样的哈希值。
2. 先把每个异位词排序，排序后的值作为key放到map中
3. 最后遍历map，返回结果

时间复杂度 O(mLogm * n) m是平均每个单词的字符串长，因为排序最快nlogn
空间复杂度 O(n) 需要一个map来保存所有单词

2022-11-13打卡

349        两个数组的交集
Link：https://leetcode.cn/problems/intersection-of-two-arrays/
题解：https://gitee.com/vincentmliu/Al ... ionOfTwoArrays.java
耗时： 5min


笔记：
1.遍历nums2的时候到nums1的哈希中判断是否存在

时间复杂度 O(n+m) n是nums1的长度，m是nums2的长度
空间复杂度 O(n) 需要一个Set来保存结果集

2022-11-14打卡

1122        数组的相对排序
Link：https://leetcode.cn/problems/find-k-closest-elements/
题解：https://gitee.com/vincentmliu/Al ... ativeSortArray.java
耗时： 14min



笔记：
1. 看标签，计数排序
2. 先把arr1的所有元素都放到计数数组中int[] arr1Check = new int[1001]; //下标代表arr1中元素的值
3. scan arr2, while(arr1Check[arr2elements] !=0) arr1Check[arr2elements]--;
4. 最后再scan一遍arr1Check，把剩余不为0的值放到结果数组末尾。


时间复杂度 O(n+m) 需要扫描两遍arr1，扫描一遍arr2，外加扫描一遍1001
空间复杂度 O(N) 需要保存arr1中的所有元素，最差O（N）