剑指offer解题思路锦集11-20题
又來更新劍指offer上的題目思路啦。
?
11、【二進制中1的個數】
?
題目：輸入一個整數，輸出該數二進制表示中1的個數。其中負數用補碼表示。
eg：NumberOf1(1)=1 NumberOf1(2)=0 NumberOf1(3)=2 NumberOf1(4)=1 NumberOf1(5)=2 NumberOf1(6)=2 NumberOf1(7)=3思路：每次都將數字n的最后一位1反轉成0，不斷反轉到這個數字變成0，然后我們統計反轉了多少次，這樣不就可以成功得到這個數字有多少位了嗎？
?
難點：如何反轉一個數字的最后一位1，解決方案如下：
n = n & (n - 1);?
代碼：
int NumberOf1(int n) {int number = 0;while (n != 0){n = n & (n - 1);++number; }return number;}?
思路2：可不可以嘗試不去改變這個數字呢？答案也可以的。假設是int類型，如果我循環32次，判斷每個位是否為1，這樣不也可以得到這個數字有多少位為1嗎？誠然，這樣也是存在著缺點的。
缺點：比思路1的時間復雜度略高，不過也是常數級別的，因為數字的位數是有限制的，兩者可能系數上存在著差別吧！~~~還有一個缺點，就是這樣的代碼移植性較差~~
存在坑：
(temp & n) != 0這里的括號不能去掉，因為&的優先級比 != 低。。。。
?
代碼：
int NumberOf1(int n) {int number = 0;int temp = 1;for (int i = 0; i < 32; ++i){if ((temp & n) != 0){++number;}temp = temp<<1;}return number;}?
12、【數值的整數次方】
給定一個double類型的浮點數base和int類型的整數exponent。求base的exponent次方。
例子：2^10
思路1：2*2*2*2*2*2*2*2*2*2，循環N次即可。時間復雜度O(n)沒啥好說的，跳過。
思路2: 分治想法，假設是求a^n
如果n為偶數，那么轉化成求x=a^(n/2)，然后返回x*x即可。
如果n為奇數，那么轉化成求x=a^(n-1/2)，然后返回x*x*a即可。
時間復雜度是O(lgn)。。。怎么證明？
應用算法導論中的主方法即可。
?
這里，有T(n) = T(n/2) + 1，即 b = 2, a = 1，f(n)=1。因此滿足條件2，因此時間復雜度為O(nlogb(a))=O(nlog2(1)*lgn)=O(1*lgn)=O(lgn)。
哈哈，是不是瞬間感覺寫難了。。。。
?
?
13、【調整數組順序使奇數位于偶數前面】
題目：輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有的奇數位于數組的前半部分，所有的偶數位于位于數組的后半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變。
思路：兩個數組，一個按順序保存奇數，另一個按順序保存偶數。。。時間復雜度O(N)，空間復雜度O(N)。
思路2：創建一個數組，循環2次，第一次只掃描奇數，丟進數組中。第二次只掃描偶數，丟進數組。。十分簡單。。。
思路3：類似冒泡算法，前偶后奇數就交換。
void reOrderArray(vector<int> &arr) {//雙指針int n = arr.size();for(int i = 0; i < n; ++i){for(int j = 0; j < n-i-1; ++j){if(arr[j]%2 == 0 && arr[j+1]%2 == 1) swap(arr[j],arr[j+1]);}}}?
思路4：兩個指針咯，一個指針1從頭到尾，另外一個指針2從尾到頭，如果指針1發現偶數，那么停下來，如果指針2發現奇數，那么也停下來。再交換兩個指針指向的數就Ok了。
問題：這樣是真的可以嗎？答案是不可以的哦~哈哈，因為這樣違反了題目要求——要求奇數和偶數順序不能改變。。。嗯，是的，如果是讓順序可以隨意的話，那么這就是很nice的解。
?
14、【鏈表中倒數第k個結點】
題目：輸入一個鏈表，輸出該鏈表中倒數第k個結點。
思路1：遍歷得到鏈表長度n，然后再遍歷一次，給返回第n-k+1個元素。這里遍歷了兩次，時間復雜度為0(n)，空間復雜度為O(1)。
思路2：思路1是否存在優化的地方呢？是存在的，我們可以考慮考慮能不能不遍歷兩次，這時候我們想能不能用空間換時間。
好比，將鏈表轉化成數組保存下來，那么我們第二次遍歷鏈表操作可以換成獲取數組中的n-k+1個元素操作了，只需要遍歷一次鏈表就可以了。但是這種方法的空間復雜度為O(N)。
思路3：兩個指針，也就是傳說中的快慢指針。一個指針先走k步，然后慢指針才開始跑?？熘羔樀筋^了，那么落后了k步的慢指針不就是倒數第k個元素了嗎？
代碼:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {if(NULL == pListHead) return NULL;ListNode* pfront = pListHead;ListNode* pend = pListHead;for (int i = 0; i < k; i++){if(pfront != NULL){pfront = pfront->next;}else{return NULL;//超出了}}for(;pfront != NULL;pfront = pfront->next){pend = pend->next;}return pend;}?
15、【反轉鏈表】
輸入一個鏈表，反轉鏈表后，輸出鏈表的所有元素。
A->B->C->D->EA->B->C->D<-E (D->NULL)A->B->C<-D<-E (C->NULL)A->B<-C<-D<-E (B->NULL)A<-B<-C<-D<-E (A->NULL)?代碼
ListNode* ReverseList(ListNode* pHead){if(pHead == NULL||pHead->next == NULL) return pHead;//得到鏈表尾部ListNode* tail = ReverseList(pHead->next);pHead->next->next = pHead;pHead->next = NULL;return tail;}?
?
16、【合并兩個排序的鏈表】
輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。
額，這題啥也不用說了吧，，，不就是歸并排序的合并過程么。。。。直接貼代碼吧。。。
ListNode* Merge(ListNode* pHead1, ListNode* pHead2){ListNode* res = NULL;ListNode* cur = NULL;ListNode* add = NULL;if(pHead1 == NULL) return pHead2;if(pHead2 == NULL) return pHead1;while(pHead1 != NULL &&pHead2 != NULL)//兩個迭代器{add = pHead1->val >= pHead2->val ?pHead2:pHead1;if(res == NULL) res = cur = add;第一次才執行 在于選擇一條鏈出來else{cur->next = add;cur = cur->next;}if(add == pHead1) pHead1=pHead1->next;else pHead2 = pHead2->next;}if(pHead1 != NULL) cur->next = pHead1;if(pHead2 != NULL) cur->next = pHead2;return res;}?
17、【樹的子結構】
題目：輸入兩棵二叉樹A，B，判斷B是不是A的子結構。（ps：我們約定空樹不是任意一個樹的子結構）
其實這里主要是靠對問題的拆分能力。
子函數CompTree：判斷兩棵樹是否相等。
判斷是否為子樹：假設當前節點為根，那么是否為子結構？
代碼：
class Solution { private:bool CompTree(TreeNode* pRoot1, TreeNode* pRoot2)//判斷2是否為1的子樹。。。。{if(pRoot2 == NULL) return true;if(pRoot1 == NULL) return false;if(pRoot1->val == pRoot2->val) return CompTree(pRoot1->left,pRoot2->left)&&CompTree(pRoot1->right,pRoot2->right);return false;} public:bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){if(pRoot1 == NULL ||pRoot2 == NULL ) return false;return CompTree(pRoot1,pRoot2) || HasSubtree(pRoot1->left,pRoot2) || HasSubtree(pRoot1->right, pRoot2);} };?
18、二叉樹的鏡像
如果這時候，我們用自然語言去描述，可以這樣認為怎么將一顆二叉樹轉化成源二叉樹的鏡像：交換兩棵樹的左子樹指針、右子樹指針。
?
假設樹的結構如下：
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {} };?
我們輕易得到第一個版本可以AC的代碼。使用遞歸即可。
零、先序遍歷遞歸版本
?
class Solution { public:void Mirror(TreeNode *pRoot) {if(pRoot != NULL){TreeNode *tmp = pRoot->left;pRoot->left = pRoot->right;pRoot->right = tmp;if (pRoot->left != NULL) {Mirror(pRoot->left);}if (pRoot->right != NULL) {Mirror(pRoot->right);}}} };?
但是這個代碼是不是最優的呢？很顯然，不是，因為其用到遞歸，可以用非遞歸實現嗎？答案是可以的。
?
這時候，我們仔細觀看一下上面的代碼，發現，如果我們將交換左右子樹指針的代碼轉換成print樹節點node值。那么上面的代碼不就是先序遍歷樹的代碼嗎？
?
因此，我們可以深思，本質上，這條題的解答，就是遍歷樹，然后將每一個節點的左右孩子交換。
?
那么我們又想到了樹的遍歷方式，不難得到以下幾種解答：
一、基于隊列的廣度優先遍歷
?
class Solution { public:void Mirror(TreeNode *pRoot) {//if(pRoot != NULL){//基于隊列廣度優先遍歷的的版本1queue<TreeNode*> que;que.push(pRoot);while(!que.empty()){TreeNode* pt = que.front();que.pop();if(pt->left != NULL || pt->right != NULL ){TreeNode* temp = pt->left;pt->left = pt->right;pt->right = temp;}if(pt->left != NULL){que.push(pt->left);}if(pt->right != NULL){que.push(pt->right);}}}} };?
?
二、后續遍歷的遞歸版本
?
class Solution { public:void Mirror(TreeNode *pRoot) {//if(pRoot != NULL){//后序遍歷整個二叉樹，交換里面的兩個指針，Mirror(pRoot->left);Mirror(pRoot->right);TreeNode* temp = pRoot->left;pRoot->left = pRoot->right;pRoot->right = temp;*/}} };?
三、先續遍歷版本改出來的非遞歸版本
?
class Solution { public:void Mirror(TreeNode *pRoot) {//if(pRoot != NULL){stack<TreeNode*> stk;stk.push(pRoot);while(!stk.empty()){TreeNode* pt = stk.top();stk.pop();if(pt->left != NULL){stk.push(pt->left);}if(pt->right != NULL){stk.push(pt->right);}if(pt->left != NULL || pt->right != NULL ){TreeNode* temp = pt->left;pt->left = pt->right;pt->right = temp;}}}} };?
?
四、基于后續遍歷版本改出來的非遞歸版本
?
神奇的代碼，，，已經寫完了，其實這里考的是將一個未知問題轉化成一個已知問題去解決。
?
19、逆時針打印矩陣
題目：輸入一個矩陣，按照從外向里以順時針的順序依次打印出每一個數字，
例如，如果輸入如下矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
?
還是畫圖吧，假設要打印的矩陣為：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16?
我們首先打印 1 2 3 4 5 8 9 12 13 14 15 16?
然后打印 6 7 10 11?
是不是很清晰？我們只要實現一個子函數，完成打印正方形的工作，然后寫個循環，不斷從外到里去調用那個子函數就ok了。
代碼如下：
class Solution { public:void GetArray(vector<vector<int> > &matrix,vector<int> &res,int ibegin,int iend,int jbegin,int jend){//注意 ibegin == iend時候 循環 1 3執行兩次 所以要判斷//同理 jbegin == jend也有這個情況int i = 0;//cout<<ibegin<<" "<<iend<<" "<<jbegin<<" "<<jend<<" "<<endl;for(i = jbegin; i <= jend;++i) res.push_back(matrix[ibegin][i]);//左到右for(i = ibegin+1; i <= iend;++i) res.push_back(matrix[i][jend]);//上到下if(ibegin != iend)for(i = jend-1; i >= jbegin;--i) res.push_back(matrix[iend][i]);//右到左if(jbegin != jend)for(i = iend-1; i > ibegin;--i) res.push_back(matrix[i][jbegin]);//下到上}vector<int> printMatrix(vector<vector<int> > matrix) {int row = matrix.size();//行int col = matrix[0].size();//列vector<int> res;int ibegin = 0;int iend = row-1;//int jbegin = 0;int jend = col-1;for(;ibegin <= iend && jbegin <= jend;++ibegin,--iend,++jbegin,--jend){GetArray(matrix,res,ibegin,iend,jbegin,jend);}return res;} };?
這里考的是對問題的分解能力。
?
?
20、包含max函數的棧
題目：定義棧的數據結構，請在該類型中實現一個能夠得到棧最大元素的max函數。
?
假設存在棧 1, 2, 3, 3, 2, 4, 5, 2, 1
那么可以搞一個輔助棧 1, 2, 3, 3, 3, 4, 5, 5, 5
?
其中輔助棧保存的是棧中的最大元素即可，當彈出時候，兩邊同時彈出即可。
?
代碼：
class Solution { public:void push(int value) {mdata.push(value);if(mmax.empty()) mmax.push(value);else{int val = mmax.top();val = val < value ? val:value;mmax.push(val);}}void pop() {mdata.pop();mmax.pop();}int top() {mmax.pop();int val = mdata.top();mdata.pop();return val;}int min() {return mmax.top();} private:stack<int> mdata;stack<int> mmax; };?
轉載于:https://www.cnblogs.com/ccXgc/p/9031974.html
總結
以上是生活随笔為你收集整理的剑指offer解题思路锦集11-20题的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： ElasticSearch 5.5 离线
- 下一篇： RunC 简介