诊断网站seo现状,建设个人购物网站,宁波高端网站建设,wordpress点评系统目录
讀題
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往後的數全部改為9return 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.监控二叉树 - 實作
思路
定義三個狀態: 有覆蓋、無覆蓋、有攝像頭二叉樹的四種可能性 左右都有覆蓋左右至少有一個無覆蓋左右至少有一個有攝像頭根節點無覆蓋加攝像頭定義一個result紀錄結果定義一個函數遍歷二叉樹 假設遍歷到null需要回傳覆蓋那在葉子節點的父節點才會加上一個攝像頭左右遍歷中節點處理三種可能性主函數 result初始化遍歷節點假設回傳為0 則代表最後一種狀態result回傳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;}
};贪心算法 總結
贪心理论基础
回顧貪心算法真的沒有固定的解法可能有類似的套路比如說重疊區間或者是子序和但整體還是一個思路上的轉換
貪心很簡單只是常識嗎
貪心算法很簡單主要體現在代碼上但難點主要是思路上的轉換說簡單也不簡單
貪心算法有沒有套路
沒有套路!沒有套路!沒有套路
真的是要讓自己的視野打開多寫多練習讓自己的腦袋瘋狂運轉會越來越好的
怎麼辨認出貪心算法
其實任何情況下只要能推導出局部最優在堆疊到全局最優的題目都可以是貪心算法但有些問題當然可以套用其他的解題技巧幫忙貪心算法我認為就像是心法它沒有招式但所以我們只能意會很奇妙的章節。
貪心題目 題目分級來源至代碼隨想錄 贪心简单题
贪心算法分发饼干贪心算法K次取反后最大化的数组和贪心算法柠檬水找零
贪心中等题
贪心算法摆动序列贪心算法单调递增的数字股票系列问题 贪心算法买卖股票的最佳时机II贪心算法买卖股票的最佳时机含手续费两个维度权衡问题 贪心算法分发糖果贪心算法根据身高重建队列
贪心难题
这里的题目如果没有接触过其实是很难想到的甚至接触过也一时想不出来所以题目不要做一遍要多练
贪心解决区间问题 贪心算法跳跃游戏贪心算法跳跃游戏II贪心算法用最少数量的箭引爆气球贪心算法无重叠区间贪心算法划分字母区间贪心算法合并区间其他难题 贪心算法最大子序和贪心算法加油站贪心算法我要监控二叉树 總結
自己实现过程中遇到哪些困难
今天的難點主要在監控二叉樹單調遞增的數字難點主要在代碼監控二叉樹則是需要考慮到多個面向的狀態但其實真的很好玩理解之後寫代碼其實反而就是之前二叉樹章節的基礎主要是思路不好想。
今日收获记录一下自己的学习时长
整體花大概兩個小時貪心算法真的很奇妙但理解之後真的很開心感覺非常好玩。
相關資料
● 今日学习的文章链接和视频链接
第八章 贪心算法 part06
738.单调递增的数字
https://programmercarl.com/0738.单调递增的数字.html
968.监控二叉树
https://programmercarl.com/0968.监控二叉树.html
总结
https://programmercarl.com/贪心算法总结篇.html
