每日算法题：Day 31（Linux）
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()方法获取当前读取数据的中位数。
思路： 由于是让我们取出一个数据流的中位数，因此我们可以使用最大堆和最小堆，首先我们建立两个堆分别为最大堆和最小堆，首先我们要清楚的是两点问题：
- 两个堆的大小要么相等（偶数），要么相差为1（奇数），最大堆为较多的
- 如果想取出中位数，那么较小的数应该在最大堆，较大的数应该在最小堆，从而在奇数情况下，中位数为两个堆堆顶之和/2.0
因此我们每插入一个数据，首先和最大堆堆顶比较，如果大于，则将该数插入最小堆（存放较大的数），否则插入到最大堆，接着需要维护两个堆的大小，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】路由和网络连接方面的指令汇总
- ping命令用来检测两部主机之间的信道是否畅通；
- route命令用来显示目前本机路由表的内容，并对路由表作相应的修改；
- traceroute命令用来探测路由的经过；
- ifconfig命令用来检测和设置本机的网络接口；
- netstat命令用于显示与IP、TCP、UDP和ICMP协议相关的统计数据，一般用于检验本机各端口的网络连接情况；
【Linux】bash配置文件
- .bash_profile 类似于编程中的构造函数，当登录shell时，shell会寻找该文件做环境初始化。
- /etc/bash.bashrc 是在bash环境时.bash_profile的替补, 注意是在etc目录中，因此是所有用户都起作用的
- ~/.bashrc 只对当前home目录中的用户有效，即只对当前用户有效，与上一个要区别开！
- .bash_logout 类似于编程中的析构函数，当登录shell退出时，shell会寻找该文件，并按其指示办事。
- /etc/profile是系统文件,对系统下全体用户起作用
腾讯云开发者
