互联网网站建设门户网,绵阳微信网站,东莞城建局电话是多少,图片添加文字在线制作目录 一、3438. 找到字符串中合法的相邻数字二、3439. 重新安排会议得到最多空余时间 I三、3440. 重新安排会议得到最多空余时间 II四、3441. 变成好标题的最少代价 一、3438. 找到字符串中合法的相邻数字
题目链接 本题有两个条件#xff1a;
相邻数字互不相同两个数字的的… 目录 一、3438. 找到字符串中合法的相邻数字二、3439. 重新安排会议得到最多空余时间 I三、3440. 重新安排会议得到最多空余时间 II四、3441. 变成好标题的最少代价 一、3438. 找到字符串中合法的相邻数字
题目链接 本题有两个条件
相邻数字互不相同两个数字的的出现次数等于数字本身
先预处理字符串 s s s 中每个字符的出现次数再从左往右两两枚举返回第一个满足上述条件的相邻数字没有返回空字符串。
代码如下
class Solution {public String findValidPair(String s) {int[] cnt new int[10];for(char c : s.toCharArray()){cnt[c-0];}for(int i1; is.length(); i){int x s.charAt(i) - 0;int y s.charAt(i-1) - 0;if(x y) continue;if(cnt[x] x cnt[y] y)return s.substring(i-1, i1);}return ;}
}二、3439. 重新安排会议得到最多空余时间 I
题目链接 题目求至多平移 k k k 个会议后可以获得的最大空余时间与会议本身的时间无关可以预处理出会议之间的空余时间注不要忘记第一个会议开始前和最后一个会议结束后的空余时间贪心的想平移的会议越多可以获得的空余时间越大此时题目变成了平移 k k k 个会议后可以获得的最大空余时间讨论 k k k 的大小 k 1 k1 k1对于 1 1 1 个会议来说无论它往前移还是往后移它会使得连续的 2 2 2 段空余时间合并. k 2 k2 k2对于 2 2 2 个会议来说无论它们往前移还是往后移它会使得连续的 3 3 3 段空余时间合并.…对于 k k k 个会议来说无论它们往前移还是往后移它会使得连续的 k 1 k1 k1 段空余时间合并.
也就是说它其实是一个滑动窗口题就是维护连续 k 1 k1 k1 段空余时间的最大值。
代码如下
class Solution {public int maxFreeTime(int event, int k, int[] start, int[] end) {int n start.length;int[] t new int[n1];t[0] start[0];t[n] event - end[n-1];for(int i1; in; i){t[i] start[i] - end[i-1];}int ans 0, res 0;for(int l0,r0; rn1; r){res t[r];if(r-l1 k 1){res - t[l];l;}ans Math.max(ans, res);}return ans;}
}三、3440. 重新安排会议得到最多空余时间 II
题目链接
本题与 T2 的区别在于只能移动 1 个会议且会议之间的顺序可以发生改变这将会导致一个新的情况如果会议 i i i 可以移动到会议 i − 1 i-1 i−1 前面的空余时间或者会议 i 1 i1 i1 后面的空余时间中即会议 i i i 的大小 空余时间那么当前的空余时间 会议 i i i 与 会议 i − 1 i-1 i−1 的空余时间 会议 i i i 与 会议 i 1 i1 i1 的空余时间 会议 i i i 本身的时间。否则与 T2 情况相同当前的空余时间 会议 i i i 与 会议 i − 1 i-1 i−1 的空余时间 会议 i i i 与 会议 i 1 i1 i1 的空余时间
接下来就是如何判断会议 i i i 可以移动到后面或前面这里可以使用前后缀分解的做法来预处理 [ 0 , i − 1 ] [0,i-1] [0,i−1] 的最大空余时间和 [ i 1 n − 1 ] [i1n-1] [i1n−1] 的最大空余时间。
代码如下
class Solution {public int maxFreeTime(int event, int[] start, int[] end) {int n start.length;int[] t new int[n1];t[0] start[0];t[n] event - end[n-1];int ans Math.max(t[0], t[n]);int[] pre new int[n1];//前缀最大值pre[0] t[0];for(int i1; in; i){t[i] start[i] - end[i-1];pre[i] Math.max(pre[i-1], t[i]);}int[] suf new int[n1];//后缀最大值suf[n] t[n];for(int in-1; i0; i--){suf[i] Math.max(suf[i1], t[i]);}int res 0;for(int l0,r1; rn1; l,r){int len end[l] - start[l];//判断当前 会议l 能否移动到前面/后面if(l0 pre[l-1] len || l2n1 suf[l2] len)ans Math.max(ans, t[r] t[l] len);else ans Math.max(ans, t[l] t[r]);}return ans;}
}四、3441. 变成好标题的最少代价
题目链接 对于本题来说它返回的好标题需要满足两个条件操作次数最少且字典序最小可以先使用 d f s dfs dfs 计算出得到好标题的最小操作次数定义 d f s ( i , j ) : dfs(i,j): dfs(i,j): 第 i i i 个位置变成 j j j 时 [ i 1 , n − 1 ] [i1,n-1] [i1,n−1] 变成好标题的最小操作次数然后转成 d p dp dp此时可以使用数组记录每个状态的转移来源最后逆推得到操作次数最小的最小的字典序。
代码如下
class Solution {public String minCostGoodCaption(String caption) {int n caption.length();if(n 3) return ;int res Integer.MAX_VALUE;char[] s caption.toCharArray();int[][] f new int[n1][26];int[][] nxt new int[n1][26];int[] minJ new int[n1];for(int in-1; i0; i--){int mn Integer.MAX_VALUE;for(int j0; j26; j){int res1 f[i1][j] Math.abs(s[i] - a - j);int res2 i n - 6 ? f[i3][minJ[i3]] Math.abs(s[i] - a - j) Math.abs(s[i1] - a - j) Math.abs(s[i2] - a - j) : Integer.MAX_VALUE;if(res1 res2 || res1 res2 minJ[i3] j){res1 res2;nxt[i][j] minJ[i3];}else{nxt[i][j] j;}f[i][j] res1;if(res1 mn){mn res1;minJ[i] j;}}}char[] ans new char[n];int i 0, j minJ[0];while(i n){ans[i] (char)(j a);int k nxt[i][j];if(k j){i;}else{ans[i2] ans[i1] ans[i];i 3;j k;}}return new String(ans);}
}
