Leetcode - 周赛423

server/2024/11/18 4:27:44/

目录

一,3349. 检测相邻递增子数组 I

二,3350. 检测相邻递增子数组 II

三,3351. 好子序列的元素之和

四,3352. 统计小于 N 的 K 可约简整数


一,3349. 检测相邻递增子数组 I

本题有两种做法:

  1. 先求出递增子数组 f (以 i 结尾的最长子数组长度),然后枚举前一个数组的末尾下标i,判断 f[i] 和 f[i+k] 是否都大于 k
  2. 求数组的两个子数组都是严格递增且相邻,有两种情况,要么它一直递增,那么最长可能满足条件的就是 cnt/2,要么它是相邻的两段递增(这两段数组长度求最小),画个图理解一下:

代码如下:

//方法一
class Solution {public boolean hasIncreasingSubarrays(List<Integer> nums, int k) {int n = nums.size();int[] f = new int[n];f[0] = 1;for(int i=1; i<n; i++){if(nums.get(i) > nums.get(i-1)){f[i] = f[i-1] + 1;}else{f[i] = 1;}}for(int i=k-1; i<n-k; i++){if(f[i]>=k && f[i+k]>=k)return true;}return false;}
}
//方法二
class Solution {public boolean hasIncreasingSubarrays(List<Integer> nums, int k) {int ans = 1, cnt = 0, pre = 0;for(int i=0; i<nums.size(); i++){cnt++;if(i == nums.size()-1 || nums.get(i) >= nums.get(i+1)){ans = Math.max(ans, Math.max(cnt/2, Math.min(cnt, pre)));pre = cnt;cnt = 0;}}return ans >= k;}
}

二,3350. 检测相邻递增子数组 II

本题和T1有一点不同,它是求满足条件的最长子数组的长度,那么就是T1的方法二,直接返回ans就行,当然如果T1是用方法一写的,那么这题肯定会想到二分。

代码如下:

class Solution {public int maxIncreasingSubarrays(List<Integer> nums) {int ans = 1, cnt = 0, pre = 0;for(int i=0; i<nums.size(); i++){cnt++;if(i == nums.size()-1 || nums.get(i) >= nums.get(i+1)){ans = Math.max(ans, Math.max(cnt/2, Math.min(cnt, pre)));pre = cnt;cnt = 0;}}return ans;}
}
//二分写法
class Solution {public int maxIncreasingSubarrays(List<Integer> nums) {int n = nums.size();int[] f = new int[n];f[0] = 1;for(int i=1; i<n; i++){if(nums.get(i) > nums.get(i-1)){f[i] = f[i-1] + 1;}else{f[i] = 1;}}int l = 1, r = n;while(l <= r){int k = (l + r) / 2;if(check(k, nums, f)){l = k + 1;}else{r = k - 1;}}return l - 1;}boolean check(int k, List<Integer> nums, int[] f){int n = nums.size();for(int i=k-1; i<n-k; i++){if(f[i]>=k && f[i+k]>=k)return true;}return false;}
}

三,3351. 好子序列的元素之和

定义 cnt[x]:以 x 结尾的子序列的个数,f[x]:所有以 x 结尾的子序列的和。枚举 nums 数组,对于当前元素 x 来说:

  • cnt[x] = cnt[x] + cnt[x-1] + cnt[x+1] + 1
  • f[x] = f[x] + f[x-1] + f[x+1] + (cnt[x-1] + cnt[x+1] + 1) * x
  • 答案就是 sum(f)

代码如下:

class Solution {public int sumOfGoodSubsequences(int[] nums) {final int MOD = 1_000_000_007;Map<Integer, Integer> f = new HashMap<>();Map<Integer, Integer> cnt = new HashMap<>();for (int x : nums) {long c = cnt.getOrDefault(x - 1, 0) + cnt.getOrDefault(x + 1, 0) + 1;f.put(x, (int)((x * c + f.getOrDefault(x, 0) + f.getOrDefault(x - 1, 0) + f.getOrDefault(x + 1, 0)) % MOD));cnt.put(x, (int)((cnt.getOrDefault(x, 0) + c) % MOD));}long ans = 0;for (int s : f.values()) {ans += s;}return (int) (ans % MOD);}
}

四,3352. 统计小于 N 的 K 可约简整数

定义 f[x]:表示 x 二进制中 1 的个数,f*[x]:将 x 通过 f[x] 不断的迭代,将 x 迭代成 1 需要的操作次数。可以得到:f*[x] = f*[f(x)] + 1

