Day37:LeedCode 738.单调递增的数字 968.监控二叉树 蓝桥杯 翻转

本文主要是介绍Day37:LeedCode 738.单调递增的数字 968.监控二叉树 蓝桥杯 翻转,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

738. 单调递增的数字

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

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

示例 1:

输入: n = 10
输出: 9

思路:

假设这个数是98,n[i]>n[i+1],让n[i]--,n[i+1]=9,即98的单调递增数就是89

如果从前往后遍历,n[i+1]不仅受n[i]影响,还受n[i+2]影响,例如332->329 这时 3又比2大了

如果从后往前遍历,332->329->299,重复利用了上一次的结果

总体来说,从后往前遍历,遇见n[i]<n[i+1]的情况,让n[i]-1,让i+1与之后的位置都变为9

class Solution {public int monotoneIncreasingDigits(int n) {String s=String.valueOf(n);char[] chars=s.toCharArray();int index=s.length();//记录开始填9的位置for(int i=chars.length-2;i>=0;i--){if(chars[i]>chars[i+1]){chars[i]--;index=i+1;}}for(int i=index;i<s.length();i++ ){chars[i]='9';}return Integer.parseInt(String.valueOf(chars));}
}

968. 监控二叉树

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

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

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

示例 1:

输入:[0,0,null,0,0]
输出:1
解释:如图所示,一台摄像头足以监控所有节点。

示例 2:

输入:[0,0,null,0,null,0,null,null,0]
输出:2
解释:需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。


提示:

  1. 给定树的节点数的范围是 [1, 1000]
  2. 每个节点的值都是 0。

思路:

把摄像头优先放在叶节点的父节点上

所以我们要从下往上看,局部最优:让叶子节点的父节点安摄像头,所用摄像头最少,整体最优:全部摄像头数量所用最少!

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

可以使用后序遍历也就是左右中的顺序,这样就可以在回溯的过程中从下到上进行推导了。

如何隔两个节点放一个摄像头?

我们分别有三个数字来表示:

  • 0:该节点无覆盖
  • 1:本节点有摄像头
  • 2:本节点有覆盖

遇见空结点怎么办?

 空节点的状态只能是有覆盖,这样就可以在叶子节点的父节点放摄像头了

单层递归逻辑: 

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

左孩子有覆盖,右孩子有覆盖,那么此时中间节点应该就是无覆盖的状态了。

  • 情况2:左右节点至少有一个无覆盖的情况

如果是以下情况,则中间节点(父节点)应该放摄像头:

  • left == 0 && right == 0 左右节点无覆盖
  • left == 1 && right == 0 左节点有摄像头,右节点无覆盖
  • left == 0 && right == 1 左节点有无覆盖,右节点摄像头
  • left == 0 && right == 2 左节点无覆盖,右节点覆盖
  • left == 2 && right == 0 左节点覆盖,右节点无覆盖

这个不难理解,毕竟有一个孩子没有覆盖,父节点就应该放摄像头。

此时摄像头的数量要加一,并且return 1,代表中间节点放摄像头。

  • 情况3:左右节点至少有一个有摄像头

如果是以下情况,其实就是 左右孩子节点有一个有摄像头了,那么其父节点就应该是2(覆盖的状态)

  • left == 1 && right == 2 左节点有摄像头,右节点有覆盖
  • left == 2 && right == 1 左节点有覆盖,右节点有摄像头
  • left == 1 && right == 1 左右节点都有摄像头

情况4:头结点没有覆盖

以上都处理完了,递归结束之后,可能头结点 还有一个无覆盖的情况

这时要给根节点加上摄像头

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int res=0;//摄像头的个数public int minCameraCover(TreeNode root) {if(travel(root)==0)res++;//如果根节点没覆盖,给根节点加摄像头,因为根节点没有父节点return res;}public int travel(TreeNode cur){if(cur==null)return 2;//空结点表示有覆盖int left= travel(cur.left);int right= travel(cur.right);//如果左右都返回覆盖,则当前结点没覆盖if(left==2&&right==2){return 0;}else if(left==0||right==0){//如果左右有任一个没覆盖,则在当前结点加摄像头res++;return 1;} else{//如果左右有任一个有摄像头,则当前结点被覆盖return 2;}}
}

