wy的leetcode刷題記錄_Day80

聲明

本文章的所有題目信息都來源于leetcode
如有侵權請聯系我刪掉!
時間：2024-3-2

前言

2368. 受限條件下可到達節點的數目

今天的每日一題是：2368. 受限條件下可到達節點的數目

題目介紹

現有一棵由 n 個節點組成的無向樹，節點編號從 0 到 n - 1 ，共有 n - 1 條邊。

給你一個二維整數數組 edges ，長度為 n - 1 ，其中 edges[i] = [ai, bi] 表示樹中節點 ai 和 bi 之間存在一條邊。另給你一個整數數組 restricted 表示 受限 節點。

在不訪問受限節點的前提下，返回你可以從節點 0 到達的 最多 節點數目。

注意，節點 0 不 會標記為受限節點。

示例 1：

輸入：n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]
輸出：4
解釋：上圖所示正是這棵樹。 在不訪問受限節點的前提下，只有節點 [0,1,2,3] 可以從節點 0 到達。

示例 2：

輸入：n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1]
輸出：3
解釋：上圖所示正是這棵樹。 在不訪問受限節點的前提下，只有節點 [0,5,6] 可以從節點 0 到達。

思路

DFS：按照題目要求進行模擬進行樹上DFS，根據題目提供的節點數目及邊的位置構建鄰接表，然后dfs遍歷整個鄰接表，遍歷到不可抵達的節點時結束dfs。其中有細節就是dfs鄰接表時可能會出現1->2->1這種死循環情況，除了本身樹成環的情況我們只需要在dfs基礎上加一個變量記錄上一次遍歷的節點以此判斷是否進入死循環即可。

代碼

class Solution {
public:int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {vector<vector<int>> LinkList(n);//鄰接表vector<int> is_restricted(n);int ans=0;for(auto x:restricted){is_restricted[x]=1;}LinkList.resize(n);for(auto v:edges){LinkList[v[0]].push_back(v[1]);LinkList[v[1]].push_back(v[0]);}function<void(int,int)> dfs = [&](int x,int f){ans++;for(auto y:LinkList[x]){if(y != f && !is_restricted[y]){dfs(y,x);}}};dfs(0,-1);// int ans=dfs(0);return ans;}
};

收獲

樹上DFS配合鄰接表。

92. 反轉鏈表 II

92. 反轉鏈表 II

題目介紹

給你單鏈表的頭指針 head 和兩個整數 left 和 right ，其中 left <= right 。請你反轉從位置 left 到位置 right 的鏈表節點，返回 反轉后的鏈表 。

示例 1：

輸入：head = [1,2,3,4,5], left = 2, right = 4
輸出：[1,4,3,2,5]

示例 2：

輸入：head = [5], left = 1, right = 1
輸出：[5]

思路

其實就是反轉鏈表的衍生題目，將鏈表中的子鏈表進行反轉，思路很簡單但是做法比較麻煩。首先我們將這個子鏈表找到，將整個鏈表切分為了三部分：首部，反轉部，尾部。將反轉部反轉后重新與首部尾部進行連接即可。細節就是在切分三部分的時候我們需要確定四個節點的位置：反轉部首部節點和其上一個節點，反轉部尾部節點和其下一個節點，記住切分一定得把反轉部完全切出來要置首部的尾節點和尾部的首節點為空，否則調用反轉的時候會導致整個后半部分全部反轉。其次就是left為1可能會導致數組上溢，因此采用啞節點來解決。

代碼

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:void reverserList(ListNode *head){ListNode* pre=nullptr;ListNode* cur=head;while(cur){ListNode* nexxt=cur->next;cur->next=pre;pre=cur;cur=nexxt;}}ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode* dom=new ListNode(0,head);ListNode* leftHeadpre=dom;ListNode* rightTailnext=nullptr;ListNode* leftHead=nullptr;ListNode* rightTail=nullptr;//定點head=dom;for(int i=0;i<left-1;i++){head=head->next;}leftHeadpre=head;for(int i=0;i<right-left+1;i++){head=head->next;}rightTail=head;leftHead=leftHeadpre->next;rightTailnext=rightTail->next;//切斷leftHeadpre->next=nullptr;rightTail->next=nullptr;reverserList(leftHead);//反轉//連接leftHeadpre->next=rightTail;leftHead->next=rightTailnext;return dom->next;}
};

收獲

在鏈表中啞節點真好用！！！！