Hello Programmer

发表于 更新于 分类于

一、初级排序算法

1、选择排序

思路：找到数组中最小的元素，其次，将它和数组的第一个元素交换位置，再找第二小，如此往复。

有两个鲜明的特点： 运行时间和输入无关和 数据移动是最少的。

直接上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Selection {
    public static void sort(Comparable[] a) {
        //将a[]按照升序排列
        int N = a.length;  //数组长度
        for (int i = 0; i < N; i++) {
            //将a[i]和a[i + 1···N]中最小的元素交换
            int min = i;  //最小元素索引
            for (int j = i + 1; j < N; j++)
                if (less(a[j], a[min]))
                    min = j;
            exch(a, i, min);
        }
    }
    
    private static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }
    
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

2、插入排序

插入排序对于实际应用中常见的某些类型的非随机数组非常有效。依次找到最大的元素并移动到最末尾，然后再找第二大……

直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Insertion {
    public static void sort(Comparable[] a) {
        //将a[]按照升序排列
        int N = a.length;
        for (int i = 1; i < N; i++)
            //将a[i]插入到a[i-1]、a[i-2]、a[i-3]...之中
            for (int j = i; j > 0 && less(a[j], a[j-1]); j--)
                exch(a, j, j - 1);
    }

    private static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

3、希尔排序

二、归并排序

1、自顶向下的归并排序

2、自底向上的归并排序

3、排序算法的复杂度

三、快速排序

1、基本的算法

2、性能特点

3、算法改进

四、优先队列

有时候，我们不需要将所有的元素排序，例如手机要运行优先级高的程序，每次取优先级最高的程序出来运行就可以了，而不必将所有程序按照优先级排序。

这种情况下，需要一个合适的数据结构： 删除最大元素和 插入元素，这种数据结构叫做 优先队列。

1、堆的定义

数据结构二叉堆能够很好的实现优先队列的基本操作。在二叉堆数组中，每个元素要保证大于等于另外的两个特定位置的元素，相应的，这两个特定位置的元素又要保证大于各自位置特定两个位置的元素，如此套娃。

当一棵二叉树的每个结点都大于等于它的两个特定节点时，它被称为堆有序

2、堆的算法

3、堆排序

五、应用

发表于 更新于 分类于

题目链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/

犯了一个非常低级的错误，特意记录一下

题目描述

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如：给定二叉树 [3,9,20,null,null,15,7]

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回：

1
[3,9,20,15,7]

题目分析

很简单，就是用一个队列做辅助来实现层序遍历

代码

我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] levelOrder(TreeNode root) {
        if (root == null)
            return new int[0];
        Queue<TreeNode> list = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            list.offer(poll);
            if (poll.left != null)
                queue.offer(poll.left);
            if (poll.right != null)
                queue.offer(poll.right);
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++)
            result[i] = list.poll().val;
        return result;
    }
}

错误原因：

1
2
for (int i = 0; i < list.size(); i++)
  	result[i] = list.poll().val;

注意看上面这段代码，for循环里面的判断条件是 i < list.size()，而 list.size()大小是动态的，因为 list.poll().val！！！非常低级的一个错误

发表于 更新于 分类于

一、简介

容器是镜像的运行时实例

二、详解

1、启动一个简单的容器

启动容器的一个简单方式是：docker container run

启动一个简单的容器化版本的Ubuntu Linux

命令的基础格式为：docker container run <options> <im- age>:<tag> <app>

1
docker container run -it ubuntu:latest /bin/bash
  • -it表示使容器具备交互性并于终端进行连接
  • /bin/bash表示了运行在容器中的程序

有些指令无法执行，大部分容器镜像都是经过高度优化的，代表某些命令或者包没有安装

2、容器进程

3、容器生命周期

4、优雅地停止容器

先docker container stop容器，再docker container rm容器

5、利用重启策略进行容器的自我修复

  • always
  • unless-stopped
  • on-failed

