day 38 435.无重叠区间 763.划分字母区间 56. 合并区间 738.单调递增的数字 968.监控二叉树

本文主要是介绍day 38 435.无重叠区间 763.划分字母区间 56. 合并区间 738.单调递增的数字 968.监控二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

435.无重叠区间

思路

为了使区间尽可能的重叠所以排序来使区间尽量的重叠,使用左边界排序来统计重叠区间的个数与452. 用最少数量的箭引爆气球恰好相反。

代码

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));int count = 0;for (int i = 1; i < intervals.length; i++) {if(intervals[i-1][1] > intervals[i][0]){count++;intervals[i][1] = Math.min(intervals[i-1][1],intervals[i][1]);}}return  count;}
}

763.划分字母区间

思路

首先想到了回溯但是使用回溯依然没有思路,在遍历的过程中相当于是要找每一个字母的边界,如果找到之前遍历过的所有字母的最远边界,说明这个边界就是分割点了。此时前面出现过所有字母,最远也就到这个边界了。

可以分为如下两步:

  • 统计每一个字符最后出现的位置
  • 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点

代码

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> list = new LinkedList<>();int [] hash = new int[27];char [] chars = s.toCharArray();for (int i = 0; i < chars.length; i++) {hash[chars[i] - 'a'] = i;}int left = 0,right = 0 ;for (int i = 0; i < chars.length; i++) {right = Math.max(right , hash[chars[i] - 'a']);if(i == right){list.add(right -left +1);left = i+1;}}return list;}
}

56. 合并区间

思路

本题的本质其实还是判断重叠区间问题。452. 用最少数量的箭引爆气球 (opens new window)和 435. 无重叠区间都是判断区间重叠,区别就是判断区间重叠后的逻辑,本题是判断区间重贴后要进行区间合并。

代码

class Solution {public int[][] merge(int[][] intervals) {LinkedList<int[]> res = new LinkedList<>();Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));res.add(intervals[0]);for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] <= res.getLast()[1]) {int start = res.getLast()[0];int end = Math.max(intervals[i][1], res.getLast()[1]);res.removeLast();res.add(new int[]{start, end});}else {res.add(intervals[i]);}}return res.toArray(new int[res.size()][]);}
}

738.单调递增的数字

思路

贪心算法

例如98,一旦出现strNum[i - 1] > strNum[i]的情况(非单调递增),首先想让strNum[i - 1]--,然后strNum[i]给为9,这样这个整数就是89,即小于98的最大的单调递增整数。

此时是从前向后遍历还是从后向前遍历呢?

从前向后遍历的话,遇到strNum[i - 1] > strNum[i]的情况,让strNum[i - 1]减一,但此时如果strNum[i - 1]减一了,可能又小于strNum[i - 2]。

数字:332,从前向后遍历的话,那么就把变成了329,此时2又小于了第一位的3了,真正的结果应该是299。

那么从后向前遍历,就可以重复利用上次比较得出的结果了,从后向前遍历332的数值变化为:332 -> 329 -> 299

class Solution {public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] chars = s.toCharArray();int start = s.length();for (int i = s.length() - 2; i >= 0; i--) {if (chars[i] > chars[i + 1]) {chars[i]--;start = i+1;}}for (int i = start; i < s.length(); i++) {chars[i] = '9';}return Integer.parseInt(String.valueOf(chars));}
}

968.监控二叉树

思路

题目示例中的摄像头都没有放在叶子节点上!这是很重要的一个线索,摄像头可以覆盖上中下三层,如果把摄像头放在叶子节点上,就浪费的一层的覆盖。

所以把摄像头放在叶子节点的父节点位置,才能充分利用摄像头的覆盖面积。

为什么不从头结点开始看起呢,为啥要从叶子节点看呢?

因为头结点放不放摄像头也就省下一个摄像头, 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。(也算是一个贪心)

局部最优:让叶子节点的父节点安摄像头,所用摄像头最少,

整体最优:全部摄像头数量所用最少!

思路就是从低到上,先给叶子节点父节点放个摄像头,然后隔两个节点放一个摄像头,直至到二叉树头结点。

在二叉树中如何从低向高推导呢?

可以使用后序遍历也就是左右中的顺序,这样就可以在回溯的过程中从下到上进行推导了。左孩子的返回值,右孩子的返回值,即left 和 right, 以后推导中间节点的状态

难点

每个节点可能有几种状态:

有如下三种:

  • 该节点无覆盖(无摄像头)
  • 本节点有摄像头
  • 本节点有覆盖(无摄像头)

空节点的状态只能是有覆盖

为了让摄像头数量最少,我们要尽量让叶子节点的父节点安装摄像头,这样才能摄像头的数量最少。

