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

标签：结点 return res 随想录 byteN 第三十七 CameraStatus 摄像头 二叉树

968. 监控二叉树

  已解答 困难  

相关标签

相关企业  

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

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

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

 

示例 1：

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

示例 2：

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

提示：

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

 

---

type CameraStatus int32

 

const ( CameraStatusHas CameraStatus = 1 CameraStatusCover CameraStatus = 2 CameraStatusUnCover CameraStatus = 3 ) // 难点1，确定贪心思路， 因为叶子结点最多，所以选择在叶子结点的父结点按摄像头， // 难点2 确认三个摄像头状态， （有有摄像头， 无摄像头但有被覆盖，无摄像头但未被覆盖） // 难点3。 nil 结点要返回什么状态，为了让叶的父结点有摄像头，所以nil结点 返回 无摄像头但有被覆盖 // 难点4。 状态的转移 // 遗漏点，叶结点如果返回 未覆盖，则结点要加一 func minCameraCover(root *TreeNode) int { var res int var camera func(node*TreeNode) CameraStatus camera = func(node *TreeNode) CameraStatus { if node == nil { return CameraStatusCover } leftStatus := camera(node.Left) rightStatus := camera(node.Right) //左或者右，返回的点是未覆盖 if leftStatus == CameraStatusUnCover || rightStatus == CameraStatusUnCover { res++ return CameraStatusHas } if leftStatus == CameraStatusHas || rightStatus == CameraStatusHas { return CameraStatusCover } return CameraStatusUnCover } rootStatus := camera(root) if rootStatus == CameraStatusUnCover { res++ } return res }

 

---

738. 单调递增的数字

  已解答 中等  

相关标签

相关企业  

提示

 

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

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

 

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

 

提示:

• 0 <= n <= 109

 

---

考虑在 33332 这种例子，这题由后向前遍历 func monotoneIncreasingDigits(n int) int { if n < 10 { return n } strN := fmt.Sprintf("%d", n) byteN := []byte(strN) for i := len(byteN) - 2; i >= 0; i-- { fmt.Println(byteN[i]) if byteN[i] <= byteN[i+1] { continue } byteN[i] = byteN[i] - 1 for j := i + 1; j < len(byteN); j++ { byteN[j] = '9' } } res, _ := strconv.Atoi(string(byteN)) return res }

标签：结点,return,res,随想录,byteN,第三十七,CameraStatus,摄像头,二叉树
From： https://www.cnblogs.com/suxinmian/p/18055803