思路

把课程看作图中的节点，所有所需学习的课程构成有向图，问题转化为查看图是否是有向无环图。

拓扑排序: 对有向无环图的顶点进行排序，使得每一条有向边均有边起点定点在有向边终点之前。

bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import collections
def canFinish(numCourses, prerequisites):
    # 入度表和邻接表
    indeg, adj = [0 for _ in range(numCourses)], [[] for _ in range(numCourses)]
    # 构建入度表和有向图邻接表
    for e, s in prerequisites:
        indeg[e] += 1
        adj[s].append(e)
    # 查找入度为0的节点
    queue = collections.deque()
    for i in range(len(indeg)):
        if indeg[i] == 0:
            queue.append(i)
    # bfs
    while queue:
        s = queue.popleft()
        numCourses -= 1
        for i in adj[s]:
            indeg[i] -= 1
            if indeg[i] == 0:
                queue.append(i)
    return numCourses == 0

dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import collections
def canFinish(numCourses, prerequisites):
    # 邻接表
    adj = [[] for _ in range(numCourses)]
    # 构建有向图邻接表
    for e, s in prerequisites:
        adj[s].append(e)
    flags = [0 for _ in range(numCourses)]

    # dfs
    def dfs(i, flags, adj):
        if flags[i] == -1: return True
        if flags[i] == 1: return False
        flags[i] = 1
        for j in adj[i]:
            if not dfs(j, flags, adj): return False
        flags[i] = -1
        return True
    
    for i in range(numCourses):
        if not dfs(i, flags, adj): return False
    return True

SQL: Structured Query Language

RDBMS: Relational Database Management System

查看命令

1. 查看数据库

1

use your_database_name;

2. 设置使用的字符集

1

set names utf-8;

select

用于从数据库中选取数据

1
2
3
4
5
6
7

# 1.
select * 
from table_name;

# 2.
select column_name, column_name 
from table_name;

select distinct

用于返回唯一不同的值(去重子集)。

1
2

select distinct column_name, column_name 
from table_name;

where

用于过滤记录

1
2
3

select column_name, column_name 
from table_name 
where column_name operator value;

and / or

用于基于一个以上的条件对记录进行过滤

如果所有条件都成立，and运算符显示一条记录。

如果有一个条件成立，or运算符显示一条记录。

1
2
3
4

select * 
from table_name
where column_name operator value 
or / and column_name operator value;

order by

用于对结果集进行排序

对结果集按照一个列或者多个列进行排序。

默认按照升序对结果进行排序。

需要按照降序排列， 使用desc关键字。

1
2
3

select column_name, column_name 
from table_name
order by column_name, column_name asc / desc;

insert into

用于向表中插入新纪录。

1
2
3
4
5
6
7

# 1. 无需指定要插入数据的列名,只需要提供被插入的值即可;
insert into table_name
values (value1, value2, ..., valuen);

# 2. 需要指定列名及被插入的值.
insert into table_name (column1, column2, ..., columnn)
values (value1, value2, ..., valuen);

update

用于更新表中已存在的记录。

1
2
3

update table_name
set column1=value1, column2=value2
where some_column = some_value;

delete

用于删除表中的记录

1
2

delete from table_name
where some_column=some_value;

select top / limit / rownum

select top

select top是SQL Server使用的语句，并非所有数据库系统都支持。mysql支持limit

create database

alter database

create table

alter table

drop table

create index

drop index

前置

1
2
3
4

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

递归

1
2
3
4
5
6

def reverseList(head):
    if not head or not head.next: return head
    end = reverseList(head.next)
    head.next.next = head
    head.next = None
    return end

迭代 1

1
2
3
4
5
6
7
8

def reverseList(head):
    if not head or not head.next: return head
    pre, cur, nex = None, head, head.next
    while nex:
        cur.next = pre
        pre, cur, nex = cur, nex, nex.next
    cur.next = pre
    return cur

迭代 2

1
2
3
4
5
6
7
8

def reverseList(head):
    if not head or not head.next: return head
    pre, cur, nex = None, head, head.next
    while cur:
        cur.next = pre
        pre, cur = cur, nex
        if nex: nex = nex.next
    return pre

dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def numIslands(grid):
    def dfs(grid, i, j):
        if not 0 <= i < width or not 0 <= j < height or grid[i][j] == "0": return
        grid[i][j] = "0"
        dfs(grid, i + 1, j)
        dfs(grid,i - 1, j)
        dfs(grid,i, j + 1)
        dfs(grid,i, j - 1)

    width, height = len(grid), len(grid[0])
    ret = 0
    for i in range(width):
        for j in range(height):
            if grid[i][j] == "0":
                continue
            dfs(grid, i, j)
            ret += 1
    return ret

bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def numIslands(grid):
    def bfs(grid, i, j):
        queue = [[i, j]]
        while queue:
            for _ in range(len(queue)):
                w, h = queue.pop(0)
                if not 0 <= w < width or not 0 <= h < height or grid[w][h] == "0":
                    continue
                queue.append([w + 1, h])
                queue.append([w - 1, h])
                queue.append([w, h + 1])
                queue.append([w, h - 1])
                grid[w][h] = "0"

    width, height = len(grid), len(grid[0])
    ret = 0
    for i in range(width):
        for j in range(height):
            if grid[i][j] == "0":
                continue
            bfs(grid, i , j)
            ret += 1
    return ret

动态规划方程

状态转移: $ f(i) = max(f(i - 2) + cur, f(i - 1)) $

初始化: $dp[0]=0,dp[1]=nums[0]$

一维动态规划

1
2
3
4
5
6
7

def rob(nums):
    # 动态规划
    dp = [0] * (len(nums) + 1)
    dp[1] = nums[0]
    for i in range(1, len(nums)):
        dp[i + 1] = max(nums[i] + dp[i - 1],dp[i])
    return dp[-1]

空间优化动态规划

1
2
3
4
5
6
7

def rob(nums):
    # 动态规划
    ppre, pre, cur = 0, nums[0], 0
    for i in range(1, len(nums)):
        cur = max(nums[i] + ppre, pre)
        ppre, pre = pre, cur
    return pre

软件测试 黑盒测试

黑盒测试是一种软件测试技术，它可以检查软件的功能，而不会窥视其内部结构或编码。其主要来源是用户声明的要求规范。

在此方法中，测试人员选择一个函数并提供输入值以检查它的功能，并检查该函数是否给出了预期的输出。如果函数产生正确的输出，则在测试中传递，否则测试失败。测试团队将结果报告给开发团队，然后测试下一个功能。如果出现严重问题，在完成所有功能测试的测试后，会将测试结果返回给开发团队进行修正。

1. 黑盒测试基于要求的规范，因此在开始的时候进行检查。

2. 测试人员通过选择有效和无效的输入值来检查软件是正确还是错误的处理它们，从而创建肯定的测试场景和不利的测试场景。

3. 测试人员开发各种测试用例: 决策表，所有对测试，等效划分，误差估计，因果图等。

4. 包括执行所有测试用例。

5. 测试仪将预期输出与实际输出进行比较。

6. 最后一步，如果软件中存在任何缺陷，则将其修复并再次测试。

测试程序

黑盒测试的测试过程是测试人员对软件工作有特定知识的一种过程，它开发测试用例以检查软件功能的准确性。

此过程不需要软件的编程知识。所有测试用例都是通过考虑特定函数的输入输出来设计的。测试人员知道特定输入的输出，但不知道结果是怎样产生的。

测试用例

测试用例是根据要求的规范创建的。测试用例通常是根据软件的工作描述创建的，包括要求，设计参数和其他规范。

对于测试，测试设计者通过采用有效输入值和不利测试场景来选择测试场景，方法是采用无效输入值来确定正确的输出。

测试用例主要用于功能测试，也可以用于非功能测试。

测试用例是由测试团队设计的，没有任何软件开发团队的参与。

黑盒测试使用的技术

决策表技术

决策表技术是用于黑盒测试的用例设计技术之一，是一种系统方法，以表格形式捕获各种输入组合及其各自的系统行为。

决策表又称因果表，用于系统的选择测试用例，能够节省测试时间，并为软件应用程序的测试区域提供良好的覆盖。

决策表技术适用于在两个和两个以上输入之间具有逻辑关系的函数。

该技术与输入的正确组合有关，并确定各种输入组合的结果。要通过决策表技术设计测试用例，需要将条件视为输入，将操作视为输出。

在使用决策表技术时，测试人员确定预期输出，如果函数产生预期输出，则在测试中传递，如果不是，则失败。将失败的软件发送回开发团队以修复缺陷。

边界值分析技术

边界值分析是用于黑盒测试用例设计技术之一。

边界值分析用于测试边界值，因为边界附近的输入值具有较高的误差机会。

边界值是包含变量上限和下限的值。

边界值的测试是通过制作有效和无效的分区来完成的。测试无效分区是因为在不利条件下测试输出也是必要的。

在使用边界值分析技术时，软件系统接收有效数字并提供所需的输出，则软件系统将在测试中传递。如果不是，则不成功。在另一种情况下，软件系统不应接受无效数字。如果输入的数字无效，则应显示错误信息。如果正在测试的软件遵循所有测试指南和规范，则将其发送给发布团队，否则发送给开发团队以修复缺陷。

状态转化技术

状态转换的一般意义是相同情况的不同形式，状态转换方法也是如此。

当不同的输入值赋予相同的函数时，它用于捕获软件应用程序的行为。

