专栏首页算法工程师之路每日算法题:Day 31(Linux)

每日算法题: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. 两个堆的大小要么相等(偶数),要么相差为1(奇数),最大堆为较多的
  2. 如果想取出中位数,那么较小的数应该在最大堆,较大的数应该在最小堆,从而在奇数情况下,中位数为两个堆堆顶之和/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是系统文件,对系统下全体用户起作用

本文分享自微信公众号 - 算法工程师之路(Zleopard7319538)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • mongodb常用的两种group方法,以及对结果排序

    版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    张凝可
  • Qt 显示视频流——安装ffmpeg(一)

    最终使用的是这样的结构:ffmpeg从USB免驱相机中获取视频流,然后推流到nginx服务器上。最后Qt使用WebView拉取Url中的视频流。

    用户5908113
  • CentOS6.X下Docker安装笔记 顶

    由于Selinux和LXC有冲突,所以需要禁用selinux.编辑/etc/selinux/config,设置两个关键变量.

    白石
  • (WJW)etcd v3 集群最佳操作指南 顶

    假设一个节点node2异常重启,可以执行/opt/app/etcd/run_etcd.sh脚本命令正常起来

    白石
  • Qt显示视频流——(三)

    之前的两次我们已经搭建好了nginx+rtmp服务和ffmpeg推流工具,本次进行最后一步结合Qt显示视频流。

    用户5908113
  • Docker安装教程

    Web 应用的自动化打包和发布。自动化测试和持续集成、发布。在服务型环境中部署和调整数据库或其他的后台应用。从头编译或者扩展现有的 OpenShift 或 Cl...

    微笑的小小刀
  • 使用MediaPipe进行设备上的实时手部跟踪

    能够感知手的形状和运动,这是改善各种技术领域和平台的用户体验的重要组成部分。例如,它可以形成手语理解和手势控制的基础,并且还可以在增强现实中实现物理世界之上的数...

    代码医生工作室
  • CentOS下Redis高可用安装笔记 顶

    mkdir /etc/keepalived/scripts/ vi /etc/keepalived/scripts/redis_check.sh

    白石
  • 基于外部ZooKeeper的GlusterFS作为分布式文件系统的完全分布式HBase集群安装指南

    192.168.1.85 hbase85 #hbase-regionserver,zookeeper

    白石
  • Docker入门

    我们了解到了Docker 的一些基本知识点,它的一些核心概念,Docker的使用安装等。此篇文章我们对 Docker 进行入门讲解

    用户6070864

扫码关注云+社区

领取腾讯云代金券