代码随想录算法训练营第三十七天|738.单调递增的数字,968.监控二叉树

本文主要是介绍代码随想录算法训练营第三十七天|738.单调递增的数字,968.监控二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 738.单调递增的数字
    • 思路
    • 代码
  • 968.监控二叉树
    • 思路
    • 代码

738.单调递增的数字

题目链接:704. 二分查找

文档讲解:代码随想录

视频讲解:贪心算法,思路不难想,但代码不好写!LeetCode:738.单调自增的数字

思路

数要尽可能的大,高位开始尽量不变,从低位开始找到不满足递减的第一个位置,当前位置减1,后面的全都变成9即可。

代码

class Solution {
public:int monotoneIncreasingDigits(int n) {string strNum = to_string(n);int idx;for (int i = strNum.size() - 1; i > 0; i--) {if (strNum[i - 1] > strNum[i]) {strNum[i] = '9';strNum[i - 1]--;}}return stoi(strNum);}
};

968.监控二叉树

题目链接:968.监控二叉树

文档讲解:代码随想录

视频讲解:贪心算法,二叉树与贪心的结合,有点难… LeetCode:968.监督二叉树

思路

很容易想到要从叶子结点的父节点开始每隔两个结点放一个摄像头为局部最优,但是怎样表示一个结点的状态(有摄像头,没有摄像头但被摄像头覆盖,没有摄像头也没有被摄像头覆盖)是个难点。

后序遍历递归返回值选择int型,返回012,其中0表示没有摄像头也没有被摄像头覆盖,1表示有摄像头,2表示没有摄像头但被摄像头覆盖。

空结点处理:

  • 如果空结点是未被覆盖状态,这时叶子结点就需要放摄像头,不是局部最优;
  • 如果空结点是有摄像头状态,这时叶子结点被覆盖,叶子结点的父节点不用放置摄像头,而父节点的父节点放置摄像头,这时叶子结点没有被覆盖;
  • 如果空结点是被覆盖状态,则叶子结点不用放置摄像头,叶子结点的父节点放置摄像头即可,是局部最优。

分四种情况:

  • 情况一:左右结点都有覆盖,这时当前结点不用放置摄像头,当前节点的父结点放置摄像头,返回0
  • 情况二:左右结点至少有一个未被覆盖,这时当前结点需要放置摄像头,返回1
  • 情况三:左右结点至少有一个摄像头,且另一个结点被覆盖,这时当前结点不需要放置摄像头,且被左右结点覆盖,返回2
  • 情况四:如果递归完后,根结点没有被覆盖,则根结点也需要放置一个摄像头

代码

class Solution {
public:int minCameraCover(TreeNode *root) {// 情况4if (traversal(root) == 0)// root无覆盖result++;return result;}private:int result = 0;int traversal(TreeNode *node) {// 空结点,该结点有覆盖if (node == NULL)return 2;int left = traversal(node->left);int right = traversal(node->right);// 情况1// 左右结点都有覆盖,则该节点放置摄像头if (left == 2 && right == 2)return 0;// 情况2// 左右结点至少有一个没有覆盖// left == 0 && right == 0 左右节点无覆盖// left == 1 && right == 0 左节点有摄像头,右节点无覆盖// left == 0 && right == 1 左节点有无覆盖,右节点摄像头// left == 0 && right == 2 左节点无覆盖,右节点覆盖// left == 2 && right == 0 左节点覆盖,右节点无覆盖if (left == 0 || right == 0) {result++;return 1;}// 情况3// left == 1 && right == 2 左节点有摄像头,右节点有覆盖// left == 2 && right == 1 左节点有覆盖,右节点有摄像头// left == 1 && right == 1 左右节点都有摄像头// 其他情况前段代码均已覆盖if (left == 1 || right == 1)return 2;return -1;}
};

这篇关于代码随想录算法训练营第三十七天|738.单调递增的数字,968.监控二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

流媒体平台/视频监控/安防视频汇聚EasyCVR播放暂停后视频画面黑屏是什么原因?

视频智能分析/视频监控/安防监控综合管理系统EasyCVR视频汇聚融合平台,是TSINGSEE青犀视频垂直深耕音视频流媒体技术、AI智能技术领域的杰出成果。该平台以其强大的视频处理、汇聚与融合能力,在构建全栈视频监控系统中展现出了独特的优势。视频监控管理系统EasyCVR平台内置了强大的视频解码、转码、压缩等技术,能够处理多种视频流格式,并以多种格式(RTMP、RTSP、HTTP-FLV、WebS

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO