Leetcode hot 100(day 4)

翻轉二叉樹

做法:遞歸即可,注意判斷為空


class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root==nullptr)return nullptr;TreeNode* node=root->left;root->left=invertTree(root->right);root->right=invertTree(node);return root;}
};

對稱二叉樹

做法一:遞歸。使用兩個不同的指針進入遞歸即可


class Solution {
public:bool check(TreeNode* p,TreeNode* q){if(!p&&!q)return true;if(!p||!q)return false;return p->val==q->val&&check(p->left,q->right)&&check(p->right,q->left);}bool isSymmetric(TreeNode* root) {return check(root->left,root->right);}
};

做法二:迭代。一開始想用deque,但卡在了迭代怎么能讓同一層進行比較,后面看了題解才知道可以直接用queue,只要壓入的時候保證順序即可


class Solution {
public:bool check(TreeNode* u, TreeNode* v) {queue<TreeNode*> q;q.push(u);q.push(v);while(!q.empty()){u=q.front();q.pop();v=q.front();q.pop();if(!u&&!v)continue;if((!u||!v)||(u->val!=v->val))return false;q.push(u->left);q.push(v->right);q.push(u->right);q.push(v->left);}return true;}bool isSymmetric(TreeNode* root) {return check(root->left,root->right);}
};

二叉樹的直徑

做法:一開始想用樹形dp,但發現搞復雜了根本不用。其實最直觀的思想就是,對每個節點依次遍歷,然后求左子樹和右子樹深度,然后進行比較。但我們可以發現,在這一過程中,重復搜索了很多地方。要么記憶化搜索,要么就直接在遞歸中比較即可,這樣就只需要遞歸一次。


class Solution {
public:int ans=0;int depth(TreeNode* root){if(root==nullptr)return 0;int L=depth(root->left);int R=depth(root->right);ans=max(ans,L+R+1);return max(L,R)+1;}int diameterOfBinaryTree(TreeNode* root) {depth(root);return ans-1;}
};

二叉樹的層序遍歷

做法一:迭代,BFS,記錄一下每層的節點個數即可


class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {if(root==nullptr)return {};vector<vector<int>> vec;queue<TreeNode*>q;q.push(root);while(!q.empty()){vector<int> v;int sz=q.size();for(int i=1;i<=sz;i++){auto u=q.front();q.pop();if(u->left!=nullptr)q.push(u->left);if(u->right!=nullptr)q.push(u->right);v.emplace_back(u->val);}vec.emplace_back(v);}        return vec;}
};

做法二:遞歸,這個想法很精妙


class Solution {
private:vector<vector<int>> ret;
public:vector<vector<int>> levelOrder(TreeNode* root) {dfs(root,0);return ret;}void dfs(TreeNode* root,int deep){if(root == nullptr) return;if(deep>=ret.size()) ret.push_back({root->val});else ret[deep].push_back(root->val);dfs(root->left,deep+1);dfs(root->right,deep+1);}
};

將有序數組轉換為二叉搜索樹

做法:每次建立中間節點即可,然后遞歸建立樹


