目錄

第61題：

給定一棵二叉搜索樹，請找出其中的第k小的結點。例如， （5，3，7，2，4，6，8） 中，按結點數值大小順序第三小結點的值為4。

解題思路：

• 由于是二叉搜索樹，其節點存放的值是有一定的規律的，所以我們可以使用一個數組存放二叉搜索樹的中序遍歷結果，然后直接將數字的第K個結果給出即可。時間復雜度為O(N),空間復雜度也為O(N)。

代碼實現：

c++

class Solution {
public:int index = 0;TreeNode* KthNode(TreeNode* pRoot, int k){if(pRoot != NULL){TreeNode* node = KthNode(pRoot->left , k);if(node != NULL) return node;index ++;if(index == k) return pRoot;node = KthNode(pRoot->right , k);if(node != NULL) return node;}return NULL;} 
};

運行時間：4ms

占用內存：608k

class Solution {
public:TreeNode* KthNode(TreeNode* pRoot, unsigned int k){if(pRoot==NULL||k<=0) return NULL;vector<TreeNode*> vec;Inorder(pRoot,vec);if(k>vec.size())return NULL;return vec[k-1];}//中序遍歷，將節點依次壓入vector中void Inorder(TreeNode* pRoot,vector<TreeNode*>& vec){if(pRoot==NULL) return;Inorder(pRoot->left,vec);vec.push_back(pRoot);Inorder(pRoot->right,vec);} 
};

python

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

第62題：

如何得到一個數據流中的中位數？如果從數據流中讀出奇數個數值，那么中位數就是所有數值排序之后位于中間的數值。如果從數據流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值。我們使用Insert()方法讀取數據流，使用GetMedian()方法獲取當前讀取數據的中位數。

解題思路：

/**
* 插入有兩種思路：
* 1：直接插入大堆中，之后若兩堆尺寸之差大于1(也就是2)，則從大堆中彈出堆頂元素并插入到小堆中
* 若兩隊之差不大于1，則直接插入大堆中即可。
* 2：奇數個數插入到大堆中，偶數個數插入到小堆中，
* 但是 可能會出現當前待插入的數比小堆堆頂元素大，此時需要將元素先插入到小堆，然后將小堆堆頂元素彈出并插入到大堆中
* 對于偶數時插入小堆的情況，一樣的道理。why?
* 因為要保證最大堆的元素要比最小堆的元素都要小。
* @param num
*/

代碼實現：

c++