6、web服务器示例

在8080端口启动一个简单的web服务

1
2
docker container run -d --name webserver -p 80:8080 \
nigelpoulton/pluralsight-docker-ci
  • -d表示后台模式启动
  • -p 80:8080表示将Docker主机的端口映射到容器内

7、查看容器详情

在上个例子中，我们并没有指定容器中具体的应用，但是容器却运行了一个简单的web服务

当构建镜像时，可以通过嵌入指令来列出希望容器运行时启动的默认应用

如下：

1
docker image inspect nigelpoulton/pluralsight-docker-ci

发表于 更新于 分类于

题目链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。

示例1

1
2
输入：[3,4,5,1,2]
输出：1

示例2

1
2
输入：[2,2,2,0,1]
输出：0

题目分析

依然是采用二分的思路，每次与两端的元素做对比，分三种结果：

  • 比最右边小
  • 比最左边大
  • 其他

代码

我写的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minArray(int[] numbers) {
        int low = 0;
        int high = numbers.length - 1;
        int pivot = 0;
        while(high >= low) {
            pivot = (low + high) / 2;
            if (numbers[pivot] < numbers[high]) {
                high = pivot;
            //错误一
            } else if (numbers[pivot] > numbers[low]) {
                //错误二
                low = pivot;
            } else {
                high--;
            }
        }
        return numbers[pivot];
    }
}

只需要将 low = pivot;改为 low = pivot + 1;便可以完美通过！

发表于 更新于 分类于

镜像与容器的关系

镜像可以理解为一种构建时（build-in）结构，容器可以理解为一种运行时（run-time）结构

查看镜像

1
docker image ls

拉取镜像

1
docker image pull ubuntu:latest

镜像命名

  • 镜像仓库服务

Docker镜像存储在镜像仓库服务（Image Registry）当中，Docker客户端的镜像仓库服务是可配置的，默认使用Docker Hub

镜像仓库服务包含多个镜像仓库（Image Repository）

一个镜像仓库包含多个镜像

  • 镜像命名与标签

只需要给出镜像的名字与标签，就能够在官方的仓库中定位一个镜像，如下拉取镜像的命令：

docker image pull :

1
2
# 从官方的Mongo库中拉取标签为3.3.11的镜像
docker image pull mongo:3.3.11
  • 为镜像打多个标签

使用-a获取一个仓库中所有的镜像

例如下面的命令中就是拉取标签为latest的镜像

1
docker image pull ubuntu:latest
  • 过滤docker image ls的输出内容

Docker提供--filter参数来过滤docker image ls命令返回的镜像列表内容

  • 通过CLI方式搜索Docker Hub

docker search命令允许通过CLI的方式搜索Docker Hub，读者可以通过“NAME”字段的内容进行匹配，并且基于返回内容中任意列的值进行过滤

1
docker search nigelpoulton

  • 镜像和分层

  • 共享镜像层

  • 根据摘要拉取镜像

发表于 更新于 分类于

知识点：

一、OSI七层模型

第一种模型是OSI七层模型，OSI为（Open System interconnect）的缩写，自上而下分别是应用层、表示层、会话层、传输层、网络层、数据链路层、物理层

物理层：网卡，网线，集线器，中继器，调制解调器

数据链路层：网桥，交换机

网络层：路由器

1、物理层

  • 物理层的媒体包括电缆、光纤等

  • 正因为物理媒体会有很多差异，所以物理层的作用正是尽可能地屏蔽这些差异，使上面的数据链路曾感觉不到这些差异

  • 在这一层，数据的单位为比特（bit）

2、数据链路层

本章重点：

（1）数据链路层的使用的信道主要有以下两种类型： 点对点信道、 广播信道

