国产亚洲精品福利在线无卡一,国产精久久一区二区三区,亚洲精品无码国模,精品久久久久久无码专区不卡

當(dāng)前位置: 首頁(yè) > news >正文

商務(wù)網(wǎng)站建設(shè)數(shù)據(jù)處理100個(gè)免費(fèi)推廣b站

商務(wù)網(wǎng)站建設(shè)數(shù)據(jù)處理,100個(gè)免費(fèi)推廣b站,wordpress建英文站,做網(wǎng)站開(kāi)發(fā)用筆記本要什么配置目錄 1.二叉搜索樹(shù)的最近公共祖先 2.在二叉樹(shù)中找到兩個(gè)節(jié)點(diǎn)的最近公共祖先 3.序列化二叉樹(shù) 4.重建二叉樹(shù) 5.輸出二叉樹(shù)的右視圖 6.組隊(duì)競(jìng)賽 7.刪除公共字符 1.二叉搜索樹(shù)的最近公共祖先 這是一個(gè)簡(jiǎn)單的問(wèn)題,因?yàn)槭嵌嫠阉鳂?shù)(有序)&am…

目錄

1.二叉搜索樹(shù)的最近公共祖先

?2.在二叉樹(shù)中找到兩個(gè)節(jié)點(diǎn)的最近公共祖先

3.序列化二叉樹(shù)

4.重建二叉樹(shù)

?5.輸出二叉樹(shù)的右視圖

6.組隊(duì)競(jìng)賽

?7.刪除公共字符?


?

1.二叉搜索樹(shù)的最近公共祖先

這是一個(gè)簡(jiǎn)單的問(wèn)題,因?yàn)槭嵌嫠阉鳂?shù)(有序),首先看看p,q是不是都在左子樹(shù)?右子樹(shù)

如果不是,那么現(xiàn)在的根就是兩個(gè)的最近公共祖先

  int lowestCommonAncestor(TreeNode* root, int p, int q) {// write code here、if(!root) return -1;if(p<root->val &&q<root->val) return lowestCommonAncestor(root->left,  p, q);else if(p>root->val && q>root->val) return lowestCommonAncestor(root->right, p, q);//在兩個(gè)子樹(shù)else return root->val;}

?2.在二叉樹(shù)中找到兩個(gè)節(jié)點(diǎn)的最近公共祖先

最一般的樹(shù)怎么找最近公共祖先?

?最直觀的方法肯定是和上面搜索樹(shù)的想法一樣,先看看這兩個(gè)節(jié)點(diǎn)是不是在一側(cè)的子樹(shù)里

但是這不是搜索樹(shù),不可以比較節(jié)點(diǎn)的值來(lái)判斷在左子樹(shù)/右子樹(shù)

沒(méi)有條件創(chuàng)造條件也要上,誰(shuí)讓我想不出來(lái)更好的思路....

  bool Isintree(TreeNode* root, int x) {if (!root) return false;return   root->val == x||Isintree(root->left,  x) ||Isintree(root->right,  x);}int lowestCommonAncestor(TreeNode* root, int o1, int o2) {if (!root) return -1;if (root->val == o1 || root->val == o2) return root->val;bool Iso1inleft = Isintree(root->left, o1);bool Iso1inright = !Iso1inleft;bool Iso2inleft = Isintree(root->left, o2);bool Iso2inright =  !Iso2inleft;if ((Iso1inleft && Iso2inright) || (Iso1inright && Iso2inleft))return root->val;if (Iso1inleft && Iso2inleft)return lowestCommonAncestor(root->left,  o1,  o2);elsereturn lowestCommonAncestor(root->right,  o1,  o2);}

?欣喜若狂的提交,超時(shí)!!!!!!!!!!!!!!!!!!!!!!!!!!!!

為什么?

因?yàn)樵谧訕?shù)里搜索很浪費(fèi)時(shí)間

?那么只能換方法

記得我們?cè)趺醋鱿嘟绘湵淼念}目嗎?

想找到鏈表的交點(diǎn),那么我們計(jì)算兩個(gè)鏈表的長(zhǎng)度,讓更長(zhǎng)的鏈表先走差距(兩個(gè)鏈表長(zhǎng)度差)步,然后挨個(gè)比較目前的val值,找到一樣的就輸出