class Solution {
public:priority_queue<int, vector<int>, less<int> > p;  //小堆priority_queue<int, vector<int>, greater<int> > q; //大堆void Insert(int num){if(p.empty() || num <= p.top()) p.push(num);else q.push(num);if(p.size() == q.size() + 2) q.push(p.top()), p.pop();if(p.size() + 1 == q.size()) p.push(q.top()), q.pop();}double GetMedian(){ return p.size() == q.size() ? (p.top() + q.top()) / 2.0 : p.top();}};

運行時間：6ms

占用內存：484k

python

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

第63題：

給定一個數組和滑動窗口的大小，找出所有滑動窗口里數值的最大值。例如，如果輸入數組{2,3,4,2,6,2,5,1}及滑動窗口的大小3，那么一共存在6個滑動窗口，他們的最大值分別為{4,4,6,6,6,5}； 針對數組{2,3,4,2,6,2,5,1}的滑動窗口有以下6個： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

解題思路：

• 暴力解法：直接使用滑動窗的原理，得出每個窗口的數據，然后給出最大值即可。時間復雜度為O(N^2).

代碼實現：

c++

python

# -*- coding:utf-8 -*-
class Solution:def maxInWindows(self, num, size):# write code hereresList = []sampleNum = (len(num)-size + 1)if sampleNum <= 0 or size <=0:return resListfor i in range(sampleNum):resList.append(max(num[i:i+size]))return resList

運行時間：31ms

占用內存：5728k

第64題：

請設計一個函數，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。如果一條路徑經過了矩陣中的某一個格子，則之后不能再次進入這個格子。 例如 a b c e s f c s a d e e 這樣的3 X 4 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字符串的第一個字符b占據了矩陣中的第一行第二個格子之后，路徑不能再次進入該格子。

解題思路：

代碼實現：

c++

class Solution {bool hasPathRecu(char* matrix, int rows, int cols, int row, int col, char *str, int length, vector<bool> used){if(length==strlen(str))return true;if(row<0||row>=rows||col<0||col>=cols)return false;int index = col + row*cols;bool result = false;if( !used[index] && matrix[index]==str[length]){used[index] = true;result = hasPathRecu(matrix, rows, cols, row-1, col, str, length+1, used)|| hasPathRecu(matrix, rows, cols, row+1, col, str, length+1, used)||hasPathRecu(matrix, rows, cols, row, col+1, str, length+1, used)||hasPathRecu(matrix, rows, cols, row, col-1, str, length+1, used);used[index] = false;}if(result)return true;return false;}
public:bool hasPath(char* matrix, int rows, int cols, char* str){vector<bool> used(strlen(matrix),false);if(str==NULL) return true;for(int i=0;i<rows;i++){for(int j=0;j<cols;j++){if(hasPathRecu(matrix, rows, cols, i, j, str, 0, used))return true;}}return false;}
};

運行時間：5ms

占用內存：364k

python

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

第65題：

地上有一個m行和n列的方格。一個機器人從坐標0,0的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能進入行坐標和列坐標的數位之和大于k的格子。 例如，當k為18時，機器人能夠進入方格（35,37），因為3+5+3+7 = 18。但是，它不能進入方格（35,38），因為3+5+3+8 = 19。請問該機器人能夠達到多少個格子？

解題思路：

代碼實現：

c++

回溯法

class Solution {bool hasPathRecu(char* matrix, int rows, int cols, int row, int col, char *str, int length, vector<bool> used){if(length==strlen(str))return true;if(row<0||row>=rows||col<0||col>=cols)return false;int index = col + row*cols;bool result = false;if( !used[index] && matrix[index]==str[length]){used[index] = true;result = hasPathRecu(matrix, rows, cols, row-1, col, str, length+1, used)|| hasPathRecu(matrix, rows, cols, row+1, col, str, length+1, used)||hasPathRecu(matrix, rows, cols, row, col+1, str, length+1, used)||hasPathRecu(matrix, rows, cols, row, col-1, str, length+1, used);used[index] = false;}if(result)return true;return false;}
public:bool hasPath(char* matrix, int rows, int cols, char* str){vector<bool> used(strlen(matrix),false);if(str==NULL) return true;for(int i=0;i<rows;i++){for(int j=0;j<cols;j++){if(hasPathRecu(matrix, rows, cols, i, j, str, 0, used))return true;}}return false;}
};

運行時間：3ms

占用內存：476k

動態規劃法

public class Solution {public int movingCount(int threshold, int rows, int cols){if(threshold<0)return 0;boolean [][] dp=new boolean[rows+1][cols+1];dp[0][0]=true;for(int i=1;i<=rows;i++){//初始化if(dp[i-1][0]&&canreach(threshold,i,0)){dp[i][0]=true;}else {dp[i][0]=false;}}for(int i=1;i<=cols;i++){//初始化if(dp[0][i-1]&&canreach(threshold,0,i)){dp[0][i]=true;}else {dp[0][i]=false;}}for(int i=1;i<=rows;i++){for(int j=1;j<=cols;j++){if((dp[i-1][j]&&canreach(threshold, i, j))||(dp[i][j-1]&&canreach(threshold, i, j))){dp[i][j]=true;}else {dp[i][j]=false;}}}int count=0;for(int i=0;i<rows;i++){for(int j=0;j<cols;j++){if(dp[i][j])count++;}}      return count;      }public  boolean canreach(int threshold, int x, int y) {int sum = 0;while (x > 0) {sum += x % 10;x /= 10;}while (y > 0) {sum += y % 10;y /= 10;}return sum <= threshold;}
}

python

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