当前位置: 首页 > news >正文

贪心算法06(leetcode738,968)

参考资料:

https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html

738. 单调递增的数字

题目描述:

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

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

示例 1:

输入: n = 10
输出: 9

思路分析:

        从后往前遍历,若两两不符合递增,则前一位数值-1,并将start(‘9’开始的下标)设为后一位的index

注意:1. start初始为len,考虑到如“1234”的情况

           2.转为字符数组便于处理

代码实现:

class Solution {public int monotoneIncreasingDigits(int n) {String s=String.valueOf(n);char[] chars=s.toCharArray();int len=chars.length;int start=len;//9开始的下标for(int i=len-2;i>=0;i--){//后往前if(chars[i]>chars[i+1]){chars[i]--;start=i+1;}}for(int i=start;i<len;i++){chars[i]='9';}return Integer.parseInt(String.valueOf(chars));}
}

 968. 监控二叉树

题目描述:

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

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

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

示例 1:

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

思路分析:

1. 后序遍历(左右中):每个叶子结点都要被监视到

2. 贪心:叶子节点的父节点放监控,最大范围的监控。

3. 每个节点的三种状态:(0)无覆盖(1)有覆盖,无放监控(2)放监控 。

4. 四种情况:(1)左右孩子都是“1”,则自己是“0”(2)左右孩子之一是“0”,则自己是“2”(3)剩下的情况(任一孩子是“2”),则自己是“1”         //(4)本应在root的上一个节点放监控,但root没有上一个,该情况在main()函数中处理。

代码实现:

/*** 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;public int minCameraCover(TreeNode root) {res=0;if(f(root)==0) res++;return res;}public int f(TreeNode cur){if(cur==null) return 1;// 0:无覆盖// 1:有覆盖,无监控// 2:有覆盖,有监控// 后序遍历:左右中int l=f(cur.left);//左int r=f(cur.right);//右//中if(l==1 && r==1) return 0;if(l==0 || r==0){res++;return 2;}return 1;}
}

相关文章:

贪心算法06(leetcode738,968)

参考资料&#xff1a; https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html 738. 单调递增的数字 题目描述&#xff1a; 当且仅当每个相邻位数上的数字 x 和 y 满足 x < y 时&#xff0c;我们称这个整数是单调递增的。…...

cve_2022_0543-redis沙盒漏洞复现 vulfocus

1. 原理 该漏洞的存在是因为Debian/Ubuntu中的Lua库是作为动态库提供的。自动填充了一个package变量&#xff0c;该变量又允许访问任意 Lua 功能。 2.复现 我们可以尝试payload&#xff1a; eval local io_l package.loadlib("/usr/lib/x86_64-linux-gnu/liblua5.1.so…...

浅解Reids持久化

Reids持久化 RDB redis的存储方式&#xff1a; rdb文件都是二进制&#xff0c;很小&#xff0c;里面存的是数据 实现方式 redis-cli链接到redis服务端 使用save命令 注&#xff1a;不推荐 因为save命令是直接写到磁盘里面&#xff0c;速度特别慢&#xff0c;一般都是redis…...

Java24:会话管理 过滤器 监听器

一 会话管理 1.cookie 是一种客户端会话技术&#xff0c;cookie由服务端产生&#xff0c;它是服务器存放在浏览器的一小份数据&#xff0c;浏览器 以后每次访问服务器的时候都会将这小份的数据带到服务器去。 //创建cookie对象 Cookie cookie1new Cookie("…...

web前端电影简介标签:深度解析与创意应用

web前端电影简介标签&#xff1a;深度解析与创意应用 在web前端开发中&#xff0c;电影简介标签的设计与实现是一项既具挑战性又充满创意的任务。这些标签不仅需要准确传达电影的核心信息&#xff0c;还要通过精美的设计和交互效果吸引用户的眼球。本文将从四个方面、五个方面…...

Java面向对象-方法的重写、super

Java面向对象-方法的重写、super 一、方法的重写二、super关键字1、super可以省略2、super不可以省略3、super修饰构造器4、继承条件下构造方法的执行过程 一、方法的重写 1、发生在子类和父类中&#xff0c;当子类对父类提供的方法不满意的时候&#xff0c;要对父类的方法进行…...

解锁ChatGPT:从GPT-2实践入手解密ChatGPT

⭐️我叫忆_恒心&#xff0c;一名喜欢书写博客的研究生&#x1f468;‍&#x1f393;。 如果觉得本文能帮到您&#xff0c;麻烦点个赞&#x1f44d;呗&#xff01; 近期会不断在专栏里进行更新讲解博客~~~ 有什么问题的小伙伴 欢迎留言提问欧&#xff0c;喜欢的小伙伴给个三连支…...

20240605解决飞凌的OK3588-C的核心板刷机原厂buildroot不能连接ADB的问题

20240605解决飞凌的OK3588-C的核心板刷机原厂buildroot不能连接ADB的问题 2024/6/5 13:53 rootrootrootroot-ThinkBook-16-G5-IRH:~/repo_RK3588_Buildroot20240508$ ./build.sh --help rootrootrootroot-ThinkBook-16-G5-IRH:~/repo_RK3588_Buildroot20240508$ ./build.sh lun…...

c++手写的bitset

支持stl bitset 类似的api #include <iostream> #include <vector> #include <climits> #include <utility> #include <stdexcept> #include <iterator>using namespace std;const int W 64;class Bitset { private:vector<unsigned …...

【机器学习系列】深入理解集成学习:从Bagging到Boosting

目录 一、集成方法的一般思想 二、集成方法的基本原理 三、构建集成分类器的方法 常见的有装袋&#xff08;Bagging&#xff09;和提升&#xff08;Boosting&#xff09;两种方法 方法1 &#xff1a;装袋&#xff08;Bagging&#xff09; Bagging原理如下图&#xff1a; …...

用FFMPEG对YUV序列进行编辑的笔记

还是单独开一个吧 每次找挺烦的 播放YUV序列 ffmpeg -f rawvideo -pix_fmt yuv420p -s 3840x2160 -i "Wood.yuv" -vf "scale1280x720" -c:v rawvideo -pix_fmt yuv420p -f sdl "Wood"4K序列转720P ffmpeg -f rawvideo -pix_fmt yuv420p -s 38…...

智能投顾:重塑金融理财市场,引领行业新潮流

一、引言 在数字化浪潮的推动下,金融行业正经历着前所未有的变革。其中,智能投顾作为金融科技的重要分支,以其高效、便捷和个性化的服务,逐渐成为金融理财市场的新宠。本文旨在探讨智能投顾如何引领金融理财新潮流,通过丰富的案例及解决方案,展示其独特的魅力和价值。 二…...

iOS18 新变化提前了解,除了AI还有这些变化

iOS 18即将在不久的将来与广大iPhone用户见面&#xff0c;这次更新被普遍认为是苹果历史上最重要的软件更新之一。据多方报道和泄露的消息&#xff0c;iOS 18将带来一系列全新的功能和改进&#xff0c;包括在人工智能领域的重大突破、全新的设计元素以及增强的性能和安全性。现…...

力扣算法题:多数元素 --多语言实现

无意间看到&#xff0c;力扣存算法代码居然还得升级vip。。。好吧&#xff0c;我自己存吧 golang&#xff1a; func majorityElement(nums []int) int {count : 0condidate : 0for _,val : range nums {if count 0 {condidate valcount 1} else if val condidate {count} …...

[Kubernetes] 容器运行时 Container Runtime

文章目录 1.容器运行时(Container Runtime)2.容器运行时接口3.容器运行时层级4.容器运行时比较5.强隔离容器6.K8S为何难以实现真正的多租户 1.容器运行时(Container Runtime) Container Runtime 是运行于 k8s 集群每个节点中&#xff0c;负责容器的整个生命周期。Docker 就目前…...

10进制与二、八、十六进制的转换

x进制转10进制 1、如八进制数123&#xff0c;通过把每一位数字和8的指数级进行相乘 1 * 8^2 2 * 8^1 3 * 8^01 * 64 2 * 8 3 * 164 16 383 2、十六进制1A3 1 * 16^2 A(即10) * 16^1 3 * 16^01 * 256 10 * 16 3 * 1256 160 3419 3、二进制1010 1 * 2^3 0 * 2…...

日常实习-小米计算机视觉算法岗面经

文章目录 流程问题请你写出项目中用到的模型代码&#xff0c;Resnet50&#xff08;1&#xff09;网络退化现象&#xff1a;把网络加深之后&#xff0c;效果反而变差了&#xff08;2&#xff09;过拟合现象&#xff1a;训练集表现很棒&#xff0c;测试集很差 把你做的工作里面的…...

(C++)string模拟实现

string底层是一个是字符数组 为了跟库里的string区别&#xff0c;所以定义一个命名空间将类string包含 一、构造 1.构造函数 注意&#xff1a;将char*传给const char*是范围缩小&#xff0c;因此只能1&#xff1a;1构造一个 strlen遇到nullptr解引用会报错&#xff0c;因此…...

类和对象的学习总结(一)

面向对象和面向过程编程初步认识 C语言是面向过程的&#xff0c;关注过程&#xff08;分析求解问题的步骤&#xff09; 例如&#xff1a;外卖&#xff0c;关注点菜&#xff0c;接单&#xff0c;送单等 C是面向对象的&#xff0c;关注对象&#xff0c;把一件事拆分成不同的对象&…...

力扣22. 括号生成

数字 n 代表生成括号的对数&#xff0c;请你设计一个函数&#xff0c;用于能够生成所有可能的并且有效的括号组合。 示例 1&#xff1a;输入&#xff1a;n 3 输出&#xff1a;["((()))","(()())","(())()","()(())","()()(…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...