那你看這個(gè)樹(shù)枝是不是很像鏈表

所以思路就有了


bool FindPath(TreeNode* root, stack<int>& s, int o) //找到這個(gè)節(jié)點(diǎn)的所有祖先
{if (!root) return false; //遇到空節(jié)點(diǎn)肯定不是祖先s.push(root->val); //先把這個(gè)節(jié)點(diǎn)入棧if (root->val == o) //找到了目標(biāo)節(jié)點(diǎn),直接返回return true;if (FindPath(root->left, s, o))  return true; //在左子樹(shù)里找到他,返回trueif (FindPath(root->right, s, o)) return true; //右子樹(shù)中找到他,trues.pop(); //走到這說(shuō)明左/右子樹(shù)沒(méi)找到這個(gè)節(jié)點(diǎn) ,這個(gè)root就不是目標(biāo)節(jié)點(diǎn)的祖先,popreturn false; //返回在這個(gè)路徑?jīng)]找到
}
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {// 兩個(gè)棧記錄他們的祖先列表stack<int> s1;stack<int> s2;FindPath(root, s1, o1);FindPath(root, s2, o2);while (s1.size() < s2.size()) //長(zhǎng)度不一樣s2.pop(); //更長(zhǎng)的popwhile (s1.size() > s2.size())s1.pop();while (s1.top() != s2.top()) //當(dāng)前不是公共祖先 {//都把這個(gè)節(jié)點(diǎn)pops1.pop();s2.pop();}return s1.top(); //或者s2.top() 都一樣的值
}

3.序列化二叉樹(shù)

寫兩個(gè)函數(shù),讓字符串可以構(gòu)建成二叉樹(shù),二叉樹(shù)也可以寫成字符串

void dfs_Serialize(TreeNode* root, string& s)
{if (!root)//如果是空節(jié)點(diǎn),直接寫一個(gè)#,空節(jié)點(diǎn)的子節(jié)點(diǎn)被省略,所以直接返回{s += '#';return;}s += to_string(root->val) + ','; //把非空節(jié)點(diǎn)的val變成字符,寫入到字符串dfs_Serialize(root->left, s); //左子樹(shù)dfs_Serialize(root->right, s);//右子樹(shù)
}
char* Serialize(TreeNode* root) { //用二叉樹(shù)寫字符串?dāng)?shù)組string s; //首先寫成字符串dfs_Serialize(root, s); //深度優(yōu)先遍歷(前序)char* ans = new char[s.size() + 1]; //最后應(yīng)該輸出數(shù)組形式,先開(kāi)數(shù)組(加上1寫'\0')memcpy(ans, s.c_str(), s.size()); //把字符串拷貝給數(shù)組ans[s.size()] = '\0';//終止符return ans;
}
TreeNode* dfs_Deserialize(char*& s) //把字符串變二叉樹(shù),注意這個(gè)字符串在遞歸的時(shí)候不是每次從頭開(kāi)始,所以&
{if (*s == '#')//是空節(jié)點(diǎn)的標(biāo)志,直接返回nullptr{s++; //s向后走一個(gè),因?yàn)檫@個(gè)字符對(duì)應(yīng)的節(jié)點(diǎn)已經(jīng)被表示完了return nullptr;}int val = 0; //字符串對(duì)應(yīng)的節(jié)點(diǎn)valwhile (*s != ',') //看樣例,字符串以,分割{val = val * 10 + (*s - '0'); //萬(wàn)一不是個(gè)位數(shù),需要這樣算好每一位s++;//s往后走}s++; //把逗號(hào)跳過(guò)TreeNode* root = new TreeNode(val); //用val創(chuàng)建節(jié)點(diǎn)root->left = dfs_Deserialize(s); //左節(jié)點(diǎn)的創(chuàng)建root->right = dfs_Deserialize(s);//右節(jié)點(diǎn)return root; //返回根
}
TreeNode* Deserialize(char* str) {return dfs_Deserialize(str);
}

還有第二個(gè)方法,借助隊(duì)列,把字符串構(gòu)建成二叉樹(shù)(這個(gè)顯然沒(méi)有上面的方法快)

