一.LCR 152. 驗(yàn)證二叉搜索樹的后序遍歷序列

題目描述：

給你一個二叉搜索樹的后續(xù)遍歷序列，讓你判斷該序列是否合法。

解題思路：

根據(jù)二叉搜索樹的特性，二叉樹搜索的每一個結(jié)點(diǎn)，大于左子樹，小于右子樹。所以二叉搜索樹的中序遍歷，本身就是一個有序的序列。由此我們看看二叉搜索樹的后續(xù)遍歷，后續(xù)遍歷的順序是，根，右子樹，左子樹。所以我們后續(xù)遍歷的第一個結(jié)點(diǎn)就是根節(jié)點(diǎn)，后面遇到的若干個比根節(jié)點(diǎn)大的結(jié)點(diǎn)就是右子樹結(jié)點(diǎn)，剩下的結(jié)點(diǎn)就都是左子樹結(jié)點(diǎn)。根據(jù)這個規(guī)律就可以輕松的將二叉搜索樹，劃分出來。并且判斷是否合法。然后將左右子樹繼續(xù)遞歸下去。

代碼：

class Solution {
public://二叉搜索樹后續(xù)遍歷特點(diǎn)，左 右 根，天然將數(shù)據(jù)劃分為三部分//最右邊一個是根//中間部分比根大//左邊部分比跟小//同時中間部分和，左邊部分又都是兩部分子樹bool dfs(vector<int>& postorder,int l,int r,int i){//一個節(jié)點(diǎn)的樹滿足二叉搜索是樹if(l>=r)return true;//獲取根的值int root=postorder[i];i--;//獲取右子樹，右子樹結(jié)點(diǎn)值大于根來判斷右子樹while(i>=l&&postorder[i]>=root){i--;}//獲取左子樹，剩下的都是左子樹值int next=i;while(next>=l){//左子樹的值應(yīng)全部小于根，由于此左子樹的依賴上面的右子樹，//如果左子樹沒有提，右子樹也就沒有問題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. 比特位計(jì)數(shù)

題目描述：

給出一個整數(shù)n，給出0~n之間每個整數(shù)的二進(jìn)制中出現(xiàn)1的個數(shù)，結(jié)果返回一個數(shù)組。

思路描述：

沒啥好的思路，打印出來找規(guī)律，規(guī)律如下。

?出來0之外的后面沒2的次方個數(shù)，就是前面所有加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. 只出現(xiàn)一次的數(shù)字 II

題目描述：

給出一個數(shù)組arr，除了一個只出現(xiàn)一次以外，數(shù)組中的數(shù)都出現(xiàn)了三次。求出只出現(xiàn)一次的那個數(shù) x。

解題思路：

（1）哈希表統(tǒng)計(jì)最簡單

（2）位運(yùn)算

位運(yùn)算主要通過計(jì)算32位比特位中，每一位在上述數(shù)組中出現(xiàn)的1次數(shù)，且第i位出現(xiàn)出現(xiàn)1的次數(shù)的可能只有三個，3n，3n+1,0。3n和0代表 x 中第i為不是1，3n+代表x的第i位是1.

這樣我們可以得到只出現(xiàn)一次的數(shù)每一位比特位了。

代碼：

class Solution {
public:int singleNumber(vector<int>& nums) {long ret=0;//遍歷每一個元素的32個比特位//切記不能從低位 往 高位遍歷,從遇到的第一位為1才開始算數(shù)值有效位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. 連續(xù)數(shù)組

題目描述：

給定一個二進(jìn)制數(shù)組 nums , 找到含有相同數(shù)量的 0 和 1 的最長連續(xù)子數(shù)組，并返回該子數(shù)組的長度。

思路描述：

思路轉(zhuǎn)換將數(shù)組中的0換成-1，那么問題就變成找到區(qū)間和為0的最長連續(xù)子數(shù)組，并返回該子數(shù)組的長度。

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

（2）前綴和，本質(zhì)還是dp

（3）前綴和+哈希表

前綴和處理之后的數(shù)組之間是由規(guī)律的：

相同的前綴和之間的數(shù)（x,y]，加一起就是0.hash表記錄前綴和數(shù)據(jù)第一次出現(xiàn)的位置，后面再出現(xiàn)就可以直接求出長度。