80. 翻转

时间限制:1.000S  空间限制:256MB

题目描述

小蓝用黑白棋的 n 个棋子排成了一行,他在脑海里想象出了一个长度为 n 的 01 串 T,他发现如果把黑棋当做 1,白棋当做 0,这一行棋子也是一个长度为 n 的 01 串 S。 小蓝决定,如果在 S 中发现一个棋子和它两边的棋子都不一样,就可以将其翻转变成另一个颜色。也就是说,如果 S 中存在子串 101 或者 010,就可以选择将其分别变为 111 和 000,这样的操作可以无限重复。 小蓝想知道最少翻转多少次可以把 S 变成和 T 一模一样。

输入描述

输入包含多组数据。 输入的第一行包含一个正整数 D 表示数据组数。 后面 2D 行每行包含一个 01 串,每两行为一组数据,第 2i − 1 行为第 i 组 数据的 Ti,第 2i 行为第 i 组数据的 Si,Si 和 Ti 长度均为 ni。

输出描述

对于每组数据,输出一行包含一个整数,表示答案,如果答案不存在请输出 −1。

输入示例
2
1000111
1010101
01000
11000
输出示例
2
-1
提示信息

对于 20% 的评测用例,1 ≤ ∑D1 ni ≤ 10 ; 对于所有评测用例,保证 1 ≤ ∑D1 ni ≤ 106 ,ni > 0 。

思路:从左往右遍历,遇见不一样的就翻转,注意开头和最后一个是不能翻转的

import java.util.*;
import java.util.stream.Stream;class Main{public static void main(String[] args){Scanner in=new Scanner(System.in);int n=in.nextInt();while(n-->0){String s1=in.next();String s2=in.next();System.out.println(solve(s1,s2));}}public static int solve(String s1,String s2){int count=0;for(int i=0;i<s1.length();i++){if(s1.charAt(i)==s2.charAt(i)){continue;}else{if(i==0||i==s2.length()-1||s2.charAt(i)==s2.charAt(i-1)||s2.charAt(i)==s2.charAt(i+1)){return -1; }count++;}}return count;}}

这篇关于Day37:LeedCode 738.单调递增的数字 968.监控二叉树 蓝桥杯 翻转的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

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

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

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

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

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

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

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

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

通过prometheus监控Tomcat运行状态的操作流程

《通过prometheus监控Tomcat运行状态的操作流程》文章介绍了如何安装和配置Tomcat,并使用Prometheus和TomcatExporter来监控Tomcat的运行状态,文章详细讲解了... 目录Tomcat安装配置以及prometheus监控Tomcat一. 安装并配置tomcat1、安装

C#实现系统信息监控与获取功能

《C#实现系统信息监控与获取功能》在C#开发的众多应用场景中,获取系统信息以及监控用户操作有着广泛的用途,比如在系统性能优化工具中,需要实时读取CPU、GPU资源信息,本文将详细介绍如何使用C#来实现... 目录前言一、C# 监控键盘1. 原理与实现思路2. 代码实现二、读取 CPU、GPU 资源信息1.

使用zabbix进行监控网络设备流量

《使用zabbix进行监控网络设备流量》这篇文章主要为大家详细介绍了如何使用zabbix进行监控网络设备流量,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录安装zabbix配置ENSP环境配置zabbix实行监控交换机测试一台liunx服务器,这里使用的为Ubuntu22.04(

springboot健康检查监控全过程

《springboot健康检查监控全过程》文章介绍了SpringBoot如何使用Actuator和Micrometer进行健康检查和监控,通过配置和自定义健康指示器,开发者可以实时监控应用组件的状态,... 目录1. 引言重要性2. 配置Spring Boot ActuatorSpring Boot Act

Java实现任务管理器性能网络监控数据的方法详解

《Java实现任务管理器性能网络监控数据的方法详解》在现代操作系统中,任务管理器是一个非常重要的工具,用于监控和管理计算机的运行状态,包括CPU使用率、内存占用等,对于开发者和系统管理员来说,了解这些... 目录引言一、背景知识二、准备工作1. Maven依赖2. Gradle依赖三、代码实现四、代码详解五