怎么免费创建一个网站,微信小程序怎么盈利,自己做ppt网站,软件开发外包哪个公司的好文章目录目录第61题#xff1a;解题思路#xff1a;代码实现#xff1a;cpython第62题#xff1a;解题思路#xff1a;代码实现#xff1a;cpython第63题#xff1a;解题思路#xff1a;代码实现#xff1a;cpython第64题#xff1a;解题思路#xff1a;代码实现解题思路代码实现cpython第62题解题思路代码实现cpython第63题解题思路代码实现cpython第64题解题思路代码实现cpython第65题解题思路代码实现c回溯法动态规划法python目录
第61题
给定一棵二叉搜索树请找出其中的第k小的结点。例如 5372468 中按结点数值大小顺序第三小结点的值为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(pRootNULL||k0) return NULL;vectorTreeNode* vec;Inorder(pRoot,vec);if(kvec.size())return NULL;return vec[k-1];}//中序遍历将节点依次压入vector中void Inorder(TreeNode* pRoot,vectorTreeNode* vec){if(pRootNULL) 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_queueint, vectorint, lessint p; //小堆priority_queueint, vectorint, greaterint 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:isize]))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, vectorbool used){if(lengthstrlen(str))return true;if(row0||rowrows||col0||colcols)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, length1, used)|| hasPathRecu(matrix, rows, cols, row1, col, str, length1, used)||hasPathRecu(matrix, rows, cols, row, col1, str, length1, used)||hasPathRecu(matrix, rows, cols, row, col-1, str, length1, used);used[index] false;}if(result)return true;return false;}
public:bool hasPath(char* matrix, int rows, int cols, char* str){vectorbool used(strlen(matrix),false);if(strNULL) return true;for(int i0;irows;i){for(int j0;jcols;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因为3537 18。但是它不能进入方格35,38因为3538 19。请问该机器人能够达到多少个格子
解题思路 代码实现
c
回溯法
class Solution {bool hasPathRecu(char* matrix, int rows, int cols, int row, int col, char *str, int length, vectorbool used){if(lengthstrlen(str))return true;if(row0||rowrows||col0||colcols)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, length1, used)|| hasPathRecu(matrix, rows, cols, row1, col, str, length1, used)||hasPathRecu(matrix, rows, cols, row, col1, str, length1, used)||hasPathRecu(matrix, rows, cols, row, col-1, str, length1, used);used[index] false;}if(result)return true;return false;}
public:bool hasPath(char* matrix, int rows, int cols, char* str){vectorbool used(strlen(matrix),false);if(strNULL) return true;for(int i0;irows;i){for(int j0;jcols;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(threshold0)return 0;boolean [][] dpnew boolean[rows1][cols1];dp[0][0]true;for(int i1;irows;i){//初始化if(dp[i-1][0]canreach(threshold,i,0)){dp[i][0]true;}else {dp[i][0]false;}}for(int i1;icols;i){//初始化if(dp[0][i-1]canreach(threshold,0,i)){dp[0][i]true;}else {dp[0][i]false;}}for(int i1;irows;i){for(int j1;jcols;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 count0;for(int i0;irows;i){for(int j0;jcols;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 -*-
