代码随想录算法训练营Day46 | 139.单词拆分，关于多重背包，你该了解这些！背包问题总结篇！ | Day 17 & 18 复习

作者：我家自动化 | 2024-03-09 10:59:55

踩

139.单词拆分

文章链接 | 题目链接 | 视频链接

C++解法


class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size()+1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++){
            for (int j = 0; j < i; j++){
                string word = s.substr(j, i-j);
                if (wordSet.find(word) != wordSet.end() && dp[j] == true){
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

Python解法


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordSet = set(wordDict)
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in wordSet:
                    dp[i] = True
                    break
        return dp[n]

关于多重背包，你该了解这些！

文章链接

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

多重背包和01背包是非常像的，为什么和01背包像呢？

每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。


void test_multi_pack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    vector<int> nums = {2, 3, 2};
    int bagWeight = 10;
    for (int i = 0; i < nums.size(); i++) {
        while (nums[i] > 1) { // nums[i]保留到1，把其他物品都展开
            weight.push_back(weight[i]);
            value.push_back(value[i]);
            nums[i]--;
        }
    }
 
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
        for (int j = 0; j <= bagWeight; j++) {
            cout << dp[j] << " ";
        }
        cout << endl;
    }
    cout << dp[bagWeight] << endl;
 
}
int main() {
    test_multi_pack();
}

背包问题总结篇！

文章链接

背包五部曲：

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

背包递推公式

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：

问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：

问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：

动态规划：474.一和零

问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

01背包

二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。

一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。

完全背包

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

Day 17 复习

110.平衡二叉树


/**
 * 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:
    bool isBalanced(TreeNode* root) {
        if (root == NULL) return true;
        unordered_map<TreeNode*, int> height_map;
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()){
            TreeNode* curr = st.top();
            st.pop();
            if (curr != NULL){
                st.push(curr);
                st.push(NULL);
                if (curr->left){
                    st.push(curr->left);
                }
                if (curr->right){
                    st.push(curr->right);
                }
            } else {
                TreeNode* node = st.top();
                st.pop();
                int left = 0, right = 0;
                if (height_map.find(node->left) != height_map.end()){
                    left = height_map[node->left];
                }
                if (height_map.find(node->right) != height_map.end()){
                    right = height_map[node->right];
                }
                if (abs(left - right) > 1){
                    return false;
                } else {
                    height_map[node] = 1 + max(left, right);
                }
            }
        }
        return true;
    }
};


class Solution {
public:
    int getHeight(TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
};

257. 二叉树的所有路径


/**
 * 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 traverse(TreeNode* curr, vector<string>& result, string path){
        if (curr == NULL){
            return;
        }
        path = path + to_string(curr->val);
        if (curr->left == NULL && curr->right == NULL){
            result.push_back(path);
            return;
        }
        if (curr->left){
            path = path + "->";
            traverse(curr->left, result, path);
            path.pop_back();
            path.pop_back();
        }
        if (curr->right){
            path = path + "->";
            traverse(curr->right, result, path);
            path.pop_back();
            path.pop_back();
        }
    }
 
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        traverse(root, result, "");
        return result;
    }
};

404.左叶子之和


/**
 * 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:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right == NULL) return 0;
        int left = 0;
        if (root->left && root->left->left == NULL && root->left->right == NULL){
            left = root->left->val;
        }
        return left + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }
};

Day 18 复习

513.找树左下角的值


/**
 * 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:
    int max_depth = INT_MIN;
    int left_most_val = -1;
 
    void traverse(TreeNode* curr, int level){
        if (curr == NULL){
            return;
        }
        if (curr->left == NULL && curr->right == NULL){
            if (level > max_depth){
                left_most_val = curr->val;
                max_depth = level;
                return;
            }
        }
        traverse(curr->left, level+1);
        traverse(curr->right, level+1);
    }
 
    int findBottomLeftValue(TreeNode* root) {
        traverse(root, 0);
        return left_most_val;
    }
};

112. 路径总和


/**
 * 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:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == NULL) return false;
        if (root->left == NULL && root->right == NULL && targetSum == root->val){
            return true;
        }
        targetSum -= root->val;
        return hasPathSum(root->left, targetSum) or hasPathSum(root->right, targetSum);
    }
};

113.路径总和ii


/**
 * 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 traverse(TreeNode* curr, int targetSum, vector<int> path, vector<vector<int>>& result){
        if (curr == NULL){
            return;
        }
        if (curr->left == NULL && curr->right == NULL && targetSum == curr->val){
            path.push_back(curr->val);
            result.push_back(path);
            return;
        }
        targetSum -= curr->val;
        path.push_back(curr->val);
        traverse(curr->left, targetSum, path, result);
        traverse(curr->right, targetSum, path, result);
    }
 
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> result;
        vector<int> path;
        traverse(root, targetSum, path, result);
        return result;
    }
};

106.从中序与后序遍历序列构造二叉树


/**
 * 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:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() < 1 || postorder.size() < 1){
            return NULL;
        }
        return traverse(inorder, postorder);
    }
    
private:
    TreeNode* traverse(vector<int>& inorder, vector<int>& postorder){
        if (postorder.size() == 0){
            return NULL;
        }
 
        int root_val = postorder[postorder.size() - 1];
        TreeNode *root = new TreeNode(root_val);
 
        if (postorder.size() == 1) return root;
 
        int index = 0;
        for (int i = 0; i < inorder.size(); i++){
            if (inorder[i] == root_val){
                index = i;
                break;
            }
        }
 
        vector<int> inorder_left(inorder.begin(), inorder.begin() + index);
        vector<int> inorder_right(inorder.begin() + index + 1, inorder.end());
        vector<int> postorder_left(postorder.begin(), postorder.begin() + inorder_left.size());
        vector<int> postorder_right(postorder.begin() + inorder_left.size(), postorder.end() - 1);
 
        root->left = traverse(inorder_left, postorder_left);
        root->right = traverse(inorder_right, postorder_right);
 
        return root;
    }
};

105.从前序与中序遍历序列构造二叉树


/**
 * 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() < 1) return NULL;
 
        int root_val = preorder[0];
        TreeNode* root = new TreeNode(root_val);
 
        int index = 0;
        for (int i = 0; i < inorder.size(); i++){
            if (inorder[i] == root_val){
                index = i;
                break;
            }
        }
 
        vector<int> inorder_left(inorder.begin(), inorder.begin()+index);
        vector<int> inorder_right(inorder.begin()+index+1, inorder.end());
        vector<int> preorder_left(preorder.begin()+1, preorder.begin()+inorder_left.size() + 1);
        vector<int> preorder_right(preorder.begin()+inorder_left.size()+1, preorder.end());
 
        root->left = buildTree(preorder_left, inorder_left);
        root->right = buildTree(preorder_right, inorder_right);
 
        return root;
    }
};

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/214819