头像

我是菜鸟


访客:1067

在线 


活动打卡代码 AcWing 119. 杨辉三角 II

const int N = 100;
class Solution {
    int cur[N], tmp[N];
public:
    vector<int> getRow(int n) {
        cur[0] = 1;

        for(int i = 1; i <= n; ++ i){
            cur[i] = 1;
            memcpy(tmp, cur, sizeof cur);
            for(int j = 1; j < i; ++ j){
                cur[j] = tmp[j - 1] + tmp[j];
            }
        }
        vector<int> ans(cur, cur + n + 1);
        return ans;
    }
};



活动打卡代码 LeetCode 118. 杨辉三角

const int N = 100;
class Solution {
    int cur[N], tmp[N];
public:
    vector<vector<int>> generate(int n) {
        if(!n) return {};
        cur[0] = 1;
        vector<vector<int>> ans;
        ans.emplace_back(cur, cur + 1);
        for(int i = 1; i < n; ++ i){
            cur[i] = 1;
            memcpy(tmp, cur, sizeof cur);
            for(int j = 1; j < i; ++ j){
                cur[j] = tmp[j - 1] + tmp[j];
            }
            ans.emplace_back(cur, cur + i + 1);
        }
        return ans;
    }
};



/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
    Node* getNext(Node* root){
        while(root){
            if(root->left) return root->left;
            if(root->right) return root->right;
            root = root->next;
        }
        return NULL;
    }

public:
    Node* connect(Node* root) {
        if(root == NULL) return NULL;
        if(root->left && root->right){
            root->left->next = root->right;
            root->right->next = getNext(root->next);
        }else if(root->left){
            root->left->next = getNext(root->next);
        }else if(root->right){
            root->right->next = getNext(root->next);
        }

        connect(root->right);
        connect(root->left);

        return root;
    }
};



/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return NULL;
        queue<Node*> qu;
        qu.push(root);
        while(qu.size()){
            int s = qu.size();
            for(int i = 0; i < s; ++ i){
                auto t = qu.front();
                qu.pop();
                if(i < s - 1) t->next = qu.front();
                if(t->left) qu.push(t->left);
                if(t->right) qu.push(t->right);
            }
        }
        return root;
    }
};



class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size(), m = t.size();
        s = ' ' + s, t = ' ' + t;
        vector<vector<long>> f(n + 1, vector<long>(m + 1));
        for(int i = 0; i <= n; ++ i) f[i][0] = 1;
        for(int i = 1; i <= n; ++ i)
            for(int j = 1; j <= m; ++ j){
                if(s[i] == t[j]){
                    f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
                }else
                    f[i][j] = f[i - 1][j];
            }

        return f[n][m];
    }
};



题目中没有说先序顺序,但是答案中默认是先序的

/**
 * 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 {
    TreeNode *dfs(TreeNode *root){
        if(root == NULL) return NULL;
        auto left = root->left;
        auto right = root->right;
        root->left = NULL;

        root->right = dfs(left);
        auto p = root;
        while(p->right) p = p->right;
        //cout << p->val << endl;
        p->right = dfs(right);

        return root;
    }

public:
    void flatten(TreeNode* root) {
        root = dfs(root);
    }
};


活动打卡代码 LeetCode 113. 路径总和 II

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    vector<vector<int>> ans;
    vector<int> cur;

    void dfs(TreeNode *root, int sum){
        if(root == NULL) return ;

        if(!root->left && !root->right){
            if(sum == root->val) cur.push_back(root->val), ans.push_back(cur), cur.pop_back();
            return ;
        }

        cur.push_back(root->val);
        dfs(root->left, sum - root->val);
        dfs(root->right, sum - root->val);
        cur.pop_back();
    }

public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        dfs(root, sum);
        return ans;
    }
};


活动打卡代码 LeetCode 112. 路径总和

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == NULL) return false;
        if(!root->left && !root->right && root->val == sum) return true;
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == NULL) return 0;
        if(!root->left && !root->right) return 1;
        if(!root->left)
            return minDepth(root->right) + 1;
        if(!root->right)
            return minDepth(root->left) + 1;
        return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
};


活动打卡代码 LeetCode 110. 平衡二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    bool ans = true;
    int dfs(TreeNode *root){
        if(root == NULL) return 0;
        if(ans == false) return false;
        int left = dfs(root->left);
        int right = dfs(root->right);
        if(abs(left - right) > 1) ans = false;
        return max(left, right) + 1;
    }
public:
    bool isBalanced(TreeNode* root) {
        dfs(root);
        return ans;
    }
};