（2）数据链路层的协议有很多种，但有三个基本问题则是共同的： 封装成帧、透明传输、差错检测

  • 封装成帧

    就是在数据前后分别添加首部和尾部，这样就构成了帧

  • 透明传输

    用字节填充法（在非帧边界的控制字符插入转义字符）解决透明传输的问题

  • 差错检测

    在数据链路层广泛使用了循环冗余检验CRC的检错技术

（3）以太网MAC层硬件地址

（4）适配器、转发器、集线器、网桥、以太网交换机的作用和使用场景

3、网络层

主要的协议有ip，主要是将报文封装成ip数据报

网络层向上层只提供简单灵活的、无连接的、尽最大努力交付的数据报服务

A、网际协议IP

与IP协议配套使用的还有三个协议：

  • 地址解析协议ARP
  • 网际控制报文协议ICMP
  • 网际组管理协议IGMP

IP数据报格式

4、传输层

IP数据报中的首部明确标记了两个主机的IP地址，但是真正进行通信的是进程。根据应用程序的不用需求，运输层需要两种不同的运输协议，即 面向连接的TCP和 无连接的UDP。TCP数据单元为段而UDP中数据单元为数据报。

TCP面向连接、全双工面向字节流，每一条TCP连接有两个端点，这两个端点是什么呢？不是主机，也不是主机IP，不是应用进程，也不是运输层的协议端口。TCP链接的端点叫做 套接字（socket）= IP地址：端口号

TCP的三次握手

TCP的四次挥手

TCP的可靠传输的实现：1.滑动窗口 2.超时重传 3.选择确认 SACK

TCP的流量控制：滑动窗口

TCP的拥塞控制：慢开始与拥塞避免

UDP是无连接 尽最大努力交付 面向报文 首部开销小 8字节 比TCP的20个字节小

5、会话层

会话单位的控制层，其主要功能是按照在应用进程之间约定的原则，按照正确的顺序收、发数据，进行各种形态的对话。

6、表示层

数据表示形式的控制层，其主要功能是把应用层提供的信息变换为能够共同理解的形式，提供字符代码、数据格式、控制信息格式、加密等的统一表示。

7、应用层

OSI参考模型的最高层。其功能是实现应用进程（如用户程序、终端操作员等）之间的信息交换。同时，还具有一系列业务处理所需要的服务功能。应用层许多协议都是基于客户服务器方式。

发表于 更新于 分类于

第一条：用静态工厂的方法代替构造器

第二条：遇到多个构造器参数时要考虑使用构造器

第三条：用私有构造器或者枚举类型强化Singleton

第四条：通过私有构造器强化不可实例化的对象

第五条：优先考虑依赖注入来使用资源

第六条：避免创建不必要的对象

第七条：消除过期对象的引用

第八条：避免使用终结方法和清除方法

第九条：try-with- resources优先try-finally

发表于 更新于 分类于

一、进程的概念

现代操作系统的重要特点是在保证安全的前提下，程序并发执行，以及系统所拥有的资源被共享和系统用户的随机的使用

1、程序的并发执行

宏观上看是多个程序同时执行，微观上看是多个程序分时占用CPU，我们称这种程序执行的方式为 并发执行

2、进程的定义

一个进程也就是一个正在执行程序的实例

进程是并发执行的程序在执行过程中分配和管理资源的基本单位

进程和程序的区别与联系：

  • 进程是一个动态概念，而程序是一个静态概念。程序是指令的有序集合。而进程则强调执行过程，被动态创建被调度执行后消亡

    如果将程序比作菜谱，那么进程是按照菜谱炒菜的过程

  • 进程具有并发特征，而程序没有

  • 进程是竞争计算机系统资源的基本单位，从而其并发性收到系统的制约

  • 不同的进程可以包含同一个程序

3、进程的创建

（1）系统初始化

（2）正在运行的程序执行了系统调用

（3）用户请求创建一个新进程

（4）一个批处理作业的初始化

二、进程的描述

一个进程是一个程序对某个数据集的执行过程，是分配资源的单位。

