题目链接：课程表你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。方法一：DFSclass Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { vector<int> f(numCourses,0); vector<vector<int>> rel(numCourses,vector<int>{}); for (auto x : prerequisites) { f[x[0]]++; rel[x[1]].push_back(x[0]); } queue<int> q; for (int i = 0;i < numCourses;i++) { if (f[i] == 0) { q.push(i); } } int les = 0; while (q.size()) { les++; int fi = q.front(); q.pop(); for (auto x : rel[fi]) { f[x]--; if (f[x] == 0) { q.push(x); } } } return les == numCourses; } };
题目链接：分割回文串给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。方法一：DFS+逗号分割class Solution { public: vector<vector<string>> ans; vector<string> path; bool is_hw(string s,int start,int end) { while (start < end) { if (s[start++] != s[end--]) return false; } return true; } void dfs(string s,int start,int i) { if (i == s.size()) { ans.push_back(path); return ; } if (i < s.size() - 1) { dfs(s,start,i+1); } if (is_hw(s,start,i)) { path.push_back(s.substr(start,i-start+1)); dfs(s,i+1,i+1); path.pop_back(); } } vector<vector<string>> partition(string s) { dfs(s,0,0); return ans; } };方法二：DFS+遍历class Solution { public: vector<vector<string>> ans; vector<string> path; bool is_hw(string s,int start,int end) { while (start < end) { if (s[start++] != s[end--]) return false; } return true; } void dfs(string s,int i) { if (i == s.size()) { ans.push_back(path); return ; } for (int j = i;j < s.size();j++) { if (!is_hw(s,i,j)) continue; path.push_back(s.substr(i,j-i+1)); dfs(s,j+1); path.pop_back(); } } vector<vector<string>> partition(string s) { dfs(s,0); return ans; } };方法三：DP+DFSclass Solution { public: vector<vector<string>> ans; vector<string> path; vector<vector<bool>> isPal; void buildPal(string s) { isPal.assign(s.size(),vector<bool>(s.size(),false)); for (int i = s.size() - 1;i >= 0;i--) { for (int j = i;j < s.size();j++) { if (s[i] == s[j] && (j-i <= 2 || isPal[i+1][j-1])) { isPal[i][j] = true; } } } } void dfs(string s,int i) { if (i == s.size()) { ans.push_back(path); return ; } for (int j = i;j < s.size();j++) { if (!isPal[i][j]) continue; path.push_back(s.substr(i,j-i+1)); dfs(s,j+1); path.pop_back(); } } vector<vector<string>> partition(string s) { buildPal(s); dfs(s,0); return ans; } };
题目链接：二叉树的右视图给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。方法一：层序遍历/** * 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: vector<int> rightSideView(TreeNode* root) { vector<int> ans; if (root == nullptr) return ans; queue<TreeNode*> q; q.push(root); int num = 0; while (q.size()) { int t = q.size(); //int num; while (t--) { TreeNode* tmp = q.front(); q.pop(); num = tmp->val; if (tmp->left != nullptr) q.push(tmp->left); if (tmp->right != nullptr) q.push(tmp->right); } ans.push_back(num); } return ans; } };方法二：bfs/** * 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: vector<int> rightSideView(TreeNode* root) { vector<int> ans; if (!root) return ans; queue<TreeNode*> q; q.push(root); while (q.size()) { int size = q.size(); ans.push_back(q.front()->val); for (int i = 0;i < size;i++) { TreeNode* node = q.front(); q.pop(); if (node->right) q.push(node->right); if (node->left) q.push(node->left); } } return ans; } };方法三：dfs/** * 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: void dfs(TreeNode* root,int depth,vector<int>& ans) { if (root == nullptr) return ; if (depth == ans.size()) ans.push_back(root->val); dfs(root->right,depth+1,ans); dfs(root->left,depth+1,ans); } vector<int> rightSideView(TreeNode* root) { vector<int> ans; dfs(root,0,ans); return ans; } };