第318场周赛

本周周赛答得不太好，只acc一道，第二第三题均超时

Problem A - 对数组执行操作

优化：如果是对数组原地操作

移动0就不需要辅助数组，使用快慢指针，fast遇到0的元素跳过，否则，复制给slow指针

然后，将slow后面的元素都复制给0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void moveVal(int nums[],int val){
    int slow=0;
    int fast=0;
    int n=nums.length;
    while (fast<n){
        if(nums[fast]!=val){
            nums[slow++]=nums[fast];
        }
        fast++;
    }
    for (int i=slow;i<n;i++){
        nums[i]=val;
    }
}

Problem B - 长度为 K 子数组中的最大和

滑动窗口

我在做的时候，滑动窗口，用HashSet存储滑动窗口里面的内容，满足条件，循环计算HashSet的和，计算答案。 –> 超时

再试一下：

预先准备好前缀和数组，再使用滑动窗口 –> 可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public long maximumSubarraySum(int[] nums, int k) {
    int n=nums.length;
    long sum[]=new long[n];
    sum[0]=nums[0];
    for(int i=1;i<n;i++){
        sum[i]=sum[i-1]+nums[i];
    }
    int left=0;
    int right=0;
    // 记录窗口中的元素
    HashSet<Integer> set=new HashSet<Integer>();
    long ans=0;
    while(right<n){
        if(set.contains(nums[right])){
            // 将left的元素移除
            set.remove(nums[left]);
            left++;
        }else{
            // 加入到窗口
            set.add(nums[right]);
            right++;
            if(set.size()>k){
                // 将left的元素移除
                set.remove(nums[left]);
                left++;
            }
            if(set.size()==k){ //窗口内元素满足条件
                long temp=left==0?sum[right-1]:sum[right-1]-sum[left-1];
                ans=ans<temp?temp:ans;
            }
        }
    }
    return ans;
}

拓展：

变长滑动窗口：字符串

最小覆盖子串

变长滑动窗口：数组

最短超串

注：返回null和返回空数组new int[0]是不同的

定长滑动窗口：异位词

字符串的排列

字符串中的变位词

定长滑动窗口：异位词的位置
6. 438. 找到字符串中所有字母异位词
题：https://leetcode.cn/problems/find-all-anagrams-in-a-string

  1. 剑指 Offer II 015. 字符串中的所有变位词
    题：https://leetcode.cn/problems/VabMRr

Problem C - 雇佣 K 位工人的总代价

做题时，没想到用堆，超时

使用两个堆，使用左右指针维护堆元素

注意：一个工人不能进入两个堆

Problem D- 2463. 最小移动总距离

一定是一个工厂修理这一段距离上的机器人。

原问题：n个工厂修理m个机器人

子问题：1个工厂修了x个机器人，那么n-1个工厂修理m-x个机器人

找子问题很关键

方法1：记忆化搜索

定义 f(i,j)表示用第 i个及其右侧的工厂，修理第 j 个及其右侧的机器人，机器人移动的最小总距离。

j=m return 0

i=n-1 表示使用最后一个工厂修理m-j个机器人，如果工厂剩余修理机器人的数量小于m-j,则不合法

枚举第 i 个工厂修了 k个机器人，则有 $f(i,j) = \min\limits_{k}^{}{f(i+1,j+k) + \text{cost}(i,j,k)}$。

这里 $\text{cost}(i,j,k)$ 表示第 i 个工厂修复从 j 到 j+k-1 的机器人，移动距离就是这些机器人到第 i 个工厂的距离之和。

注意 $k\le\textit{limit}$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    int m;
    int n;
    static final long VALUE=100000000000L;
    public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
        // 排序
        Collections.sort(robot);
        Arrays.sort(factory,(a,b)->a[0]-b[0]);
        m=robot.size();
        n=factory.length;
        return f(0,0,robot,factory);
    }

    // f(i,j)表示第i个及其右侧的工厂修理第j个及其右侧的机器人，所需移动的机器人最小距离
    long f(int i,int j,List<Integer> robot,int[][] factory){
        if(j==m){ // 都修理完了，无需移动
            return 0;
        }
        if(i==n-1){ //最后一个工厂,需要修理m-j个机器人
            if(factory[i][1]<m-j){ //超过该工厂修理的最大数量，则说明不合理
                return VALUE;
            }else{
                long s=0;
                for(int t=j;t<m;t++){
                    s+=Math.abs(factory[i][0]-robot.get(t));
                }
                return s;
            }
        }
        // 修理第i个工厂
        long res=f(i+1,j,robot,factory);//不修理
        // 枚举修理k个机器人
        long cost=0;
        for(int k=1;k<=factory[i][1] && j+k-1<m;k++){
            cost+=Math.abs(factory[i][0]-robot.get(j+k-1));
            res=Math.min(res,cost+f(i+1,j+k,robot,factory));
        }
        return res;
    }
    
}

结果：超时

时间复杂度分析：

时间复杂度=O(状态个数)*O(单个状态转移次数)*O(单个状态转移时间)

状态个数：i的范围*j的范围

O=O(m*n)*O(m)*O(1)

方法2：递推

image-20221110115600452

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
    // 排序
    Collections.sort(robot);
    Arrays.sort(factory,(a,b)->a[0]-b[0]);
    int m=robot.size();
    int n=factory.length;
    // dp[i][j]含义：前i个工厂修理前j个机器人，所需要的最小的移动距离
    long dp[][]=new long[n][m];
    long s=0;
    for(int i=0;i<Math.min(factory[0][1],m);i++){
        s+=Math.abs(factory[0][0]-robot.get(i));
        dp[0][i]=s;
    }
    if(m>factory[0][1]){
        for(int i=factory[0][1];i<m;i++){
            dp[0][i]=Integer.MAX_VALUE;
        }
    }
    for(int i=1;i<n;i++){
        for(int j=0;j<m;j++){
            // 一个都不修
            dp[i][j]=dp[i-1][j];
            // 修理k个机器人  0<=k<=min(j,limit[i])
            s=0;
            for(int k=1;k<=Math.min(j,factory[i][1]);k++){
                s+=Math.abs(factory[i][0]-robot.get(k));
                dp[i][j]=Math.min(dp[i][j],s+dp[i-1][j-k]);
            }
        }
    }
    return dp[n-1][m-1];
}

类似题：1478安排邮筒

补：316场周赛 未解决

2449. 使数组相似的最少操作次数