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

題目描述：

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

解題思路：

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

代碼：

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

題目描述：

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

思路描述：

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

?出來(lái)0之外的后面沒(méi)2的次方個(gè)數(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

題目描述：

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

解題思路：

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

（2）位運(yùn)算

位運(yùn)算主要通過(guò)計(jì)算32位比特位中，每一位在上述數(shù)組中出現(xiàn)的1次數(shù)，且第i位出現(xiàn)出現(xiàn)1的次數(shù)的可能只有三個(gè)，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;//遍歷每一個(gè)元素的32個(gè)比特位//切記不能從低位 往 高位遍歷,從遇到的第一位為1才開(kāi)始算數(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ù)組

題目描述：

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

思路描述：

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

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

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

（3）前綴和+哈希表

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

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