題目描述

統(tǒng)計一個數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。

解析：采用二分查找，搜到數(shù)字后在其前后判斷并計數(shù)

class Solution { public:int GetNumberOfK(vector<int> data ,int k) {int length=data.size();if(length <= 0)return 0;int cnt=0;int left=0;int right=length-1;int mid=(left + right)/2;while(k != data[mid] && left < right){if(k<data[mid]){right=mid-1;mid=(left + right)/2;}if(k>data[mid]){left=mid+1;mid=(left + right)/2;}}int flag=0;//搜索標(biāo)志 找到時為1if(k == data[mid]){cnt++;flag=1;}int pos=mid;if(flag){int i=mid-1;while(data[i]==k){cnt++;i--;}i=mid+1;while(data[i]==k){cnt++;i++;}}return cnt;} };
題目描述

輸入一棵二叉樹，求該樹的深度。從根結(jié)點到葉結(jié)點依次經(jīng)過的結(jié)點（含根、葉結(jié)點）形成樹的一條路徑，最長路徑的長度為樹的深度。

解析：遞歸計算結(jié)點的左右結(jié)點

/* struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {} };*/ class Solution { public:int TreeDepth(TreeNode* pRoot){if(pRoot==NULL)return 0;int left=TreeDepth(pRoot->left);int right=TreeDepth(pRoot->right);return left>right?left+1:right+1;} };題目描述

輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹。

解析：后序遍歷，每遍歷一個結(jié)點時保存該結(jié)點的深度，當(dāng)某結(jié)點不滿足條件時返回假

class Solution { public:bool IsBalanced_Solution(TreeNode* pRoot) {int depth=0;return isBalance(pRoot,&depth);}bool isBalance(TreeNode* pRoot,int* depth){if(pRoot==NULL){*depth=0;return true;}int left,right;if(isBalance(pRoot->left,&left) && isBalance(pRoot->right,&right)){int dif=left-right;if(dif<=1 && dif>=-1){*depth = left > right ? left+1 : right+1;return true;}}return false;} };題目描述一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。

題目描述

一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。

解析：亦或處理：相同數(shù)字異或結(jié)果為零，把數(shù)組遍歷全部異或，結(jié)果必為兩個只出現(xiàn)一個的數(shù)字的異或結(jié)果，由于兩個數(shù)字不同，必然異或的數(shù)存在至少一位為1，找到一位，并以這一位所在數(shù)字為0或為1，把整個數(shù)組重新分為兩個子數(shù)組，這樣兩個不同的數(shù)就分到了兩個子數(shù)組中，再分別遍歷異或兩個子數(shù)組就能得到唯二的兩個單獨(dú)出現(xiàn)的數(shù)字

class Solution { public:void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {int length=data.size();if(length==0 || length==1){*num1=0;*num2=0;return;}int exclusive=resultExclusive(data);int num=1;while(exclusive < (num ^ exclusive) )num = (num << 1);vector<int> data1;vector<int> data2;for(int i=0;i<length;i++){if((data[i] ^ num) > data[i])data1.push_back(data[i]);elsedata2.push_back(data[i]);}*num1=resultExclusive(data1);*num2=resultExclusive(data2);}int resultExclusive(vector<int> data){int length=data.size();if(length==0)return 0;int result=0;for(int i=0;i<length;i++){result=(result ^ data[i]);}return result;} };

總結(jié)

以上是生活随笔為你收集整理的剑指offer 算法 （知识迁移能力）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。