使用相同的函数，但每次输出不同时，称为状态转换。

在测试软件应用程序的情况下，此方法测试函数是否遵循进入不同输入的状态转换规范。适用于那些提供访问应用程序的特定尝试次数的应用程序类型。

成对测试技术

成对测试技术也称为配对测试。

适用于测试所有可能的离散值组合。

用于测试使用复选框输入，单选按钮输入的应用程序，列表框，文本框等。

因果测试技术

因果图来自黑盒测试技术，强调了给定结果与影响结果的所有因素之间的关系。用于编写动态测试实例。

当代码根据用户输入动态运行时，将使用动态测试用例。

因果图基于一系列需求，用于确定可覆盖软件最大测试区域的最小可能测试用例。

主要优点是减少了测试执行的时间和成本。

该技术旨在减少测试用例的数量，但仍覆盖所有必要的测试用例，覆盖范围大，以达到所需的应用程序质量。

因果图技术通过使用AND，OR和NOT等逻辑运算符将需求规范转换为输入和输出条件之间的逻辑关系。

在给定情况的因果图后，测试人员需要将原因和结果转换为逻辑语句，然后设计因果图。如果函数根据输入(原因)给出输出(效果)，则认为它是无缺陷，如果不这样做，则将其发送给开发团队指正。

步骤总结：

1. 画出效果和圆圈；
2. 从效果开始，然后选择导致此效果的原因。
3. 最后绘制相互排斥的原因(通过一种效应和一种原因直接连接的独占原因)。
4. 使用逻辑门绘制动态测试用例。

等效分区技术

暴力hash解法

1
2
3
4
5
6
7
8
9
10
11

def majorityElement(nums):
    # 假设只有两个数
    save = {}
    for num in nums:
        if num in save.keys():
            save[num] += 1
        else:
            save[num] = 1
    
    save = {v: k for k, v in save.items()}
    return save[max(save.keys())]

摩尔投票法

1
2
3
4
5
6
7
8
9
10
11
12

def majorityElement(nums):
    # 假设只有两个数
    cand, count = nums[0], 0
    for num in nums:
        if cand == num:
            count += 1
        else:
            count -= 1
            if count == 0:
                cand, count = num, 1
    
    return cand

物理层

物理层考虑的是怎样才能在连接各种计算机的传输媒体上传输数据比特流。需要尽可能屏蔽计算机网络中的硬件设备和传输媒体以及通信手段的不同，使得物理层上面的数据链路层感觉不到这些差异，让数据链路层只需要考虑如何完成本层的协议和服务，不必考虑网络具体的传输媒体和通信手段。

物理层规程(procedure)指物理层的协议。

物理层的主要任务是确定与传输媒体的借口有关的一些特性：

1. 机械特性: 指明接口所用接线器的形状和尺寸，引脚数目和排列，固定和锁定装置等。
2. 电气特性: 指明在接口电缆的各条线上出现的电压的范围。
3. 功能特性: 指明某条线上出现的某一点评的电压的意义。
4. 过程特性: 指明对于不同功能的各种可能事件的出现顺序。

数据通信系统的模型

数据通信系统可划分为三部分: 源系统/发送端/发送方，传输系统/传输网络，目的系统/接收端/接收方。

1. 源系统

   源系统一般包括两个部分，源点/源站/信源(source)和发送器。

   • 源点: 源点设备产生要传输的数据。
   • 发送器: 通常源点生成的数字比特流要通过发送器编码后才能够在传输系统中进行传输。

2. 目的系统
   目的系统一般包括两个部分，接收器和终点/目的站/信宿(destination)。

   • 接收器: 接收传输系统传送过来的信号，并把它转换为能够被目的设备处理的信息。
   • 终点: 终点设备从接收器获取传送来的数字比特流，把信息输出。

在源系统和目的系统之间的传输系统可以是简单的传输线，也可以是连接在源系统和目标系统之间的复杂网络系统。

通信的目的是传送消息(message)。

数据(data)是运送消息的实体。其严格定义为是使用特定方式表示的信息，通常是有异议的符号序列。

信号(signal)则是数据的电气或电磁的表现。

信号可分为模拟信号和数字信号:

1. 模拟信号/连续信号: 消息参数的取值是连续的。
2. 数字信号/离散信号: 消息参数的取值是离散的。代表不同离散数值的基本波形成为码元。

信道(channel)一般用来表示向某一个方向传送信息的媒体。

从通信的双方信息交互的方式来看，有三种基本方式: 单向通信/单工通信，双向交替通信/半双工通信和双向同时通信/全双工通信。

1. 单向通信: 只能有一个方向的通信而没有反方向的交互，eg: 无线广播，电视。
2. 双向交替通信: 通信的双方都可以发送信息，但不能双方同时发送/同时接收。这种通信方式是一方发送另一方接收，过一段时间后反向工作。
3. 双向同时通信: 通信的双方可以同时发送和接收信息。

