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

二叉树

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