666.路徑和IV

題目鏈接：666.路徑和IV

解法：

參考這篇題解：【LeetCode - 666】路徑和 IV_力扣666路徑總和4-CSDN博客

關鍵點在于：

（1）使用map來存node：key 為整數的前兩位，value 為整數的后一位，即 key 為位置信息，value 為權值，KV是(num / 10, num % 10);

（2）左右子樹的表示：對于某一個節點來說，如果它的深度為depth，位置編號為 pos，那么它的左子節點的深度為depth+1，位置編號為 pos?× 2 - 1，那么key就是 (depth+1) * 10 + pos*2-1。而它的右子節點的pos和key都是左子節點的加1；

（3）如果左子節點和右子節點均不在 map 中，說明一條路徑計算完畢，ans += sum；

（4）如果兩個子節點中有一個不在map中，那么dfs會直接對該子節點return，否則繼續dfs。

邊界條件：左子樹或者右子樹為空。

時間復雜度：O(n)

空間復雜度：O(n)

class Solution {int ans = 0;// 使用unordered_map，插入、刪除和查找的平均時間復雜度為O(1)// 而map是有序的，這三種操作為O(logn)unordered_map<int,int> map;public:int pathSum(vector<int>& nums) {for (int num: nums) {map[num / 10] = num % 10;}dfs(nums[0]/10, 0);return ans;}private:void dfs(int node, int sum) {auto it = map.find(node);if (it == map.end()) {return;}sum += it->second;int depth = node / 10;int pos = node % 10;int left = (depth + 1) * 10 + pos * 2 - 1;int right = left + 1;if (map.find(left)==map.end() && map.find(right)==map.end()) {ans += sum;} else {dfs(left, sum);dfs(right, sum);}}
};

207.課程表

題目鏈接：207.course-schedule

解法：

兩種解法，bfs和dfs。

bfs：需要提前計算所有課的入度和先修課的鄰接表，入度為0的課意味著沒有任何先修課，可以先選。剩下的看題解，這篇題解寫得很好：bfs題解。

代碼的實現參考這篇題解：bfs代碼

dfs：在構造鄰接表時，有的答案是把先修課作為vector的索引或者map的key，也有的把先修課作為vector的元素。這里按前一種，把先修課作為vector的索引，得從先修課開始選，根據先修課再去遍歷以它為前置條件的課程，直到搜索到某門課不是任何課程的先修課，說明從當前課開始dfs的路徑，是有限無環的。

以下題解來自eetcode中文區：dfs代碼

邊界條件：

時間復雜度 O(N+M)： 遍歷一個圖需要訪問所有節點和所有臨邊，N?和 M分別為節點數量和臨邊數量；
空間復雜度 O(N+M)： 為建立鄰接表所需額外空間，adjacency 長度為 N?，并存儲 M條臨邊的數據。

// bfs
class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> adjacency(numCourses);vector<int> indegrees(numCourses, 0);queue<int> que;for (const auto& cp:prerequisites) {adjacency[cp[1]].push_back(cp[0]);indegrees[cp[0]]++;}for (int i=0; i<numCourses; i++) {if (indegrees[i]==0) que.push(i);}while (!que.empty()) {int pre = que.front();que.pop();numCourses--;for (int cur: adjacency[pre]) {indegrees[cur]--;if (indegrees[cur]==0) que.push(cur);}}return numCourses == 0;}
};

// dfs
class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> adjacency(numCourses);vector<int> flags(numCourses, 0);for (const auto& cp:prerequisites) {adjacency[cp[1]].push_back(cp[0]);}for (int i=0; i<numCourses; i++) {if (!dfs(adjacency, flags, i)) return false;}return true;}private:bool dfs(const vector<vector<int>>& adjacency, vector<int>& flags, int i) {if (flags[i] == 1) return false;if (flags[i] == -1) return true;flags[i] = 1;for (int j: adjacency[i]) {if (!dfs(adjacency, flags, j)) return false;}flags[i] = -1;return true;}
};

210. 課程表||

題目鏈接：210.course-schedule-ii

解法：

與207幾乎一樣，代碼改動量很小。如果不先做207，那幾乎是搞不懂的。

dfs改動大一些，result需要翻轉一下，因為先修課是最后才加入列表的。

邊界條件：

時間復雜度：同207

空間復雜度：同207

// bfs
class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> adjacency(numCourses);vector<int> indegrees(numCourses, 0);queue<int> que;vector<int> result;for (const auto& cp:prerequisites) {adjacency[cp[1]].push_back(cp[0]);indegrees[cp[0]]++;}for (int i=0; i<numCourses; i++) {if (indegrees[i]==0) que.push(i);}while (!que.empty()) {int pre = que.front();que.pop();result.push_back(pre);for (int cur: adjacency[pre]) {indegrees[cur]--;if (indegrees[cur]==0) que.push(cur);}}if (result.size()!=numCourses) return {};return result;}
};

// dfs
class Solution {vector<int> result;public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> adjacency(numCourses);vector<int> flags(numCourses, 0);for (const auto& cp:prerequisites) {adjacency[cp[1]].push_back(cp[0]);}for (int i=0; i<numCourses; i++) {if (!dfs(adjacency, flags, i)) return {};}// 要翻轉reverse(result.begin(), result.end());return result;}private:bool dfs(const vector<vector<int>>& adjacency, vector<int>& flags, int i) {if (flags[i] == 1) return false;if (flags[i] == -1) return true;flags[i] = 1;for (int j: adjacency[i]) {if (!dfs(adjacency, flags, j)) return false;}flags[i] = -1;result.push_back(i);return true;}
};