最长上升子序列(LIS)的定义:    一个数的序列bi,当b1 < b2 < … < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN),我们可以得到一些上升的子序列(ai1, ai2, …, aiK),这里1 <= i1 < i2 < … < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8). 三种求解方法: 1. O(n^2)的DP 2. O(nlogn)的二分+贪心法 3. O(nlogn)的树状数组优化的DP 题目:Longest Increasing Subsequence 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2, 继续阅读 >>


刘生玺 18/07/20 12:10:14
题目:不同路径 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。 问总共有多少条不同的路径? 例如,上图是一个7 x 3 的网格。有多少可能的路径? 说明:m 和 n 的值均不超过 100。 示例 1: 输入: m = 3, n = 2 输出: 3 解释: 从左上角开始,总共有 3 条路径可以到达右下角。 1. 向右 -> 向右 -> 向下 2. 向右 -> 向下 -> 向右 3. 向下 -> 向右 -> 向右 示例 2: 输入: m = 7, n = 3 输出: 28 原题链接:https://leetcode-cn.com/explore/interview/card/top-interview-questions-medium/51/dynamic-programming/105/ 继续阅读 >>


刘生玺 18/07/19 11:15:47
1. 感性认识“动态规划” 1. 基本概念    是求解决策过程(decision process)最优化的数学方法。把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,是一种解决这类过程优化问题的新方法。 2. 使用技巧:    动态规划算法通常用于求解具有某种最优性质的问题!!!特别的 ,动态规划(Dynamic Programming)对于子问题重叠的情况特别有效,因为它将子问题的解保存在表格中,当需要某个子问题的解时,直接取值即可,从而避免重复计算! 3. 基本思想与策略 我们通过一个问题来引出: 提问:动态规划与分治法有什么不同?    答:适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题 继续阅读 >>


刘生玺 18/07/18 19:02:57
全排列算法思想: 1. 全排列的定义和公式:    从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。由排列的定义,显然不同的顺序是一个不同的排列。从n个元素中取m个元素的所有排列的个数,称为排列数。从n个元素取出n个元素的一个排列,称为一个全排列。 公式:全排列数f(n) = n! (定义0!=1) 2. 时间复杂度:    n个数(字符、对象)的全排列一共有n!种,所以全排列算法至少时间O(n!)的。如果要对全排列进行输出,那么输出的时间要O(n∗n!),因为每一个排列都有n个数据。所以实际上,全排列算法对大型的数据是无法处理的,而一般情况下也不会要求我们去遍历一个大型数据的全排列。 3. 全排列的初始思想    为了解决一个算法问题,我们选择从基本的想法做起。先回顾一下我们自己是如何写一组数的全排列的:1,3,5,9 首先肯定是 : 1 ,[3, 5,9的全排列] 3 继续阅读 >>


刘生玺 18/07/17 11:08:08
在阿里云上源码配置Apache,还是遇到很多问题。不过还好都是解决了,所以想写一篇博客来帮助大家配置Apache. 阿里云服务器配置 Centos 6.8 首先来看看阿里云官方配置Apache教程 这看起来很简单 但是其实有很多坑 首先先按官网的下载和解压Apache的源码包 这是我遇到的其中几个问题 checking for APR… no configure: error: APR not found. Please read the documentation. checking for APR-util… no configure: error: APR-util not found. Please read the documentation. configure: error: APR-util not found. Please read the documentation. checking for pcre-config… false configure 继续阅读 >>


陈苏扬 18/07/16 08:24:54
结构化与非结构化网络 非结构化的P2P网络是指网络节点之间不存在组织关系,节点之间完全是对等的,比如第一代P2P网络Napster。 结构化的P2P网络与非结构化恰好相反,我们认为网络在逻辑上存在一个人为设计的结构,比如Chord假定网络是一个环,Kadelima则假定为一颗二叉树。有了这些逻辑结构,就给我们资源查找引入了更多的算法和思路。 引言 我们在 计算机网络–详解P2P对等网络(一)—BitTorrent协议 这一篇博客中讲述了BT下载的过程:在对等用户拿到种子文件的时候,首先会联系tracker服务器,然后加入用户集群,并在用户集群中寻找自己所需的内容,最后与拥有内容的对等用户进行联系。 从BT下载的过程中引出本节所要讨论的问题:如何高效的从用户集群中找出哪些对等用户拥有你正在寻求的具体内容? 在历史中有三种比较典型的模型来解决这个问题: Napster:使用一个中心服务器接收所有的查询,服务器告知去哪下载其所需要的数据。存在的问题是中心服务器单点失效导致整个网络瘫痪。 继续阅读 >>