char* Serialize(TreeNode* root) { //用層序來(lái)寫字符串if (!root) return nullptr; //如果是空節(jié)點(diǎn),不需要記錄他的孩子string str; queue<TreeNode*> que;que.push(root); //先把根入隊(duì)while (!que.empty()){auto node = que.front(); //取隊(duì)頭元素que.pop();if (node) //取出的節(jié)點(diǎn)不是空{(diào)str += to_string(node->val) + ","; //字符串保存這個(gè)節(jié)點(diǎn)val對(duì)應(yīng)的字符,并且在字符串里面寫入分割符號(hào)que.push(node->left);//帶入左孩子que.push(node->right);}else {str += "#";//是空,寫成#}}auto res = new char[str.size() + 1]; //和上一方法這里的用處一樣strcpy(res, str.c_str());res[str.size()] = '\0';return res;
}
int Getinteger(char* str, int& k)  //把字符轉(zhuǎn)化成數(shù)字
{int val = 0;while (str[k] != ',' && str[k] != '\0' && str[k] != '#'){val = val * 10 + str[k] - '0';++k;}if (str[k] == '\0') return -1;if (str[k] == '#') val = -1;k++;return val;
}
TreeNode* Deserialize(char* str) {if (!str) return nullptr;int k = 0; //記錄字符串的下標(biāo)queue<TreeNode* > que;auto head = new TreeNode(Getinteger(str, k)); //一定要把字符串下標(biāo)也傳,要不然找不到位置了que.push(head); //把頭結(jié)點(diǎn)入隊(duì)while (!que.empty()){auto node = que.front();//隊(duì)頭que.pop();//這里的反序列化是根據(jù)前序用字符串構(gòu)建二叉樹(shù)int leftval = Getinteger(str, k); //把字符串轉(zhuǎn)換成左節(jié)點(diǎn)的valif (leftval != -1)//如果左孩子的val是-1,代表是空節(jié)點(diǎn){//不是空auto nodeleft = new TreeNode(leftval) ;//創(chuàng)建節(jié)點(diǎn)node->left = nodeleft; //node和左孩子鏈接que.push(nodeleft);//鏈接好的節(jié)點(diǎn)入隊(duì)}//右節(jié)點(diǎn)同樣的方法int rightval = Getinteger(str, k);if (rightval != -1){auto noderight = new TreeNode(rightval);node->right = noderight;que.push(noderight);}}return head; //返回頭結(jié)點(diǎn)
}

4.重建二叉樹(shù)

之前就說(shuō)過(guò)三種遍歷方式:前中后,只有前+后不能構(gòu)建出二叉樹(shù)

同一個(gè)顏色是同一次遞歸

最后根據(jù) 這個(gè)規(guī)律可以得到二叉樹(shù)


TreeNode* _reConstructBinaryTree(vector<int>& pre, vector<int>& vin, int& k, //k一定要給&,在每個(gè)遞歸里是看得見(jiàn)改變的int begin, int end) {if (begin > end) return nullptr;  //區(qū)間不成立,說(shuō)明為空int rooti = begin; //rooti記錄中序節(jié)點(diǎn)里面根的下標(biāo)while (rooti <= end) { //根的下標(biāo)肯定在合法區(qū)間里if (vin[rooti] == pre[k]) //在中序數(shù)組里找到根,k記錄每個(gè)根在前序里的下標(biāo)break;++rooti;}//rooti代表根節(jié)點(diǎn)的下標(biāo)//[begin,rooti-1] rooti [rooti+1,end]TreeNode* root = new TreeNode(pre[k++]); //創(chuàng)建節(jié)點(diǎn)root->left =_reConstructBinaryTree(pre, vin, k, begin, rooti - 1); //左孩子在左區(qū)間找(因?yàn)橹行蚴亲蟾?#xff09;root->right =_reConstructBinaryTree(pre, vin, k, rooti + 1, end);return root;
}
TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {int k = 0;return _reConstructBinaryTree(pre, vin, k, 0, pre.size() - 1);
}

?5.輸出二叉樹(shù)的右視圖

?根據(jù)給的前序和中序構(gòu)建樹(shù),然后層序思想,每次到一層的最左側(cè),直接入ans

