划水摸鱼

快速幂算法传统的求幂算法，当n非常大的时候，需要执行的循环次数也非常多，算法的复杂度为O(N) 快速幂算法能以O(logN)的复杂度计算非常大的幂，核心思想就是每一步把指数分成两半，而相应的底数做平方运算 例子： $3^{10}$ = $9^5$ 此时指数缩减为原来的一半，底数变为原来的平方 而对于 $9^5$ 指数不能缩减为原来的一半，但可以 $9^5$ = $9^4 * 9^1$ 对于剩下的 $9^4$ 继续进行指数缩减为原来的一半的操作 $3^{10} = 9^5 = (9^4)(9^1) = (81^2)(9^1) = (6561^1)*(9^1)$ 快慢指针假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。 一快一慢。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位 ...

行为模式这类模式负责对象间的高效沟通和职责委派。 迭代器模式问题 不断向集合中添加遍历算法会模糊集合“高效存储数据”的主要职责 使用多种集合的客户端代码可能并不关心存储数据的方式，不过由于集合提供不同的元素访问方式，你的代码将不得不与特定集合类进行耦合 解决方案迭代器能够在不暴露集合低层表现形式的情况下遍历集合中的所有元素 迭代器模式的主要思想是将集合的遍历行为抽取为单独的迭代器对象。除了实现自身算法外，迭代器还封装了遍历操作的所有细节，多个迭代器可以在相互独立的情况下同时访问集合。 迭代器通常会提供弄一个获取集合元素的方法，客户端可不断调用该方法直至它不返回任何内容。 所有迭代器必须实现相同的接口，当需要采用特殊方式来遍历集合时，只需要创建一个新的迭代器类即可，无需修改集合或客户端。 结构 Iterator 接口声明了遍历集合所需的操作 ConcreteIterator 实现遍历集合的一种特定算法，多个迭代器可相互独立的遍历同一集合 IterableCollection 接口声明一个或多个方法来获取与集合兼容的迭代器 ConcreteCollection 会在客户端请求迭代器时返 ...

前序遍历中序遍历递归123456789101112131415public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); inorder(root, res); return res; } public void inorder(TreeNode root, List<Integer> res) { if (root == null) { return; } inorder(root.left, res); res.add(root.val); inorder(root.right, res); } 时间复杂度：O(n)其中 n为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被 ...

排序算法插入排序123456789101112131415public int[] sort(int[] example){ int key, j; for (int i = 1; i < example.length; i++){ key = example[i]; j = i - 1; // 往前插入合适的位置，比该数大的数往后顺移 while (j >= 0 && example[j] > key){ example[j+1] = example[j]; j--; } example[j+1] = key; } return example; }

Linked ListsCoarse-grainedFine-GrainedOptimisticLazyLock-FreeQueues and StacksQueue enq() and deq() FIFO Stack push() and pop() LIFO

剩余知识名词解释PDU协议数据单元（Protocol Data Unit）是指 对等层次之间传递的数据单位。协议数据单元(Protocol Data Unit )物理层的PDU 是数据位（bit），数据链路层的PDU是数据帧（frame），网络层的PDU 是数据包（packet），传输层的PDU 是数据段（segment），其他更高层次的PDU 是报文（message）。 Full duplexOSISplit horizonCSMA/CDCSMA/CADNSTime division multiplexingSTPRARPPVCs、SVCs DTE（data terminal equipment） DCE（data circuit-terminating equipment） PPP是一种标准的串行链路封装协议 PAP（Password Authentication Protocol ） CHAP（Challenge Handshake Authentication Protocol） ISDN（Integrated Services Digital Networks）综合数字服 ...

多路访问控制协议信道划分MAC协议随机访问MAC协议时隙ALOHA协议假定所有帧大小相同，时间被划分为等长的时隙，每个时隙可以传输1个帧，节点只能在时隙开始时刻发送帧，节点间时钟同步，如果2个或2个以上节点在同一时隙发送帧，节点即检测到冲突 当节点有新的帧时，在下一个时隙发送 如果无冲突：该节点可以在下一个时隙继续发送新的帧 如果冲突：该节点在下一个时隙以概率p重传该帧，直至成功 优点： 单个节点活动是，可以连续以信道全部速率传输数据 高度分散化：只需同步时隙 简单 缺点： 冲突，浪费时隙 空闲时隙 节点也许能以远小于分组传输时间检测到冲突 要求所有节点时钟同步 非时隙ALOHA协议更加简单，无需同步，当有新的帧生成时，立即发送 冲突可能性增大，在$t_0$时刻发送帧，会与在[$t_0-1,t_0+1$]期间其它节点发送的帧冲突 CSMA协议载波监听多路访问协议（carrier sense multiple access） 发送帧之前，监听信道 信道空闲：发送完整帧 信道忙：推迟发送 1-坚持CSMA：一直监听 非坚持CSMA：随机等待一段时间再监听 P- ...

数据管理基础笔记

防火墙 由软件和硬件构成的系统，是一种特殊编程的路由器，用来在两个网络之间实施接入控制策略。接入控制策略是由防火墙的单位自行制定的，为的是可以最适合本单位的需要 防火墙内的网络被称为可信赖网络，而将外部的因特网称为不可信赖网络 防火墙可用来解决内联网和外联网的安全问题 其实只用一个路由器就可以完成防火墙的划分。 例子中:应用网关，可以内部外部进行访问过滤。 优点:在防火墙中的外局域网和内局域网都可以放置一些服务器，由左侧过滤的路由器控制访问，而右侧的路由控制内部网络的访问，从而达成一个访问权限控制，内部的服务器更为安全 内网络安全也是一个问题 功能 防火墙的功能有两个：阻止和允许 阻止就是阻止某种类型的通信量通过防火墙(从外部网络到内部网络，或反过来)：比如阻止内部的对迅雷的请求向外发送 允许的功能与阻止恰好相反。 防火墙必须能够识别通信量的各种类型。不过在大多数情况下防火墙的主要功能是阻止。 防火墙技术分类 网络级防火墙：用来防止整个网络出现外来非法的入侵。属于这类的有分组过滤和授权服务器 前者检查所有流入本网络的信息，然后拒绝不符合事先制订好的一套准则 ...

网络层服务概述从发送主机向接收传送数据段 发送主机：将数据封装到数据包中 接收主机：向传输层交付数据段 每个主机和路由器都运行网络层协议 路由器检验所有穿越它的$IP$数据报的头部域，决策如何处理$IP$数据报 网络层的核心功能转发（forwarding）：将分组从路由器的输入端口转移到合适的输出端口 路由（routing）：确定分组从源到目的的经过的路径 路由算法 某些网络的重要功能—连接建立 数据分组传输之前两端主机需要首先建立虚拟/逻辑连接，网络设备（如路由器）参与连接的建立 不同于传输层的两个应用进程之间，对中间网络设备透明，网络连接是两个主机之间，路径上的路由器等网络设备参与其中的 网络层服务模型 无连接服务：不事先为系列分组的传输确定传输路径，每个分组独立确定传输路径，不同分组可能传输路径不同 数据报网络：简化网络，复杂“边缘” 连接服务：首先为系列分组的传输确定从源到目的经过的路径，然后沿该路径传输系列分组，系列分组传输路径相同 虚电路网络：简化“边缘”，复杂网络 虚电路网络虚电路（$VC$） 一条从源主机到目的主机，类似于电路的逻辑（逻辑连接） ...