一、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;}
}