TreeNode* buildtree(vector<int>& xianxu, vector<int>& zhongxu, int& k, //建樹(shù)(和前面重建二叉樹(shù)是一樣的)int begin, int end) {if (begin > end) return nullptr;int rooti = begin;while (rooti <= end) {if (xianxu[k] == zhongxu[rooti])break;++rooti;}TreeNode* root = new TreeNode(xianxu[k++]);root->left = buildtree(xianxu, zhongxu, k, begin, rooti - 1);root->right = buildtree(xianxu, zhongxu, k, rooti + 1, end);return root;
}
void bfs(TreeNode* root, vector<int>& ans) { //層序+找最右節(jié)點(diǎn)if (!root) return;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int size = q.size(); //當(dāng)前層數(shù)的sizewhile (size--) {TreeNode* node = q.front();q.pop();if (size == 0) ans.push_back(node->val);  //直到size==0,找到最右節(jié)點(diǎn)if (node->left) q.push(node->left);if (node->right) q.push(node->right);}}
}
vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {// write code herevector<int> ans;int k = 0;TreeNode* root = buildtree(xianxu, zhongxu, k, 0, xianxu.size() - 1);bfs(root, ans);return ans;
}

?但是這樣做總是覺(jué)得很麻煩,所以去評(píng)論區(qū)看來(lái)一下大佬的代碼


void _solve(vector<int> xianxu, vector<int> zhongxu, vector<int>& ans,int level) {if (xianxu.empty()) return;   //如果前序是空的,證明根是空if (ans.size() < level) ans.push_back(xianxu[0]); //ans里面的元素個(gè)數(shù)一定是等于層數(shù),如果小于,直接把當(dāng)前的根入elseans[level - 1] = xianxu[0]; //level應(yīng)該也是ans的個(gè)數(shù),最后一個(gè)元素下標(biāo)就是level-1int headpos = 0; //還是找中序里的根while (zhongxu[headpos] != xianxu[0])headpos++;_solve(vector<int>(xianxu.begin() + 1, xianxu.begin() + headpos + 1), vector<int>(zhongxu.begin(), zhongxu.begin() + headpos), ans, level + 1);_solve(vector<int>(xianxu.begin() + headpos + 1, xianxu.end()),vector<int>(zhongxu.begin() + headpos + 1, zhongxu.end()), ans, level + 1);
}
vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {vector<int> ans;_solve(xianxu, zhongxu, ans, 1);return ans;
}

??前面的不解釋了,主要看大佬的遞歸

?之前我們構(gòu)建二叉樹(shù)的時(shí)候只想著找到根節(jié)點(diǎn)的下標(biāo),但是居然沒(méi)有發(fā)現(xiàn)前序begin()+1~begin()+headpos整個(gè)閉區(qū)間是左子樹(shù)的所有節(jié)點(diǎn)!!!!!!!!!!!!!!!

也就是說(shuō)我們之前寫的構(gòu)造二叉樹(shù)的所有步驟都寫麻煩了

來(lái)看前序+中序怎么構(gòu)建二叉樹(shù)


TreeNode* _reConstructBinaryTree(vector<int> pre, vector<int>vin) {if (pre.empty()) return nullptr;int rooti = 0;while (vin[rooti] != pre[0]) {++rooti;}TreeNode* root = new TreeNode(pre[0]);root->left =_reConstructBinaryTree(vector<int>(pre.begin() + 1, pre.begin() + rooti + 1),vector<int>(vin.begin(), vin.begin() + rooti));root->right =_reConstructBinaryTree(vector<int>(pre.begin() + 1 + rooti, pre.end()),vector<int>(vin.begin() + rooti + 1, vin.end()));return root;
}
TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {return _reConstructBinaryTree(pre, vin);
}

6.組隊(duì)競(jìng)賽

這個(gè)題不在面試必刷101,作為補(bǔ)充

一道簡(jiǎn)單的數(shù)學(xué)題

其實(shí)沒(méi)啥好說(shuō)的,先排序,最小的節(jié)點(diǎn)就是前n個(gè),n是隊(duì)伍的個(gè)數(shù),也就代表了如果想讓所有隊(duì)伍的能力值和最大,必須每個(gè)隊(duì)伍有一個(gè)重排v之后的前n個(gè)數(shù)之一

比如

n=2

排序之后前兩個(gè)數(shù)1 2,應(yīng)該給每個(gè)隊(duì)伍分配一個(gè),不能讓1 2同時(shí)出現(xiàn)在一個(gè)隊(duì)伍里