调制

来自信源的信号称为基带信号(基本频带信号)。

基带信号往往包含有较多的低频成分，甚至有直流成分，而很多信道并不能传输这种低频分量或直流分量。

为了解决这一问题，就必须对基带信号进行调制(modulation)。

调制可分为两大类:基带调制和带通调制。

1. 基带调制: 仅仅对基带信号的波形进行变换，使它能够与信道特性相适应。变换后的信号仍是基带信号。

   这种基带调制是把数字信号转换为另一种形式的数字信号，又称为编码(coding)。

2. 带通调制: 使用载波(carrier)的调制。把基带信号的频率范围搬移到较高的频段，并转换为模拟信号，这样就能够更好地在模拟信道中传输。

   经过载波调制后的信号成为带通信号，即仅在一段频率范围内能够通过信道。

常用编码方式

1. 不归零制: 正电平代表1，负电平代表0。
2. 归零制: 正脉冲代表1，负脉冲代表0。
3. 曼彻斯特编码: 位周期中心的向上跳变代表0，为周期中心的向下跳变代表1，但也可以反过来定义。
4. 差分曼彻斯特编码: 在每一位中心处始终都有跳变。位开始边界有跳变代表0， 而位开始边界没有跳变代表1。

从信号波形看，曼彻斯特(Manchester)编码产生的信号频率比不归零高。

从自同步能力看，不归零制不能从信号波形本身中提取信号时钟频率，即没有自同步能力，而曼彻斯特编码具有自同步能力。

基本的带通调制方法

1. 调幅(AM): 载波的振幅随基带数字信号而变化。
2. 调频(FM): 载波的频率随基带数字信号而变化。
3. 调相(PM): 载波的初始相位随基带数字信号而变化。

为了达到更多的信息传输速率，必须技术上采用更复杂的多元制的振幅相位混合调制方法，eg:正交振幅调制(Quadrature Amplitude Modulation)。

信道的极限容量

数字通信的优点: 虽然信号在信道上传输时会不可避免的失真，但在只要在接收端从失真的波形中能够识别出原来的信号，那么这种失真对通信质量就没有影响。

码元传输的速率越高，或信号传输的距离越远，或噪声干扰越大，或传输媒体质量差，在接收端的波形失真就越严重。

从概念上讲，限制码元在信道上的传输速率的因素有两个:

1. 信道能够通过的频率范围
   具体的信道所能通过的频率范围总是有限的，信号中的许多高频分量往往不能通过信道。

   码间串扰: 信号中的高频分量在传输时受到衰减，在接收端收到的波形前沿和后沿就变得不陡峭了，每一个码元所占的时间界限就会变得模糊，失去了码元之间的清晰界限。

   在任何信道中，码元传输的速率是有上限的，传输速率超过此上限，就会出现严重的码间串扰问题，使接收端对码元的判决/识别成为不可能。

   如果信道的频带越宽，能通过的高频分量越多，就可以用更高的速率传送码元而不出现码间干扰。

2. 信噪比
   噪声存在于所有的电子设备和通信信道中，但噪声的影响是相对的。如果信号相对较强，那么噪声的影响就相对较小。

   信噪比: 信号的平均功率和噪声的平均功率之比，$S/N$。单位为分贝(dB)。

   $ 信噪比 = 10 \log_{10}(S/N)$

   香农公式: 信道的极限信息传输速率$ C = W \log_2(1 + S/N) $

   $ W $为信道的带宽，$ S $为信道内所传信号的平均功率，$ N $为信道内部的高斯噪声功率。

   香农公式表明，信道的带宽或信道中的信噪比越大，信息的极限传输速率就越高。

   如果信道频带宽度一定，信噪比无法提升，码元的传输速率也达到了上限值，那么为了提高信息的传输速率，就要使用编码的方法使得每一个码元携带更多比特的信息量。

物理层下的传输媒体

传输媒体也称传输介质/传输媒介，是数据传输系统中在发送器和接收器之间的物理通路。

传输媒体可分为导引型传输媒体和非导引型传输媒体。

导引型传输媒体

在导引型传输媒体中，电磁波被导引沿着固体媒体传播。

