当前位置: 首页 > 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;["((()))","(()())","(())()","()(())","()()(…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

OpenLayers 可视化之热力图

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

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...