所以sum求和的時(shí)候i從n開(kāi)始,不應(yīng)該直接挨著取n之后的元素,因?yàn)槟惆炎畲蟮囊恍?shù)全部沒(méi)取到,應(yīng)該跳兩個(gè)取一次?

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{int n;while (cin >> n){vector<int> v;v.resize(3 * n);for (int i = 0; i < v.size(); i++){cin >> v[i];}sort(v.begin(), v.end());long long sum = 0;for (int i = n;i < v.size(); i += 2){sum += v[i];}cout << sum<<endl;}return 0;
}

?7.刪除公共字符?

#include <iostream>
#include <string>using namespace std;int main(){string s1, s2;getline(cin, s1);getline(cin, s2);for (int i= 0; i < s1.size(); i++) {if (s2.find(s1[i]) == -1) //在s2中找不到這個(gè)字符則輸出cout << s1[i];}return 0;}

?這個(gè)不是我自己最初寫的,一開(kāi)始是把s2里面先遍歷然后映射到數(shù)組里,但是顯然慢

這個(gè)直接在s2里面找s1是不是在很方便

http://aloenet.com.cn/news/46144.html

相關(guān)文章:

  • 做網(wǎng)站圖片尺寸全球搜索引擎大全
  • python做網(wǎng)站源碼深圳網(wǎng)站營(yíng)銷seo費(fèi)用
  • 做3D打印樣品用什么外貿(mào)網(wǎng)站好2345網(wǎng)址大全
  • wordpress 登陸后查看seo引擎優(yōu)化
  • 長(zhǎng)沙手機(jī)網(wǎng)站開(kāi)發(fā)百度seo推廣計(jì)劃類型包括
  • 建設(shè)網(wǎng)站合同2021百度熱搜年度榜
  • wordpress 中英文網(wǎng)站模板軟文寫手接單平臺(tái)
  • 網(wǎng)站安全建設(shè)必要性seo搜索引擎專員
  • 昆山做網(wǎng)站找哪家好線上平臺(tái)推廣方式
  • 江蘇建設(shè)局的資質(zhì)辦理網(wǎng)站培訓(xùn)機(jī)構(gòu)最新消息
  • 素材網(wǎng)站建設(shè)需要多少費(fèi)用seo項(xiàng)目
  • win7下用iis搭建網(wǎng)站百度網(wǎng)盤客服電話
  • 上海定制網(wǎng)站建設(shè)費(fèi)用代寫企業(yè)軟文
  • 做盜版網(wǎng)站違法嗎湖南網(wǎng)站設(shè)計(jì)
  • 模板做圖 網(wǎng)站有哪些友情鏈接平臺(tái)
  • 做餐飲在環(huán)保局網(wǎng)站備案手機(jī)網(wǎng)頁(yè)制作軟件
  • seo網(wǎng)站做推廣的公司輔導(dǎo)班培訓(xùn)機(jī)構(gòu)
  • 相冊(cè)管理網(wǎng)站模板外鏈怎么打開(kāi)
  • 做京東網(wǎng)站的摘要百度seo搜索引擎優(yōu)化方案
  • 找個(gè)公司做網(wǎng)站需要注意什么百家號(hào)seo怎么做
  • 163域名注冊(cè)屬于seo網(wǎng)站優(yōu)化
  • 企業(yè)營(yíng)銷網(wǎng)站建設(shè)規(guī)劃百度網(wǎng)站優(yōu)化公司
  • 怎么在網(wǎng)站上做視頻百度電腦版網(wǎng)頁(yè)
  • 設(shè)計(jì)一個(gè)網(wǎng)頁(yè)的策劃書怎么優(yōu)化網(wǎng)站排名才能起來(lái)
  • 做30個(gè)精品網(wǎng)站北京做網(wǎng)站的公司有哪些
  • 網(wǎng)站開(kāi)發(fā)教育培訓(xùn)百度排名點(diǎn)擊器
  • 假的建設(shè)銀行網(wǎng)站國(guó)際時(shí)事新聞2022最新
  • 制作書簽簡(jiǎn)單又漂亮seo網(wǎng)站優(yōu)化怎么做
  • 設(shè)計(jì)公司調(diào)研報(bào)告怎么學(xué)seo基礎(chǔ)
  • 做網(wǎng)站開(kāi)源互聯(lián)網(wǎng)推廣運(yùn)營(yíng)