那么空节点不能是无覆盖的状态,这样叶子节点就要放摄像头了,空节点也不能是有摄像头的状态,这样叶子节点的父节点就没有必要放摄像头了,而是可以把摄像头放在叶子节点的爷爷节点上。

主要有如下四类情况:

  • 情况1:左右节点都有覆盖

  • 情况2:左右节点至少有一个无覆盖的情况:中间节点(父节点)应该放摄像头

如果left == 1, right == 0 怎么办?其实这种条件在情况2中已经判断过了,如图:

  • 情况3:左右节点至少有一个有摄像头:左右孩子节点有一个有摄像头了,那么其父节点就应该是2(覆盖的状态)
  • 情况4:头结点没有覆盖

代码

class Solution {int result = 0 ;public int minCameraCover(TreeNode root) {if(traversal(root) == 0){result++;}return result;}/**节点的状态值:0 表示无覆盖1 表示 有摄像头2 表示有覆盖后序遍历,根据左右节点的情况,来判读 自己的状态*/public int traversal(TreeNode root){if(root == null) return 2;int left = traversal(root.left);int right = traversal(root.right);if(left==2 && right==2) return 0;if(left == 0 || right ==0){result++;return 1;}if(left == 1 || right ==1){return 2;}return -1;}
}

这篇关于day 38 435.无重叠区间 763.划分字母区间 56. 合并区间 738.单调递增的数字 968.监控二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/999337

相关文章

使用PyTorch实现手写数字识别功能

《使用PyTorch实现手写数字识别功能》在人工智能的世界里,计算机视觉是最具魅力的领域之一,通过PyTorch这一强大的深度学习框架,我们将在经典的MNIST数据集上,见证一个神经网络从零开始学会识... 目录当计算机学会“看”数字搭建开发环境MNIST数据集解析1. 认识手写数字数据库2. 数据预处理的

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

Python实现合并与拆分多个PDF文档中的指定页

《Python实现合并与拆分多个PDF文档中的指定页》这篇文章主要为大家详细介绍了如何使用Python实现将多个PDF文档中的指定页合并生成新的PDF以及拆分PDF,感兴趣的小伙伴可以参考一下... 安装所需要的库pip install PyPDF2 -i https://pypi.tuna.tsingh

使用Apache POI在Java中实现Excel单元格的合并

《使用ApachePOI在Java中实现Excel单元格的合并》在日常工作中,Excel是一个不可或缺的工具,尤其是在处理大量数据时,本文将介绍如何使用ApachePOI库在Java中实现Excel... 目录工具类介绍工具类代码调用示例依赖配置总结在日常工作中,Excel 是一个不可或缺的工http://

使用Python创建一个能够筛选文件的PDF合并工具

《使用Python创建一个能够筛选文件的PDF合并工具》这篇文章主要为大家详细介绍了如何使用Python创建一个能够筛选文件的PDF合并工具,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录背景主要功能全部代码代码解析1. 初始化 wx.Frame 窗口2. 创建工具栏3. 创建布局和界面控件4

Python自动化办公之合并多个Excel

《Python自动化办公之合并多个Excel》在日常的办公自动化工作中,尤其是处理大量数据时,合并多个Excel表格是一个常见且繁琐的任务,下面小编就来为大家介绍一下如何使用Python轻松实现合... 目录为什么选择 python 自动化目标使用 Python 合并多个 Excel 文件安装所需库示例代码

Linux使用nload监控网络流量的方法

《Linux使用nload监控网络流量的方法》Linux中的nload命令是一个用于实时监控网络流量的工具,它提供了传入和传出流量的可视化表示,帮助用户一目了然地了解网络活动,本文给大家介绍了Linu... 目录简介安装示例用法基础用法指定网络接口限制显示特定流量类型指定刷新率设置流量速率的显示单位监控多个

linux下多个硬盘划分到同一挂载点问题

《linux下多个硬盘划分到同一挂载点问题》在Linux系统中,将多个硬盘划分到同一挂载点需要通过逻辑卷管理(LVM)来实现,首先,需要将物理存储设备(如硬盘分区)创建为物理卷,然后,将这些物理卷组成... 目录linux下多个硬盘划分到同一挂载点需要明确的几个概念硬盘插上默认的是非lvm总结Linux下多

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2

Java数字转换工具类NumberUtil的使用

《Java数字转换工具类NumberUtil的使用》NumberUtil是一个功能强大的Java工具类,用于处理数字的各种操作,包括数值运算、格式化、随机数生成和数值判断,下面就来介绍一下Number... 目录一、NumberUtil类概述二、主要功能介绍1. 数值运算2. 格式化3. 数值判断4. 随机