LeetCode刷题【树状数组、并查集】
目录
- 树状数组
- 307. 区域和检索 - 数组可修改
- 406. 根据身高重建队列
- 673. 最长递增子序列的个数
- 1409. 查询带键的排列
- 并查集
- 128. 最长连续序列
- 130. 被围绕的区域
树状数组
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';
}
}
}
}
};