class Solution {
public:TreeNode* build(vector<int>& nums,int left,int right){if(left>right)return nullptr;int mid=(left+right)>>1;TreeNode* root=new TreeNode(nums[mid]);root->left=build(nums,left,mid-1);root->right=build(nums,mid+1,right);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {return build(nums,0,nums.size()-1);}};

驗證二叉搜索樹

做法一:分別dfs兩邊的子樹,如果不滿足條件就返回false


class Solution {
public:bool dfs(TreeNode* root,long long lower,long long upper){if(root==nullptr)return true;if(root->val<=lower||root->val>=upper)return false;return dfs(root->left,lower,root->val)&&dfs(root->right,root->val,upper);}bool isValidBST(TreeNode* root) {return dfs(root,LONG_MIN,LONG_MAX);}
};

做法二:中序遍歷。這里可以遞歸或者不遞歸都可以


class Solution {
public:vector<int> vec;bool flag=true;void dfs(TreeNode* root){if(root==nullptr)return;dfs(root->left);if(vec.size()&&vec.back()>=root->val){flag=false;return;}vec.emplace_back(root->val);dfs(root->right);}bool isValidBST(TreeNode* root) {dfs(root);return flag;}
};

二叉搜索樹中第k小的元素

做法一:非優化。簡單直接的中序遍歷,剛好練一下非遞歸


class Solution {
public:int kthSmallest(TreeNode* root, int k) {int cnt=0;stack<TreeNode*> s;while(root!=nullptr||!s.empty()){if(root!=nullptr){s.push(root);root=root->left;}else{root=s.top();s.pop();cnt++;if(cnt==k)return root->val;root=root->right;}}return -1;}
};

做法二:如果要頻繁訪問第k小的數字,可以通過預處理節點數,有點類似快排找第k個大的


class Solution {
public:unordered_map<TreeNode*,int>nodenum;int countnodenum(TreeNode* node){if(node==nullptr)return 0;nodenum[node]=1+countnodenum(node->left)+countnodenum(node->right);return nodenum[node];}int getnodenum(TreeNode* node){if(node!=nullptr&&nodenum.count(node)){return nodenum[node];}return 0;}int kthSmallest(TreeNode* root, int k) {countnodenum(root);while(root!=nullptr){int left=getnodenum(root->left);if(left<k-1){root=root->right;k-=left+1;}else if(left==k-1)break;else root=root->left;}    return root->val;}
};

二叉樹的右視圖

做法一:迭代,廣度優先遍歷即可


class Solution {
public:vector<int> rightSideView(TreeNode* root) {if(root==nullptr)return {};queue<TreeNode*> q;vector<int> vec;q.push(root);while(!q.empty()){int sz=q.size();for(int i=1;i<sz;i++){TreeNode* cur=q.front();q.pop();if(cur->left)q.push(cur->left);if(cur->right)q.push(cur->right);}TreeNode* cur=q.front();q.pop();if(cur->left!=nullptr)q.push(cur->left);if(cur->right!=nullptr)q.push(cur->right);vec.emplace_back(cur->val);}return vec;}
};

做法二:遞歸,其實就和二叉樹層序遍歷那題一樣


class Solution {
public:void bst(TreeNode* node,vector<int>& ans,int depth){if(!node)return;if(depth>ans.size())ans.push_back(node->val);bst(node->right,ans,depth+1);bst(node->left,ans,depth+1);}vector<int> rightSideView(TreeNode* root) {if(!root)return {};vector<int> ans;bst(root,ans,1);return ans;}
};

二叉樹展開為鏈表

做法一:按照前序遍歷的順序來構造鏈表,所以先進行一次前序遍歷,然后用一個vector存下來所有的節點。然后逐步遍歷設置即可


class Solution {
public:void preorder(TreeNode* root,vector<TreeNode*> &vec){if(root){vec.emplace_back(root);preorder(root->left,vec);preorder(root->right,vec);}}void flatten(TreeNode* root) {vector<TreeNode*> vec;preorder(root,vec);int n=vec.size();for(int i=1;i<n;i++){TreeNode* prev=vec[i-1],*cur=vec[i];prev->left=nullptr;prev->right=cur;}}
};

做法二:空間復雜度O(1),對于一個節點,如果左子節點為空,則不需要操作,如果不為空,那么對于右邊,要找到左子樹最右的節點,把右節點連接上去,然后再把左子樹連到右邊即可。非常巧妙的做法


class Solution {
public:void flatten(TreeNode* root) {TreeNode* cur=root;while(cur!=nullptr){if(cur->left!=nullptr){auto next=cur->left;auto predecessor=next;while(predecessor->right!=nullptr)predecessor=predecessor->right;predecessor->right=cur->right;cur->left=nullptr;cur->right=next;}cur=cur->right;}}
};

從前序與中序遍歷序列構造二叉樹

做法一:遞歸,前序遍歷第一個節點是根節點,中序遍歷則是[左子樹,根節點,右子樹],我們可以先根據前序定位根節點,然后根據中序才能知道哪些在左邊,哪些在右邊。遞歸構建即可


class Solution {
public:unordered_map<int,int> mp;TreeNode* build(vector<int>& preorder,vector<int>& inorder,int pl,int pr,int il,int ir){if(pl>pr)return nullptr;int p_root=pl;int in_root=mp[preorder[p_root]];TreeNode* root=new TreeNode(preorder[p_root]);int sz_l=in_root-il;root->left=build(preorder,inorder,pl+1,pl+sz_l,il,in_root-1);root->right=build(preorder,inorder,pl+sz_l+1,pr,in_root+1,ir);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n=preorder.size();for(int i=0;i<n;i++){mp[inorder[i]]=i;}return build(preorder,inorder,0,n-1,0,n-1);}
};

做法二:迭代 先放養,因為肯定會忘記


路徑總和III

做法一:直接遍歷每個節點,對每個節點dfs看有幾個滿足的路徑


class Solution {
public:int rootsum(TreeNode* root,long long target){if(!root)return 0;int ans=0;if(root->val==target)ans++;ans+=rootsum(root->left,target-root->val);ans+=rootsum(root->right,target-root->val);return ans;}int pathSum(TreeNode* root, long long targetSum) {if(!root)return 0;int ans=rootsum(root,targetSum);ans+=pathSum(root->left,targetSum);ans+=pathSum(root->right,targetSum);return ans;}
};

做法二:可以利用前綴和,用哈希表將對應前綴和和數量對應起來。如果遍歷到某一前綴和,前綴和-target的數量就是目前路徑的總和為target的線路。要記得遍歷前哈希加1,遞歸后面要減去1


class Solution {
public:unordered_map<long long,int> pre;int dfs(TreeNode *root,long long cur,int target){if(!root)return 0;int ans=0;cur+=root->val;if(pre.count(cur-target)){ans=pre[cur-target];//哈希表存儲對應值有幾個}pre[cur]++;ans+=dfs(root->left,cur,target);ans+=dfs(root->right,cur,target);pre[cur]--;//因為遍歷完左右子樹就不存在這個前綴和了return ans;}int pathSum(TreeNode* root, int targetSum) {pre[0]=1;return dfs(root,0,targetSum);}
};

二叉樹的最近公共祖先?想起數鏈剖分了

做法一:哈希表


class Solution {
public:unordered_map<int,TreeNode*>fa;unordered_map<int,bool>vis;void dfs(TreeNode* root){if(root->left){fa[root->left->val]=root;dfs(root->left);}if(root->right){fa[root->right->val]=root;dfs(root->right);}}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {fa[root->val]=nullptr;dfs(root);while(p!=nullptr){vis[p->val]=true;p=fa[p->val];}while(q!=nullptr){if(vis[q->val])return q;q=fa[q->val];}return nullptr;}
};

二叉樹中的最大路徑和

做法:由于不能向上面走,所以不是樹形dp。只需要遞歸即可。對于空節點,那么就是貢獻度為0,遞歸的時候,要比較,該節點加左子樹和右子樹的和是否大于maxum,返回的不是和而是節點值加上max(left,right),因為每個節點至多只出現一次


class Solution {
public:int maxSum=INT_MIN;int maxsum(TreeNode* root){if(!root)return 0;int sum=root->val;int leftsum=maxsum(root->left);int rightsum=maxsum(root->right);//maxSum=max(maxSum,leftsum);//maxSum=max(maxSum,rightsum);if(leftsum>0)sum+=leftsum;else leftsum=0;if(rightsum>0)sum+=rightsum;else rightsum=0;maxSum=max(maxSum,sum);return root->val+max(leftsum,rightsum);}int maxPathSum(TreeNode* root) {maxsum(root);return maxSum;}
};

島嶼數量

做法一:深度優先遍歷,搜尋到一個節點,我們可以dfs周邊滿足條件的節點,這樣就能把一整個島嶼全部化為海水。dfs了幾次就代表有幾個島嶼

class Solution {
public:void dfs(vector<vector<char>>& grid,int r,int c){int nr=grid.size();int nc=grid[0].size();grid[r][c]='0';if(r-1>=0&&grid[r-1][c]=='1')dfs(grid,r-1,c);if(r+1<nr&&grid[r+1][c]=='1')dfs(grid,r+1,c);if(c-1>=0&&grid[r][c-1]=='1')dfs(grid,r,c-1);if(c+1<nc&&grid[r][c+1]=='1')dfs(grid,r,c+1);}int numIslands(vector<vector<char>>& grid) {int nr=grid.size();if(!nr)return 0;int nc=grid[0].size();int num=0;for(int r=0;r<nr;r++)for(int c=0;c<nc;c++){if(grid[r][c]=='1'){num++;dfs(grid,r,c);}}return num;}
};

做法二:BFS其實差不多,也是加入pair組成的隊列

做法三:好像能用并查集吧 我不會


腐爛的橘子

做法:BFS

class Solution {
public:int cnt;int dis[10][10];int dir_x[4]={0,1,0,-1};int dir_y[4]={1,0,-1,0};int orangesRotting(vector<vector<int>>& grid) {queue<pair<int,int>>q;cnt=0;int n=grid.size();int m=grid[0].size();for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(grid[i][j]==2){q.push({i,j});//dis[i][j]=0;}else if(grid[i][j]==1){cnt++;}}if(q.empty()&&cnt)return -1;int ans=0;while(!q.empty()){int t=q.size();for(int k=0;k<t;k++){pair<int,int> p=q.front();q.pop();for(int i=0;i<4;i++){int x=p.first+dir_x[i];int y=p.second+dir_y[i];if(x>=0&&x<n&&y>=0&&y<m&&grid[x][y]==1){grid[x][y]=2;q.push({x,y});cnt--;}}}if(!q.empty())ans++;}if(cnt)return -1;return ans;}
};

課程表

做法一:拓撲排序

class Solution {
public:int du[2010];unordered_map<int,vector<int>>mp;bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {for(auto cur:prerequisites){du[cur[1]]++;mp[cur[0]].push_back(cur[1]);}queue<int> q;for(int i=0;i<numCourses;i++){if(du[i]==0)q.push(i);}while(!q.empty()){int u=q.front();q.pop();numCourses--;for(auto num:mp[u]){du[num]--;if(du[num]==0)q.push(num);}}if(numCourses==0)return true;return false;}
};

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/pingmian/75426.shtml
繁體地址,請注明出處:http://hk.pswp.cn/pingmian/75426.shtml
英文地址,請注明出處:http://en.pswp.cn/pingmian/75426.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

C,C++語言緩沖區溢出的產生和預防

緩沖區溢出的定義 緩沖區是內存中用于存儲數據的一塊連續區域&#xff0c;在 C 和 C 里&#xff0c;常使用數組、指針等方式來操作緩沖區。而緩沖區溢出指的是當程序向緩沖區寫入的數據量超出了該緩沖區本身能夠容納的最大數據量時&#xff0c;額外的數據就會覆蓋相鄰的內存區…

大數據(4)Hive數倉三大核心特性解剖:面向主題性、集成性、非易失性如何重塑企業數據價值?

目錄 背景&#xff1a;企業數據治理的困境與破局一、Hive數據倉庫核心特性深度解析1. ?面向主題性&#xff08;Subject-Oriented&#xff09;&#xff1a;從業務視角重構數據?2. ?集成性&#xff08;Integrated&#xff09;&#xff1a;打破數據孤島的統一視圖?3. ?非易失…

A股復權計算_前復權數據計算_終結章

目錄 前置&#xff1a; 計算方法推導 數據&#xff1a; 代碼&#xff1a; 視頻&#xff1a; 前置&#xff1a; 1 本系列將以 “A股復權計算_” 開頭放置在“隨想”專欄 2 權息數據結合 “PostgreSQL_” 系列博文中的股票未復權數據&#xff0c;可以自行計算復權日數據 …

Nature:新發現!首次闡明大腦推理神經過程

人類具有快速適應不斷變化的環境的認知能力。這種能力的核心是形成高級、抽象表示的能力&#xff0c;這些表示利用世界上的規律來支持泛化。然而&#xff0c;關于這些表征如何在神經元群中編碼&#xff0c;它們如何通過學習出現以及它們與行為的關系&#xff0c;人們知之甚少。…

Kotlin 集合函數:map 和 first 的使用場景

Kotlin 提供了豐富的集合操作函數&#xff0c;使開發者可以更加簡潔、高效地處理數據。其中&#xff0c;map 和 first 是兩個常用的函數&#xff0c;分別用于轉換集合和獲取集合中的第一個元素。 1. map 的使用場景 場景 1&#xff1a;對象列表轉換 在開發中&#xff0c;我們…

EIR管理中IMEI和IMSI信息的作用

在EIR&#xff08;設備身份注冊&#xff09;管理中&#xff0c;IMEI&#xff08;國際移動設備身份碼&#xff09;和IMSI&#xff08;國際移動用戶識別碼&#xff09;各自具有重要作用&#xff0c;以下是詳細介紹&#xff1a; IMEI的作用 設備身份識別&#xff1a;IMEI是移動設…

MAUI開發第一個app的需求解析:登錄+版本更新,用于喂給AI

vscode中MAUI框架已經搭好,用MAUI+c#webapi+orcl數據庫開發一個app, 功能是兩個界面一個登錄界面,登錄注冊常用功能,另一個主窗體,功能先空著,顯示“主要功能窗體”。 這是一個全新的功能,需要重零開始涉及所有數據表 登錄后檢查是否有新版本程序,自動更新功能。 1.用戶…

KUKA機器人查看運行日志的方法

對于KUKA機器人的運行日志都是可以查看和導出的&#xff0c;方便查找問題。KUKA機器人的運行日志查看方法如下&#xff1a; 1、在主菜單下&#xff0c;選擇【診斷】-【運行日志】-【顯示】下打開&#xff1b; 2、顯示出之前的機器人運行日志&#xff1b; 3、也可以通過【過濾器…

Kali Linux 2025.1a:主題煥新與樹莓派支持的深度解析

一、年度主題更新與桌面環境升級 Kali Linux 2025.1a作為2025年的首個版本&#xff0c;延續了每年刷新主題的傳統。本次更新包含全新的啟動菜單、登錄界面及桌面壁紙&#xff0c;涵蓋Kali標準版和Kali Purple版本。用戶可通過安裝kali-community-wallpapers包獲取社區貢獻的額…

【UVM學習筆記】更加靈活的UVM—通信

系列文章目錄 【UVM學習筆記】UVM基礎—一文告訴你UVM的組成部分 【UVM學習筆記】UVM中的“類” 文章目錄 系列文章目錄前言一、TLM是什么&#xff1f;二、put操作2.1、建立PORT和EXPORT的連接2.2 IMP組件 三、get操作四、transport端口五、nonblocking端口六、analysis端口七…

uni-app項目上傳至gitee方法詳細教程

1. 準備工作 1.1 安裝 Git 下載并安裝 Git&#xff1a;前往 Git 官網&#xff0c;根據操作系統下載安裝包。 配置用戶名和郵箱&#xff08;需與 Gitee 賬號一致&#xff09;&#xff1a; git config --global user.name "你的Gitee用戶名" git config --global use…

走向多模態AI之路(三):多模態 AI 的挑戰與未來

目錄 前言一、多模態 AI 真的成熟了嗎&#xff1f;二、多模態 AI 的主要挑戰2.1 計算資源消耗&#xff1a;模型復雜度帶來的成本問題2.2 數據標注困難&#xff1a;跨模態數據集的挑戰2.3 對齊和融合的難點2.4 泛化能力與魯棒性2.5 倫理與隱私問題 三、研究方向與未來發展3.1 輕…

STM32單片機入門學習——第12節: [5-2]對射式紅外傳感器計次旋轉編碼器計次

寫這個文章是用來學習的,記錄一下我的學習過程。希望我能一直堅持下去,我只是一個小白,只是想好好學習,我知道這會很難&#xff0c;但我還是想去做&#xff01; 本文寫于&#xff1a;2025.04.03 STM32開發板學習——第12節: [5-2]對射式紅外傳感器計次&旋轉編碼器計次 前言…

匯編學習之《jcc指令》

JCC&#xff08;Jump on Condition Code&#xff09;指的是條件跳轉指令&#xff0c;c中的就是if-else, while, for 等分支循環條件判斷的邏輯。它包括很多指令集&#xff0c;各自都不太一樣&#xff0c;接下來我盡量將每一個指令的c 源碼和匯編代碼結合起來看&#xff0c;加深…

深度解析算法之滑動窗口

12滑動窗口—將 x 減到 0 的最小操作數 題目傳送門 題目描述&#xff1a; 給你一個整數數組 nums 和一個整數 x 。每一次操作時&#xff0c;你應當移除數組 nums 最左邊或最右邊的元素&#xff0c;然后從 x 中減去該元素的值。請注意&#xff0c;需要 修改 數組以供接下來的操…

[MySQL初階]MySQL表的操作

MySQL表的操作 1. 創建表2. 查看表結構3. 修改表&#xff08;修改表的屬性而非表的數據&#xff09;4. 刪除表 1. 創建表 語法&#xff1a; CREATE TABLE table_name (field1 datatype,field2 datatype,field3 datatype ) character set 字符集 collate 校驗規則 engine 存儲…

sqlalchemy詳細介紹以及使用方法

SQLAlchemy是一個Python的ORM&#xff08;對象關系映射&#xff09;工具&#xff0c;它允許開發者使用Python代碼來操作數據庫而不必直接編寫SQL語句。SQLAlchemy提供了一種抽象層&#xff0c;使開發者可以通過簡單的Python對象來表示數據庫表和記錄&#xff0c;從而實現對數據…

圖解AUTOSAR_SWS_LINDriver

AUTOSAR LIN驅動詳解文檔 基于AUTOSAR標準的本地互聯網絡(LIN)驅動程序技術規范解析 目錄 1. 概述 1.1 AUTOSAR LIN驅動簡介1.2 LIN協議基礎2. LIN驅動架構 2.1 類圖結構2.2 狀態機設計3. LIN幀結構 3.1 基本幀組成3.2 PID結構4. LIN驅動配置 4.1 主要配置參數4.2 配置結構5. L…

《網絡管理》實踐環節03:snmp服務器上對網絡設備和服務器進行初步監控

蘭生幽谷&#xff0c;不為莫服而不芳&#xff1b; 君子行義&#xff0c;不為莫知而止休。 應用拓撲圖 3.0準備工作 所有Linux服務器上&#xff08;服務器和Agent端&#xff09;安裝下列工具 yum -y install net-snmp net-snmp-utils 保證所有的HCL網絡設備和服務器相互間能…

2025年內外網文件交換系統排名分析

在時代&#xff0c;企業的日常運營離不開內外網文件的交換。然而&#xff0c;傳統的文件傳輸方式難以滿足企業對多方面的要求。以下是一些備受關注的內外網文件交換系統及其排名分析。 第一名&#xff1a;陽途內外網文件交換系統 陽途內外網文件交換系統是一款專為解決內外網…