1. 双绞线/双扭线

   把两根互相绝缘的铜导线并排放在一起，然后用规则的方法绞合(twist)起来就构成了双绞线。

   绞合可以减少对相邻导线的电磁干扰。

   模拟传输和数字传输都可以使用双绞线，其通信距离一般为几到十几公里。距离太长就需要放大器将衰减的信号放大到合适的数值(模拟传输)，中继器对失真的数字信号进行整形(数字传输)。

   

   为了提高双绞线抗电磁干扰的能力，可以在双绞线的外面加上一层用金属丝编织成的屏蔽层，即屏蔽双绞线(STP，Shielded Twisted Pair)。以此作为区别，还有无屏蔽双绞线(UTP，Unshielded Twisted Pair)。

   用于室内传送数据的无屏蔽双绞线和屏蔽双绞线的最新布线标准为EIA/TIA-568-A。此标准规定了5个种类的UTP标准(1-5类线)。

   5类线和3类线的最主要区别就是大大增加了每单位长度的绞合次数。3类线的绞合长度是7.5至10cm，5类线的绞合长度是0.6至0.85cm。

   

   无论是哪种类别的双绞线，衰减都随频率的升高而增大。使用更粗的导线可以降低衰减，增加导线的重量和价格。

   信号应当有足够大的振幅，以便在噪声干扰下能够在接收端正确的被检测出来。

   双绞线的最高速率还与数字信号的编码方法有关。

2. 同轴电缆

   

   同轴电缆由内导体铜制芯线(单股实心线或多股绞合线)，绝缘层，网状编织的外导体屏蔽层以及保护塑料外层组成。

   由于外导体屏蔽层的作用，同轴电缆具有很好的抗干扰特性，被广泛用于传输较高速率的数据。

   同轴电缆目前主用于在有限电视网的居民小区中。同轴电缆的带宽取决于电缆的质量。目前高质量的同轴电缆的带宽已接近1GHz。

3. 光缆

   光线通信就是利用光导纤维传递光脉冲来进行通信。光纤是光纤通信的传输媒体。

   有光脉冲相当于1，没有光脉冲相当于0。

   在发送端有光源，可以采用发光二极管或半导体激光器，它们在电脉冲的作用下能产生出光脉冲。在接收端利用光电二极管做成光检测器，在检测到光脉冲时可还原出电脉冲。

   光纤通常由非常透明的石英玻璃拉成细丝，主要由纤芯和包层构成双层通信圆柱体。纤芯很细，直径只有8~100微米。

   光波通过纤芯进行传导。包层较纤芯有较低的折射率。当光线从该折射率的媒体射向低折射率媒体时，其折射角将大于入射角。因此，如果入射角足够大，就会出现全反射，即光线碰到包层时就会折射回纤芯。这个过程不断重复，光也就会沿着光纤传输下去。

   只要从纤芯中射到纤芯表面的光线的入射角大于某个临界角度，就可产生全反射。因此，可以存在多条不同角度入射的光线在一条光线中传输。这样的光纤叫做多模光纤。

   多模光纤中，光脉冲在多模光纤中传输时会逐渐展宽，造成失真，只适合近距离传输。单模光纤是光纤的直径减少到只有一个光的波长，使光纤一直向前传播，不会产生多次反射。

   光纤通信中常用的三个波段中心是850纳米，1300纳米和1550纳米。带宽为25000~30000GHz。

   一根光缆少则只有一根光纤，多则可包括数十、数百根光纤，再加上加强芯和填充物可提高机械强度，可再加上远供电源线，最后加上包带层和外护套。这样就达到工程施工的强度要求。

   光纤的特点：

   1. 通信容量大
   2. 传输损耗小，中继距离长，对远距离传输很经济。
   3. 抗雷电和电磁干扰性能好。
   4. 无串音干扰，保密性好，也不易被窃听或截取数据。
   5. 体积小，重量轻。

非导引型传输媒体

非导引型传输媒体，即自由空间。在非导引型传输媒体中电磁波的传输常称为无线传输。

波段的正式名称：

1. LF/低频：波长1km~10km/30kHz~300kHz。

2. MF/中频：300kHz~3MHz。

3. HF/高频：3MHz~30MHz。

4. VHF/甚高频：30MHz~300MHz。

5. UHF/特高频：300MHz~3GHz。

6. SHF/超高频：3GHz~30GHz。

7. EHF/极高频：30GHz~300GHz。

8. 短波通信

   多径效应：同一个信号经过不同的反射路径到达同一个接收点，但各反射路径的衰减和时延都不相同，时的最后得到的合成信号失真很大。

   短波通信/高频通信，主要靠电离层反射。但电离层的不稳定所产生的衰落现象以及电离层反射产生的多径效应，使得短波信道的通信质量较差。当必须使用短波无线电台传送数据时，一般是低速传输。

