Leetcode - 147双周赛

一、3407. 子字符串匹配模式

题目链接

字符串匹配问题，把字符串 p 分成两段 、，i 是 ’ * ’ 的下标，判断 s 是否包含这两段，且这两段处于不相交 && 有前后关系

代码如下：

class Solution {
    public boolean hasMatch(String s, String p) {
        int idx = p.indexOf('*');
        int i = s.indexOf(p.substring(0, idx));
        return i>=0 && s.substring(i+idx).contains(p.substring(idx+1));
    }
}

二、3408. 设计任务管理器

题目链接

使用哈希存当前每个 taskId，对应的 userId 和 priority，再使用堆存储 taskId 和 priority，按照 priority 排序，如果优先级相同，按照 taskId 排序。

• TaskManager()，将数据存入哈希表和堆
• add()，将数据存入哈希表和堆
• edit()，更新哈希表，将更新后的数据存入堆
• rmv()，更新哈希表 execTop()，不断的将数据排出堆，使用懒删除，如果当前数据存储在哈希表中，返回当前的 userId

代码如下:

class TaskManager {
    Map<Integer, int[]> map = new HashMap<>();
    PriorityQueue<int[]> que = new PriorityQueue<>((x,y)->x[1]==y[1]?y[0]-x[0]:y[1]-x[1]);
    public TaskManager(List<List<Integer>> tasks) {
        for(List<Integer> x : tasks){
            int userId = x.get(0), taskId = x.get(1), priority = x.get(2);
            map.put(taskId, new int[]{userId, priority});
            que.offer(new int[]{taskId, priority});
        }    
    }
    
    public void add(int userId, int taskId, int priority) {
        map.put(taskId, new int[]{userId, priority});
        que.offer(new int[]{taskId, priority});
    }
    
    public void edit(int taskId, int newP) {
        int[] t = map.get(taskId);
        t[1] = newP;
        map.put(taskId, t);
        que.offer(new int[]{taskId, t[1]});
    }
    
    public void rmv(int taskId) {
        map.remove(taskId);
    }
    
    public int execTop() {
        while(!que.isEmpty()){
            int[] t = que.poll();
            if(map.containsKey(t[0]) && map.get(t[0])[1] == t[1]){
                int user = map.get(t[0])[0];
                map.remove(t[0]);
                return user;
            }
        }
        return -1;
    }
}

三、3409. 最长相邻绝对差递减子序列

题目链接

定义$f[i][j]$: 以 $x=nums[i]$ 为结尾的且与倒数第二个数的绝对值的差至少为 $j$（即倒数第二个数为 $x-j/x+j$）的子序列的最长长度。

对于 $x=nums[i]$，题目要求两数差的绝对值是非递增的（即倒数第三个数和倒数第二个数的绝对差值 $>=j$ ），分类讨论：

• $nums[i]$ 单独形成一个子序列 ，$f[i][j]=1$
• 倒数第一个数和倒数第二个数的绝对差值 $>j$，也就是绝对差值 $>=j+1$，$f[i][j]=f[i][j+1]$
• 倒数第一个数和倒数第二个数的绝对差值 $=j$，也就是倒数第二个数的值为 $x+j/x-j$，$f[i][j]=max(f[last[x-j]][j]，f[last[x+j]][j])$
• $last[x]$：值为 $x$ 的数在 $nums$ 数组中的下标

最终 $f[i][j]=max(1,f[i][j+1],f[last[x+j]][j],f[last[x-j]][j])$

代码如下：

