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

第18讲:商品模型织梦网站系统 dedecms 教学课件微商城建设

news 2025/9/17 1:40:34

第18讲:商品模型织梦网站系统 dedecms 教学课件,微商城建设,jquery前端框架教程,网站建设最新技术及发展趋势目录讀題 738.单调递增的数字自己看到题目的第一想法看完代码随想录之后的想法 968.监控二叉树自己看到题目的第一想法看完代码随想录之后的想法 738.单调递增的数字 - 實作思路 Code 968.监控二叉树 - 實作思路 Code 贪心算法總結贪心理论基础貪心…

讀題

738.单调递增的数字

自己看到题目的第一想法

看完代码随想录之后的想法

968.监控二叉树

自己看到题目的第一想法

看完代码随想录之后的想法

738.单调递增的数字 - 實作

思路

Code

968.监控二叉树 - 實作

思路

Code

贪心算法總結

贪心理论基础

貪心很簡單，只是常識嗎

貪心算法有沒有套路

怎麼辨認出貪心算法

貪心題目

贪心简单题

贪心中等题

贪心难题

總結

自己实现过程中遇到哪些困难

今日收获，记录一下自己的学习时长

相關資料

第八章贪心算法 part06

讀題

738.单调递增的数字

自己看到题目的第一想法

我在思考局部最優可能就是由後往前遍歷，倆倆比較假設後大於前，則不用變，前大於後，那就減掉前面的值，遍歷全部的數，但實際要怎麼解，帶馬上沒有想法。

看完代码随想录之后的想法

看完之後發現跟我的想法相同，但更直接一點是把後面的數都變為9，很直接但很符合貪心的想法，基本上這樣做就不用擔心是否為單調遞增，並且取最大的單調遞增數並且透過flag紀錄i在哪裡開始要全部變成9，整體透過兩個不嵌套的迴圈解決這個問題。

另外轉成string也很棒，就是讓我們可以更直覺地去操控數字，因為如果沒有的話可能要花更多的代碼量去處理最後的結果。

968.监控二叉树

自己看到题目的第一想法

在思考是不是貪心算法是找到葉子節點的父節點，並且之後都往跳兩層的父節點，這樣就可以找到全部了，但因為牽涉到二叉樹，並不是那麼了解到底怎麼處理。

看完代码随想录之后的想法

貪心思路，後序遍歷，狀態劃分，四種情況

左右都有覆蓋

左右至少有一個無覆蓋

左右至少有一個有攝像頭

最後遍歷根節點無覆蓋，加攝像頭

看完之後覺得這題我只思考到貪心算法，但是後序遍歷，這個我需要去複習，狀態劃分以及四種情況我沒有思考到，但題目是有趣的，讓我對二叉樹以及貪心算法有個好玩的結合。

738.单调递增的数字 - 實作

思路

n轉為string -> 方便處理數字變化
flag記錄從哪裡開始變為九
假設前一個數大於當前的數，紀錄flag並且將number[i - 1] -- (因為在string當中，--可以直接將數字往下掉一個數，並且可以想像這個數就是要減掉，當前的位數才能為9)
將flag往後的數全部改為9
return stoi(number);

Code

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

968.监控二叉树 - 實作

思路

定義三個狀態: 有覆蓋、無覆蓋、有攝像頭
二叉樹的四種可能性
1. 左右都有覆蓋
2. 左右至少有一個無覆蓋
3. 左右至少有一個有攝像頭
4. 根節點無覆蓋，加攝像頭
定義一個result紀錄結果
定義一個函數遍歷二叉樹
1. 假設遍歷到null，需要回傳覆蓋，那在葉子節點的父節點才會加上一個攝像頭
2. 左右遍歷
3. 中節點處理三種可能性
主函數
1. result初始化
2. 遍歷節點，假設回傳為0 則代表最後一種狀態result++
3. 回傳result.

Code

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int result = 0;int traveral(TreeNode* cur) {if(cur == NULL) return 2; // 假設在葉子節點，需要選擇有覆蓋，那在葉子節點的父節點才會加上一個攝像頭int left = traveral(cur->left);int right = traveral(cur->right);if(left == 2 && right == 2) return 0; //左右都有覆蓋if(left == 0 || right == 0) { //左右至少有一個無覆蓋，則一定要一個攝像頭result++;return 1;}if(left == 1 || right == 1) return 2; // 左右至少有一個攝像頭，則return 2，因為代表該節點有被覆蓋到return -1;}int minCameraCover(TreeNode* root) {result = 0;if(traveral(root) == 0) { //最後一種情況，假設根節點左右節點都有覆蓋，那則要多加一個攝像頭result++;}return result;}
};