9. 地面微波接力通信

   地面微波接力通信和卫星通信同属无线电微波通信。

   微波在空间中主要以直线传播。能够穿透电离层进入宇宙。

   微波在空间中直线传播，地球是球体，传播距离受到限制，一般为50km。若采用100m高的天线塔，可增大到100km。

   为实现远距离通信，在一条微波通信信道的两个终端之间建立若干个中继站。中继站把前一站传送过来的信号经过放大再发送到下一站。

   微波接力通信可传输电话，电报，图像，数据等信息。主要特点是：

   1. 微波波段频率很高，其频段范围很宽，其通信新到的容量很大。
   2. 微波通信因为其高频率，可以避免工业干扰和天气干扰，传输质量较高。
   3. 与相同容量和长度的电缆载波通信比较，微波接力通信建设性价比高。

   微波接力通信的缺点：

   1. 相邻站之间必须直视，不能有障碍物。
   2. 微波的传输有时也会受到恶略天气的影响。
   3. 与电缆通信系统比较，微波通信的隐蔽性和保密性较差。
   4. 对大量中继站的使用和维护要耗费较多的人力和物力。

10. 卫星通信

    常用的卫星通信方法是在地球站之间利用位于约3万6千公里高空的人造同步地球卫星作为中继器的一种微波接力通信。

    卫星通信的最大特点是通信距离远，且通信费用与通信距离无关。

    与微波接力通信相似，卫星通信的频带很宽，通信容量很大，信号受到的干扰也比较小，通信比较稳定。

    卫星通信的另一特点是具有较大的传播时延。

    在偏远地区进行通信几乎要完全依赖卫星通信。

    上述卫星通信使用的是对地静止的卫星。现在低轨道卫星通信系统也开始使用。低轨道卫星不停绕地球旋转。目前，大功率，大容量，低轨道宽带卫星已经开始在空间部署，并构成了空间高速链路。

另外，红外通信，激光通信也使用非引导型传输媒体，用于近距离的笔记本电脑相互传送数据。

信道复用技术

复用(multiplexing)最基本的是频分复用FDM(Frequency Division Multiplexing)和时分复用TDM(Time Division Multiplexing)。

在进行通信时，复用器(multiplexer)总是和分用器(demultiplexer)成对的使用。在复用器和分用器之间是用户共享的高速信道。

在发送端使用复用器，可以让复数用户共享一个信道。分用器把高速信道传送过来的数据进行分用，分别交付给相应的用户。

频分复用和时分复用

用户在分配到一定的频带后，在通信过程中自始至终都占用这个频带。频分复用的所有用户在同样的时间占用不同的带宽(频带)资源。

把时间划分为一段段等长的时分复用帧(TDM帧)。每一个时分复用的用户在每一个TDM帧中占用固定序号的时隙。时分复用的所有用户是在不同的时间占用相同的频带宽度。

上述两种复用方法的优点是技术比较成熟，但缺点是不够灵活。同时，时分复用更有利于数字传输。

统计时分复用

统计时分复用STDM(Statistic TDM)是一种改进的时分复用，能够提高信道利用率。

集中器(concentrator)常用于统计时分复用。

统计时分复用使用STDM帧来传送复用的数据，但每一个STDM帧中的时隙数小于连接在集中器上的用户数。

各用户有了数据就随时发往集中器的输入缓存，然后集中器按顺序依次扫描输入缓存，把缓存中的输入数据放入STDM帧中。对没有数据的缓存就跳过去。当一个帧的数据放满了，就发送出去。因此，STDM帧不是固定分配时隙，而是按需动态分配时隙。因此，统计时分复用可以提高线路的利用率。

因为STDM帧中的时隙并不是固定的分配给每个用户，因此在每个时隙中还必须有用户的地址信息，这是统计时分复用必须要有的和不可避免的开销。

集中器又称智能复用器。它能提供对整个报文的存储转发能力，通过排队方式使各用户更合理地共享信道。

波分复用

波分复用WDM(Wavelength Division Multiplexing)就是光的频分复用。使用一根光纤同时传输多个频率很接近的光载波信号。

最初的波分复用，一根光纤只能复用两路光载波信号。密集波分复用(Dense Wavelength Division Multiplexing)可在一根光纤上复用几十路或更多路的信号。

首先将光载波调制到不同的波长。

送到光复用器/合波器后，在一根光纤中传输。

光信号会在传输一段距离后衰减，因此需要对衰减了的光信号进行放大才能继续传输。现在利用掺铒光纤放大器(Erbium Doped Fiber Amplifier)，其不需要进行光电转换而直接对光信号进行放大。两个光纤放大器之间的光缆线路长度可达120km。

光复用器/合波器和光分用器/分波器之间的无光电转换的距离可达600k(4个EDFA光纤放大器)。

码分复用

码分复用CDM(Code Division Multiplexing)也是共享信道的方法。又称码分多址CDMA(Code Division Multiple Access)。

每一个用户可以在同样的时间使用同样的频带进行通信。这是因为各用户使用经过特殊挑选的不同码型，因此各用户之间不会造成干扰。有很强的抗干扰能力，其频谱类似白噪声，不易被敌人发现。

CDMA可提高通信的话音质量和数据传输的可靠性，减少干扰对通信的影响，增大通信系统的容量，降低手机的平均发射功率等。

