LeetCode刷题【树状数组、并查集、二叉树】

树状数组
- 307. 区域和检索 - 数组可修改
- - 406. 根据身高重建队列
  - 673. 最长递增子序列的个数
  - 1409. 查询带键的排列
并查集
- - 128. 最长连续序列
  - 130. 被围绕的区域
二叉树
- - 94. 二叉树的中序遍历
  - 104. 二叉树的最大深度
  - 101. 对称二叉树
  - 543. 二叉树的直径
  - 108. 将有序数组转换为二叉搜索树

树状数组

307. 区域和检索 - 数组可修改

给你一个数组 nums ，请你完成两类查询。

其中一类查询要求 更新 数组 nums 下标对应的值
另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right

实现 NumArray 类：

NumArray(int[] nums) 用整数数组 nums 初始化对象
void update(int index, int val) 将 nums[index] 的值 更新 为 val
int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]）

class NumArray {
private:
    vector<int> tree;
    vector<int> &nums;
    int lowBit(int x){
        return x & -x;
    }
    void add(int index, int val){
        while(index < tree.size()){
            tree[index] += val;
            index += lowBit(index);
        }
    }
    int prefixSum(int index){
        int sum = 0;
        while(index > 0){
            sum += tree[index];
            index -= lowBit(index);
        }
        return sum;
    }

public:
    NumArray(vector<int>& nums) : tree(nums.size() + 1), nums(nums) {
        for(int i = 0; i < nums.size(); i++){
            add(i + 1, nums[i]);
        }
    }
    
    void update(int index, int val) {
        add(index + 1, val - nums[index]);
        nums[index] = val;
    }
    
    int sumRange(int left, int right) {
        return prefixSum(right + 1) - prefixSum(left);
    }
};

406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面正好有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](const vector<int>& u, const vector<int>& v){
            return u[0] < v[0] || (u[0] == v[0] && u[1] > v[1]);
        });
        int n = people.size();
        vector<vector<int>> ans(n);
        for(vector<int>& person : people){
            int spaces = person[1] + 1;
            for(int i = 0; i < n; i++){
                if(ans[i].empty()){
                    spaces--;
                    if(!spaces){
                        ans[i] = person;
                        break;
                    }
                }
            }
        }
        return ans;
    }
};

673. 最长递增子序列的个数

给定一个未排序的整数数组 nums ，返回最长递增子序列的个数。

注意这个数列必须是严格递增的。

示例 1:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1), cnt(n, 1);
        int maxs = 1;
        int count = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    if(dp[i] < dp[j] + 1){
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];
                    }
                    else if(dp[i] == dp[j] + 1){
                        cnt[i] += cnt[j];
                    }
                }
            }
            if(dp[i] > maxs){
                maxs = dp[i];
                count = cnt[i];
            }
            else if(dp[i] == maxs){
                count += cnt[i];
            }
        }
        return count;
    }
};

1409. 查询带键的排列

给定一个正整数数组 queries ，其取值范围在 1 到 m 之间。请你根据以下规则按顺序处理所有 queries[i]（从 i=0 到 i=queries.length-1）：

首先，你有一个排列 P=[1,2,3,...,m]。
对于当前的 i ，找到 queries[i] 在排列 P 中的位置（从 0 开始索引），然后将它移到排列 P 的开头（即下标为 0 处）。注意， queries[i] 的查询结果是 queries[i] 在 P 中移动前的位置。

返回一个数组，包含从给定 queries 中查询到的结果。

示例 1：
输入：queries = [3,1,2,1], m = 5
输出：[2,1,2,1] 
解释：处理 queries 的过程如下：
对于 i=0: queries[i]=3, P=[1,2,3,4,5], 3 在 P 中的位置是 2，然后我们把 3 移动到 P 的开头，得到 P=[3,1,2,4,5] 。
对于 i=1: queries[i]=1, P=[3,1,2,4,5], 1 在 P 中的位置是 1，然后我们把 1 移动到 P 的开头，得到 P=[1,3,2,4,5] 。 
对于 i=2: queries[i]=2, P=[1,3,2,4,5], 2 在 P 中的位置是 2，然后我们把 2 移动到 P 的开头，得到 P=[2,1,3,4,5] 。
对于 i=3: queries[i]=1, P=[2,1,3,4,5], 1 在 P 中的位置是 1，然后我们把 1 移动到 P 的开头，得到 P=[1,2,3,4,5] 。 
因此，包含结果的数组为 [2,1,2,1] 。

