Serendipity

经典 DP 问题之一 ——LIS。 描述300. 最长上升子序列Difficulty: 中等 给定一个无序的整数数组，找到其中最长上升子序列的长度。 示例: 123 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释：最长的上升子序列是 [2,3,7,101]，它的长度是 4。 说明: 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 $O (n^2)$ 。 进阶：你能将算法的时间复杂度降低到 $O (nlogn)$ 吗？ 思路 & 题解经典 LIS思路对于所有的 DP 问题，经典四步走： 定义状态 由于一个子序列一定会以一个数结尾，于是将状态定义成：dp [i] 表示以 nums [i] 结尾的「上升子序列」的长度。注意：这个定义中 `nums [i] 必须被选取，且必须是这个子序列的最后一个元素。 考虑状态转移方程 遍历到 nums [i] 时，需要把下标 i 之前的所有的数都看一遍；只要 nums [i] 严格大于在它位置之前的某个数，那么 nums [i] 就可以接在这个数后面形成一个更长的上升子序列 ...

一道经典的自动状态机题。 题目描述剑指 Offer20. 表示数值的字符串 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串 “+100”、”5e2”、”-123”、”3.1416”、”-1E-16”、”0123” 都表示数值，但 “12e”、”1a3.14”、”1.2.3”、”+-5” 及 “12e+5.4” 都不是。 思路这题是典型的自动状态机，定义当前状态，以当前字符作为状态转移动作。 字符类型 ： 空格 「 」、数字「 0—9 」 、正负号 「 +- 」 、小数点 「 . 」 、幂符号 「 eEeE 」 。 状态定义 ： 按照字符串从左到右的顺序，定义以下 9 种状态。 开始的空格 幂符号前的正负号 小数点前的数字 小数点、小数点后的数字 当小数点前为空格时，小数点、小数点后的数字 幂符号 幂符号后的正负号 幂符号后的数字 结尾的空格 结束状态 合法的结束状态有 2, 3, 7, 8 。 题解1234567891011121314151617181920212223242526272829303132333435363738394041424 ...

借助这题复习一下 Java 并发类和工具。 题目描述两个不同的线程将会共用一个 FooBar 实例。其中一个线程将会调用 foo () 方法，另一个线程将会调用 bar () 方法。 请设计修改程序，以确保 “foobar” 被输出 n 次。 我们提供一个类： 12345678910111213141516171819202122232425class FooBar { private int n; public FooBar(int n) { this.n = n; } public void foo(Runnable printFoo) throws InterruptedException { for (int i = 0; i < n; i++) { //printFoo.run () outputs "foo". Do not change or remove this line. ...

什么是 Let’s EncryptLet’s Encrypt 是国外一个公共的免费 SSL 项目，由 Linux 基金会托管。它的来头不小，由 Mozilla、思科、Akamai、IdenTrust 和 EFF 等组织发起，目的就是向网站自动签发和管理免费证书。以便加速互联网由 HTTP 过渡到 HTTPS，目前 Facebook 等大公司开始加入赞助行列。 Let’s Encrypt 已经得了 IdenTrust 的交叉签名，这意味着其证书现在已经可以被 Mozilla、Google、Microsoft 和 Apple 等主流的浏览器所信任。用户只需要在 Web 服务器证书链中配置交叉签名，浏览器客户端会自动处理好其它的一切，Let’s Encrypt 安装简单，使用非常方便。 本文将会详细介绍如何免费申请 Let’s Encrypt 通配符证书。 什么是通配符证书域名通配符证书类似 DNS 解析的泛域名概念，通配符证书就是证书中可以包含一个通配符。主域名签发的通配符证书可以在所有子域名中使用，比如 .example.com、bbs.example.com。 申请通配符证书Le ...

缺页中断（英语：Page fault，又名硬错误、硬中断、分页错误、寻页缺失、缺页中断、页故障等）指的是当软件试图访问已映射在虚拟地址空间中，但是目前并未被加载在物理内存中的一个分页时，由中央处理器的内存管理单元所发出的中断。 通常情况下，用于处理此中断的程序是操作系统的一部分。如果操作系统判断此次访问是有效的，那么操作系统会尝试将相关的分页从硬盘上的虚拟内存文件中调入内存。而如果访问是不被允许的，那么操作系统通常会结束相关的进程。 虽然其名为 “页缺失” 错误，但实际上这并不一定是一种错误。而且这一机制对于利用虚拟内存来增加程序可用内存空间的操作系统（比如 Microsoft Windows 和各种类 Unix 系统）中都是常见且有必要的。 微软在较新版 Windows 的资源监视器中使用 “硬错误”（Windows Vista 及以上）、“硬中断”（Windows 8 及以上）这一术语来指代 “页缺失”。 缺页分类软性页缺失软性页缺失指页缺失发生时，相关的页已经被加载进内存，但是没有向 MMU 注册的情况。操作系统只需要在 MMU 中注册相关页对应的物理地址即可。 发生这种情况的 ...

每当我们安心的使用 LINUX 系统或者在编写 C 语言的时候，安心的使用 malloc 或者 free 的时候，我们很少关注过其底层的内存是怎么工作的，CPU 是如何获取从主存中获取数据的，我们的寻址是不是可以直接寻找到对应的数据，还是通过某种转化机制。实际上，对于每一个进程，它所能接触到的地址都不是实际的物理地址，而是通过虚拟地址进行映射而来的。这里来研究一下虚拟存储器的技术细节。 物理内存和虚拟内存物理内存物理内存就是我们电脑上的 RAM 提供的内存。他是固定的，内存条的容量多大，物理内存就有多大（集成显卡系统除外）。但是如果程序运行很多或者程序本身很大的话，就会导致大量的物理内存占用，甚至导致物理内存消耗殆尽。 虚拟内存简明的说，虚拟内存就是在硬盘上划分一块页面文件，充当内存。当程序在运行时，有一部分资源还没有用上或者同时打开几个程序却只操作其中一个程序时，系统没必要将程序所有的资源都塞在物理内存中，于是，系统将这些暂时不用的资源放在虚拟内存上，等到需要时在调出来用。 值得一提的是，虽然可以直接把物理地址理解成插在机器上那根内存本身，把内存看成一个从 0 字节一直到最大空量逐 ...

在多道程序环境下，要使程序运行，必须先为之创建进程。而创建进程的第一件事，便是将程序和数据装入内存。如何将一个用户源程序变为一个可在内存中执行的程序，通常都要经过以下几个步骤： 编译、链接和装入。 程序从编译到运行过程编译编译：源程序 -> 目标模块（Object modules）————Compiler 由编译程序 (Compiler) 将用户源代码编译成 cpu 可执行的目标代码，产生了若干个目标模块 (Object Module)（即若干程序段）。形成的目标代码，每个目标代码都是以 0 为基址顺序进行编址，原来用符号名访问的单元用具体的数据 —— 单元号取代。这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间，简称逻辑空间。 在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为 逻辑地址 。很简单， 逻辑地址 就是你源程序里使用的地址，或者源代码经过编译以后编译器将一些标号，变量转换成的地址。 链接链接：一组目标模块 -> 装入模块 （Load Module）—————Linker 由链接程序 (Linker) 将编译后形成的一组目标模块（程 ...

操作系统的内存管理分为物理内存管理和虚拟内存管理。 物理内存管理包括程序装入等概念、交换技术、连续分配管理方式和非连续分配管理方式（分页、分段、段页式）。 虚拟内存管理包括虚拟内存概念、请求分页管理方式、页面置换算法、页面分配策略、工作集和抖动。 我们以计算机存储结构来开始探讨。 计算机存储体系内存是计算机很重要的一个资源，因为程序只有被加载到内存中才可以运行；此外，CPU 所需要的指令与数据也都是来自内存的。可以说，内存是影响计算机性能的一个很重要的因素。 分层存储器体系在介绍内存管理的细节前，先要了解一下分层存储器体系： 大部分的计算机都有一个存储器层次结构，即少量的非常快速、昂贵、易变的高速缓存 (cache)；若干兆字节的中等速度、中等价格、易变的主存储器 (RAM)；数百兆或数千兆的低速、廉价、不易变的磁盘。这些资源的合理使用与否直接关系着系统的效率。 CPU 缓存（Cache Memory）：是位于 CPU 与内存之间的临时存储器，它的容量比内存小的多但是交换速度却比内存要快得多。缓存的出现主要是为了解决 CPU 运算速度与内存 读写速度不匹配的矛盾，因为 CPU 运算速度 ...

把 CPU 作为大脑的话，CPU 缓存是人的瞬时记忆，内存是人的短时记忆，磁盘是人的长时记忆。那么 CPU 如何与内存交互？ 什么是内存内存（Memory）是计算机中最重要的部件之一，它是程序与 CPU 进行沟通的桥梁。计算机中所有程序的运行都是在内存中进行的，因此内存对计算机的影响非常大，内存又被称为 主存，其作用是存放 CPU 中的运算数据，以及与硬盘等外部存储设备交换的数据。只要计算机在运行中，CPU 就会把需要运算的数据调到主存中进行运算，当运算完成后 CPU 再将结果传送出来，主存的运行也决定了计算机的稳定运行。 内存是易失性存储，与磁盘不同，掉电则失去所有数据。 内存的物理结构内存的内部是由各种 IC 电路组成的，它的种类很庞大，但是其主要分为三种存储器 随机存储器（RAM）： 内存中最重要的一种，表示既可以从中读取数据，也可以写入数据。当机器关闭时，内存中的信息会 丢失。 只读存储器（ROM）：ROM 一般只能用于数据的读取，不能写入数据，但是当机器停电时，这些数据不会丢失。 高速缓存（Cache）：Cache 也是我们经常见到的，它分为一级缓存（L1 Cache）、 ...

CPU 的全称是 Central Processing Unit，即中央处理单元，是计算机的核心部件 - 计算部件。CPU 的核心是从程序或应用程序获取指令并执行计算。此过程可以分为三个关键阶段： 提取，解码和执行 。CPU 从系统的主存中提取指令，然后解码该指令的实际内容，然后再由 CPU 的相关部分执行该指令。 计算机内部处理过程以 C 语言为例来说明程序运行流程： 在这个流程中，CPU 负责的就是解释和运行最终转换成机器语言的内容。CPU 主要由两部分构成：控制单元 和 算术逻辑单元（ALU） 控制单元：从内存中提取指令并解码执行算数逻辑单元（ALU）：处理算数和逻辑运算 CPU 是计算机的心脏和大脑，它和内存都是由许多晶体管组成的电子部件。它接收数据输入，执行指令并处理信息。它与输入 / 输出（I / O）设备进行通信，这些设备向 CPU 发送数据和从 CPU 接收数据。从功能来看，CPU 的内部由寄存器、控制器、运算器和时钟四部分组成，各部分之间通过电信号连通。 寄存器 是中央处理器内的组成部分。它们可以用来暂存指令、数据和地址。可以将其看作是内存的一种。根据种类 ...