目錄

第11題：

給定一個double類型的浮點數base和int類型的整數exponent。求base的exponent次方。

解題思路：

• 這道題非常簡單，但是存在陷阱，即當exponent為負數和0的時候要特別考慮，其余的沒有了

代碼實現：

c++

#include <iostream>
#include <vector>
#include <cmath>using namespace std;double Power(double base, int exponent) {double temp = base;if(exponent < 0 ){for(int i =1 ;i<-(exponent);i++){temp *= base;}return 1.0/temp;}else if(exponent ==0){return 1;}else{for(int i = 1 ; i<exponent ; i++){temp *= base;}return temp;}}int main(){cout<<Power(2,-3)<<endl;cout<<Power(2,0)<<endl;cout<<Power(2,2)<<endl;return 0;
}

運行時間：5ms

占用內存：456k

python

# -*- coding:utf-8 -*-
class Solution:def Power(self, base, exponent):# write code herereturn base**exponent

運行時間：22ms
占用內存：5624k

第12題：

輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有的奇數位于數組的前半部分，所有的偶數位于數組的后半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變。

解題思路：

• 通過使用2個棧結果來保存奇數項和偶數項,然后對數組從后向前遍歷，遇到奇數就壓奇數棧，遇到偶數就壓偶數棧，然后在依次彈出奇數棧和偶數棧中的內容，并保存在原始的數組中（先將原始數組清空）

代碼實現：

c++

#include <stack>
class Solution {
public:void reOrderArray(vector<int> &array) {stack<int> oddStack;//定義奇數棧stack<int> evenStack;//定義偶數棧for(int i = array.size()-1 ; i >= 0 ;i--){if(array[i] % 2 == 0){evenStack.push(array[i]);}else{oddStack.push(array[i]);}}array.clear();while(!oddStack.empty()){array.push_back(oddStack.top());oddStack.pop();}while(!evenStack.empty()){array.push_back(evenStack.top());evenStack.pop();} }
};

運行時間：5ms

占用內存：480k

python

# -*- coding:utf-8 -*-
# -*- coding:utf-8 -*-
class Solution:def reOrderArray(self, array):# write code hereoddList = []  #保存奇數evenList = []  #保存偶數for i in array:if i % 2 == 0:evenList.append(i)else:oddList.append(i)array = []for i in oddList:array.append(i)for i in evenList:array.append(i)return array

運行時間：23ms

占用內存：5724k

第13 題：

輸入一個鏈表，輸出該鏈表中倒數第k個結點。

解題思路：

• 首先順序遍歷一遍鏈表，并將值壓棧，然后在通過棧彈出第K個元素即為鏈表的倒數第K個元素。時間復雜度為O(n),空間復雜度為O(n);

代碼實現：

c++

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {stack<ListNode*> tempStack;if(pListHead == NULL){return NULL;}if(k <= 0){return NULL;}int dataCount = 0;while (pListHead != NULL){tempStack.push(pListHead);pListHead = pListHead->next;dataCount++;}if(dataCount < k){return NULL;}for(int i = 0 ; i < k - 1 ; i++){tempStack.pop();}return tempStack.top();}
};

運行時間：4ms

占用內存：476k

python

# -*- coding:utf-8 -*-
class Solution:def FindKthToTail(self, head, k):# write code hereres=[]while head:res.append(head)head=head.nextif k>len(res) or k<1:returnreturn res[-k]

運行時間：26ms
占用內存：5732k

第 14題：

輸入一個鏈表，反轉鏈表后，輸出新鏈表的表頭。

解題思路：

• 本體的意思應該是輸出原始鏈表的反轉鏈表，而不是僅僅只是輸出反轉后鏈表的頭結點，所以通過棧的結構實現不佳。思想是：從頭到尾遍歷鏈表，然后將每兩個節點進行反轉操作即可，最好將原始的頭結點的后繼置NULL，頭結點直接取最后一個元素

代碼實現：

c++

