题目链接：课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

方法一：DFS

class 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+DFS

class 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;
    }
};