周赛通过情况总结
- 本次参加周赛通过2道题目，卡在第3道题目因为解题思路的原因，没能顺利通过所有的数据集。
周赛题目
将数组分成最小总代价的子数组 I
给你一个长度为 n 的整数数组nums
一个数组的代价是它的第一个元素。比方说[1,2,3]的代价是1，[3,4,1]的代价是3。
你需要将nums分成3个连续且没有交集的子数组。
请你返回这些子数组的最小代价总和
- 解题思路
- 第一个子数组的下标一定是0，所以我们只需要剩下的两个数字的起始下标。因为需要累加和最小，所以实际上我们需要找的是除第一个数字外最小的两个数字。代码如下：
class Solution {
public int minimumCost(int[] nums) {
int result=nums[0];
int idx=-1;
int midIdx=-1;
for(int i=1;i<nums.length;i++){
if (idx==-1||nums[idx]>nums[i]){
idx=i;
}
}
for(int i=1;i<nums.length;i++){
if (idx==i){
continue;
}
if (midIdx==-1||nums[midIdx]>nums[i]){
midIdx=i;
}
}
result+=nums[idx]+nums[midIdx];
return result;
}
}
判断一个数组是否可以变为有序
给你一个下标从0开始且全是正整数的数组nums。
一次操作中，如果两个相邻元素在二进制下数位为1的数目相同，那么你可以将这两个元素交换。你可以执行这个操作任意次（也可以0次）。
如果你可以使数组变有序，请你返回 true ，否则返回 false。
- 解题思路：
- 主要是通过多层循环遍历组的方式解决，代码如下：
class Solution {
public boolean canSortArray(int[] nums) {
int n=nums.length;
int i=0,preMax=0;
while(i<n){
int mn=nums[i],mx=mn;
int ones=Integer.bitCount(mn);
for(i++;i<n&&Integer.bitCount(nums[i])==ones;i++){
mn=Math.min(mn,nums[i]);
mx=Math.max(mx,nums[i]);
}
if (mn<preMax){
return false;
}
preMax=mx;
}
return true;
}
}
通过操作使数组长度最小
给你一个下标从0开始的整数数组nums，它只包含正整数。
你的任务是通过进行以下操作任意次（可以是0次）最小化nums的长度：
在nums中选择两个不同的下标i和j，满足nums[i]>0且nums[j]>0。
将结果nums[i]%nums[j]插入nums的结尾。
将nums中下标为i和j的元素删除。
请你返回一个整数，它表示进行任意次操作以后nums的最小长度。
- 解题思路
- 本题是一道脑筋急转弯题目。解题关键在于找出数组中的最小值。通过使用这个最小值对数组中的所有其他数字进行取余操作，我们可以得到答案。处理时需考虑两种情况：若最小数只出现一次，则答案为1；否则，计算该最小数出现的次数即为所求答案。代码如下：
class Solution {
public int minimumArrayLength(int[] nums) {
int m = Integer.MAX_VALUE;
for (int x : nums) {
m = Math.min(m, x);
}
for (int x : nums) {
if (x % m > 0) {
return 1;
}
}
int cnt = 0;
for (int x : nums) {
if (x == m) {
cnt++;
}
}
return (cnt + 1) / 2;
}
}
将数组分成最小总代价的子数组 II
给你一个下标从0开始长度为n的整数数组nums和两个正整数k和dist。
一个数组的代价是数组中的第一个元素。比方说，[1,2,3]的代价为1，[3,4,1]的代价为3。
你需要将nums分割成k个连续且互不相交的子数组，满足第二个子数组与第k个子数组中第一个元素的下标距离不超过dist。换句话说，如果你将nums分割成子数组nums[0…(i1-1)],nums[i1…(i2-1)],…,nums[ik-1…(n-1)]，那么它需要满足ik-1-i1<=dist。
请你返回这些子数组的最小总代价.
- 解题思路
- 通过PriorityQueue大顶堆将数组分成多个小数组，外加上懒删除的方法。代码如下：
class Solution {
int k;
PriorityQueue<int[]> lower;
PriorityQueue<int[]> higher;
int lowerSize;
int higherSize;
Set<Integer> lowerSet;
Set<Integer> higherSet;
Set<Integer> removeSet;
long totalCost;
public long minimumCost(int[] nums, int k, int dist) {
this.k = k;
this.lower = new PriorityQueue<int[]>((a, b) -> b[0] - a[0]);
this.higher = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
this.lowerSize = 0;
this.higherSize = 0;
this.lowerSet = new HashSet<Integer>();
this.higherSet = new HashSet<Integer>();
this.removeSet = new HashSet<Integer>();
this.totalCost = nums[0];
int n = nums.length;
for (int i = 1; i <= dist + 1; i++) {
add(nums[i], i);
}
long minCost = totalCost;
for (int i = dist + 2; i < n; i++) {
remove(nums[i - dist - 1], i - dist - 1);
add(nums[i], i);
minCost = Math.min(minCost, totalCost);
}
return minCost;
}
public void add(int num, int index) {
if (lowerSize < k - 1 || num <= lower.peek()[0]) {
lower.offer(new int[]{
num, index});
lowerSet.add(index);
lowerSize++;
totalCost += num;
} else {
higher.offer(new int[]{
num, index});
higherSet.add(index);
higherSize++;
}
adjustPriorityQueues();
}
public void remove(int num, int index) {
removeSet.add(index);
if (lowerSet.contains(index)) {
lowerSize--;
totalCost -= num;
} else {
higherSize--;
}
adjustPriorityQueues();
}
public void adjustPriorityQueues() {
if (lowerSize > k - 1) {
int[] arr = lower.poll();
higher.offer(arr);
lowerSize--;
higherSize++;
totalCost -= arr[0];
lowerSet.remove(arr[1]);
higherSet.add(arr[1]);
} else if (lowerSize < k - 1 && higherSize > 0) {
int[] arr = higher.poll();
lower.offer(arr);
lowerSize++;
higherSize--;
totalCost += arr[0];
lowerSet.add(arr[1]);
higherSet.remove(arr[1]);
}
for (PriorityQueue<int[]> pq : Arrays.asList(lower, higher)) {
while (!pq.isEmpty() && removeSet.contains(pq.peek()[1])) {
int[] arr = pq.poll();
removeSet.remove(arr[1]);
}
}
}
}
总结
- 在解决算法问题时，掌握Java基础提供的方法至关重要。例如，在第二题中，虽然我们构建了一个求二进制中1的个数的方法，但实际上Java已经为我们提供了相应的方法。因此，我们应该充分利用这些现有方法来提高解题效率。
- 尽管工作繁忙，仍需加强对LeetCode算法题目的熟练度，并建立自己的知识体系。为了实现这一目标，需要细化年度计划，将LeetCode算法练习具体到每日：工作日专注于解决简单题目以保持题感，而在周末，除了参加每周竞赛外，还需额外完成至少一个中等或困难难度的题目。此外，每周应选择一个特定类型的题目进行集中训练。
![[MRCTF2020]Ez_bypass1](https://img-blog.csdnimg.cn/direct/53eab380c09e4cc1945c71bd0d6a995d.png)