码片(chip)指在CDMA中每一个比特再划分为m个短的间隔。

通常m的值是64或者128。

扩频: 要发送信息的数据率为b bit/s，由于每一个比特要转换成m个比特的码片，因此实际的发送数据率为mb bit/s，其所占的频带也提高到原来数值的m倍。

扩频通常有直接序列扩频DSSS(Direct Sequence Spread Spectrum)和跳频扩频FHSS(Frequency Hopping Spread Spectrum)。

1. 直接序列扩频
   

   使用码分多址的每一站被指派一个唯一的m bit码片序列(chip sequence)。

   一个站如果要发送比特1，则发送它的m bit码片序列，如果要发送比特0，则发送该码片序列的反码。

   在实用的系统中使用伪随机码序列，并且需要给每一个站分配的码片序列不相同的同时正交。

   如果需要接收某站发送的数据，使用此站的唯一性码片序列和接受的数据流作内积，得到真实信号。

2. 跳频扩频

   

   使用码分多址的每一站被指派一个唯一的m bit码片序列(chip sequence)。

   跳频是载波频率在一定范围内不断跳变意义上的扩频，而不是对被传送信息进行扩谱，不会得到直序扩频的处理增益。

   解扩需要知道扩频码。

宽带接入技术

从宽带接入的媒体来看，可以划分为有线宽带接入技术和无线宽带接入技术。现仅对有线宽带接入进行讨论。

ADSL技术

非对称数字用户线ADSL(Asymmetric Digital Subscriber Line)技术是用数字技术对现有的模拟电话用户线进行改造，使它能够承载宽带数字业务。

ADSL技术把0-4kHz低端频谱留给传统电话使用，而把原来没有被利用的高端频谱留给用户上网使用。

ADSL技术的传输距离取决于数据率和用户线的线径。用户线越细，信号传输时的衰减就越大。

ADSL在用户线的两端各安装一个ADSL调制解调器。我国目前采用的调制解调方案是离散多音调DMT(Discrete Multi-Tone)。

DMT调制技术采用频分复用的方法，把40kHz以上至1.1MHz的高端频谱划分为许多子信道，其中25个子信道用于上行信道，249个子信道用于下行信道，并使用不同的载波进行数字调制。

ADSL采用自适应调制技术使用户线能够传送尽可能高的数据率。当ADSL启动时，用户线两端的ADSL调制解调器就会测试可用的频率，各子信道受到干扰的情况以及在每一个频率上测试信号的传输质量。这样使得ADSL能够选择合适的调制方案以获得尽可能高的数据率。ADSL不能保证固定的数据率。

基于ADSL的接入网由以下三个部分组成：

1. 数字用户线接入复用器DSLAM(DSL Access Multiplexer)。
2. 用户线。
3. 用户家的一些设施。

数字用户线接入复用器包括许多ADSL调制解调器。

ADSL调制解调器又称接入端接单元ATU(Access Termination Unit)。

由于ADSL调制解调器必须成对使用，因此把在电话端局/远端站和用户家中所用的ADSL调制解调器分别记为ATU-C(entral Office)和ATU-R(emote)。

用户电话通过电话分离器(Splitter)和ATU-R连在一起，经用户线到端局，并再次经过一个电话分离器把电话连到本地电话交换机。

一个DSLAM可支持500~1000个用户。

ADSL可以利用现有电话网中的用户线，不需要重新布线。

ADSL调制解调器有两个插口，较大的一个是RJ-45，较小的一个是RJ-11。RJ-45用来与计算机相连，RJ-11用来与电话分离机相连。

电话分离机只需要用三个带有RJ-11插的连线就可以连接好。

ADSL借用了在用户线两端安装的ADSL调制解调器对数字信号进行调制，使得调制后的数字信号的频谱适合在原来的用户线上传输。

ADSL技术也在不断改进，ADSL2(G.992.3 G.992.4)和ADSL2+(G.992.5)是新提出的更高速率的第二代ADSL标准。

第二代ADSL的主要改进点在于：

1. 通过提高调制效率得到了更高的数据率。
2. 采用了无缝速率自适应技术SRA(Seamless Rate Adaptation)。可在运营中不中断通信和不产生误码的情况下根据线路的实时状况，自适应的调整数据率。
3. 改善了线路质量评测和故障定位功能，这对提高网络的运行维护水平具有非常重要的意义。

ADSL适用于居民用户，这是因为居民上行数据并不多。但是ADSL技术并不适用于企业。企业需要使用上行信道发送大量数据给用户。为了满足企业的需求，ADSL技术有几种变形。

1. 对称DSL：把ADSL的带宽平均分配到上行和下行两个方向。
2. HDSL(High speed DSL): 使用一对线或两对线的对称DSL，用来取代T1线路的高速数字用户线。
3. VDSL(Very high speed DSL)，是ADSL的快速版本，又称甚高速数字用户线。

