算法笔记——LCR

一.LCR 152. 验证二叉搜索树的后序遍历序列

题目描述：

给你一个二叉搜索树的后续遍历序列，让你判断该序列是否合法。

解题思路：

根据二叉搜索树的特性，二叉树搜索的每一个结点，大于左子树，小于右子树。所以二叉搜索树的中序遍历，本身就是一个有序的序列。由此我们看看二叉搜索树的后续遍历，后续遍历的顺序是，根，右子树，左子树。所以我们后续遍历的第一个结点就是根节点，后面遇到的若干个比根节点大的结点就是右子树结点，剩下的结点就都是左子树结点。根据这个规律就可以轻松的将二叉搜索树，划分出来。并且判断是否合法。然后将左右子树继续递归下去。

代码：

class Solution {
public://二叉搜索树后续遍历特点，左 右 根，天然将数据划分为三部分//最右边一个是根//中间部分比根大//左边部分比跟小//同时中间部分和，左边部分又都是两部分子树bool dfs(vector<int>& postorder,int l,int r,int i){//一个节点的树满足二叉搜索是树if(l>=r)return true;//获取根的值int root=postorder[i];i--;//获取右子树，右子树结点值大于根来判断右子树while(i>=l&&postorder[i]>=root){i--;}//获取左子树，剩下的都是左子树值int next=i;while(next>=l){//左子树的值应全部小于根，由于此左子树的依赖上面的右子树，//如果左子树没有提，右子树也就没有问题if(postorder[next]>=root)return false;next--;}return dfs(postorder,l,next,next)&&dfs(postorder,next+1,r-1,r-1);}bool verifyTreeOrder(vector<int>& postorder) {//左 右 根//小 大 等int r=postorder.size()-1;return dfs(postorder,0,r,r);}
};

二. LCR 003. 比特位计数

题目描述：

给出一个整数n，给出0~n之间每个整数的二进制中出现1的个数，结果返回一个数组。

思路描述：

没啥好的思路，打印出来找规律，规律如下。

 出来0之外的后面没2的次方个数，就是前面所有加1.

代码：

class Solution {
public:vector<int> countBits(int n) {vector<int>ans;ans.push_back(0);//初始化int num = 1,m=1;while(num<=n) {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的次数的可能只有三个，3n，3n+1,0。3n和0代表 x 中第i为不是1，3n+代表x的第i位是1.

这样我们可以得到只出现一次的数每一位比特位了。

代码：

class Solution {
public:int singleNumber(vector<int>& nums) {long ret=0;//遍历每一个元素的32个比特位//切记不能从低位 往 高位遍历,从遇到的第一位为1才开始算数值有效位for(int i=31;i>=0;i--){int bits=0;for(auto e:nums){if(e&(1<<i))bits++;} bits%=3;//在遇到1之前ret一直是0ret=ret*2+bits;}return ret;}
};

四.LCR 011. 连续数组

题目描述：

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

思路描述：

思路转换将数组中的0换成-1，那么问题就变成找到区间和为0的最长连续子数组，并返回该子数组的长度。

（1）dp：dp[i][j]代表i~j之间的和。

（2）前缀和，本质还是dp

（3）前缀和+哈希表

前缀和处理之后的数组之间是由规律的：

相同的前缀和之间的数（x,y]，加一起就是0.hash表记录前缀和数据第一次出现的位置，后面再出现就可以直接求出长度。