董恒毅 18/06/28 21:24:59
本文档翻译自: http://redis.io/topics/protocol 。 Redis 协议在以下三个目标之间进行折中: 易于实现 可以高效地被计算机分析(parse) 可以很容易地被人类读懂 网络层 客户端和服务器通过 TCP 连接来进行数据交互, 服务器默认的端口号为 6379 。 客户端和服务器发送的命令或数据一律以 \r\n (CRLF)结尾。 请求 Redis 服务器接受命令以及命令的参数。 服务器会在接到命令之后,对命令进行处理,并将命令的回复传送回客户端。 新版统一请求协议 新版统一请求协议在 Redis 1.2 版本中引入, 并最终在 Redis 2.0 版本成为 Redis 服务器通信的标准方式。 你的 Redis 客户端应该按照这个新版协议来进行实现。 在这个协议中, 所有发送至 Redis 服务器的参数都是二进制安全(binary safe)的。 以下是这个协议的一般形式: *<参数数量> CR LF $< 继续阅读 >>


杜肖孟 18/06/28 17:41:22
什么是string_view std::string_view是C++ 17标准中新加入的类,正如其名,它提供一个字符串的视图,即可以通过这个类以各种方法“观测”字符串,但不允许修改字符串。由于它只读的特性,它并不真正持有这个字符串的拷贝,而是与相对应的字符串共享这一空间。即——构造时不发生字符串的复制。同时,你也可以自由的移动这个视图,移动视图并不会移动原定的字符串。 正因这些特性,当你不需要改变字符串时,应当抛弃原来使用的const string而采用新的string_view,这样可以避免多余的字符串拷贝。 构造 std::string_view允许通过C风格的字符串、字符串字面量、std::string或者其他的string_view进行构造。在构造的同时允许指定“大小”。 const char *cstr_pointer = "pointer"; char cstr_array[] = "array"; std::string stdstr = "std::string"; s 继续阅读 >>


娄泽豪 18/06/26 21:55:29
C++ 17标准已经发布了有一段时间了(甚至于后一个版本C++ 20也在路上了),最近终于得空(懒癌治愈),查阅了相关资料,简单上手一下。感觉到,一个是“现代”C++和C语言确实已经是天差地别,另一个就是标准库中的东西以及新语法确实更加方便我们编程了。虽然这些特性也许很长一段时间内都不一定用得上,然而学习一下总是好的,并且,体验一下“更现代”的C++的感觉也不错。 带初始化的选择语句 这个特性用于if和switch语句中,现在允许在这两个选择语句中声明并初始化一个变量,该变量在整个选择语句中都可用。这个特性显然有助于代码的清晰性,现在你可以这样写了: if (int fd = open("filename", O_RDWR | O_CREAT); fd == -1) { perror("something"); } else { // 可以继续在这里使用fd } switch (int op = getOp(); op) { case xxx: ... case 继续阅读 >>


娄泽豪 18/06/26 19:24:43
Docker 是什么 Docker是一个开源的引擎,可以轻松的为任何应用创建一个轻量级的、可移植的、自给自足的容器。它属于 Linux 容器的一种封装,提供简单易用的容器使用接口。 Docker 将应用程序与该程序的依赖,打包在一个文件里面。运行这个文件,就会生成一个虚拟容器。程序在这个虚拟容器里运行,就好像在真实的物理机上运行一样。有了 Docker ,就不用担心环境问题。 虚拟机 与 Linux 容器 虚拟机(virtual machine)就是带环境安装的一种解决方案。它可以在一种操作系统里面运行另一种操作系统。虚拟机看上去跟真实系统一模一样,而对于底层系统来说,虚拟机就是一个普通文件。 虚拟机的缺点:资源占用多、冗余步骤多、启动慢。 Linux 容器(Linux Containers,缩写为 LXC)不是模拟一个完整的操作系统,而是对进程进行隔离。 容器的优势:启动快、资源占用少、体积小。 容器是进程级别的,有点像轻量级的虚拟机,能够提供虚拟化的环境,但是成本开销小得多。 继续阅读 >>


李猛 18/06/24 21:23:44