网站建设教程自学网,丹江口市建设局网站,网站营销推广企业,网络规划设计师教程(第2版)一.LCR 152. 验证二叉搜索树的后序遍历序列
题目描述#xff1a;
给你一个二叉搜索树的后续遍历序列#xff0c;让你判断该序列是否合法。
解题思路#xff1a;
根据二叉搜索树的特性#xff0c;二叉树搜索的每一个结点#xff0c;大于左子树#xff0c;小于右子树。…一.LCR 152. 验证二叉搜索树的后序遍历序列
题目描述
给你一个二叉搜索树的后续遍历序列让你判断该序列是否合法。
解题思路
根据二叉搜索树的特性二叉树搜索的每一个结点大于左子树小于右子树。所以二叉搜索树的中序遍历本身就是一个有序的序列。由此我们看看二叉搜索树的后续遍历后续遍历的顺序是根右子树左子树。所以我们后续遍历的第一个结点就是根节点后面遇到的若干个比根节点大的结点就是右子树结点剩下的结点就都是左子树结点。根据这个规律就可以轻松的将二叉搜索树划分出来。并且判断是否合法。然后将左右子树继续递归下去。
代码
class Solution {
public://二叉搜索树后续遍历特点左 右 根天然将数据划分为三部分//最右边一个是根//中间部分比根大//左边部分比跟小//同时中间部分和左边部分又都是两部分子树bool dfs(vectorint postorder,int l,int r,int i){//一个节点的树满足二叉搜索是树if(lr)return true;//获取根的值int rootpostorder[i];i--;//获取右子树右子树结点值大于根来判断右子树while(ilpostorder[i]root){i--;}//获取左子树剩下的都是左子树值int nexti;while(nextl){//左子树的值应全部小于根由于此左子树的依赖上面的右子树//如果左子树没有提右子树也就没有问题if(postorder[next]root)return false;next--;}return dfs(postorder,l,next,next)dfs(postorder,next1,r-1,r-1);}bool verifyTreeOrder(vectorint postorder) {//左 右 根//小 大 等int rpostorder.size()-1;return dfs(postorder,0,r,r);}
};
二. LCR 003. 比特位计数
题目描述
给出一个整数n给出0~n之间每个整数的二进制中出现1的个数结果返回一个数组。
思路描述
没啥好的思路打印出来找规律规律如下。 出来0之外的后面没2的次方个数就是前面所有加1.
代码
class Solution {
public:vectorint countBits(int n) {vectorintans;ans.push_back(0);//初始化int num 1,m1;while(numn) {for (int i 0; i m num n; i, num) {ans.push_back(ans[i] 1);}m * 2;//每次记得把m*2,m就是2^x}return ans;}
};
三.LCR 004. 只出现一次的数字 II
题目描述
给出一个数组arr除了一个只出现一次以外数组中的数都出现了三次。求出只出现一次的那个数 x。
解题思路
1哈希表统计最简单
2位运算
位运算主要通过计算32位比特位中每一位在上述数组中出现的1次数且第i位出现出现1的次数的可能只有三个3n3n1,0。3n和0代表 x 中第i为不是13n代表x的第i位是1.
这样我们可以得到只出现一次的数每一位比特位了。
代码
class Solution {
public:int singleNumber(vectorint nums) {long ret0;//遍历每一个元素的32个比特位//切记不能从低位 往 高位遍历,从遇到的第一位为1才开始算数值有效位for(int i31;i0;i--){int bits0;for(auto e:nums){if(e(1i))bits;} bits%3;//在遇到1之前ret一直是0retret*2bits;}return ret;}
};四.LCR 011. 连续数组
题目描述
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组并返回该子数组的长度。
思路描述
思路转换将数组中的0换成-1那么问题就变成找到区间和为0的最长连续子数组并返回该子数组的长度。
1dpdp[i][j]代表i~j之间的和。
2前缀和本质还是dp
3前缀和哈希表
前缀和处理之后的数组之间是由规律的
相同的前缀和之间的数x,y]加一起就是0.hash表记录前缀和数据第一次出现的位置后面再出现就可以直接求出长度。