struct BIT{
    vector<int> a;
    int n;
    BIT(int _n): n(_n), a(_n + 1){}
    static int lowbit(int x){
        return x & (-x);
    }
    int query(int x){
        int ret = 0;
        while(x){
            ret += a[x];
            x -= lowbit(x);
        }
        return ret;
    }
    void update(int x, int dt){
        while(x <= n){
            a[x] += dt;
            x += lowbit(x);
        }
    }
};

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        int n = queries.size();
        BIT bit(m + n);
        
        vector<int> pos(m + 1);
        for (int i = 1; i <= m; ++i) {
            pos[i] = n + i;
            bit.update(n + i, 1);
        }
        
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            int& cur = pos[queries[i]];
            bit.update(cur, -1);
            ans.push_back(bit.query(cur));
            cur = n - i;
            bit.update(cur, 1);
        }
        return ans;
    }
};

并查集

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

使用哈希表，先找到最小的元素，再遍历，我之前的方法是直接使用sort(nums.begin(), nums.end());

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set;
        for(int num : nums){
            num_set.insert(num);
        }
        int longstStreak = 0;
        for(int num : num_set){
            if(!num_set.count(num - 1)){
                int currentNum = num;
                int currentStreak = 1;
                while(num_set.count(currentNum + 1)){
                    currentNum += 1;
                    currentStreak += 1;
                }
                longstStreak = max(longstStreak, currentStreak);
            }
        }
        return longstStreak;
    }
};

130. 被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
在这里插入图片描述

考虑边界上的‘O’，将其置为‘A’，之后再对矩阵中剩下的‘O’进行操作。

class Solution {
public:
    int n, m;
    void dfs(vector<vector<char>>& board, int x, int y){
        if(x < 0 || x >= n || y < 0 || y>= m || board[x][y] != 'O'){
            return;
        }
        board[x][y] = 'A';
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
    }
    void solve(vector<vector<char>>& board) {
        n = board.size();
        if(n == 0){
            return;
        }
        m = board[0].size();
        for(int i = 0; i < n; i++){
            dfs(board, i, 0);
            dfs(board, i, m - 1);
        } 
        for(int i = 1; i < m - 1; i++){
            dfs(board, 0, i);
            dfs(board, n - 1, i);
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(board[i][j] == 'A'){
                    board[i][j] = 'O';
                }
                else if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }         
    }
};

二叉树

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的中序遍历。
方法一：递归

class Solution {
public:
    void inorder(TreeNode* root, vector<int>& v){
        if(root == nullptr){
            return;
        }
        else{
            inorder(root->left, v);
            v.push_back(root->val);
            inorder(root->right, v);
        }
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        inorder(root, v);
        return v;
    }
};

方法二：迭代（使用栈）

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> stk;
        while(!stk.empty() || root != nullptr){
            while(root != nullptr){
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            v.push_back(root->val);
            root = root->right;
        }
        return v;
    }
};

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

方法一：深度优先搜索

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

方法二：广度优先搜索（队列）

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }
        queue<TreeNode*> q;
        q.push(root);
        int ans = 0;
        while(!q.empty()){
            int s = q.size();
            while(s > 0){
                TreeNode* temp = q.front();
                q.pop();
                if(temp->left){
                    q.push(temp->left);
                }
                if(temp->right){
                    q.push(temp->right);
                }
                s--;
            }
            ans++;
        }
        return ans;
    }
};

101. 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。
在这里插入图片描述

方法一：递归

class Solution {
public:
    bool check(TreeNode* p, TreeNode* q){
        if(p == nullptr && q == nullptr){
            return true;
        }
        if(p == nullptr || q == nullptr){
            return false;
        }
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }
    bool isSymmetric(TreeNode* root) {
        return check(root->left, root->right);
    }
};

方法二：迭代（队列）

class Solution {
public:
    bool check(TreeNode* u, TreeNode* v){
        queue<TreeNode*> q;
        q.push(u);
        q.push(v);
        while(!q.empty()){
            u = q.front();
            q.pop();
            v = q.front();
            q.pop();
            if(u == nullptr && v == nullptr){
                continue;
            }
            if(u == nullptr || v == nullptr || u->val != v->val){
                return false;
            }
            q.push(u->left);
            q.push(v->right);

            q.push(u->right);
            q.push(v->left);
        }
        return true;
    }
    bool isSymmetric(TreeNode* root) {
        return check(root->left, root->right);
    }
};

543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的直径。

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的长度由它们之间边数表示。
在这里插入图片描述

class Solution {
public:
    int ans = 1;
    int depth(TreeNode* root){
        if(root == nullptr){
            return 0;
        }
        int l = depth(root->left);
        int r = depth(root->right);
        ans = max(ans, l + r + 1);
        return max(l, r) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        depth(root);
        return ans - 1;
    }
};

108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。
在这里插入图片描述
直接对数组进行转换

class Solution {
public:
    TreeNode* helper(vector<int> nums, int left, int right){
        if(left > right){
            return nullptr;
        }
        int mid = (left + right) / 2;
        TreeNode* root =new TreeNode(nums[mid]);
        root->left = helper(nums, left, mid - 1);
        root->right = helper(nums, mid + 1, right);
        return root; 
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return  helper(nums, 0, nums.size() - 1);
    }
};