光纤同轴混合网/HFC网

光纤同轴混合网(HFC网, Hybrid Fiber Coax)是在目前覆盖面很广的有线电视网的基础上开发的一种居民宽带接入网，除可传送电视节目外，还能提供电话，数据和其他宽带交互型业务。

最早的有线电视网是树形拓扑结构的同轴电缆网络，它采用模拟技术的频分复用对电视节目进行单向广播传输，改造后，成为光纤同轴混合网。

光纤同轴混合网的主要特点：

为了提高传输的可靠性和电视信号的质量，同轴电缆主干换为光纤，光纤从头端连接到光纤节点(fiber node)。在光纤节点光信号被转换为电信号，然后通过同轴电缆传送到每个用户家庭。

从头端到用户家庭所需的放大器因为末端采用同轴电缆数目仅有4~5个。

连接到一个光纤节点的典型用户数是500~2000。

光纤节点与头端的典型距离为25km，从光纤节点到其用户的距离则不超过2~3km。

原有有限电视网的最高传输频率是450MHz，并且仅用于电视信号的下行传输。光纤同轴混合网具有双向传输功能，而且扩展了传输频带。

要使现有的模拟电视机能够接收数字电视信号，需要把机顶盒(set-top box)设备连接在同轴电缆和用户的电视机之间。同时，为了用户使用HFC网接入互联网，以及在上行信道中传送交互数字电视所需的一些信息，需要增加一个为HFC网使用调制解调器：电缆调制解调器(cable modem)。电缆调制解调器可以做成一个单独的设备，例如ADSL的猫，也可以做成内置式，安装在电视机的机顶盒中。

电缆调制解调器不需要成对使用，只需要安装在用户端。电缆调制解调器因为是多用户共享的，需要思考共享信道中可能出现的冲突问题。

FTTx技术

为了更快地下载视频文件，以及更加流畅的欣赏网上的各种高清视频节目，需要升级用户的上网效率，光纤到户FTTH(Fiber To The Home)从技术上来说是最好的选择。

光纤到户是把光纤一直铺设到用户家庭。只有到用户家庭后，才从光信号转化为电信号，使用户获得最高的上网效率。

问题:

1. 价格不够低。
2. 用户需求不需要如此高的数据率。

基于以上两个问题，出现了多种宽带光纤接入方式：FTTx。x表示不同的光纤接入地点。

为了有限利用光纤资源(问题2)，在光纤干线和广大用户之间还需要铺设一段中间的转换装置：光配线网ODN(Optical Distribution Network)，使得数十个家庭用户能够共享一根光纤干线。

无源光网络表明在光配网中无需配备电源，因此基本不要维护，长期运营和管理成本很低，而无源的光配网又称为无源光网络PON(Passive Optical Network)。

OLT光线路终端(Optical Line Terminal)是连接到光纤干线的终端设备。

OLT把收到的下行数据发往无源的1：N光分路器(splitter)，然后用广播向所有用户端的光网络单元ONU(Optical Network Unit)发送。典型的光分路器使用分路比是1：32，有时也可使用多级的光分路器。每个ONU根据特有的标识只接收发送给自己的数据，然后转换为电信号发往用户家中。每一个ONU到用户家的距离具体情况具体分析，OLT给ONU分配适当的光功率。

OLT发送上行数据时， 先把电信号转化为光信号，光分路器把各ONU发来的上行数据汇总后，以TDMA方式发往OLT，发送时间和长度由OLT集中控制，以便有序地共享光纤主干。

光配线网采用波分复用，上行和下行分别使用不同的波长。

FTTx有光纤到户FTTH，光纤到路边FTTC(urb)，光纤到小区FTTZ(one)，光线到大楼FTTB(uliding)，光纤到楼层FTTF(loor)，光纤到办公室FTTO(ffice)，光纤到桌面FTTD(esk)。

前置

1
2
3
4

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def getIntersectionNode(headA, headB):
    a, countA, b, countB = headA, 0, headB, 0
    while a:
        countA += 1
        a = a.next
    while b:
        countB += 1
        b = b.next
    # print(countA, countB)
    if countA > countB:
        c, cur, other = countA - countB, headA, headB
    else:
        c, cur, other = countB - countA, headB, headA
    while c > 0:
        cur = cur.next
        c -= 1
    
    while cur != other:
        cur = cur.next
        other = other.next

    return cur

栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import collections
class MinStack:

    def __init__(self):
        self.stack = collections.deque()
        self.min_stack = collections.deque()

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or self.min_stack[-1] >= val:
            self.min_stack.append(val)

    def pop(self) -> None:
        cur = self.stack.pop()
        if cur == self.min_stack[-1]: self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]