怎么搜索网站,做我男朋友的网站,网站2019建设目标,专业网站建设顾问目录 一、3407. 子字符串匹配模式二、3408. 设计任务管理器三、3409. 最长相邻绝对差递减子序列四、3410. 删除所有值为某个元素后的最大子数组和 一、3407. 子字符串匹配模式
题目链接 字符串匹配问题#xff0c;把字符串 p 分成两段 、#xff0c;i 是 ’ * ’ 的下标把字符串 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 i0 s.substring(iidx).contains(p.substring(idx1));}
}二、3408. 设计任务管理器
题目链接 使用哈希存当前每个 taskId对应的 userId 和 priority再使用堆存储 taskId 和 priority按照 priority 排序如果优先级相同按照 taskId 排序。
TaskManager()将数据存入哈希表和堆add()将数据存入哈希表和堆edit()更新哈希表将更新后的数据存入堆rmv()更新哈希表 execTop()不断的将数据排出堆使用懒删除如果当前数据存储在哈希表中返回当前的 userId
代码如下:
class TaskManager {MapInteger, int[] map new HashMap();PriorityQueueint[] que new PriorityQueue((x,y)-x[1]y[1]?y[0]-x[0]:y[1]-x[1]);public TaskManager(ListListInteger tasks) {for(ListInteger 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 ] f[i][j] f[i][j]: 以 x n u m s [ i ] x nums[i] xnums[i] 为结尾的且与倒数第二个数的绝对值的差至少为 j j j即倒数第二个数为 x − j / x j x-j/xj x−j/xj的子序列的最长长度。
对于 x n u m s [ i ] x nums[i] xnums[i]题目要求两数差的绝对值是非递增的即倒数第三个数和倒数第二个数的绝对差值 j j j 分类讨论 n u m s [ i ] nums[i] nums[i] 单独形成一个子序列 f [ i ] [ j ] 1 f[i][j] 1 f[i][j]1倒数第一个数和倒数第二个数的绝对差值 j j j也就是绝对差值 j 1 j1 j1 f [ i ] [ j ] f [ i ] [ j 1 ] f[i][j] f[i][j1] f[i][j]f[i][j1]倒数第一个数和倒数第二个数的绝对差值 j j j也就是倒数第二个数的值为 x j / x − j xj/x-j xj/x−j f [ i ] [ j ] m a x ( f [ l a s t [ x − j ] ] [ j ] f [ l a s t [ x j ] ] [ j ] ) f[i][j] max(f[last[x-j]][j]f[last[xj]][j]) f[i][j]max(f[last[x−j]][j]f[last[xj]][j]) l a s t [ x ] last[x] last[x]值为 x x x 的数在 n u m s nums nums 数组中的下标
最终 f [ i ] [ j ] m a x ( 1 , f [ i ] [ j 1 ] , f [ l a s t [ x j ] ] [ j ] , f [ l a s t [ x − j ] ] [ j ] ) f[i][j] max(1,f[i][j1],f[last[xj]][j],f[last[x-j]][j]) f[i][j]max(1,f[i][j1],f[last[xj]][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][maxD2];int[] last new int[mx 1];Arrays.fill(last, -1);for(int i0; in; i){int x nums[i];for(int jmaxD; j0; j--){f[i][j] Math.max(f[i][j1], 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[xj] 0){f[i][j] Math.max(f[i][j], f[last[xj]][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[mx1][maxD1];for(int x : nums){int fx 1;for(int jmaxD; j0; j--){if(x-j 0){fx Math.max(fx, f[x-j][j] 1);}if(xj mx){fx Math.max(fx, f[xj][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[n2];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(i1, l, m, nums);build(i1|1,m1,r,nums);tree[i] merge(tree[i1],tree[i1|1]);}Info merge(Info a, Info b){return new Info(a.sum b.sum,Math.max(a.pre, a.sumb.pre),Math.max(b.suf, a.sufb.sum),Math.max(Math.max(a.ans, b.ans), a.sufb.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(o1, l, m, i, val);}else{update(o1|1, m1, r, i, val);}tree[o] merge(tree[o1], tree[o1|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;MapInteger, ListInteger map new HashMap();for(int i0; in; i){if(nums[i] 0)map.computeIfAbsent(nums[i], e-new ArrayList()).add(i);}for(ListInteger 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;}
}
