记录LeetCode刷题时遇到的数组相关题目,第三篇
第一篇地址
第二篇地址
看到最小k,第一个想到的就是用优先队列 / 堆来解题;除此之外也可以先对数组排序然后直接取前k个数。但是这两种做法都需要对整个数组进行调整,但是我们只需要其中 k 个最小就够;而且这两种做法取出来的最小 k 个数都是有序的,但题目并不要求有序。总而言之,这两种做法会出现多余的操作
可以借助快排的思想:快排操作就是每次将一个数 (枢轴) 放置到其按顺序所该存放的位置上,保证其左边所有的数都小于等于它,其右边所有的数都大于等于它。那么,假设一次操作完,将枢轴放到它所应该在的位置上,发现恰好是下标 k 的位置,那么整个数组中最小 k 个数不就正好是它左边那 k 个数吗
所以只需在快排的基础上,每次排完一个枢轴判断它的位置,如果是索引 k 的位置,那就返回其左边 k 个数;如果是索引 k - 1 的位置,就返回其左边 k - 1个数再加上它本身;如果大于 k ,就对左边部分进行快排;如果小于k - 1,就对右边部分进行快排
class Solution {
int[] quickSort(int[] arr,int l,int r,int k){
if(l >= r) return null;
int ll = l;
int rr = r;
while(rr > ll){
while(arr[rr] >= arr[l] && rr > ll) rr--;
while(arr[ll] <= arr[l] && rr > ll) ll++;
if(rr != ll){ //这里如果改成了rr > ll,用时就变 2ms 了
swap(arr,rr,ll);
}
}
swap(arr,rr,l);
if(rr == k) return Arrays.copyOfRange(arr,0,rr);
if(rr == k - 1) return Arrays.copyOfRange(arr,0,rr + 1);
if(rr > k) return quickSort(arr,l,rr - 1,k);
if(rr < k) return quickSort(arr,rr + 1,r,k);
return null;
}
public int[] smallestK(int[] arr, int k) {
if(k == 0) return new int[0];
return quickSort(arr,0,arr.length - 1,k);
}
void swap(int[] arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
面试题 17.24. 最大子矩阵
解题思路来自该题解
大概就是,对于每一行 i,将第 i 行到第 j 行 (j = i,i + 1,…,row - 1) 之间的所有行 “压榨” 为一行,然后进行一维数组的最大子数组和 (参考LeetCode 53题) 求解
public int[] getMaxMatrix(int[][] matrix) {
int row = matrix.length;
int column = matrix[0].length;
int maxSum = Integer.MIN_VALUE,r1 = 0,c1 = 0,r2 = 0,c2 = 0,sum,r1Tmp = 0,c1Tmp = 0;
int[] rowSum = new int[column]; //当前被“压榨”的所有行中每一列的和
for(int i = 0;i < row;i++){ //对于每一行 i
Arrays.fill(rowSum,0);
for(int j = i;j < row;j++){ //枚举 j
sum = 0;
for(int k = 0;k < column;k++){
rowSum[k] += matrix[j][k]; //求i 到 j 行间所有行中每一列的和
if(sum > 0) sum += rowSum[k];
else{ //前面的和小于0,那就弃掉,让当前列的和作为新的 sum,同时更新左上角的行列坐标
sum = rowSum[k];
r1Tmp = i;
c1Tmp = k;
}
if(sum > maxSum){ //如果得到了比维护的子矩阵最大和还大的和,就更新维护答案的四个坐标以及maxSum
maxSum = sum;
r1 = r1Tmp;
c1 = c1Tmp;
r2 = j;
c2 = k;
}
}
}
}
return new int[]{r1,c1,r2,c2};
}
1498. 满足条件的子序列数目 (双指针)
首先要清楚:对于选取的子序列,我们只需要关注其中的最大元素和最小元素,而不需要考虑其中元素的相对位置,所以我们可以先变治,排序简化问题
那么思路就是:对数组排序,然后使用双指针枚举每个 最小元素 + 最小元素 小于等于 target 的区间,然后在这个区间中选取子序列,只要其中的最小元素一定被选,那么其它元素选不选,得到的子序列都是满足条件,所以如果区间长度为 l ,那么该区间可以得到的子序列数就是 2l-1
public int numSubseq(int[] nums, int target) {
Arrays.sort(nums);
if (nums[0] * 2 > target) {
return 0;
}
int left = 0; //左指针
int right = nums.length - 1; //右指针
int res = 0; //记录最终答案
int[] pow = new int[nums.length]; //维护 2次幂 数组,pow[i] = 2的i次幂
pow[0] = 1;
int modNum = 1_000_000_007;
for (int i = 1; i < nums.length; i++) {
pow[i] = pow[i - 1] * 2;
pow[i] %= modNum;
}
while (left <= right) {
if (nums[left] + nums[right] <= target) {
res += pow[right - left];
res %= modNum;
left++; //以left为最小元素的子序列已被计算过,left右移
}
else {
right--;
}
}
return res;
}
在官方题解中看到下面两个公式,拿过来记录一下:
原有的每个区间都无重叠。插入区间插入后,原有区间跟他的关系为:在插入区间的左侧,在插入区间的右侧,跟插入区间有重叠部分。对于跟插入区间有重叠部分的区间,我们不用对其情况进行细分,因为不管区间是以怎样的形式与插入区间重叠,这些区间最终都应跟插入区间一起合并为一个大交集。而这个大交集的左边界就是这些包括插入区间在内的所有重叠区间的左边界的最小值,而大交集的右边界就是这些所有重叠区间的右边界的最大值
引入大交集后,所有的区间又可以分为这样的三类:在原来的插入区间的左侧的区间,在原来的插入区间右侧的区间,以及大交集
所以解题思路就是遍历 intervals 数组,找出所有在原来的插入区间的左侧的区间直接放到结果 list 中,一边维护更新大交集的左右边界,在找到第一个在原来的插入区间的右侧的区间时,就可以将大交集放入 list,再把剩下的在原来的插入区间右侧的区间全部加入 list 即可
还要注意的 case 是,插入区间就在原有所有区间的左侧或者就在原有所有区间的右侧
public int[][] insert(int[][] intervals, int[] newInterval) {
int left = newInterval[0];
int right = newInterval[1];
boolean flag = false; //标记大交集是否已放入 list
List list = new ArrayList<>();
for (int[] interval : intervals) {
if (interval[0] > right) { //区间在大交集的右侧
//此时 大交集如果还未放入,就要先把大交集放入,即遍历到第一个在大交集右侧的区间。以后再遍历到大交集右侧的区间时直接放入即可
if (!flag) {
list.add(new int[]{left, right});
flag = true;
}
list.add(interval);
} else if (interval[1] < left) {//在大交集的左侧
list.add(interval);
} else {
// 与插入区间有交集,计算它们的并集
left = Math.min(left, interval[0]);
right = Math.max(right, interval[1]);
}
}
if (!flag) { //如果从头到尾大交集都没有被放入,说明插入区间在所有原来区间的右侧,此时的大交集只有插入区间本身。直接放入即可
list.add(new int[]{left, right});
}
return list.toArray(new int[0][]);
}
898. 子数组按位或操作 (位运算)
下面给出的是有经过剪枝操作后的暴力做法,把那句 if 去掉就是单纯的暴力做法
首先从暴力做法说起。首先是一个 Set 用于去重。枚举数组中的每一个元素 arr[i],然后遍历其左边的每个元素 arr[j],计算 arr[j] | arr[i] 的值,然后将这个值放入 Set,由 Set 完成去重的工作。这里其实就是枚举了 arr[j,…,i] 这个子数组,那么可能就会有疑惑了,不是只计算了 arr[j] | arr[i] 吗,为什么计算完表示的就是 arr[j,…,i] 的或运算和。这里每次 arr[j,…,i] 计算后是赋值回 arr[j] 的,所以 arr[j] 是具有累积性的,那么由于原数组 arr 被覆盖了,我们以 a 数组来表示原来数组中的数。
当枚举到 arr[i] 时,其左边的每个 arr[j] 的值其实等于 a[j] | a[j + 1] | … | a[i - 1],这个可以通过拿一个 case 模拟一遍就可以看出来,所以 a[j] | a[i] 后就会得到 a[j,…,i] 的或运算和
搞明白了暴力做法的原理还不够,因为直接暴力的话会超时。接下来考虑怎么剪枝
前面提到,当枚举到 a[i] 时,有
a
r
r
[
j
]
=
a
[
j
]
∣
a
[
j
+
1
]
∣
.
.
.
∣
a
[
i
−
1
]
arr[j] = a[j] | a[j + 1] | ... | a[i - 1]
arr[j]=a[j] ∣ a[j+1] ∣ ... ∣ a[i−1],
那么就有
a
r
r
[
j
−
1
]
=
a
[
j
−
1
]
∣
a
[
j
]
∣
a
[
j
+
1
]
∣
.
.
.
∣
a
[
i
−
1
]
=
a
[
j
−
1
]
∣
a
r
r
[
j
]
arr[j - 1] = a[j - 1] | a[j] | a[j + 1] | ... | a[i - 1] = a[j - 1] | arr[j]
arr[j−1]=a[j−1] ∣ a[j] ∣ a[j+1] ∣ ... ∣ a[i−1] = a[j−1] ∣ arr[j],
那么如果有
a
r
r
[
j
]
∣
a
[
i
]
=
=
a
r
r
[
j
]
arr[j] | a[i] == arr[j]
arr[j] ∣ a[i] == arr[j],就会有
a
r
r
[
j
−
1
]
∣
a
[
i
]
=
a
[
j
−
1
]
∣
a
r
r
[
j
]
∣
a
[
i
]
=
a
[
j
−
1
]
∣
a
r
r
[
j
]
=
a
r
r
[
j
−
1
]
arr[j - 1] | a[i] = a[j - 1] | arr[j] | a[i] = a[j - 1] | arr[j] = arr[j - 1]
arr[j−1] ∣ a[i] = a[j−1] ∣ arr[j] ∣ a[i] = a[j−1] ∣ arr[j] = arr[j−1],
以此类推,从 arr[j] 开始再往左的所有 arr[j] 经过与 a[i] 或运算后都不变,那就没必要再次添加到 Set 中,也就没必要继续往左去算了,这就是剪枝操作
public int subarrayBitwiseORs(int[] arr) {
HashSet set = new HashSet<>();
int len = arr.length;
for(int i = 0;i < len;i++){
set.add(arr[i]);
for(int j = i - 1;j >= 0;j--){
//注意位运算要加括号
if((arr[j] | arr[i]) == arr[j]) break; //把这行去掉就是没有剪枝的暴力做法
arr[j] |= arr[i];
set.add(arr[j]);
}
}
return set.size();
}
189. 轮转数组
首先,向后轮转的实际位数为 k % n。可以发现,轮转后的结果,一是原数组中的后 k % n 个数放到了前面;二是剩下的前面 n - (k % n) 个数按顺序向后移了 k % n 位
所以可以,先翻转整个数组,然后再分别将前 k % n 个数以及剩下的后面 n - ( k % n) 个数翻转
class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
//交换数字用三步异或进一步提高效率
nums[start] ^= nums[end];
nums[end] ^= nums[start];
nums[start] ^= nums[end];
start++;
end--;
}
}
}
674. 最长连续递增序列
要求子序列必须是连续的。变量 l 维护当前遍历到的数所在的连续序列的长度,那么,当遍历到 nums[i] 时,如果 nums[i] > nums[i - 1],l 就加一,否则 nums[i] 就应该作为新的递增序列的开头重新计算, l 置为 1
public int findLengthOfLCIS(int[] nums) {
int len = nums.length;
int l = 1,maxL = 1; //maxL维护最大长度。l初始化为1,对应 nums[0]
for(int i = 1;i < len;i++){
if(nums[i] > nums[i - 1]){
l++;
maxL = Math.max(l,maxL);
}
else l = 1;
}
return maxL;
}
658. 找到 K 个最接近的元素
方法一,由于一定要删除数组中 len - k 个元素,所以可以用头尾双指针,l 初始指向 arr[0],r 初始指向 arr[len - 1],然后判断 l 跟 r 对应元素谁更靠近 x,如果 l 更靠近,就 r–;否则 l++,判断 len - k 次之后,[l,r] 中的元素就是最接近 x 的 K 个元素
public List986. 区间列表的交集findClosestElements(int[] arr, int k, int x) { if(k == 0) return new LinkedList<>(); int len = arr.length; int count = len - k; int l = 0; int r = len - 1; for(int i = 0;i < count;i++){ if(Math.abs(arr[l] - x) <= Math.abs(arr[r] - x)){ r--; }else{ l++; } } List list = new LinkedList<>(); for(int i = l;i <= r;i++){ list.add(arr[i]); } return list; }
双指针遍历 A,B 每一个区间,然后取交集,但是不能每遍历完一对区间就都考虑下一对区间,即不能两个指针都前移,因为考虑到可能某个数组中有一个大区间,其中包含了另一个数组中多个区间,所以要判断,如果某个数组中当前区间的右边界大于另一个数组中当前区间的右边界,就不前移这个数组的指针
public int[][] intervalIntersection(int[][] A, int[][] B) {
List ans = new LinkedList<>();
int i = 0, j = 0;
while (i < A.length && j < B.length) {
//取交集
int lo = Math.max(A[i][0], B[j][0]);
int hi = Math.min(A[i][1], B[j][1]);
if (lo <= hi) ans.add(new int[]{lo, hi});
//判断哪个指针要前移
if (A[i][1] < B[j][1]) i++;
else j++;
}
return ans.toArray(new int[0][]);
}
66. 加一
public int[] plusOne(int[] digits) {
//根据题意,首位是0的话digits表示的就是0,直接返回1
if(digits[0] == 0) return new int[]{1};
int len = digits.length;
//如果最低位小于9,那就直接加一然后返回,如[1,8,8],直接返回[1,8,9]
if(digits[len - 1] < 9){
digits[len - 1] += 1;
return digits;
}
//如果最低位等于9,那就加一进位,进位后可以被进的高一位也要进位,所以要一直进位到出现进位完
//小于等于9的位,或者一直进位到最高位然后最左边补个1,
//如[1,9,9],进位进到1,得到[2,0,0]
//又如[9,9,9],进位完最左边要多补一位,得到[1,0,0,0]
int index = len - 1;
digits[index] = 10;
while(digits[index] > 9){
digits[index--] = 0;
//已经进到最高位了,所以多补一个最高位的1
if(index == -1){
int[] ans = new int[len + 1];
ans[0] = 1;
System.arraycopy(digits,0,ans,1,len);
return ans;
}
digits[index] += 1;
}
return digits;
}


![[LeetCode]-数组-3 [LeetCode]-数组-3](http://www.mshxw.com/aiimages/31/936799.png)