进程的静态描述由三部分组成： 进程控制块（PCB）、程序段、数据

1、进程的控制块

进程的PCB是系统感知进程的唯一实体，它包括以下信息：

  • 描述信息

    进程名或进程标识号、用户名或用户标识号、家族关系

  • 控制信息

    进程当前状态（五种状态）、进程优先级、程序开始地址、各种计时信息、通信信息

  • 资源管理信息

    PCB中包含最多的就是资源管理信息，包括有关存储器的信息、使用输入输出设备的信息、有关文件系统的信息

  • CPU现场保护结构

2、进程上下文

3、进程上下文切换

提出进程上下文的概念就是为了进程上下文的切换

4、进程空间与大小

任意进程都有自己的地址空间，该空间称为进程空间或者虚空间

三、进程的状态及转换

1、进程状态

五种基本状态：初始态、执行状态、等待状态、就绪状态、终止状态

2、进程状态转换

四、进程控制

1、进程创建与撤销

2、进程的阻塞与唤醒

五、进程互斥

1、资源共享所引起的制约

2、互斥的加锁实现

3、信号量与P、V原语

4、用P、V原语实现进程互斥

六、进程同步

1、同步的概念

2、私用信号量

3、用P、V原语操作实现同步

4、生产者-消费者问题

七、进程通信

1、进程的通信方式

2、消息缓冲机制

3、邮箱通信

4、进程通信的实例-和控制台通信

5、进程通信的实例-管道

八、死锁问题

1、死锁的概念

2、死锁的消除方法

九、线程的概念

1、为什么要引入线程

2、线程的基本概念

3、线程与进程的区别

4、线程的适用范围

十、线程分类与执行

1、线程的分类

2、线程的执行特性

发表于 更新于 分类于

一、文件查找之find命令

1、语法格式

2、选项参数对照表

表格一
表格二

3、示例实操

  • 查找 /etc目录下以conf结尾的文件

    1
    find /etc -name '*.conf'

  • 查找/etc目录下大于1M的文件

    1
    find /etc -size +

  • 从二级子目录开始查找文件（f）/目录（d）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
      find . -mindepth 2 -type f

    #### 4、操作

    #### （1）-print

    打印输出，默认选项

    #### （2）-exec

    对搜索到的文件执行特定的操作，格式为` -exec 'command {} \;'`

    - 搜索`/etc`下的文件（非目录），文件以conf结尾，且大于10k，然后将其删除

      ```shell
      find ./etc/ -type f -name '*.conf' -size +10k -exec rm -f {} \;

  • 搜索条件和例一一样，将其复制到/root/conf目录下

    1
    find ./etc/ -size +10k -type f name '*.conf' -exec cp {} /root/conf/ \;

  • 将/var/log目录下以’*.log’结尾的文件且更改时间在七天以上的删除

    1
    find /var/log/ -name '*.log' -mtime +7 -exec rn -rf {} \;
（3）-ok

和exec功能一样，但是每次操作都会给用户提示

5、逻辑运算符

  • -a

    与

  • -o

    或

  • -not / !

示例：查找当前目录下，属主不是hdfs的所有文件

1
find . -not -user hdfs | find . ! -user hdfs

6、find、locate、whereis和which总结及适用场景分析

（1）locate
  • 文件查找命令，所属软件包是mlocate
  • 不同于find命令是在整块磁盘中搜索，locate命令是在数据库文件中查找
  • find默认是全部匹配，locate是默认匹配部分

通过updatedb命令更新数据库

（2）whereis
（3）which
作用：只返回二进制文件
（4）比较分析
命令 场景 分析
find 查找某一类文件，比如文件名部分一致 功能强大，速度慢
locate 只查找单个文件 功能强大，速度快
whereis 查找程序的可执行文件、帮助文档等 不常用
which 只查找程序的可执行文件 常用于查找程序的绝对路径