上海嘉定区网站建设公司,wordpress本地环境搭建,怎样制作做实景的网站,北仑seo排名优化技术前言 整体评价
T4的dp解法没想到#xff0c;走了一条不归路, 这个区间合并解很特殊#xff0c;它是带状态的#xff0c;而且最终的正解也是基于WA的case#xff0c;慢慢理清的。 真心不容易#xff0c;太难了。 T1. 相同分数的最大操作数目 I
思路: 模拟
c…
前言 整体评价
T4的dp解法没想到走了一条不归路, 这个区间合并解很特殊它是带状态的而且最终的正解也是基于WA的case慢慢理清的。 真心不容易太难了。 T1. 相同分数的最大操作数目 I
思路: 模拟
class Solution {public int maxOperations(int[] nums) {int n nums.length;int res 1;for (int i 2; i 1 n; i 2) {if (nums[i] nums[i 1] nums[0] nums[1]) {res;} else {break;}}return res;}}T2. 进行操作使字符串为空
思路: 模拟 感觉有点绕
class Solution {public String lastNonEmptyString(String s) {ListInteger []g new List[26];Arrays.setAll(g, x-new ArrayList());for (int i 0; i s.length(); i) {int p s.charAt(i) - a;g[p].add(i);}int mz 0;for (int i 0; i 26; i) {mz Math.max(g[i].size(), mz);}Listint[] lasts new ArrayList();for (int i 0; i 26; i) {if (g[i].size() mz) {lasts.add(new int[] {i, g[i].get(mz - 1)});}}Collections.sort(lasts, Comparator.comparing(x - x[1]));StringBuilder sb new StringBuilder();for (int[] e: lasts) {sb.append((char)(e[0] a));}return sb.toString();}
}T3. 相同分数的最大操作数目 II
思路: 枚举区间DP
因为要求和相等所以枚举最初的和然后记忆化搜索一下就出来了
class Solution {int dfs(Integer[][] dp, int[] nums, int s, int e, int v) {if (s e) return 0;if (dp[s][e] ! null) return dp[s][e];int res 0;if (nums[s] nums[e] v) {int r dfs(dp, nums, s 1, e - 1, v);res Math.max(res, r 1);}if (nums[s] nums[s 1] v) {int r dfs(dp, nums, s 2, e, v);res Math.max(res, r 1);} if (nums[e - 1] nums[e] v) {int r dfs(dp, nums, s, e - 2, v);res Math.max(res, r 1);}return dp[s][e] res;}public int maxOperations(int[] nums) {int n nums.length;int r1 dfs(new Integer[n][n], nums, 1, n - 2, nums[0] nums[n - 1]);int r2 dfs(new Integer[n][n], nums, 2, n - 1, nums[0] nums[1]);int r3 dfs(new Integer[n][n], nums, 0, n - 3, nums[n - 2] nums[n - 1]);return Math.max(r1, Math.max(r2, r3)) 1;}}T4. 修改数组后最大化数组中的连续元素数目
思路: 区间合并
但是这个区间合并很特别是带状态的
class Solution {static class Segment {int start, end;int lastStart, full;public Segment(int start, int end, int lastStart, int full) {this.start start;this.end end;this.lastStart lastStart;this.full full;}}public int maxSelectedElements(int[] nums) {int n nums.length;Arrays.sort(nums);ListSegment segs new ArrayList();int i 0;while (i n) {int flag 0;int j i 1;while (j n nums[j - 1] 1 nums[j]) {if (nums[j - 1] nums[j]) {flag 1;}j;}segs.add(new Segment(nums[i], nums[j - 1], nums[i], flag));i j;}Segment pre null;int res 0;for (Segment seg: segs) {if (pre null) {pre new Segment(seg.start, seg.end, seg.start, seg.full);} else {if (pre.end 2 seg.start) {if (pre.full 1) {pre new Segment(pre.start, seg.end, seg.start, seg.full);} else {pre new Segment(pre.lastStart 1, seg.end, seg.start, seg.full);}} else {pre new Segment(seg.start, seg.end, seg.start, seg.full);}}res Math.max(res, pre.end - pre.start 1);if (pre.full 1) {res Math.max(res, pre.end - pre.start 2);}}return res;}}写在最后
