2022年2月

给定一个二叉树(具有根结点 root), 一个目标结点 target ,和一个整数值 k 。

返回到目标结点 target 距离为 k 的所有结点的值的列表。 答案可以以 任何顺序 返回。

 

示例 1:

image.png

输入:root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
输出:[7,4,1]
解释:所求结点为与目标结点(值为 5)距离为 2 的结点,值分别为 7,4,以及 1
示例 2:

输入: root = [1], target = 1, k = 3
输出: []
 

提示:

节点数在 [1, 500] 范围内
0 <= Node.val <= 500
Node.val 中所有值 不同
目标结点 target 是树上的结点。
0 <= k <= 1000

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/all-nodes-distance-k-in-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


DFS

返回距离目标target为k的所有结点,显然不是最短路径问题,只能用dfs,我们知道二叉树是特殊的图,因此可以对二叉树的那个结点进行dfs,但最大的问题就是二叉树可以对左孩子和右孩子进行遍历,但是对父节点进行进行遍历很麻烦,所以我们要用一个容器缓存结点的父节点,即map【由题目可知结点的值唯一,因此可以用值作为哈希的键】。
初始化好map之后就可以用dfs算法对target结点开始父节点 左孩子,右孩子进行dfs访问,为了防止重复访问要设置一个visit数组访问过得结点设置访问标志。

