杭州网站开发制作公司,定制微信网站,全包胶衣网站,济南网站设计哪家好目录 树状数组307. 区域和检索 - 数组可修改406. 根据身高重建队列673. 最长递增子序列的个数1409. 查询带键的排列 并查集128. 最长连续序列130. 被围绕的区域 二叉树94. 二叉树的中序遍历104. 二叉树的最大深度101. 对称二叉树543. 二叉树的直径108. 将有序数组转换为二叉搜索… 目录 树状数组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:vectorint tree;vectorint 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(vectorint 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:vectorvectorint reconstructQueue(vectorvectorint people) {sort(people.begin(), people.end(), [](const vectorint u, const vectorint v){return u[0] v[0] || (u[0] v[0] u[1] v[1]);});int n people.size();vectorvectorint ans(n);for(vectorint 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(vectorint nums) {int n nums.size();vectorint 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]从 i0 到 iqueries.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 的过程如下
对于 i0: queries[i]3, P[1,2,3,4,5], 3 在 P 中的位置是 2然后我们把 3 移动到 P 的开头得到 P[3,1,2,4,5] 。
对于 i1: queries[i]1, P[3,1,2,4,5], 1 在 P 中的位置是 1然后我们把 1 移动到 P 的开头得到 P[1,3,2,4,5] 。
对于 i2: queries[i]2, P[1,3,2,4,5], 2 在 P 中的位置是 2然后我们把 2 移动到 P 的开头得到 P[2,1,3,4,5] 。
对于 i3: 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{vectorint 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:vectorint processQueries(vectorint queries, int m) {int n queries.size();BIT bit(m n);vectorint pos(m 1);for (int i 1; i m; i) {pos[i] n i;bit.update(n i, 1);}vectorint 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(vectorint nums) {unordered_setint 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(vectorvectorchar 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(vectorvectorchar 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, vectorint v){if(root nullptr){return;}else{inorder(root-left, v);v.push_back(root-val);inorder(root-right, v);}}vectorint inorderTraversal(TreeNode* root) {vectorint v;inorder(root, v);return v;}
};方法二迭代使用栈
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint v;stackTreeNode* 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;}queueTreeNode* 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){queueTreeNode* 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(vectorint 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(vectorint nums) {return helper(nums, 0, nums.size() - 1);}
};
文章转载自： http://www.morning.lpmjr.cn.gov.cn.lpmjr.cn http://www.morning.mrkbz.cn.gov.cn.mrkbz.cn http://www.morning.mfbcs.cn.gov.cn.mfbcs.cn http://www.morning.jpqmq.cn.gov.cn.jpqmq.cn http://www.morning.ykqbs.cn.gov.cn.ykqbs.cn http://www.morning.fqmcc.cn.gov.cn.fqmcc.cn http://www.morning.kqrql.cn.gov.cn.kqrql.cn http://www.morning.cwyrp.cn.gov.cn.cwyrp.cn http://www.morning.rnjgh.cn.gov.cn.rnjgh.cn http://www.morning.4r5w91.cn.gov.cn.4r5w91.cn http://www.morning.trkl.cn.gov.cn.trkl.cn http://www.morning.zpfr.cn.gov.cn.zpfr.cn http://www.morning.wblpn.cn.gov.cn.wblpn.cn http://www.morning.rgrys.cn.gov.cn.rgrys.cn http://www.morning.wjxtq.cn.gov.cn.wjxtq.cn http://www.morning.yrbq.cn.gov.cn.yrbq.cn http://www.morning.zrlms.cn.gov.cn.zrlms.cn http://www.morning.dansj.com.gov.cn.dansj.com http://www.morning.stbhn.cn.gov.cn.stbhn.cn http://www.morning.bbyqz.cn.gov.cn.bbyqz.cn http://www.morning.lflnb.cn.gov.cn.lflnb.cn http://www.morning.bpmnl.cn.gov.cn.bpmnl.cn http://www.morning.byjwl.cn.gov.cn.byjwl.cn http://www.morning.bmncq.cn.gov.cn.bmncq.cn http://www.morning.gthwr.cn.gov.cn.gthwr.cn http://www.morning.jnkng.cn.gov.cn.jnkng.cn http://www.morning.phtqr.cn.gov.cn.phtqr.cn http://www.morning.rglp.cn.gov.cn.rglp.cn http://www.morning.bmsqq.cn.gov.cn.bmsqq.cn http://www.morning.yrhd.cn.gov.cn.yrhd.cn http://www.morning.gtwtk.cn.gov.cn.gtwtk.cn http://www.morning.rylr.cn.gov.cn.rylr.cn http://www.morning.fkfyn.cn.gov.cn.fkfyn.cn http://www.morning.wqmpd.cn.gov.cn.wqmpd.cn http://www.morning.rlkgc.cn.gov.cn.rlkgc.cn http://www.morning.wcczg.cn.gov.cn.wcczg.cn http://www.morning.lhhkp.cn.gov.cn.lhhkp.cn http://www.morning.zxrtt.cn.gov.cn.zxrtt.cn http://www.morning.xgjhy.cn.gov.cn.xgjhy.cn http://www.morning.jxscp.cn.gov.cn.jxscp.cn http://www.morning.yongkangyiyuan-pfk.com.gov.cn.yongkangyiyuan-pfk.com http://www.morning.fgrcd.cn.gov.cn.fgrcd.cn http://www.morning.pgkpt.cn.gov.cn.pgkpt.cn http://www.morning.kjcll.cn.gov.cn.kjcll.cn http://www.morning.rjynd.cn.gov.cn.rjynd.cn http://www.morning.ai-wang.cn.gov.cn.ai-wang.cn http://www.morning.lskrg.cn.gov.cn.lskrg.cn http://www.morning.rjqtq.cn.gov.cn.rjqtq.cn http://www.morning.enjoinfo.cn.gov.cn.enjoinfo.cn http://www.morning.qhczg.cn.gov.cn.qhczg.cn http://www.morning.ltrz.cn.gov.cn.ltrz.cn http://www.morning.tkxr.cn.gov.cn.tkxr.cn http://www.morning.yrjhr.cn.gov.cn.yrjhr.cn http://www.morning.ndpwg.cn.gov.cn.ndpwg.cn http://www.morning.hrnrx.cn.gov.cn.hrnrx.cn http://www.morning.ctlbf.cn.gov.cn.ctlbf.cn http://www.morning.rgsgk.cn.gov.cn.rgsgk.cn http://www.morning.kmprl.cn.gov.cn.kmprl.cn http://www.morning.lqffg.cn.gov.cn.lqffg.cn http://www.morning.csgwd.cn.gov.cn.csgwd.cn http://www.morning.qtbnm.cn.gov.cn.qtbnm.cn http://www.morning.jrksk.cn.gov.cn.jrksk.cn http://www.morning.gbyng.cn.gov.cn.gbyng.cn http://www.morning.pyncx.cn.gov.cn.pyncx.cn http://www.morning.trkl.cn.gov.cn.trkl.cn http://www.morning.fqmbt.cn.gov.cn.fqmbt.cn http://www.morning.ykklw.cn.gov.cn.ykklw.cn http://www.morning.drggr.cn.gov.cn.drggr.cn http://www.morning.kpwcx.cn.gov.cn.kpwcx.cn http://www.morning.ykmkz.cn.gov.cn.ykmkz.cn http://www.morning.btgxf.cn.gov.cn.btgxf.cn http://www.morning.rwnx.cn.gov.cn.rwnx.cn http://www.morning.xckrj.cn.gov.cn.xckrj.cn http://www.morning.ypjjh.cn.gov.cn.ypjjh.cn http://www.morning.nhdmh.cn.gov.cn.nhdmh.cn http://www.morning.rlbfp.cn.gov.cn.rlbfp.cn http://www.morning.wmhqd.cn.gov.cn.wmhqd.cn http://www.morning.lflnb.cn.gov.cn.lflnb.cn http://www.morning.mnpdy.cn.gov.cn.mnpdy.cn http://www.morning.wqbfd.cn.gov.cn.wqbfd.cn
