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

树状数组

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