class Solution {
    public int longestSubsequence(int[] nums) {
        int n = nums.length;
        int mx = nums[0], mn = nums[0];
        for(int x : nums){
            mx = Math.max(mx, x);
            mn = Math.min(mn, x);
        }
        int maxD = mx - mn;
        int ans = 0;
        int[][] f = new int[n][maxD+2];
        int[] last = new int[mx + 1];
        Arrays.fill(last, -1);
        for(int i=0; i<n; i++){
            int x = nums[i];
            for(int j=maxD; j>=0; j--){
                f[i][j] = Math.max(f[i][j+1], 1);
                if(x - j >= 0 && last[x - j] >= 0){
                    f[i][j] = Math.max(f[i][j], f[last[x-j]][j] + 1);
                }
                if(x + j <= mx && last[x+j] >= 0){
                    f[i][j] = Math.max(f[i][j], f[last[x+j]][j] + 1);
                }
                ans = Math.max(ans, f[i][j]);
            }
            last[x] = i;
        }
        return ans;
    }
}

//定义f[x][j]:以值 x 结尾的且与倒数第二个数的绝对差值至少为 j 的子序列的最长长度
class Solution {
    public int longestSubsequence(int[] nums) {
        int n = nums.length;
        int mx = nums[0], mn = nums[0];
        for(int x : nums){
            mx = Math.max(mx, x);
            mn = Math.min(mn, x);
        }
        int maxD = mx - mn;
        int ans = 0;
        int[][] f = new int[mx+1][maxD+1];
        for(int x : nums){
            int fx = 1;
            for(int j=maxD; j>=0; j--){
                if(x-j >= 0){
                    fx = Math.max(fx, f[x-j][j] + 1);
                }
                if(x+j <= mx){
                    fx = Math.max(fx, f[x+j][j] + 1);
                }
                f[x][j] = fx;
                ans = Math.max(ans, fx);
            }
        }
        return ans;
    }
}

四、3410. 删除所有值为某个元素后的最大子数组和

题目链接

本题直接使用线段数来维护四个值——区间和，最大前缀和，最大后缀和，区间最大子数组和，代码如下：

class SegmentTree{
    private record Info(long sum, long pre, long suf, long ans){}
    Info[] tree;
    public SegmentTree(int[] nums){
        int n = nums.length;
        tree = new Info[n<<2];
        build(1, 0, n-1, nums);
    }
    void build(int i, int l, int r, int[] nums){
        if(l == r){
            int val = nums[l];
            tree[i] = new Info(val, val, val, val);
            return;
        }
        int m = (l + r) / 2;
        build(i<<1, l, m, nums);
        build(i<<1|1,m+1,r,nums);
        tree[i] = merge(tree[i<<1],tree[i<<1|1]);
    }
    Info merge(Info a, Info b){
        return new Info(
            a.sum + b.sum,
            Math.max(a.pre, a.sum+b.pre),
            Math.max(b.suf, a.suf+b.sum),
            Math.max(Math.max(a.ans, b.ans), a.suf+b.pre)
        );
    }
    void update(int o, int l, int r, int i, int val){
        if(l == r){
            tree[o] = new Info(val, val, val, val);
            return;
        }
        int m = (l + r) / 2;
        if(i <= m){
            update(o<<1, l, m, i, val);
        }else{
            update(o<<1|1, m+1, r, i, val);
        }
        tree[o] = merge(tree[o<<1], tree[o<<1|1]);
    }
    long queryAll(){
        return tree[1].ans;
    }
}
class Solution {
    public long maxSubarraySum(int[] nums) {
        SegmentTree t = new SegmentTree(nums);
        long ans = t.queryAll();
        if(ans <= 0) return ans;
        int n = nums.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i=0; i<n; i++){
            if(nums[i] < 0)
                map.computeIfAbsent(nums[i], e->new ArrayList<>()).add(i);
        }
        for(List<Integer> x : map.values()){
            for(int i : x){
                t.update(1, 0, n-1, i, 0);
            }
            ans = Math.max(ans, t.queryAll());
            for(int i : x){
                t.update(1, 0, n-1, i, nums[i]);
            }
        }
        return ans;
    }
}

原文地址：https://blog.csdn.net/m0_74859835/article/details/145122688

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！