class Solution {
public:ListNode* ReverseList(ListNode* pListHead) {if(pListHead == NULL)return NULL;ListNode *pCurrent ,*pPre,*pNext;//一、指針的初始化階段pPre = pListHead;pCurrent = pPre->next ;while(pCurrent)               //二、反轉單鏈表的核心代碼{pNext = pCurrent->next ;   //1. 緩沖pCurrent后面的單鏈表pCurrent->next = pPre ;	   //2. 反轉單鏈表pPre = pCurrent;           //3.讓pPre指針后移pCurrent = pNext ;         //4. 讓pCurrent指針后移}//三、處理并返回頭指針pListHead->next = NULL;                //把原頭結點的next域變成空指針pListHead = pPre ;		           //把頭結點指向最后一個結點產生新的頭結點，也就是把原單鏈表的尾結點變成頭結點return pListHead;}
};

運行時間：5ms

占用內存：464k

python

# -*- coding:utf-8 -*-

第15 題：

輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。

解題思路：

• 遞歸的方法：依次在鏈表1和鏈表2遍歷，每次取兩個鏈表中較小的那個值插入到新的鏈表中去。

代碼實現：

c++

遞歸實現

class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2){if(pHead1 == NULL && pHead2 == NULL){return NULL;}if(pHead1 == NULL){return pHead2;}if(pHead2 == NULL){return pHead1;}ListNode* head;  //新鏈表的表頭if(pHead1->val < pHead2->val){head = pHead1;head->next =  Merge(pHead1->next , pHead2); //遞歸調用}else{head = pHead2;head->next =  Merge(pHead1, pHead2->next);}return head;}
};

運行時間：4ms

占用內存：492k

python

# -*- coding:utf-8 -*-

第16 題：

輸入兩棵二叉樹A，B，判斷B是不是A的子結構。（ps：我們約定空樹不是任意一個樹的子結構）

解題思路：

• 找一顆樹是否為另外一顆樹的子樹，當然是遍歷主樹，先從根節點開始，如果根節點相同，就比較左右孩子節點，如果相同，則返回true，否則就遞歸遍歷主樹的左子樹和右子樹，只要找到一個相同即可。在比較子樹和主樹之前，我們要定義一個函數用于比較兩個二叉樹是否相同。也是從根節點開始，依次對比根節點，左孩子，右孩子是否相同，只有全部節點相同才是相同。

代碼實現：

c++

class Solution {
public:bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){if(!pRoot1 || !pRoot2) return false;bool result=false;if(pRoot1->val == pRoot2->val)result=isSubtree(pRoot1,pRoot2); // 找到判斷子樹if(!result) result=HasSubtree(pRoot1->left,pRoot2); // 未找到匹配的根節點以及匹配的子樹，則繼續向下遞歸if(!result) result=HasSubtree(pRoot1->right,pRoot2);return result;}//判斷2棵樹是否相同bool isSubtree(TreeNode* pRoot1, TreeNode* pRoot2){if(!pRoot2) return true; // 子樹遍歷完成（關鍵語句）if(!pRoot1) return false; // 主樹異常時的輸出（關鍵語句：提高魯棒性）bool result=true;if(pRoot1->val!=pRoot2->val) result=false; //根節點不同肯定不同if(result) result=isSubtree(pRoot1->left,pRoot2->left); //判斷兩顆樹的左子樹是否相同if(result) result=isSubtree(pRoot1->right,pRoot2->right);//判斷兩顆樹的右子樹是否相同return result;}
};

運行時間：3ms

占用內存：504k

python

# -*- coding:utf-8 -*-

第17題：

操作給定的二叉樹，將其變換為源二叉樹的鏡像。

解題思路：

從題目中給出的例子可以看出，其實就是對樹的每一層中雙親的左右孩子交換了一下。我們可以遞歸的訪問樹的每一層，然后交換每一層的雙親節點的左右孩子就可以。

• 遞歸的方法：先從根節點開始，交換根節點左右孩子節點，然后調用遞歸，依次遍歷樹的左子樹和右子樹，交換子樹中的孩子節點。

代碼實現：

c++

遞歸實現

