当前位置：首页 > ds >正文

代码随想录算法训练营第二十七天(补)

ds 2025/5/7 5:48:03

LeetCode题目:

56. 合并区间
738. 单调递增的数字
968. 监控二叉树
2845. 统计趣味子数组的数目(每日一题4-26)

其他:

今日总结
往期打卡

56. 合并区间

跳转: 56. 合并区间

学习: 代码随想录公开讲解

问题:

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

思路:

按开头排列,看看前一个能不能覆盖当前的开头,能就更新当前区间,不能就记录上一个区间

复杂度:

时间复杂度: $O (n l o g n)$
空间复杂度: $O (n)$

代码:

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals,(a, b)->a[0]-b[0]);List<int[]> list = new ArrayList<>();int n = intervals.length;for(int i=1;i<n;i++){if(intervals[i-1][1]>=intervals[i][0]){intervals[i][0] = intervals[i-1][0];intervals[i][1] = Math.max(intervals[i-1][1],intervals[i][1]);}else{list.add(intervals[i-1]);}}list.add(intervals[n-1]);int[][] ans = new int[list.size()][2];int j=0;for(int[] i:list) ans[j++]=i;return ans;}
}

738. 单调递增的数字

跳转: 738. 单调递增的数字

学习: 代码随想录公开讲解

问题:

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回小于或等于 n 的最大数字，且数字呈 单调递增 。

思路:

贪心,一旦递减,后面剩的-1,前面全部变成9
如果不用字符串的话建议记录完翻转

复杂度:

时间复杂度: $O (l o g n)$
空间复杂度: $O (1)$

代码:

class Solution {public int monotoneIncreasingDigits(int n) {int tmp = 0;int[] nums = {9,99,999,9999,99999,999999,9999999,99999999,999999999};int b = 0;while (n > 0) {tmp *= 10;if (n % 10 < n/10%10) {tmp = nums[b];n /= 10;n--;} else {tmp += n % 10;n /= 10;}b++;}int ans = 0;while(tmp>0){ans*=10;ans+=tmp%10;tmp/=10;}return ans;}
}

968. 监控二叉树

跳转: 968. 监控二叉树

学习: 代码随想录公开讲解

问题:

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

思路:

贪心,能不装就不装
需要分析三种情况,已覆盖监控,安装监控,未覆盖监控
子节点有未覆盖就一定要安监控
否则有监控当前就是已覆盖
剩下的就是子节点都覆盖,自身返回未覆盖等父节点安
最后还要特判一下根节点,未覆盖就安装监控
安装时计数

复杂度:

时间复杂度: $O (n)$
空间复杂度: $O (n)$

代码:

class Solution {int ans = 0;int dfs(TreeNode root){if(root==null) return 2;int a = dfs(root.left);int b = dfs(root.right);if(a==0||b==0){ans++;return 1;}else if(a==1||b==1){return 2;}return 0;}public int minCameraCover(TreeNode root) {if(root.left==null&&root.right==null) return 1;if(dfs(root)==0) ans++;return ans;}
}

2845. 统计趣味子数组的数目(每日一题4-26)

跳转: 2845. 统计趣味子数组的数目

学习: 灵茶山艾府题解

问题:

给你一个下标从 0 开始的整数数组 nums ，以及整数 modulo 和整数 k 。

请你找出并统计数组中趣味子数组的数目。

如果子数组 nums[l…r] 满足下述条件，则称其为趣味子数组：

在范围 [l, r] 内，设 cnt 为满足 nums[i] % modulo == k 的索引 i 的数量。并且 cnt % modulo == k 。
以整数形式表示并返回趣味子数组的数目。

注意：子数组是数组中的一个连续非空的元素序列。

思路:

前缀计数,当前cnt大于等于k,就加上之前余数为(cnt-k)%modulo的个数
需要初始化0处为1,让刚好满足的情况下先记一个

复杂度:

时间复杂度: $O (n)$
空间复杂度: $O (n)$

代码:

class Solution {public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {int n = nums.size();Map<Integer,Integer> map = new HashMap<>();int sum = 0;long ans = 0;map.put(0,1);for(int i=0;i<n;i++){if(nums.get(i)%modulo==k){sum++;}if(sum>=k)ans+=map.getOrDefault((sum-k)%modulo,0);map.merge(sum%modulo,1,Integer::sum);}return ans;}
}