/**
 * 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:
    map<int, TreeNode*> parent;
    TreeNode* pre;
    bool visit[501];
    vector<int> res;
    void initParent(TreeNode* node) {
        if(node == NULL){
            return;
        }
        parent[node->val] = pre;
        pre = node;
        initParent(node->left);
        pre = node;
        initParent(node->right);
    }

    void dfs(TreeNode* node, int k){
        if(node == NULL){
            return;
        } else if(visit[node->val]){
            return;
        }
        visit[node->val] = true;
        if(k == 0){
            res.push_back(node->val);
            return;
        } else if(k < 0){
            return;
        }
        // 上
        if(parent[node->val]){
            dfs(parent[node->val], k - 1);
        }
        // 左
        dfs(node->left, k - 1);
        // 右
        dfs(node->right, k - 1);
    }

    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        memset(visit, false, sizeof(visit));
        initParent(root);
        dfs(target, k);
        return res;
    }
};

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

首先找到需要删除的节点;
如果找到了,删除它。
 

示例 1:

输入:root = [5,3,6,2,4,null,7], key = 3
输出:[5,4,6,2,null,null,7]
解释:给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点
示例 3:

输入: root = [], key = 0
输出: []
 

提示:

节点数的范围 [0, 104].
-105 <= Node.val <= 105
节点值唯一
root 是合法的二叉搜索树
-105 <= key <= 105
 

进阶: 要求算法时间复杂度为 O(h),h 为树的高度。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/delete-node-in-a-bst
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

deleteNode负责遍历二叉搜索树,遇到要删除的结点进行删除,若结点为叶子结点且值为要删除的结点则直接返回nullptr,
fuckLeft表示找到当前结点在中序遍历中的上一个结点,fuckRight为找到当前结点在中序遍历中的下一个结点。
若当前结点为要删除结点 优先找fuckRight,没有则找fuckLeft 然后交换节点之后递归删除被替换的结点,被替换的结点仍然要满足删除结点的递归操作即重复上述过程直到叶子结点为止,逻辑比较绕。

/**
 * 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 fuckLeft(TreeNode* node){
        while(node->right){
            node = node->right;
        }
        return node->val;
    }

    int fuckRight(TreeNode* node){
        while(node->left){
            node = node->left;
        }
        return node->val;
    }

    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == nullptr){
            return nullptr;
        }
        if(root->val < key){
            root->right = deleteNode(root->right, key);
        } else if(root->val > key) {
            root->left = deleteNode(root->left, key);
        } else {
            if(root->left == nullptr && root->right == nullptr){
                root = nullptr;
            } else if(root->right != nullptr){
                root->val = fuckRight(root->right);
                root->right = deleteNode(root->right, root->val);
            } else {
                root->val = fuckLeft(root->left);
                root->left = deleteNode(root->left, root->val);
            }
        }
        return root;
    }
};

给你二叉搜索树的根节点 root ,该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下,恢复这棵树 。


示例 1:
image.png

输入:root = [1,3,null,null,2]
输出:[3,1,null,null,2]
解释:3 不能是 1 的左孩子,因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2:
image.png

输入:root = [3,1,4,null,null,2]
输出:[2,1,4,null,null,3]
解释:2 不能在 3 的右子树中,因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
 

提示:

树上节点的数目在范围 [2, 1000] 内
-231 <= Node.val <= 231 - 1
 

进阶:使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/recover-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

显示中序遍历

看到二叉搜索树就应该联想到中序遍历,而对于一个恰好换了两个点值的结点,我们观察两个样例的中序遍历
[3, 2, 1]
[1, 3 ,2 ,4]
可以看到样例的中序遍历的乱序的两个点,第一个点是从左往右数第一个逆序的,而第二个点是从右往左数第一个逆序的,所以我们可以先求得二叉树的中序遍历 然后分别从左和右遍历一次取出逆序的点。

/**
 * 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> inOrders;
    void inOrder(TreeNode* node){
        if(node == nullptr){
            return;
        }
        inOrder(node->left);
        inOrders.push_back(node->val);
        inOrder(node->right);
    }
    void recoverTree(TreeNode* root) {
        inOrder(root);
        int x = 0, y = inOrders.size() - 1;
        // 找左边的
        for(int i = 1; i < inOrders.size(); i++){
            if(inOrders[i] > inOrders[i-1]){
                continue;
            }
            x = inOrders[i - 1];
            break;
        }
        // 找右边的
        for(int i = y - 1; i >= 0; i--){
            if(inOrders[i] < inOrders[i+1]){
                continue;
            }
            y = inOrders[i + 1];
            break;
        }
        shitTree(root, x, y);
    }
    void shitTree(TreeNode* node, int x, int y){
        if(node == nullptr){
            return;
        }
        shitTree(node->left, x, y);
        shitTree(node->right, x, y);
        if(node->val == x || node->val == y) {
            node->val = node->val == x ? y : x;
        }
    }
};

隐式中序遍历

进一步分析我们似乎不用存整个中序遍历,因为实际只需要存当前中序的值与上一次中序的值进行比较,这里有一个点若第一个点没有找到时,找到一个逆序的点时就可以赋值x与y,【但是】如果后续再遇到乱序的话要把y设为当前结点?为什么?观察第一个样例数据的中序遍历
[3, 2, 1]
这种情况是要1与3进行交换。若是2与3进行交换的话得到的是[2, 3, 1] 还是逆序的,也就是说逆序的时候第二个点要找尽可能往右靠的否则无法一次就进行恢复,因为这样子会导致恢复了局部逆序导致总体还不是正序的。究其本质原因是根据题目要求只会存在两个值被替换即存在a, b 使得b>a,b,..,a 而因为恰有两个值被替换也就是说其他值是顺序的即b与a中夹着的值均大于a, 若不大于a则a就不是那个被替换的值。也就是如果b与(b, a)序列中的任何一个交换都会导致a与被交换的值是逆序仍然要继续交换。
直观的理解我们交换值只是在中序遍历中随机抽两个不相同的点进行交换,那么设样例数据[1,2,3,4,5] 设被交换的点为2和4,交换之后为[1, 4, 3, 2, 5] 而因为4大于2,2大于1,所以交换之后4仍然大于1不会逆序但是4却大于3,同理2小于5,4也小于5,因此交换之后2与5无逆序但是2小于3,因此被交换的两值肯定分别对右边逆序和对左边逆序。

/**
 * 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 *pre, *x, *y;
    void inOrder(TreeNode* node){
        if(node == nullptr){
            return;
        }
        inOrder(node->left);
        if(pre != nullptr && node->val < pre->val) {
            if(x == nullptr){
                x = pre;
                y = node;
            } else {
                y = node;
            }
        }
        pre = node;
        inOrder(node->right);
    }
    void recoverTree(TreeNode* root) {
        inOrder(root);
        int tmp = x->val;
        x->val = y->val;
        y->val = tmp;
    }
};

https://www.acwing.com/problem/content/3/
有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。
第 i 种物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

输入格式

第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行两个整数 vi,wi隔开,分别表示第 i 种物品的体积和价值。

输出格式

输出一个整数,表示最大价值。

数据范围

0<N,V≤1000≤1000
0<vi,wi≤1000≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例:

10



DP

注意:这里的状态转移方程为:
dpi = j >= w[i] ? max(dpi-1, dpi] + v[i]) : dpi-1;
与01背包不同的是dpi] + v[i] 这里不是用dpi-1] 为什么?因为这里的物品是可以取多次的,而01背包是只能取1次,所以01背包用的是i-1表示不取当前物品时的最佳状态,而完全背包用的是i因为完全背包是可以取多次的,那么dp[i] 里就包含了之前取了多次物品i的情况下的最优解。

#include <iostream>
#include <cstring>
using namespace std;
int v[1002], w[1002], dp[1002][1002];


int main() {
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> w[i] >> v[i];
    }

    memset(dp, 0, sizeof(dp));

    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++){
            dp[i][j] = j >= w[i] ? max(dp[i-1][j], dp[i][j-w[i]] + v[i]) : dp[i-1][j];
        }
    }
    cout << dp[n][m];
    return 0;
}

滚动数组优化

同理 因为不需要i-1的数据了 所以二层遍历的时候不需要逆序了 可以变成正序了。

#include <iostream>
#include <cstring>
using namespace std;
int v[1002], w[1002], dp[1002];


int main() {
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> w[i] >> v[i];
    }

    memset(dp, 0, sizeof(dp));

    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++){
            dp[j] = j >= w[i] ? max(dp[j], dp[j-w[i]] + v[i]) : dp[j];
        }
    }
    cout << dp[m];
    return 0;
}

Description


Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).


Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.


Input

  • Line 1: Two space-separated integers: N and M
  • Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di


Output

  • Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints


Sample Input


4 6
1 4
2 6
3 12
2 7
Sample Output


23

对于每一个物品有选或者不选
若选择一个物品的结果就是dpi-1] +d[i]也就是说没选这个物品时,且它的重量是刚好能放下当前物品的最大值+当前物品的价值。
若不选择一个物品的结果就是dpi-1 也就是说是不选择此物品时的最大值。

二维DP 会MLE

#include <iostream>
using namespace std;
const int MAXN = 3402, MAXM = 12881;
int n,m, w[MAXN], d[MAXN], dp[MAXN][MAXM];
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> w[i] >> d[i];
    }

    memset(dp, 0, sizeof(dp));

    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++) {
            dp[i][j] = j-w[i] < 0 ? dp[i-1][j] : max(dp[i-1][j], dp[i-1][j-w[i]] + d[i]);
        }
    }

    cout << dp[n][m];
    return 0;
}

滚动数组优化的一维DP

image.png
可以看到dpi 只依赖dpi-1] 与dpi-1 我们可以让原本的0~m的遍历变成m->w[i]的遍历 如果不这样子的话我们正序的遍历的时候会覆盖上面的数据,但是如果我们逆序的话是先算后面的,并不会导致前面的数据被覆盖因此可以达到数据复用的过程,本质原因是dpi依赖之前的数据 如果正序的话之前的会被覆盖。

#include <iostream>
using namespace std;
const int MAXN = 3403, MAXM = 12881;
int n,m, w[MAXN], d[MAXN], dp[MAXM];
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> w[i] >> d[i];
    }

    memset(dp, 0, sizeof(dp));

    for(int i = 1; i <= n; i++){
        for(int j = m; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j-w[i]] + d[i]);
        }
    }

    cout << dp[m] << endl;
    return 0;
}