class Solution {
public:void Mirror(TreeNode *pRoot) {//遞歸推出條件if(pRoot==NULL){return;}//交換根節點的兩個孩子TreeNode* tempNode;tempNode = pRoot->left;pRoot->left = pRoot->right;pRoot->right = tempNode;Mirror(pRoot->left);  //遞歸左子樹Mirror(pRoot->right); //遞歸右子樹}
};

運行時間：4ms

占用內存：468k

python

# -*- coding:utf-8 -*-
class Solution:# 返回鏡像樹的根節點def Mirror(self, root):# write code hereif root == None:return ;tempNode = TreeNode(-1)tempNode = root.leftroot.left = root.rightroot.right = tempNodeself.Mirror(root.left)self.Mirror(root.right)

運行時間：34ms

占用內存：5736k

第18題：

輸入一個矩陣，按照從外向里以順時針的順序依次打印出每一個數字，例如，如果輸入如下4 X 4矩陣： 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.

解題思路：

• 設定四個變量，分別指向行，列的起始點和終止點，然后將數據遍歷分成4個節階段，分別是：從左到右，從上到下，從右向左，從下到上，每個過程結束后，對應的指針都應該變化，循環執行，直到遍歷完全部的數據。

代碼實現：

c++

class Solution {
public:vector<int> printMatrix(vector<vector<int> > matrix) {vector<int>res;  //用來保存遍歷過的數據res.clear(); int row=matrix.size();//行數int collor=matrix[0].size();//列數//計算打印的圈數int circle=((row<collor?row:collor)-1)/2+1;//圈數for(int i=0;i<circle;i++){//從左向右打印for(int j=i;j<collor-i;j++)res.push_back(matrix[i][j]);         //從上往下的每一列數據for(int k=i+1;k<row-i;k++)res.push_back(matrix[k][collor-1-i]);//判斷是否會重復打印(從右向左的每行數據)for(int m=collor-i-2;(m>=i)&&(row-i-1!=i);m--)res.push_back(matrix[row-i-1][m]);//判斷是否會重復打印(從下往上的每一列數據)for(int n=row-i-2;(n>i)&&(collor-i-1!=i);n--)res.push_back(matrix[n][i]);}return res;}
};

運行時間：4ms

占用內存：468k

python

# -*- coding:utf-8 -*-

第19題：

定義棧的數據結構，請在該類型中實現一個能夠得到棧中所含最小元素的min函數（時間復雜度應為O（1））

解題思路：

• 定義一個輔助棧，這個棧頂元素始終是最小值。

代碼實現：

c++

class Solution {
public:stack<int> stack1,stack2;void push(int value) {stack1.push(value);//兩種情況下才將元素壓入輔助棧中if(stack2.empty())stack2.push(value);else if(value<=stack2.top()){stack2.push(value);}}void pop() {if(stack1.top()==stack2.top())stack2.pop();stack1.pop();}int top() {return stack1.top();       }int min() {return stack2.top();}};

運行時間：2ms

占用內存：472k

python

# -*- coding:utf-8 -*-
class Solution:def __init__(self):self.data = []self.minData = []def push(self, node):# write code hereself.data.append(node)if self.minData == [] or node < self.minData[-1]:self.minData.append(node)def pop(self):# write code hereif self.data[-1] == self.minData[-1]:self.minData.pop()self.data.pop()def top(self):# write code herereturn self.data[-1]def min(self):# write code herereturn self.minData[-1]

運行時間：31ms

占用內存：5624k

第20 題：

輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）

解題思路：

借用一個輔助的棧，遍歷壓棧順序，先講第一個放入棧中，這里是1，然后判斷棧頂元素是不是出棧順序的第一個元素，這里是4，很顯然1≠4，所以我們繼續壓棧，直到相等以后開始出棧，出棧一個元素，則將出棧順序向后移動一位，直到不相等，這樣循環等壓棧順序遍歷完成，如果輔助棧還不為空，說明彈出序列不是該棧的彈出順序。

舉例：

入棧1,2,3,4,5

出棧4,5,3,2,1

首先1入輔助棧，此時棧頂1≠4，繼續入棧2

此時棧頂2≠4，繼續入棧3

此時棧頂3≠4，繼續入棧4

此時棧頂4＝4，出棧4，彈出序列向后一位，此時為5，,輔助棧里面是1,2,3

此時棧頂3≠5，繼續入棧5

此時棧頂5=5，出棧5,彈出序列向后一位，此時為3，,輔助棧里面是1,2,3

….

依次執行，最后輔助棧為空。如果不為空說明彈出序列不是該棧的彈出順序

代碼實現：

c++

class Solution {
public:bool IsPopOrder(vector<int> pushV,vector<int> popV) {if(pushV.size() == 0) return false;  vector<int> stack;for(int i = 0,j = 0 ;i < pushV.size();){stack.push_back(pushV[i++]);while(j < popV.size() && stack.back() == popV[j]){  //當輔助棧的棧頂元素與彈出棧的相同，則將輔助棧的元素彈出，同時繼續遍歷彈出棧stack.pop_back();j++;}      }return stack.empty();}
};

運行時間：3ms

占用內存：380k

python

# -*- coding:utf-8 -*-