算法笔记——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<
            } 
            bits%=3;
            //在遇到1之前ret一直是0
            ret=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表记录前缀和数据第一次出现的位置，后面再出现就可以直接求出长度。