通过上述公式可以算出二进制中有 x 个 1 的数需要操作 f*[x] 次才能转换成 1,本题问的是有多少个整数,可以使用数位DP进行计算,通过枚举每一个二进制位为 0 / 1,计算出总共有多少满足条件的整数,注:题目要求所有整数小于给的二进制数 s。

代码如下:

class Solution {private static final int MOD = 1_000_000_007;public int countKReducibleNumbers(String s, int k) {int n = s.length();int ans = 0;int[] f = new int[n];memo = new int[n][n];for(int[] r : memo) Arrays.fill(r, -1);List<Integer> v = new ArrayList<>();for(int i=1; i<n; i++){f[i] = f[Integer.bitCount(i)] + 1;if(f[i] <= k){ //原本f[1]=0,f[i] < k, 但是这里f[1]=1,相当于所有f[i]+1,所以<=kans = (ans + dfs(0, i, true, s.toCharArray())) % MOD;}}return ans;}int[][] memo;int dfs(int i, int j, boolean islimit, char[] s){if(i == s.length) return !islimit&&j==0?1:0;//1.防止与s全部相同。2.使用了j个1if(!islimit && memo[i][j] != -1) return memo[i][j];int up = islimit ? s[i] - '0' : 1;int res = 0;for(int d=0; d<=Math.min(j, up); d++){res = (res + dfs(i+1, j-d, islimit && d==up, s)) % MOD;}if(!islimit) memo[i][j] = res;return res;}
}

 


http://www.ppmy.cn/server/142812.html

相关文章

蓝桥杯-洛谷刷题-day3(C++)

目录 1.忽略回车的字符串输入 i.getline() ii.逐个字符的识别再输入 2.获取绝对值abs() 3.做题时的误区 4.多个变量的某一个到达判断条件 i.max() 5.[NOIP2016 提高组] 玩具谜题 i.代码 6.逻辑上的圆圈 i.有限个数n的数组 7.数组的定义 i.动态数组 1.忽略回车的字符串输…

3D Gaussian Splatting 代码层理解之Part3

最后,内容到达了高斯泼溅过程中最有趣的阶段:渲染!这一步可以说是最关键的,因为它决定了模型的真实性。然而,它也可能是最简单的。在本系列的Part 1和Part2,文章演示了如何将 Raw 3D椭球 转换为可渲染的格式,但现在我们实际上必须完成这项工作并渲染到一组固定的像素上。…

02-1_MVCC版本链清理

MVCC-版本链清理 文章目录 MVCC-版本链清理简介依赖机制Purge 操作的触发时机版本链清理的详细过程示例操作流程延迟清理配置和监控总结 简介 MySQL 中的 MVCC 机制通过版本链来管理数据的多版本存储&#xff0c;以支持高并发的读写操作。然而&#xff0c;随着事务的进行&…

【Framework系列】UnityEditor调用外部程序详解

需求介绍 之前Framework系列有介绍过导表配置工具&#xff0c;感兴趣的小伙伴可以看一看之前的文章《【Framework系列】Excel转Json&#xff0c;配置表、导表工具介绍》。由于导表工具和Unity是两个工程&#xff0c;导表工具不在Unity工程之内&#xff0c;所以在配置生成完成之…

【原创】java+ssm+mysql商品库存管理系统(进销存)设计与实现

个人主页&#xff1a;程序猿小小杨 个人简介&#xff1a;从事开发多年&#xff0c;Java、Php、Python、前端开发均有涉猎 博客内容&#xff1a;Java项目实战、项目演示、技术分享 文末有作者名片&#xff0c;希望和大家一起共同进步&#xff0c;你只管努力&#xff0c;剩下的交…

电子电气架构 -- 下一代整车电网

我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&#xff1a; 所有人的看法和评价都是暂时的&#xff0c;只有自己的经历是伴随一生的&#xff0c;几乎所有的担忧和畏惧…

GRE做题笔记(零散的个人经验)

locomotive机车By 1813, the Luddite resistance had all but vanished. all but表示“几乎完全”的程度&#xff0c;或者表示排除piston活塞attributed to 归因于how a sportsperson accounted for their own experience of stress 运动员如何解释自己的压力经历 &#xff0c;…

vscode-相关自用插件(倒计时,时间显示,编码对齐,css等编码颜色,简体中文,git提交相关,vue项目)

1.倒计时插件 2.时间显示插件 3.编码对齐格式颜色条 4.css等编码颜色 5.简体中文 6.git提交相关 7.vue项目