Day 31, Linux知识点走起~
1
编程题
【剑指Offer】二叉搜索树的第k个结点
给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8)中,按结点数值大小顺序第三小结点的值为4。
思路: 由于根据二叉搜索树的特性,其中序遍历正好是一个排好序的序列,从小到大依次排序,因此其第k个最小节点则为数组第k-1个数(数组从零开始索引)。一般功能修改的话,建议在非递归遍历版本进行修改,其思路更加清晰,我们只需要设置一个索引index,stack每次做pop操作后,让index+1,如果等于k,则输出节点即可!
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
TreeNode* KthNode(TreeNode* pRoot, int k)
{
if(pRoot == nullptr) return nullptr;
stack<TreeNode*> sta;
TreeNode* cur = pRoot;
int index = ;
while(!sta.empty() || cur != nullptr){
if(cur != nullptr){
sta.push(cur);
cur = cur->left;
}else{
cur = sta.top();
sta.pop();
if(index++ == k){
return cur;
}
cur = cur->right;
}
}
return nullptr;
}
};
【剑指Offer】数据流中的中位数
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。
思路: 由于是让我们取出一个数据流的中位数,因此我们可以使用最大堆和最小堆,首先我们建立两个堆分别为最大堆和最小堆,首先我们要清楚的是两点问题:
因此我们每插入一个数据,首先和最大堆堆顶比较,如果大于,则将该数插入最小堆(存放较大的数),否则插入到最大堆,接着需要维护两个堆的大小,maxheap.size = minheap.size或者maxheap.size = minheap.size+1. 如果不满足,则将多的堆的堆顶pop出来放入到少的堆中。
class Solution {
public:
void Insert(int num)
{
if(maxheap.empty() || num < maxheap.top()) maxheap.push(num);
else minheap.push(num);
if(maxheap.size() == minheap.size()+){
minheap.push(maxheap.top());
maxheap.pop();
}
if(maxheap.size() + == minheap.size()){
maxheap.push(minheap.top());
minheap.pop();
}
}
double GetMedian()
{
return maxheap.size() == minheap.size() ? (maxheap.top()+minheap.top()) / 2.0 : maxheap.top();
}
private:
priority_queue<int, vector<int>, less<int>> maxheap;
priority_queue<int, vector<int>, greater<int>> minheap;
};
2
概念题
【Linux】ssh和scp命令的区别??
ssh命令用于Linux机器的远程登录,格式如下: ssh [-l login_name][-p port][user@]hostname
scp是Linux系统基于ssh登录后进行远程文件拷贝的命令 scp file_source file_target
ssh user@被监控主机ip "uptime" :可以查看远程Linux系统运行了多长时间,uptime表示当前Linux机器运行了多长时间
【Linux】路由和网络连接方面的指令汇总
【Linux】bash配置文件